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
]]]
Index: subversion/libsvn_delta/compose_delta.c
===================================================================
--- subversion/libsvn_delta/compose_delta.c (revision 928181)
+++ subversion/libsvn_delta/compose_delta.c (working copy)
@@ -160,36 +160,49 @@
}
/* Find the index of the delta op thet defines that data at OFFSET in
- NDX. */
+ NDX. HINT is an arbitrary positin within NDX and doesn't even need
+ to be valid. To effectively speed up the search, use the last result
+ as hint because most lookups come as a sequence of decreasing values
+ for OFFSET and they concentrate on the lower end of the array. */
static int
-search_offset_index(const offset_index_t *ndx, apr_size_t offset)
+search_offset_index(const offset_index_t *ndx, apr_size_t offset, int hint)
{
int lo, hi, op;
assert(offset < ndx->offs[ndx->length]);
- for (lo = 0, hi = ndx->length, op = (lo + hi)/2;
- lo < hi;
- op = (lo + hi)/2)
+ lo = 0;
+ hi = ndx->length;
+
+ /* If we got a valid hint, use it to reduce the range to cover.
+ Note that this will only be useful if either the hint is a
+ hit (i.e. equals the desired result) or narrows the range
+ length by a factor larger than 2. */
+
+ if (hint < hi)
{
- const apr_size_t this_offset = ndx->offs[op];
- const apr_size_t next_offset = ndx->offs[op + 1];
- if (offset < this_offset)
- hi = op;
- else if (offset > next_offset)
- lo = op;
+ if (offset < ndx->offs[hint])
+ hi = hint;
+ else if (offset < ndx->offs[hint+1])
+ return hint;
else
- {
- /* this_offset <= offset <= next_offset */
- if (offset == next_offset)
- ++op;
- break;
- }
+ lo = hint+1;
}
- assert(ndx->offs[op] <= offset && offset < ndx->offs[op + 1]);
- return op;
+ /* ordinary binary search */
+
+ for (op = (lo + hi)/2; lo != hi; op = (lo + hi)/2)
+ {
+ if (offset < ndx->offs[op])
+ hi = op;
+ else
+ lo = ++op;
+ }
+
+ --lo;
+ assert(ndx->offs[lo] <= offset && offset < ndx->offs[lo + 1]);
+ return lo;
}
@@ -614,29 +627,34 @@
/* Copy the instructions from WINDOW that define the range [OFFSET,
LIMIT) in WINDOW's target stream to TARGET_OFFSET in the window
- represented by BUILD_BATON. Use NDX to find the instructions in
- WINDOW. Allocate space in BUILD_BATON from POOL. */
+ represented by BUILD_BATON. HINT is a position in the instructions
+ array that helps finding the position for OFFSET. A safe default
+ is 0. Use NDX to find the instructions in WINDOW. Allocate space
+ in BUILD_BATON from POOL. */
static void
-copy_source_ops(apr_size_t offset, apr_size_t limit,
+copy_source_ops(apr_size_t offset, apr_size_t limit,
apr_size_t target_offset,
+ int hint,
svn_txdelta__ops_baton_t *build_baton,
const svn_txdelta_window_t *window,
const offset_index_t *ndx,
apr_pool_t *pool)
{
- const int first_op = search_offset_index(ndx, offset);
- const int last_op = search_offset_index(ndx, limit - 1);
- int op_ndx;
-
- for (op_ndx = first_op; op_ndx <= last_op; ++op_ndx)
+ int op_ndx = search_offset_index(ndx, offset, hint);
+ for (;; ++op_ndx)
{
const svn_txdelta_op_t *const op = &window->ops[op_ndx];
const apr_size_t *const off = &ndx->offs[op_ndx];
+ apr_size_t fix_offset;
+ apr_size_t fix_limit;
- const apr_size_t fix_offset = (offset > off[0] ? offset - off[0] : 0);
- const apr_size_t fix_limit = (off[1] > limit ? off[1] - limit : 0);
+ if (off[0] >= limit)
+ break;
+ fix_offset = (offset > off[0] ? offset - off[0] : 0);
+ fix_limit = (off[1] > limit ? off[1] - limit : 0);
+
/* It would be extremely weird if the fixed-up op had zero length. */
assert(fix_offset + fix_limit < op->length);
@@ -667,6 +685,7 @@
copy_source_ops(op->offset + fix_offset,
op->offset + op->length - fix_limit,
target_offset,
+ op_ndx,
build_baton, window, ndx, pool);
}
else
@@ -692,6 +711,7 @@
copy_source_ops(op->offset + ptn_overlap,
op->offset + ptn_overlap + length,
tgt_off,
+ op_ndx,
build_baton, window, ndx, pool);
fix_off += length;
tgt_off += length;
@@ -707,6 +727,7 @@
copy_source_ops(op->offset,
op->offset + length,
tgt_off,
+ op_ndx,
build_baton, window, ndx, pool);
fix_off += length;
tgt_off += length;
@@ -788,7 +809,7 @@
range->limit - range->offset,
NULL, pool);
else
- copy_source_ops(range->offset, range->limit, tgt_off,
+ copy_source_ops(range->offset, range->limit, tgt_off, 0,
&build_baton, window_A, offset_index,
pool);
