diff options
| author | Lucas De Marchi <lucas.demarchi@intel.com> | 2013-08-22 01:36:45 -0300 |
|---|---|---|
| committer | Lucas De Marchi <lucas.demarchi@intel.com> | 2013-09-20 01:10:37 -0500 |
| commit | 82fc7d986cdc60aeb34224f59a92a04e2d514da9 (patch) | |
| tree | bc8e205d6950aca01ddccd547eabb3f0b13e3c52 | |
| parent | 3ba7f59e84857eb4dbe56a68fc7a3ffe8a650393 (diff) | |
| download | kmod-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.c | 15 |
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; |