[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] times to load various things from the database
From: |
Thomas Moschny |
Subject: |
Re: [Monotone-devel] times to load various things from the database |
Date: |
Tue, 13 Jan 2009 14:41:20 +0100 |
User-agent: |
Thunderbird 2.0.0.19 (X11/20090105) |
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.