[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: Branko Čibej <brane_at_xbc.nu>
Date: 2005-02-10 16:37:32 CET

Daniel Berlin wrote:

>On Thu, 2005-02-10 at 12:30 +0100, Branko Čibej wrote:
>
>
>>Branko Čibej wrote:
>>
>>
>>
>
>
>
>>The really horrible bit are the timings (in microseconds)
>>
>>Function Average Min Max
>>
>>svn_txdelta__compose_windows 47.17 0.07 297.67
>>copy_source_ops 0.05 0.04 308.98
>>search_offset_index 0.06 0.01 0.07
>>
>>
>>This shows that the index xearch is fairly stable, but copy_source_ops
>>is not. Note that about 95% of all calls to copy_source_ops come from
>>the recursion.
>>
>>
>
>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
copy_source_ops anomaly. And we could avoid that if it could just use
the deltas that the FS already stores, where possible.

Deciding about a particular delta algorithm would then be a minor issue.

-- Brane

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Thu Feb 10 16:39:09 2005

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