Re: [Gnu-arch-users] Re: RFC: arch protocol, smart server, and tla implementation prototypes

[Tom Lord]

    > From: Chris Gray <address@hidden>

    > Yes, as I have said, the archive size should grow at a rate on the
    > order of n log n (where n is the number of changesets).

Something to keep in mind is that access patterns to neither revisions
or deltas should be expected to be random.  Nor should they be
expected to be static.

If you just journal the commit transactions as the basic way to store
an archive (and that's essentially what the dumb-fs implementation
does) you get both a very compact archive and optimization for both
recent deltas and any delta which is a short-sequence of successive
deltas from any point in history.   That really does cover a huge
fraction of actual access patterns.

Then, yes -- depending on how the archive is being used -- perhaps you
want to add transient, ancillary data structures to optimize other
access patterns.  But if you start off constraining yourself to think
only about structures that provide fast random access, then you've
started off with one constraint too many and you may therefore miss
the simplest effective answer.

-t