[Monotone-devel] Speed of Annotate

[Thomas Moschny]

Hi all,

Speed of annotate has been an issue for a long time. There have been 
discussions about this problem earlier, see e.g. this thread:
http://lists.gnu.org/archive/html/monotone-devel/2006-07/msg00231.html .

Starting with 0.32, this has become a bit better, albeit not perfect. We now 
use heights to make use of the markings already present and try to read 
(and parse) only a subset of all rosters, thus making annotate and log 
faster.

However, as we now store delta rosters, the effect is not as good as 
it could be, because in order to get a specific roster, the whole chain of 
deltas has to be read, parsed, and applied to a base roster.

So, there was the idea of looking directly at the roster deltas instead. The 
head version of n.v.m.experiment.annotate.roster_deltas does exactly 
that. It introduces a way to extract node-specific changes from a roster 
delta, and uses these methods in the annotate code. It also avoids fetching 
the same information twice, as the old code did.

Furthermore, it stops fetching the roster for a marked revision at all, as 
that doesn't contain new information: the markings set will only contain the 
revision itself (as it is marked), and the node's content hash will be same 
as in the unmarked descendants (otherwise they would have been marked).

In principle, while searching for node specific roster data, you have to 
follow a proper reconstruction path, looking at all roster_deltas on the way, 
until you found it. It turns out however, that constructing those paths is 
rather expensive, too. So a heuristic was used here: first look at all 
available roster deltas for the target revision, and only if that fails, 
construct and follow the path to some base roster.

Here are some timings for some files with different numbers of changing 
revisions:

./mtn annotate README 0,12s user 0,02s system 99% cpu 0,148 total
./mtn annotate annotate.cc 0,62s user 0,14s system 100% cpu 0,761 total
./mtn annotate Makefile.am 4,69s user 2,55s system 99% cpu 7,243 total
./mtn annotate database.cc 10,54s user 3,06s system 99% cpu 13,595 total
./mtn annotate ChangeLog 172,64s user 14,81s system 98% cpu 3:10,95 total

compared to 0.32+ (f612f74889c12998e416dfafe7ee941fb909311a):

mtn annotate README 0,29s user 0,05s system 100% cpu 0,337 total
mtn annotate annotate.cc 4,70s user 0,33s system 99% cpu 5,036 total
mtn annotate Makefile.am 43,24s user 2,29s system 99% cpu 45,683 total
mtn annotate database.cc 50,17s user 2,25s system 98% cpu 53,036 total
mtn annotate ChangeLog 440,45s user 18,44s system 99% cpu 7:40,51 total

Regards,
Thomas