Re: Index/hash order

[Florian Weimer <fw@deneb.enyo.de>]

* Linus Torvalds:

>  - I want things to distribute well. This means that it has to be based 
>    on a "append data" model, where historical data never changes, and you 
>    only append on top of it (either by adding totally new files, or by 
>    just letting the files grow).

Yes, I think this is something which can easily dominate the choice of
data structure.

>    This works in a forward-delta environment (which is fundamentally based 
>    on the notion of "we know the old version, we're adding new stuff on
>    top of it"), but does _not_ work in the backwards model of "we keep the
>    old history as a delta against the new" model.

Forward deltas don't have to be terribly inefficient.  You can get
O(log n) access to revision n fairly easily, using the trick described
there:

  <http://svn.collab.net/repos/svn/trunk/notes/skip-deltas>

I've run a few tests, just to get a few numbers of the overhead
involved.  I used the last ~8,000 changesets from the BKCVS kernel
repository.  With cold cache, a checkout from cold cache takes about
250 seconds on my laptop.  I don't have git numbers, but a mere copy
of the kernel tree needs 40 seconds.

For the hot-cache case, the difference is 140 seconds vs. 2.5 seconds
(or 6 seconds with decompression).

Uh-oh.  I wouldn't have imaged the difference would be *that*
dramatic.  The file system layer is *fast*.

Subversion's delta implementation is not a speed daemon (it handles
arbitrarily large files, which increases complexity significantly and
slows things down, compared to simpler in-memory algorithms), but it
will be very hard to come even close to the 2.5 seconds.

On the storage front, we have 220 MB for the skip deltas vs. 106 MB
for pure deltas-to-previous vs. 1.1 GB for uncompressed files
(directories are always delta-compressed, so to speak[1]).  In the
first two cases, the first revision in the repository is deltaed
against /dev/null and itself and thus compressed, in case you think
the numbers are suspiciously low.

1. AFAICS, you can't really avoid that if you want to track file
   identity information without introducing arbitrary file IDs.