Re: [Monotone-devel] [sqlite] disk locality (and delta storage)

[drh]

Nathaniel Smith <address@hidden> wrote:
> > 
> > Can you store forward deltas for the benefit of netsync, but
> > also keep a cache of the N most recently accessed files (which
> > will typically be the ends of the chains) or perhaps just the
> > latest files in each chain, and thus avoid the O(n) deltas
> > that would otherwise be required to checkout the head?
> 
> Hrm.  The downsides are probably that 
>   -- people access stuff near the head as well (e.g., running "diff"
>      on the latest few revisions, or running plain "diff" or "commit"
>      in a workspace whose base revision is not the head).
>   -- it makes performance unpredictable -- sometimes you go fast,
>      sometimes slow, and the user can't tell why.

Another idea:  Store both forward and reverse chains.

I ran an experiment yesterday on a linear chain (no forking)
of the largest and most commonly changed file in sqlite: "vdbe.c"
540 revisions.  I constructed a forward chain consisting of
the first revision followed by 539 deltas.  And a backwards
chain consisting of the last revision with 539 back deltas.
I compressed the revisions and all deltas using libz.

  Forward chain:    291349
  Backwards chain:  276839
  Total of both:    568188
  Size of RCS file: 998349

This comparison is not really fair to RCS since the RCS file
is uncompressed and because the RCS file contains revision
comments and other meta information omitted from my chains.
But I have never heard anybody complain that their RCS files
where too big.  So if you can store both forward and backwards
chains in less space than an RCS file, you solve your speed
problem and you still come out ahead of CVS on storage space
efficiency.

Just a thought....
--
D. Richard Hipp   <address@hidden>