[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: CPU usage during commits

From: John Szakmeister <john_at_szakmeister.net>
Date: 2006-05-25 10:12:41 CEST

----- Simon Butler <simon@icmethods.com> wrote:
> can anyone explain why we need a binary diff at the repos? what is
> the algorithm for determining which previous revision is diffed for
> the FSFS repos delta? it seems like this is redundant

The binary diff is there to help reduce storage requirements. The algorithm used to determine which revision is diffed against is called skip-deltas. Documentation about it can be found here:

Assuming that I understand correctly, you believe it's redundant because we're computing a delta to send over the wire, and then another one for storage into the repos. The reason there are two is that sending a delta over the wire is more WAN friendly. The reason that we don't use those deltas to store into the repos comes down to algorithmic efficiency. If we used the deltas the client sent, then we would need to combine every single revision of a file in order to produce the full-text. That means the more revisions you have, the more deltas that need to be combined, and it grows in a linear fashion. OTOH, using skip-deltas, the Subversion team has been able to limit that to O(lg(N)) behavior, which is much more favorable when you start talking about repositories with hundreds of thousands of revisions (think GCC, and ASF repositories).
> >
> > I understand that Subversion has a good binary delta algorithm and
> > that it is used for all files, text or binary, and that
> > improvements in the algorithm are certainly welcomed.
> >
> reducing redundant delta calculation would be the first step here.


To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org
Received on Thu May 25 10:14:02 2006

This is an archived mail posted to the Subversion Users mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.