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

[Thomas Moschny]

Derek Scherger wrote:
> 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, at least (as Nathaniel pointed out) if you are loading oldest
rosters first. We could sprinkle complete rosters into our database, say
every M revisions[1], and your access pattern would turn into a O(N)
operation.

Knowing the details of our roster cache, you could try to simulate that
by first asking for the roster of a some later descendant L before
loading roster 1, 2, ...L-1; hoping that roster L stays in the cache.

- Thomas

[1] Of course I'm simplifying here, we don't have a linear history but a
dag, but you get the point.