Mercurial Linux Symposium paper

[Malcolm Rowe <ma...@farside.org.uk>]

Something I thought people might be interested in: the proceedings
of the 2006 Ottawa Linux Symposium includes an interesting, if short,
paper titled "Towards a Better SCM: Revlog and Mercurial".

It describes in brief how Mercurial handles revision storage through its
revlog structure and delta storage.  I know that dberlin has been looking
at using something like the former to reduce the number of files we open
during FSFS read operations; and as Mercurial uses an algorithm called
'bdiff'[1] (based on Python's difflib algorithm) rather than xdelta,
it might also be interesting to explore what kind of performance/storage
results we'd get by doing the same.

Available in volume 2 of the proceedings, pp.91-98.
http://www.linuxsymposium.org/2006/linuxsymposium_procv2.pdf

[1] e.g. http://www.selenic.com/hg/?f=60111a755b30;file=mercurial/bdiff.c

Regards,
Malcolm

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Mercurial Linux Symposium paper

[Malcolm Rowe <ma...@farside.org.uk>]

On Tue, Jul 25, 2006 at 10:06:03PM -0400, Daniel Berlin wrote:
> So, i've explored about a billion different delta algorithms, including
> what mercurial does.
> 

> I've got an improved delta algorithm based on rabin fingerprinting that
> is roughly 10% faster than xdelta most of the time, and up to 50-60%
> faster on larger (>a couple meg) files.  The delta sizes are either the
> same, slightly smaller, or slightly larger, depending :)
> 

Because I've just spent ages trying to find out what Rabin fingerprinting
is, I'll say that there's some interesting information at [1].  Not
interesting directly (it's primarily about duplicate elimination rather
than delta encoding), but interesting because it contains electronic
copies of some of the relevant papers (at [2]), which I couldn't find
anywhere else.

Dan, are you working on something like that described in this paper?

  M. Ajtai, R. Burns, R. Fagin, D. D. E. Long, and L. Stockmeyer.
  Compactly encoding unstructured inputs with differential compression.
  Journal of the ACM, 49(3):318367, May 2002.
  http://www.cs.utah.edu/~shanth/stuff/research/dup_elim/delta_encode.pdf

I've not read it properly yet, but it seems to be based around similar
concepts.

Regards,
Malcolm

[1] http://www.cs.utah.edu/~shanth/stuff/research/dup_elim/final.txt
[2] http://www.cs.utah.edu/~shanth/stuff/research/dup_elim/

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Mercurial Linux Symposium paper

[Branko Čibej <br...@xbc.nu>]

Daniel Berlin wrote:
> (This is because the code currently relies on knowing whether there are
> more windows waiting to consume by comparing the window length against
> the default window size, instead of by seeing if there is an EOF :( )
>   
Yes, I plead guilty. :(

On the other hand, changing the window size to something different than
what's used in the repository will break the delta combiner, and I get
nightmares when I think about trying to support variable window sizes in
the combiner.

-- Brane

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Mercurial Linux Symposium paper

[Daniel Berlin <db...@dberlin.org>]

Malcolm Rowe wrote:
> Something I thought people might be interested in: the proceedings
> of the 2006 Ottawa Linux Symposium includes an interesting, if short,
> paper titled "Towards a Better SCM: Revlog and Mercurial".
> 
> It describes in brief how Mercurial handles revision storage through its
> revlog structure and delta storage.  I know that dberlin has been looking
> at using something like the former to reduce the number of files we open
> during FSFS read operations; and as Mercurial uses an algorithm called
> 'bdiff'[1] (based on Python's difflib algorithm) rather than xdelta,
> it might also be interesting to explore what kind of performance/storage
> results we'd get by doing the same.

So, i've explored about a billion different delta algorithms, including
what mercurial does.

They actually break data (including binary data) into lines, bucket it,
and then just match things against the buckets.

In other words, it's not significantly different than xdelta, except
that it uses a window size consisting of "one line" instead of "64 bytes".

For text data, i'm sure it does great. For binary data, i have a hard
time seeing how it could do all that great.  They zlib compress the
result, so most of their binary compression probably comes from that.

I've got an improved delta algorithm based on rabin fingerprinting that
is roughly 10% faster than xdelta most of the time, and up to 50-60%
faster on larger (>a couple meg) files.  The delta sizes are either the
same, slightly smaller, or slightly larger, depending :)

I also think we should up our default window size, but due to some
silliness in how this is currently implemented, changing the window size
is backwards incompatible!

(This is because the code currently relies on knowing whether there are
more windows waiting to consume by comparing the window length against
the default window size, instead of by seeing if there is an EOF :( )

--Dan

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Mercurial Linux Symposium paper

[Greg Hudson <gh...@MIT.EDU>]

On Tue, 2006-07-25 at 12:54 +0100, Malcolm Rowe wrote:
> It describes in brief how Mercurial handles revision storage through its
> revlog structure and delta storage.  I know that dberlin has been looking
> at using something like the former to reduce the number of files we open
> during FSFS read operations; and as Mercurial uses an algorithm called
> 'bdiff'[1] (based on Python's difflib algorithm) rather than xdelta,
> it might also be interesting to explore what kind of performance/storage
> results we'd get by doing the same.

I was *almost* cited in that paper!  I'm listed as "unknown," although
since the cited URL is in the Subversion project repository, it would
have only taken a small amount of work to identify me as the author.
(To be fair, much more work than is required to identify the author of
the usual scholarly paper.)

When I orginally wrote FSFS, I concentrated on deployability in as many
environments as possible.  By having one new file per revision, for
instance, it is possible to make the revisions directory insert-only in
some filesystems, which makes it impossible to tamper with old data.

For best performance, we want a substantially different approach.
Certainly, the data for a given file should be located in one contiguous
area, either in revlog-style or a weave.  It should also be possible to
compress directories without seriously compromising performance, using a
btree with multiple roots. (Currently, in both back ends, we store every
revision of every directory separately and in full, so retrieval is fast
but space performance for large directories is abysmal.)

After reading the paper, I'm a little confused about how revlog works.
I believe it is using storing a flat (self-compressed) revision every
time the amount of patch data exceeds a certain multiple of the
compressed size of the last checkpoint revision.  That's an interesting
take on checkpoint revisions.  I originally discarded checkpoint
revisions because if you're naively storing, say, 10% of your revisions
flat, then your space cost is at least 10% of <total size of all
revisions>, which isn't a good order characteristic.  Skip-deltas was
supposed to achieve similar access benefits (O(lg(n)) tends to behave
like O(1) in practice) while still having better space characteristics.
Revlog's space-sensitive checkpointing may achieve similar space
efficiency without requiring as much seeking around.

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org