monotone-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Derek Scherger
Subject: Re: [Monotone-devel] times to load various things from the database
Date: Sun, 11 Jan 2009 21:35:07 -0700


On Sun, Jan 11, 2009 at 9:04 PM, Nathaniel Smith <address@hidden> wrote:
On Sat, Jan 10, 2009 at 10:58 PM, Derek Scherger <address@hidden> wrote:
> However, reading rosters is comparably slow.
[...]
> There is some improvement here but not all that much. It seems that long
> delta chains are likely a bigger factor. After reconstructing an old
> roster with a long delta chain (600 deltas), the roster for the next
> revision is reconstructed by rebuilding essentially the same delta chain
> (599 deltas) and applying it again.

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.

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).

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.

Cheers,
Derek


reply via email to

[Prev in Thread] Current Thread [Next in Thread]