summaryrefslogtreecommitdiff
path: root/ewah
diff options
context:
space:
mode:
authorLibravatar Jeff King <peff@peff.net>2020-12-08 17:03:42 -0500
committerLibravatar Junio C Hamano <gitster@pobox.com>2020-12-08 14:48:16 -0800
commit2e2d141afdaa2b086ac5d4228de0dd0003eb69ff (patch)
tree92e871c039a5ea83244b6ef38b8a3e04c231f1bc /ewah
parentewah: factor out bitmap growth (diff)
downloadtgif-2e2d141afdaa2b086ac5d4228de0dd0003eb69ff.tar.xz
ewah: make bitmap growth less aggressive
If you ask to set a bit in the Nth word and we haven't yet allocated that many slots in our array, we'll increase the bitmap size to 2*N. This means we might frequently end up with bitmaps that are twice the necessary size (as soon as you ask for the biggest bit, we'll size up to twice that). But if we just allocate as many words as were asked for, we may not grow fast enough. The worst case there is setting bit 0, then 1, etc. Each time we grow we'd just extend by one more word, giving us linear reallocations (and quadratic memory copies). A middle ground is relying on alloc_nr(), which causes us to grow by a factor of roughly 3/2 instead of 2. That's less aggressive than doubling, and it may help avoid fragmenting memory. (If we start with N, then grow twice, our total is N*(3/2)^2 = 9N/4. After growing twice, that array of size 9N/4 can fit into the space vacated by the original array and first growth, N+3N/2 = 10N/4 > 9N/4, leading to less fragmentation in memory). Our worst case is still 3/2N wasted bits (you set bit N-1, then setting bit N causes us to grow by 3/2), but our average should be much better. This isn't usually that big a deal, but it will matter as we shift the reachability bitmap generation code to store more bitmaps in memory. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Taylor Blau <me@ttaylorr.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'ewah')
-rw-r--r--ewah/bitmap.c11
1 files changed, 4 insertions, 7 deletions
diff --git a/ewah/bitmap.c b/ewah/bitmap.c
index 7c1ecfa6fd..6f9e5c529b 100644
--- a/ewah/bitmap.c
+++ b/ewah/bitmap.c
@@ -37,13 +37,10 @@ struct bitmap *bitmap_new(void)
static void bitmap_grow(struct bitmap *self, size_t word_alloc)
{
- if (word_alloc > self->word_alloc) {
- size_t old_size = self->word_alloc;
- self->word_alloc = word_alloc * 2;
- REALLOC_ARRAY(self->words, self->word_alloc);
- memset(self->words + old_size, 0x0,
- (self->word_alloc - old_size) * sizeof(eword_t));
- }
+ size_t old_size = self->word_alloc;
+ ALLOC_GROW(self->words, word_alloc, self->word_alloc);
+ memset(self->words + old_size, 0x0,
+ (self->word_alloc - old_size) * sizeof(eword_t));
}
void bitmap_set(struct bitmap *self, size_t pos)