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. _______________________________________________ Monotone-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/monotone-devel
