Mercurial > hg > mercurial-crew-with-dirclash

comparison mercurial/bdiff.c @ 5363:058e93c3d07d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 9dc64c8414ca
children 5737845fd974
comparison
equal deleted inserted replaced
5338:f87685355c9c 5363:058e93c3d07d
115 } 115 }
116 116
117 static int equatelines(struct line *a, int an, struct line *b, int bn) 117 static int equatelines(struct line *a, int an, struct line *b, int bn)
118 { 118 {
119 int i, j, buckets = 1, t; 119 int i, j, buckets = 1, t;
120 int scale = 32;
120 struct pos *h; 121 struct pos *h;
121 122
122 /* build a hash table of the next highest power of 2 */ 123 /* build a hash table of the next highest power of 2 */
123 while (buckets < bn + 1) 124 while (buckets < bn + 1)
124 buckets *= 2; 125 buckets *= 2;
125 126
126 h = (struct pos *)malloc(buckets * sizeof(struct pos)); 127 /* try to allocate a large hash table to avoid collisions */
127 buckets = buckets - 1; 128 do {
129 scale /= 2;
130 h = (struct pos *)malloc(scale * buckets * sizeof(struct pos));
131 } while (!h && scale != 1);
132
128 if (!h) 133 if (!h)
129 return 0; 134 return 0;
135
136 buckets = buckets * scale - 1;
130 137
131 /* clear the hash table */ 138 /* clear the hash table */
132 for (i = 0; i <= buckets; i++) { 139 for (i = 0; i <= buckets; i++) {
133 h[i].pos = -1; 140 h[i].pos = -1;
134 h[i].len = 0; 141 h[i].len = 0;