lazymanifest: use a binary search to do an insertion
This makes insertions log(n) plus some memmove() overhead, rather than
doing an append followed by an n*log(n) sort. There's probably a lot
of performance to be gained by adding a batch-add method, which could
be smarter about the memmove()s performed.
Includes a couple of extra tests that should help prevent bugs.
Thanks to Martin for some significant pre-mail cleanup of this change.
context: don't sort manifest entries
The manifest iterator is now pre-sorted, so we can skip this check.
manifest: use custom C implementation of lazymanifest
This version is actually lazy, unlike the pure-python version. The
latter could stand to be optimized if anyone actually wants to use it
seriously. I put no work into it.
Before any of my related changes on mozilla-central:
perfmanifest tip
! wall 0.268805 comb 0.260000 user 0.260000 sys 0.000000 (best of 37)
perftags
! result: 162
! wall 0.007099 comb 0.000000 user 0.000000 sys 0.000000 (best of 401)
perfstatus
! wall 0.415680 comb 0.420000 user 0.260000 sys 0.160000 (best of 24)
hgperf export tip
! wall 0.142118 comb 0.140000 user 0.140000 sys 0.000000 (best of 67)
after all of my changes on mozilla-central:
./hg:
perfmanifest tip
! wall 0.232640 comb 0.230000 user 0.220000 sys 0.010000 (best of 43)
perftags
! result: 162
! wall 0.007057 comb 0.010000 user 0.000000 sys 0.010000 (best of 395)
perfstatus
! wall 0.415503 comb 0.420000 user 0.280000 sys 0.140000 (best of 24)
hgperf export tip
! wall 0.025096 comb 0.030000 user 0.030000 sys 0.000000 (best of 102)
so it's no real change in performance on perf{manifest,tags,status},
but is a huge win on 'hgperf export tip'.
There's a little performance work that could still be done here:
fastdelta() could be done significantly more intelligently by using
the internal state of the lazymanifest type in C, but that seems like
good future work.
manifest: split manifestdict into high-level and low-level logic
The low-level logic type (_lazymanifest) matches the behavior of the C
implementation introduced in
a5f1bccd. A future patch will use that
when available.
manifest: do parsing inside manifestdict contstructor
This shape to the code will make using a C implementation of the
manifest storage easier.
manifest: move parsing functions up in file
These functions are about to change signature and be hidden inside the
manifestdict constructor. Doing the code motion now as an isolated
change to make things easier to review.