Mercurial > hg > mercurial-crew-with-dirclash
changeset 5363:058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
pretty easy to find after I recompiled the python interpreter and
mercurial for profiling.
In "bdiff.c" function "equatelines" allocates the minimum hash table
size, which can lead to tons of collisions. I introduced an
"overcommit" factor of 16, this is, I allocate 16 times more memory
than the minimum value. Overcommiting 128 times does not improve the
performance over the 16-times case.
| author | Christoph Spiel <cspiel@freenet.de> |
|---|---|
| date | Thu, 27 Sep 2007 23:57:57 -0500 |
| parents | f87685355c9c |
| children | 5737845fd974 |
| files | mercurial/bdiff.c |
| diffstat | 1 files changed, 9 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/bdiff.c +++ b/mercurial/bdiff.c @@ -117,17 +117,24 @@ int inline cmp(struct line *a, struct li static int equatelines(struct line *a, int an, struct line *b, int bn) { int i, j, buckets = 1, t; + int scale = 32; struct pos *h; /* build a hash table of the next highest power of 2 */ while (buckets < bn + 1) buckets *= 2; - h = (struct pos *)malloc(buckets * sizeof(struct pos)); - buckets = buckets - 1; + /* try to allocate a large hash table to avoid collisions */ + do { + scale /= 2; + h = (struct pos *)malloc(scale * buckets * sizeof(struct pos)); + } while (!h && scale != 1); + if (!h) return 0; + buckets = buckets * scale - 1; + /* clear the hash table */ for (i = 0; i <= buckets; i++) { h[i].pos = -1;