[PATCH] delta_files() speedup 1/3: delta composer

Hi devs,

this is part of the delta_files() speedup patch series:
http://svn.haxx.se/dev/archive-2010-03/0604.shtml

SVN spends significant time doing a binary search in
an offset array. Half of the lookup (the one for the
upper limit) is unnecessary because copy_source_ops
access the required information anyway. So we can
simply test while we go. Also, it turns out that most
times, the loop is run only once.

The second optimization required some analysis of
the 'offset access trail', i.e. whether the lookup was
more or less random or allowed for some sort of
favoring certain patterns. Here a typical example:

(offset to find, resulting index, table size)
...
20461 2784 7364
18704 2576 7364
12389 1774 7364
12221 1750 7364
2385 337 7364
51 3 7364
33 2 7364
8037 1150 7364
7109 1012 7364
6968 992 7364
1203 151 7364
4444 645 7364
3970 570 7364
2112 292 7364
79 4 7364
2418 341 7364
4153 599 7364
2218 311 7364
6212 894 7364
3812 543 7364
1212 153 7364
573 71 7364
...

It shows the recursive nature of copy_source_ops
quite well. But most important: the majority of accesses
concentrate at the lower end of the array and ask for
smaller offsets than the respective previous call.

Therefore, we can narrow the range by passing the
last result as a hint to search_offset_index. If it doesn't
fit, we fall back to the full range. Profiling data suggests
that this saves 3/10 iterations in the binary search loop.

Performance gain is ~7%:

s~$ time ~/1.7-928181/svn export --ignore-externals -q $REPO/trunk /dev/shm/t
real 0m3.727s
user 0m3.189s
sys 0m0.542s

~$ time ~/1.7-patched/svn export --ignore-externals -q $REPO/trunk /dev/shm/t
real 0m3.481
user 0m2.935s
sys 0m0.556s

-- Stefan^2.

[[[
Optimize the copy operation table lookup. For details see
http:// ...

* subversion/libsvn_delta/compose_delta.c
  (search_offset_index): add hint parameter and use a
  simpler binary search implementation
  (copy_source_ops): Add hint parameter to pass through
  to search_offset_index. Check for upper limit on-the-fly.
  (svn_txdelta_compose_windows): Pass default value for
  hint to copy_source_ops.

patch by stefanfuhrmann < at > alice-dsl.de
]]]