[v3,07/24] ewah: make bitmap growth less aggressive

Commit Message

Taylor Blau Dec. 8, 2020, 12:04 a.m. UTC

From: Jeff King <[e-mail]>

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 <[e-mail]>
Signed-off-by: Taylor Blau <[e-mail]>
---
 ewah/bitmap.c | 11 ++++-------
 1 file changed, 4 insertions(+), 7 deletions(-)

Patch

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)