[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 09:03:08 CET

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?

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?

> copy_source_ops anomaly. And we could avoid that if it could just use
> the deltas that the FS already stores, where possible.
>
Will that really be comon for consecutive revisions? I didn't see it in
the GCC example repository. And fs_base stores deltas backwards...

I'm surely missing something.

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 09:02:58 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.