[Monotone-devel] Roster handling in the code

[Patrick Georgi]

Hi,

I'm currently trying to optimize the roster deltification code (as used
by pull, put_revision, probably commit and others).

The current code takes two rosters, compares them, and registers the
differences. The problem is that this approach scales by roster size
(which is directly dependent on the tree size). The problem is, that I'm
working with trees with 50000 files - comparing all of their entries
just to find the 5 that actually changed is quite a waste of time.
As a test, I disabled the roster deltification code, and got quite some
speedup (pushing 10 revisions with put_revision in approx. half the
time), so there's definitely room for improvement.

The pattern, to compare all entries, appears several times more in the code:
    parallel::iter<node_map> i(from.all_nodes(), to.all_nodes())
sometimes with other names for "from" and "to", so more parts of
monotone might benefit from such an optimization.

My current approach is to try to create the roster_delta while the new
roster is created out of the old (using
cset.apply_to(editable_roster_for_{non,}merge)). The most appropriate
place for this seems to be editable_roster_for_{non,}merge, as all data
is passed to it as some point of the operation.

But I'm looking for a more direct approach: Is there a way to get figure
out the revision that matches a roster?
>From there, it should be possible to find out the changeset between the
two revisions, which contains most of the data a roster_delta contains -
basically everything but node_ids and markings, if I'm not mistaken -
and those can be fetched out of the rosters, given the cset data. 5
lookups instead of 50000.

If anyone has ideas on how to improve this area in a better way than
what I tried to describe here, I'd be grateful to hear them. I'm not
that used to the monotone code base, and this is the first time I really
dive into it.


Regards,
Patrick