libkmod-hash: always align n_buckets to power of 2

By aligning n_buckets to power of 2 we can turn the "bucket = hashval %
n_buckets" into a less expensive bucket = hashval & (n_buckets - 1).
This removes the DIV instruction as shown below.

Before:
	xor    %edx,%edx
	divl   0x8(%rbx)
	mov    %edx,%eax
	add    $0x1,%rax
	shl    $0x4,%rax
	add    %rbx,%rax

After:
	lea    -0x1(%rdi),%edx
	and    %edx,%eax
	add    $0x1,%rax
	shl    $0x4,%rax
	add    %rbx,%rax

With a microbenchmark, measuring the time to locate the bucket (i.e.
time_to_calculate_hashval + time_to_calculate_bucket_position) we have
the results below (time in clock cycles):

	keylen      before   after
	2-10          79.0    61.9 (-21.65%)
	11-17         81.0    64.4 (-20.48%)
	18-25         90.0    73.2 (-18.69%)
	26-32        104.7    87.0 (-16.82%)
	33-40        108.4    89.6 (-17.37%)
	41-48        111.2    91.9 (-17.38%)
	49-55        120.1   102.1 (-15.04%)
	56-63        134.4   115.7 (-13.91%)

As expected the gain is constant, regardless of the key length.
The time to clculate the hashval varies with the key length, which
explains the bigger gains for short keys.

diff --git a/libkmod/libkmod-hash.c b/libkmod/libkmod-hash.c
index 57f475c1cefd663f0e2748a5b7e87f84d428ab16..c751d2d4ff1fdb2ff0258566fd03952edad2455d 100644 (file)
--- a/libkmod/libkmod-hash.c
+++ b/libkmod/libkmod-hash.c
@@ -48,8 +48,11 @@ struct hash {
 struct hash *hash_new(unsigned int n_buckets,
                                        void (*free_value)(void *value))
 {
-       struct hash *hash = calloc(1, sizeof(struct hash) +
-                               n_buckets * sizeof(struct hash_bucket));
+       struct hash *hash;
+
+       n_buckets = ALIGN_POWER2(n_buckets);
+       hash = calloc(1, sizeof(struct hash) +
+                     n_buckets * sizeof(struct hash_bucket));
        if (hash == NULL)
                return NULL;
        hash->n_buckets = n_buckets;
@@ -145,7 +148,7 @@ int hash_add(struct hash *hash, const char *key, const void *value)
 {
        unsigned int keylen = strlen(key);
        unsigned int hashval = hash_superfast(key, keylen);
-       unsigned int pos = hashval % hash->n_buckets;
+       unsigned int pos = hashval & (hash->n_buckets - 1);
        struct hash_bucket *bucket = hash->buckets + pos;
        struct hash_entry *entry, *entry_end;
 
@@ -187,7 +190,7 @@ int hash_add_unique(struct hash *hash, const char *key, const void *value)
 {
        unsigned int keylen = strlen(key);
        unsigned int hashval = hash_superfast(key, keylen);
-       unsigned int pos = hashval % hash->n_buckets;
+       unsigned int pos = hashval & (hash->n_buckets - 1);
        struct hash_bucket *bucket = hash->buckets + pos;
        struct hash_entry *entry, *entry_end;
 
@@ -232,7 +235,7 @@ void *hash_find(const struct hash *hash, const char *key)
 {
        unsigned int keylen = strlen(key);
        unsigned int hashval = hash_superfast(key, keylen);
-       unsigned int pos = hashval % hash->n_buckets;
+       unsigned int pos = hashval & (hash->n_buckets - 1);
        const struct hash_bucket *bucket = hash->buckets + pos;
        const struct hash_entry se = {
                .key = key,
@@ -250,7 +253,7 @@ int hash_del(struct hash *hash, const char *key)
 {
        unsigned int keylen = strlen(key);
        unsigned int hashval = hash_superfast(key, keylen);
-       unsigned int pos = hashval % hash->n_buckets;
+       unsigned int pos = hashval & (hash->n_buckets - 1);
        unsigned int steps_used, steps_total;
        struct hash_bucket *bucket = hash->buckets + pos;
        struct hash_entry *entry, *entry_end;