[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: Daniel Berlin <dberlin_at_dberlin.org>
Date: 2005-02-11 15:07:57 CET

On Fri, 2005-02-11 at 09:03 +0100, Peter N. Lundblad wrote:
> On Thu, 10 Feb 2005, [UTF-8] Branko ^Libej wrote:
>
> > Daniel Berlin wrote:
> >
> > >The worst part, is that having stared at the delta combiner for quite a
> > >while myself, i'm actually not sure you can do anything about this
> > >either. I believe that handling source ops from the second window (or
> > >target ops from the first) is just going to be O(n^2) because of what is
> > >*has* to do to make it work right.
> > >
> > >:(
> > >
> > >
> > Yup. At least I'm glad I was right about that. :-\
> >
> > We do know from other measurements that using the delta combiner is
> > better than just applying the deltas in series (generating intermediate
> > fulltexts). But that's not much consolation.
> >
> > Since we're looking specifically at blame, I suspect the best way to
> > improve perfoemance would be to do what I suggested earlier, that is,
> > teach get_file_revs to not recrete every fulltext from scratch. That
> > would reduce the whole blame computation from O(N^2) to O(N), modulo the
>
> 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 :).

IE it could do

send fulltext of start
last = start

for each revision (current) you asked it for besides start:
        send delta between last and current to client
        last = current

Again, get_file_revs already does this though.

> 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.

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

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

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