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?
>
>
You can't avoid recreating fulltexts, but you can certainly avoid
combining a whole chain of deltas for each fulltext. If you have the
fulltext for file F in revision R, there's a good chance that you can
get to F in R-1 by applying a single delta that's already stored in the
repository
In hindsight, it seems that it was a mistake for get_file_revs to return
the list in aacending revision order... As far as the blame calculation
is concerned, the direction shouldn't matter.
>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)
>
>
That's what skip deltas are about.
>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?
>
>
Something along those lines, yes.
>>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.
>
>
I did say "where possible" :-)
-- Brane
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Feb 11 10:48:17 2005