Merge branch 'master' of ssh://brick.kernel.dk/data/git/fio
authorJens Axboe <axboe@kernel.dk>
Wed, 7 Nov 2012 12:39:18 +0000 (13:39 +0100)
committerJens Axboe <axboe@kernel.dk>
Wed, 7 Nov 2012 12:39:18 +0000 (13:39 +0100)
Makefile
hash.h
lib/zipf.c
rbtree.c
rbtree.h
t/genzipf.c

index 88d397b66b7f38bc9926023a7547f3c5c280c767..f59f809616e73b73a1d132f9e2fc318ab5b75347 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -77,7 +77,7 @@ T_IEEE_OBJS += lib/ieee754.o
 T_IEEE_PROGS = t/ieee754
 
 T_ZIPF_OBS = t/genzipf.o
-T_ZIPF_OBJS += t/log.o lib/ieee754.o lib/rand.o lib/zipf.o t/genzipf.o
+T_ZIPF_OBJS += rbtree.o t/log.o lib/ieee754.o lib/rand.o lib/zipf.o t/genzipf.o
 T_ZIPF_PROGS = t/genzip
 
 T_OBJS = $(T_SMALLOC_OBJS)
diff --git a/hash.h b/hash.h
index 4b8c6bf0bcc49bd9b1f1b56c38c6e6b6243df22e..93dd8318ffa11dcb4324ab5ec7622880506916fd 100644 (file)
--- a/hash.h
+++ b/hash.h
@@ -28,7 +28,7 @@
 #error Define GOLDEN_RATIO_PRIME for your wordsize.
 #endif
 
-static inline unsigned long hash_long(unsigned long val, unsigned int bits)
+static inline unsigned long __hash_long(unsigned long val)
 {
        unsigned long hash = val;
 
@@ -52,8 +52,13 @@ static inline unsigned long hash_long(unsigned long val, unsigned int bits)
        hash *= GOLDEN_RATIO_PRIME;
 #endif
 
+       return hash;
+}
+
+static inline unsigned long hash_long(unsigned long val, unsigned int bits)
+{
        /* High bits are more random, so use them. */
-       return hash >> (BITS_PER_LONG - bits);
+       return __hash_long(val) >> (BITS_PER_LONG - bits);
 }
        
 static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
index 28e8d77e5602d13b95e73e561ce4df418750d441..527ae294cf9afd6212151e004e2220163e25f888 100644 (file)
@@ -9,6 +9,7 @@
 #include "../log.h"
 #include "zipf.h"
 #include "../minmax.h"
+#include "../hash.h"
 #include "../os/os.h"
 
 struct fio_zipf_disk {
@@ -124,7 +125,7 @@ unsigned long long zipf_next(struct zipf_state *zs)
        else
                val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha));
 
-       return val - 1;
+       return __hash_long(val - 1) % zs->nranges;
 }
 
 void pareto_init(struct zipf_state *zs, unsigned long nranges, double h)
@@ -142,5 +143,5 @@ unsigned long long pareto_next(struct zipf_state *zs)
        double rand = (double) __rand(&zs->rand) / (double) FRAND_MAX;
        unsigned long long n = zs->nranges - 1;
 
-       return n * pow(rand, zs->pareto_pow);
+       return __hash_long(n * pow(rand, zs->pareto_pow)) % zs->nranges;
 }
index 7cff649821e85260014efc0aca4916221575962b..883bc7231d0905b114e45fb57c9a0b525e252b98 100644 (file)
--- a/rbtree.c
+++ b/rbtree.c
@@ -300,3 +300,34 @@ struct rb_node *rb_first(struct rb_root *root)
                n = n->rb_left;
        return n;
 }
+
+struct rb_node *rb_next(const struct rb_node *node)
+{
+       struct rb_node *parent;
+
+       if (RB_EMPTY_NODE(node))
+               return NULL;
+
+       /*
+        * If we have a right-hand child, go down and then left as far
+        * as we can.
+        */
+       if (node->rb_right) {
+               node = node->rb_right; 
+               while (node->rb_left)
+                       node=node->rb_left;
+               return (struct rb_node *)node;
+       }
+
+       /*
+        * No right-hand children. Everything down and left is smaller than us,
+        * so any 'next' node must be in the general direction of our parent.
+        * Go up the tree; any time the ancestor is a right-hand child of its
+        * parent, keep going up. First time it's a left-hand child of its
+        * parent, said parent is our 'next' node.
+        */
+       while ((parent = rb_parent(node)) && node == parent->rb_right)
+               node = parent;
+
+       return parent;
+}
index 7563725e51a90e37cff54e81c546ed30b151b28f..c6cfe4a9384d8041c978d7cef4b31cc587125e65 100644 (file)
--- a/rbtree.h
+++ b/rbtree.h
@@ -141,6 +141,7 @@ extern void rb_erase(struct rb_node *, struct rb_root *);
 
 /* Find logical next and previous nodes in a tree */
 extern struct rb_node *rb_first(struct rb_root *);
+extern struct rb_node *rb_next(const struct rb_node *);
 
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                struct rb_node ** rb_link)
index f28674424df13fdf15b16aed76ec488dff1e266a..d06f5619b15d38f3c991bb0e20b4e28d35b1effe 100644 (file)
 #include <string.h>
 
 #include "../lib/zipf.h"
+#include "../flist.h"
+#include "../hash.h"
+#include "../rbtree.h"
 
 #define DEF_NR         1000000
 #define DEF_NR_OUTPUT  23
 
-static int val_cmp(const void *p1, const void *p2)
+struct node {
+       struct flist_head list;
+       struct rb_node rb;
+       unsigned long long val;
+       unsigned long hits;
+};
+
+static struct flist_head *hash;
+static unsigned long hash_bits = 24;
+static unsigned long hash_size = 1 << 24;
+static struct rb_root rb;
+
+static struct node *hash_lookup(unsigned long long val)
+{
+       struct flist_head *l = &hash[hash_long(val, hash_bits)];
+       struct flist_head *entry;
+       struct node *n;
+
+       flist_for_each(entry, l) {
+               n = flist_entry(entry, struct node, list);
+               if (n->val == val)
+                       return n;
+       }
+
+       return NULL;
+}
+
+static void hash_insert(unsigned long long val)
+{
+       struct flist_head *l = &hash[hash_long(val, hash_bits)];
+       struct node *n = malloc(sizeof(*n));
+
+       n->val = val;
+       n->hits = 1;
+       flist_add_tail(&n->list, l);
+}
+
+static void rb_insert(struct node *n)
+{
+       struct rb_node **p, *parent;
+
+       memset(&n->rb, 0, sizeof(n->rb));
+       p = &rb.rb_node;
+       parent = NULL;
+       while (*p) {
+               struct node *__n;
+
+               parent = *p;
+               __n = rb_entry(parent, struct node, rb);
+               if (n->hits > __n->hits)
+                       p = &(*p)->rb_left;
+               else
+                       p = &(*p)->rb_right;
+       }
+
+       rb_link_node(&n->rb, parent, p);
+       rb_insert_color(&n->rb, &rb);
+}
+
+static unsigned long rb_add(struct flist_head *list)
+{
+       struct flist_head *entry;
+       unsigned long ret = 0;
+       struct node *n;
+
+       flist_for_each(entry, list) {
+               n = flist_entry(entry, struct node, list);
+
+               rb_insert(n);
+               ret++;
+       }
+
+       return ret;
+}
+
+static unsigned long rb_gen(void)
 {
-       const unsigned long *v1 = p1;
-       const unsigned long *v2 = p2;
+       unsigned long ret = 0;
+       unsigned int i;
 
-       return *v1 - *v2;
+       for (i = 0; i < hash_size; i++)
+               ret += rb_add(&hash[i]);
+
+       return ret;
 }
 
 int main(int argc, char *argv[])
 {
        unsigned long nranges, output_nranges;
-       unsigned long *vals;
-       unsigned long i, j, nr_vals, cur_vals, max_val, interval;
+       unsigned long offset;
+       unsigned long i, j, nr_vals, cur_vals, interval;
        double *output, perc, perc_i;
        struct zipf_state zs;
+       struct rb_node *n;
        int use_zipf;
        double val;
 
@@ -71,52 +153,67 @@ int main(int argc, char *argv[])
        else
                pareto_init(&zs, nranges, val);
 
-       vals = malloc(nranges * sizeof(unsigned long));
+       hash_bits = 0;
+       hash_size = nranges;
+       while ((hash_size >>= 1) != 0)
+               hash_bits++;
+
+       hash_size = 1 << hash_bits;
+
+       hash = malloc(hash_size * sizeof(struct flist_head));
+       for (i = 0; i < hash_size; i++)
+               INIT_FLIST_HEAD(&hash[i]);
+
+       for (nr_vals = 0, i = 0; i < nranges; i++) {
+               struct node *n;
 
-       max_val = nr_vals = 0;
-       for (i = 0; i < nranges; i++) {
                if (use_zipf)
-                       vals[nr_vals] = zipf_next(&zs);
+                       offset = zipf_next(&zs);
                else
-                       vals[nr_vals] = pareto_next(&zs);
+                       offset = pareto_next(&zs);
+
+               n = hash_lookup(offset);
+               if (n)
+                       n->hits++;
+               else
+                       hash_insert(offset);
 
-               if (vals[nr_vals] > max_val)
-                       max_val = vals[nr_vals];
                nr_vals++;
        }
 
-       qsort(vals, nr_vals, sizeof(unsigned long), val_cmp);
+       nr_vals = rb_gen();
 
-       interval = (max_val + output_nranges - 1) / output_nranges;
+       interval = (nr_vals + output_nranges - 1) / output_nranges;
 
        output = malloc(output_nranges * sizeof(double));
 
-       for (i = j = 0, cur_vals = 0; i < nr_vals; i++) {
-               if (vals[i] > interval) {
-                       output[j] = (double) (cur_vals + 1) / (double) nr_vals;
+       i = j = cur_vals = 0;
+       
+       n = rb_first(&rb);
+       while (n) {
+               struct node *node = rb_entry(n, struct node, rb);
+
+               if (i >= interval) {
+                       output[j] = (double) (cur_vals + 1) / (double) nranges;
                        output[j] *= 100.0;
                        j++;
-                       cur_vals = 0;
-                       interval += (max_val + output_nranges - 1) / output_nranges;
-                       continue;
-               }
-               cur_vals++;
-       }
+                       cur_vals = node->hits;
+                       interval += (nr_vals + output_nranges - 1) / output_nranges;
+               } else
+                       cur_vals += node->hits;
 
-       if (cur_vals) {
-               output[j] = (double) (cur_vals + 1) / (double) nr_vals;
-               output[j] *= 100.0;
-               j++;
+               n = rb_next(n);
+               i++;
        }
 
        perc_i = 100.0 / (double) output_nranges;
        perc = 0.0;
        for (i = 0; i < j; i++) {
-               printf("%6.2f%% -> %6.2f%%:\t%6.2f%%\n",  perc, perc + perc_i, output[i]);
                perc += perc_i;
+               printf("%s %6.2f%%:\t%6.2f%% of hits\n", i ? "|->" : "Top", perc, output[i]);
        }
 
        free(output);
-       free(vals);
+       free(hash);
        return 0;
 }