genzip: switch to jenkins hash
authorJens Axboe <axboe@fb.com>
Wed, 8 Apr 2015 22:25:49 +0000 (16:25 -0600)
committerJens Axboe <axboe@fb.com>
Wed, 8 Apr 2015 22:25:49 +0000 (16:25 -0600)
Normal distribution causes a lot of collisions with the normal hash,
for some reason. This speeds it up a lot.

Signed-off-by: Jens Axboe <axboe@fb.com>
t/genzipf.c

index 3f36ece86dbc6933cbc4d0469d9ce49277b47f63..ff0729e5bd3bae68fe6045824d69e61df1c473fa 100644 (file)
@@ -59,9 +59,14 @@ static int output_type = OUTPUT_NORMAL;
 #define DEF_ZIPF_VAL   1.2
 #define DEF_PARETO_VAL 0.3
 
 #define DEF_ZIPF_VAL   1.2
 #define DEF_PARETO_VAL 0.3
 
+static unsigned int hashv(unsigned long long val)
+{
+       return jhash(&val, sizeof(val), 0) & (hash_size - 1);
+}
+
 static struct node *hash_lookup(unsigned long long val)
 {
 static struct node *hash_lookup(unsigned long long val)
 {
-       struct flist_head *l = &hash[hash_long(val, hash_bits)];
+       struct flist_head *l = &hash[hashv(val)];
        struct flist_head *entry;
        struct node *n;
 
        struct flist_head *entry;
        struct node *n;
 
@@ -74,14 +79,13 @@ static struct node *hash_lookup(unsigned long long val)
        return NULL;
 }
 
        return NULL;
 }
 
-static struct node *hash_insert(struct node *n, unsigned long long val)
+static void hash_insert(struct node *n, unsigned long long val)
 {
 {
-       struct flist_head *l = &hash[hash_long(val, hash_bits)];
+       struct flist_head *l = &hash[hashv(val)];
 
        n->val = val;
        n->hits = 1;
        flist_add_tail(&n->list, l);
 
        n->val = val;
        n->hits = 1;
        flist_add_tail(&n->list, l);
-       return n;
 }
 
 static void usage(void)
 }
 
 static void usage(void)
@@ -306,7 +310,7 @@ int main(int argc, char *argv[])
 
        hash_size = 1 << hash_bits;
 
 
        hash_size = 1 << hash_bits;
 
-       hash = malloc(hash_size * sizeof(struct flist_head));
+       hash = calloc(hash_size, sizeof(struct flist_head));
        for (i = 0; i < hash_size; i++)
                INIT_FLIST_HEAD(&hash[i]);
 
        for (i = 0; i < hash_size; i++)
                INIT_FLIST_HEAD(&hash[i]);
 
@@ -329,7 +333,6 @@ int main(int argc, char *argv[])
                        hash_insert(&nodes[j], offset);
                        j++;
                }
                        hash_insert(&nodes[j], offset);
                        j++;
                }
-
        }
 
        qsort(nodes, j, sizeof(struct node), node_cmp);
        }
 
        qsort(nodes, j, sizeof(struct node), node_cmp);