Re: [Monotone-devel] times to load various things from the database

[Nathaniel Smith]

On Sun, Jan 11, 2009 at 8:35 PM, Derek Scherger <address@hidden> wrote:
>
> On Sun, Jan 11, 2009 at 9:04 PM, Nathaniel Smith <address@hidden> wrote:
>>
>> Right, roster deltas themselves are tiny, and therefore quick to parse
>> (they're basically like revisions).  The problem in profiles has
>> always been a combination of poor access patterns/caching, and the
>> overhead of copying the whole large roster structure in-memory before
>> applying the small delta.
>
> I don't think disk access patterns are affecting my test as this is on
> a hot cache and the database fits in ram comfortably. Looking at where
> database::get_roster_version applies the list of deltas during
> reconstruction I don't immediately *see* anywhere that is copying the
> roster, although I'm sure a copy could be hiding in there somewhere.

I'm not talking about disk access, I'm talking about the roster cache :-).

> My impression is that to load N rosters in dag order we end up doing
> something like:
> - load roster 1 by loading roster N and applying N-1 deltas to it.
> - load roster 2 by loading roster N and applying N-2 deltas to it.
> - ...
> - load roster N.
> Which is O(N squared).

Yes, if you're doing the O(n^2) pessimal thing, then it will suck no
matter what :-).  If you reconstruct in the other order, then the
cache has a chance to help:
 - load roster N by loading it from the database
 - load roster N-1 by pulling roster N from the cache, copying it, and
applying 1 delta to it
 - load roster N-2 by pulling roster N-1 from the cache, copying it,
and applying 1 delta to it
etc.  So for the code you're running the access pattern doesn't play
well with the cache, and if the access pattern or cache were better,
then the copying would be the big problem, that's what I meant :-).

> It appears that building the reconstruction_graph to recreate a roster takes
> time comparable to applying the list of deltas when reconstructing the
> roster as well and I wonder whether we could do better using the cached
> revision_ancestry data? The comment in graph.cc about "loading too much of
> the storage graph into memory" doesn't seem all that relevant as we load the
> full ancestry cache in many other places.

I doubt it.  Profile first, but 1) optimizing inner parts of the
algorithm (like delta application or reconstruction_graph building) is
useless when the problem is that the outer code is calling them too
many times.  O(n^2) with one inner chunk twice as fast is still
O(n^2), 2) we load the full ancestry cache in very few places these
days, we've slowly implemented local algorithms for most things as
loading the full graph really does become a bottleneck.

-- Nathaniel