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

Re: delta combiner sloooooooowwwwww

From: Peter N. Lundblad <peter_at_famlundblad.se>
Date: 2005-02-11 22:43:03 CET

On Fri, 11 Feb 2005, Daniel Berlin wrote:

> On Fri, 2005-02-11 at 09:03 +0100, Peter N. Lundblad wrote:
> > On Thu, 10 Feb 2005, [UTF-8] Branko ^Libej wrote:
> >
> > Can you clarify this a bit for someone who knows very much less about FS
> > internals than you? How can get_file_revs avoid recreating fulltexts?
> >
> It can't.
> However, i believe he's saying it could simple send the delta between
> the last revision it sent, and the current revision it is now sending
> (thus only sending a real fulltext for the first revision it sends)
> He is correct.
> However, it already does this :).
>
Yes, I know, since I wrote that code:-) But to be able to be able to
produce deltas between arbitrary revisions, it internally recreates
fulltexts. Look at the implementation of svn_fs_get_file_delta_stream.

> > I did some experimentation with FSFS and noticed that consecutive file
> > revisions often share a common delta predecessor (or how it is spelled).
> > For example:
> > rev 400's delta may be based on r360's delta, which is base on r200, then
> > r80, then r2
> > and r401 may be based on r386, then r360...
> > (the numbers are faked, but you get what I mean)
> > So, since we're reconstructing the deltas in paralell, we could avoid some
> > combining work, it looks like. Is that what you're talking about?
>
> No, that is more what skip deltas were designed to solve, so that you
> could bound the number of predecessors it would have to look at to find
> the deltas.
>
My point is that two consecutive revisions share a common predecessor
pretty soon. Currently, then predecessors for both files are walked and
deltas are combined until the beginning (a delta based on the empty
stream) is reached. Those two walks could share some work meaning less
delta combining. That doesn't solve the O(n^2) of the combiner ofcourse,
but it may make tha constant factor somewhat smaller.

Regards,
//Peter

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Feb 11 22:42:57 2005

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