2 files changed, 28 insertions, 44 deletions

diff --git a/Makefile b/Makefile
index 00fd0ba..997b886 100644
--- a/Makefile
+++ b/Makefile
@@ -1 +1,7 @@
-CFLAGS=-Wall -g -O2
+CFLAGS := -Wall -Werror -D_FILE_OFFSET_BITS=64 -g -O2
+
+all: bitmap
+
+.PHONY: clean
+clean:
+	@rm -f bitmap bitmap.o
diff --git a/bitmap.c b/bitmap.c
index 5e7bcb5..78034fd 100644
--- a/bitmap.c
+++ b/bitmap.c
@@ -1,35 +1,28 @@
-#include <assert.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
-#define TREE_ARY	8
-#define BITS_PER_LEAF	(TREE_ARY * 64)
+typedef uint32_t unset_t;
+
+#define BITS_PER_WORD	(sizeof(unset_t) * 8)
+#define bits_unset(x)	(BITS_PER_WORD - __builtin_popcount(x))
+
+#define TREE_ARY	16
+#define BITS_PER_LEAF	(TREE_ARY * BITS_PER_WORD)
 
 struct bitmap_tree {
-	uint64_t	size;
-	uint64_t	nr_unset;
-	size_t		first_leaf;
+	struct {
+		uint64_t	size;
+		uint64_t	nr_unset;
+		size_t		first_leaf;
+	} __attribute__((aligned(64)));
 
 	struct bitmap_tree_node {
-		uint64_t nr_unset[TREE_ARY];
+		unset_t nr_unset[TREE_ARY];
 	} tree[];
 };
 
-unsigned popcount_64(uint64_t x)
-{
-	static const uint64_t m1  = 0x5555555555555555LLU;
-	static const uint64_t m2  = 0x3333333333333333LLU;
-	static const uint64_t m4  = 0x0f0f0f0f0f0f0f0fLLU;
-	static const uint64_t h01 = 0x0101010101010101LLU;
-
-	x -= (x >> 1) & m1;
-	x = (x & m2) + ((x >> 2) & m2);
-	x = (x + (x >> 4)) & m4;
-	return (x * h01) >> 56;
-}
-
 static void bitmap_tree_init(struct bitmap_tree *tree, size_t i,
 			     uint64_t nr_unset, uint64_t nr_this_level)
 {
@@ -42,8 +35,6 @@ static void bitmap_tree_init(struct bitmap_tree *tree, size_t i,
 		nr_this_level /= TREE_ARY;
 
 		while (nr_unset) {
-			assert(j < TREE_ARY);
-
 			n->nr_unset[j] = nr_unset < nr_this_level
 				? nr_unset : nr_this_level;
 
@@ -92,43 +83,34 @@ static uint64_t set_nth_unset_bit_recurse(struct bitmap_tree *tree, size_t i,
 					  uint64_t bit_to_set)
 {
 	struct bitmap_tree_node *n = tree->tree + i;
-	unsigned j = 0;
+	unsigned j = 0, bit = 0;
 
 	if (i < tree->first_leaf) {
 		i = TREE_ARY * i + 1;
+		__builtin_prefetch(tree->tree + i);
 
 		while (bit_to_set > n->nr_unset[j]) {
 			bit_to_set -= n->nr_unset[j];
 			j++;
-			assert(j < TREE_ARY);
 		}
 
 		n->nr_unset[j]--;
 
 		return set_nth_unset_bit_recurse(tree, i + j, bit_to_set);
 	} else {
-		uint64_t ret = (i - tree->first_leaf) * BITS_PER_LEAF;
-		unsigned bit = 0;
-
-		while (bit_to_set > 64 - popcount_64(n->nr_unset[j])) {
-			bit_to_set -= 64 - popcount_64(n->nr_unset[j]);
-
-			ret += 64;
+		while (bit_to_set > bits_unset(n->nr_unset[j])) {
+			bit_to_set -= bits_unset(n->nr_unset[j]);
 			j++;
-			assert(j < TREE_ARY);
 		}
 
 		do {
-			while (n->nr_unset[j] & (1ULL << bit)) {
-				ret++;
+			while (n->nr_unset[j] & (1ULL << bit))
 				bit++;
-				assert(bit < 64);
-			}
 		} while (bit_to_set--);
 
 		n->nr_unset[j] &= ~(1ULL << bit);
 
-		return ret;
+		return ((i - tree->first_leaf) * TREE_ARY + j) * BITS_PER_WORD + bit;
 	}
 }
 
@@ -144,12 +126,8 @@ int main()
 {
 	struct bitmap_tree *tree = bitmap_tree_alloc(123320987);
 
-	while (tree->nr_unset) {
-		uint64_t bit = set_nth_unset_bit(tree, lrand48());
-
-		if (!(tree->nr_unset % 10000))
-			printf("set bit %lu\n", bit);
-	}
+	while (tree->nr_unset)
+		set_nth_unset_bit(tree, lrand48());
 
 	return 0;
 }