summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLucas De Marchi <lucas.demarchi@intel.com>2013-08-22 01:36:45 -0300
committerLucas De Marchi <lucas.demarchi@intel.com>2013-09-20 01:10:37 -0500
commit82fc7d986cdc60aeb34224f59a92a04e2d514da9 (patch)
treebc8e205d6950aca01ddccd547eabb3f0b13e3c52
parent3ba7f59e84857eb4dbe56a68fc7a3ffe8a650393 (diff)
downloadkmod-82fc7d986cdc60aeb34224f59a92a04e2d514da9.tar.gz
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.
-rw-r--r--libkmod/libkmod-hash.c15
1 files changed, 9 insertions, 6 deletions
diff --git a/libkmod/libkmod-hash.c b/libkmod/libkmod-hash.c
index 57f475c..c751d2d 100644
--- 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;