[ This is the discussed stupid approach - just sort the dang hash array,
so that we can use a linear scan over the src/dst ]
On Tue, 2 Oct 2007, David Kastrup wrote:
>
> This does not actually require an actual merge _sort_ AFAICS: do the
> "sort file.hashed" step using qsort. The comparison step does not
> actually need to produce merged output, but merely advances through
> two hash arrays and generates statistics.
>
> This should already beat the pants off the current implementation,
> even when the hash array is sparse, simply because our inner loop then
> has perfect hash coherence.
Sadly, that's not the case. It *does* seem to beat the current
implementation, but it's not "beat the pants off". It looks like an
improvement of about 15%, which is nothing to sneeze at, but it's not an
order-of-magnitude improvement either.
Here's a test-patch. I don't guarantee anything, except that when I did
the timings I also did a "wc" on the result, and they matched..
Before:
[torvalds@woody linux]$ time git diff -l0 --stat -C v2.6.22.. | wc
7104 28574 438020
real 0m10.526s
user 0m10.401s
sys 0m0.136s
After:
[torvalds@woody linux]$ time ~/git/git diff -l0 --stat -C v2.6.22.. | wc
7104 28574 438020
real 0m8.876s
user 0m8.761s
sys 0m0.128s
but the diff is fairly simple, so if somebody will go over it and say
whether it's likely to be *correct* too, that 15% may well be worth it.
[ Side note, without rename detection, that diff takes just under three
seconds for me, so in that sense the improvement to the rename detection
itself is larger than the overall 15% - it brings the cost of just
rename detection from 7.5s to 5.9s, which would be on the order of just
over a 20% performance improvement. ]
Hmm. The patch depends on half-way subtle issues like the fact that the
hashtables are guaranteed to not be full => we're guaranteed to have zero
counts at the end => we don't need to do any steenking iterator count in
the loop. A few comments might in order.
Linus
---
diffcore-delta.c | 54 ++++++++++++++++++++++++++++++------------------------
1 files changed, 30 insertions(+), 24 deletions(-)
diff --git a/diffcore-delta.c b/diffcore-delta.c
index d9729e5..6d65697 100644
--- a/diffcore-delta.c
+++ b/diffcore-delta.c
@@ -46,22 +46,6 @@ struct spanhash_top {
struct spanhash data[FLEX_ARRAY];
};
-static struct spanhash *spanhash_find(struct spanhash_top *top,
- unsigned int hashval)
-{
- int sz = 1 << top->alloc_log2;
- int bucket = hashval & (sz - 1);
- while (1) {
- struct spanhash *h = &(top->data[bucket++]);
- if (!h->cnt)
- return NULL;
- if (h->hashval == hashval)
- return h;
- if (sz <= bucket)
- bucket = 0;
- }
-}
-
static struct spanhash_top *spanhash_rehash(struct spanhash_top *orig)
{
struct spanhash_top *new;
@@ -122,6 +106,20 @@ static struct spanhash_top *add_spanhash(struct spanhash_top *top,
}
}
+static int spanhash_cmp(const void *_a, const void *_b)
+{
+ const struct spanhash *a = _a;
+ const struct spanhash *b = _b;
+
+ /* A count of zero compares at the end.. */
+ if (!a->cnt)
+ return !b->cnt ? 0 : 1;
+ if (!b->cnt)
+ return -1;
+ return a->hashval < b->hashval ? -1 :
+ a->hashval > b->hashval ? 1 : 0;
+}
+
static struct spanhash_top *hash_chars(struct diff_filespec *one)
{
int i, n;
@@ -158,6 +156,10 @@ static struct spanhash_top *hash_chars(struct diff_filespec *one)
n = 0;
accum1 = accum2 = 0;
}
+ qsort(hash->data,
+ 1ul << hash->alloc_log2,
+ sizeof(hash->data[0]),
+ spanhash_cmp);
return hash;
}
@@ -169,7 +171,7 @@ int diffcore_count_changes(struct diff_filespec *src,
unsigned long *src_copied,
unsigned long *literal_added)
{
- int i, ssz;
+ struct spanhash *s, *d;
struct spanhash_top *src_count, *dst_count;
unsigned long sc, la;
@@ -190,22 +192,26 @@ int diffcore_count_changes(struct diff_filespec *src,
}
sc = la = 0;
- ssz = 1 << src_count->alloc_log2;
- for (i = 0; i < ssz; i++) {
- struct spanhash *s = &(src_count->data[i]);
- struct spanhash *d;
+ s = src_count->data;
+ d = dst_count->data;
+ for (;;) {
unsigned dst_cnt, src_cnt;
if (!s->cnt)
- continue;
+ break;
+ while (d->cnt) {
+ if (d->hashval >= s->hashval)
+ break;
+ d++;
+ }
src_cnt = s->cnt;
- d = spanhash_find(dst_count, s->hashval);
- dst_cnt = d ? d->cnt : 0;
+ dst_cnt = d->hashval == s->hashval ? d->cnt : 0;
if (src_cnt < dst_cnt) {
la += dst_cnt - src_cnt;
sc += src_cnt;
}
else
sc += dst_cnt;
+ s++;
}
if (!src_count_p)
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
