WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/timeout/timeoutbench1.c

  */
 #include <test.h>
 #include <print.h>
 #include <adt/avl.h>
+#include <adt/favl.h>
 #include <adt/extavl.h>
 #include <adt/extavlrel.h>
 #include <debug.h>
 #include <arch/types.h>
 #include <arch/cycle.h>
 /*
  * Wrapper tree data structures.
  */
 static avltree_t avltree;
+static favltree_t favltree;
 static extavltree_t extavltree;
 static extavlreltree_t extavlreltree;
 /*
  * Slab cache variables.
  */
 static slab_cache_t *avl_slab;
+static slab_cache_t *favl_slab;
 static slab_cache_t *extavl_slab;
 static slab_cache_t *extavlrel_slab;
 /*
  * Head of free nodes' list:
  */
 static avltree_node_t *avl_ffn = NULL;
+static favltree_node_t *favl_ffn = NULL;
 static extavltree_node_t *extavl_ffn = NULL;
 static extavlreltree_node_t *extavlrel_ffn = NULL;
 static void keys_prepare(int node_count, int type)
+{
     unsigned int i;
     uint16_t s;
     avltree_node_t *a = avl_ffn;
+    favltree_node_t *b = favl_ffn;
-    extavltree_node_t *b = extavl_ffn;
+    extavltree_node_t *c = extavl_ffn;
-    extavlreltree_node_t *c = extavlrel_ffn;
+    extavlreltree_node_t *d = extavlrel_ffn;
     switch (type) {
         case 0:
             s = (uint16_t) get_cycle();
             for (i = 0; i < node_count; i++) {
                 a->key = s;
                 b->key = s;
                 c->key = s;
+                d->key = s;
                 s += GEN_NUM;
                 a = a->par;
                 b = b->par;
                 c = c->par;
+                d = d->par;
+            }
             break;
         case 1:
             for (i = 1; i <= node_count; i++) {
                 a->key = i;
                 b->key = i;
                 c->key = i;
+                d->key = i;
                 a = a->par;
                 b = b->par;
                 c = c->par;
+                d = d->par;
+            }
             break;
         case 2:
             for (i = node_count; i > 0; i--) {
                 a->key = i;
                 b->key = i;
                 c->key = i;
+                d->key = i;
                 a = a->par;
                 b = b->par;
+                c = c->par;
-                c = c->par;
+                d = d->par;
+            }
             break;
+    }
+}
+{
     int i;
     avltree_node_t *a;
     extavltree_node_t *b;
     extavlreltree_node_t *c;
+    favltree_node_t *d;
     avl_ffn = NULL;
+    favl_ffn = NULL;
     extavl_ffn = NULL;
     extavlrel_ffn = NULL;
     for (i = 0; i < node_count; i++) {
         a = (avltree_node_t *) slab_alloc(avl_slab,0);
         c = (extavlreltree_node_t *) slab_alloc(extavlrel_slab,0);
         if (!c) {
             printf("Not enough memory to allocate test arrays.");
             return false;
+        }
+        d = (favltree_node_t *) slab_alloc(favl_slab,0);
+        if (!d) {
+            printf("Not enough memory to allocate test arrays.");
+            return false;
+        }
         a->par = avl_ffn;
         b->par = extavl_ffn;
         c->par = extavlrel_ffn;
+        d->par = favl_ffn;
         avl_ffn = a;
         extavl_ffn = b;
         extavlrel_ffn = c;
+        favl_ffn = d;
+    }
     return true;
+}
 static void free_nodes(int node_count)
+{
     int i;
     avltree_node_t *a;
     extavltree_node_t *b;
     extavlreltree_node_t *c;
+    favltree_node_t *d;
     for (i = 0; i < node_count; i++) {
         a = avl_ffn;
         b = extavl_ffn;
         c = extavlrel_ffn;
+        d = favl_ffn;
-        if (!a || !b || !c) {
+        if (!a || !b || !c || !d) {
-            printf("Deleted nodes: %d, node count: %d, a: %p, b: %p,c: %p ",i,node_count,a,b,c);
+            printf("Deleted nodes: %d, node count: %d, a: %p, b: %p, c: %p, d: %p\n",
+                    i,node_count,a,b,c,d);
             panic("Some nodes have been lost!");
+        }
         avl_ffn = avl_ffn->par;
         extavl_ffn = extavl_ffn->par;
         extavlrel_ffn = extavlrel_ffn->par;
+        favl_ffn = favl_ffn->par;
         slab_free(avl_slab,a);
         slab_free(extavl_slab,b);
         slab_free(extavlrel_slab,c);
+        slab_free(favl_slab,d);
+    }
+}
 static avltree_node_t *alloc_avltree_node(void)
+{
     avl_ffn = avl_ffn->par;
     return node;
+}
+static favltree_node_t *alloc_favltree_node(void)
+{
+    favltree_node_t *node;
+    node = favl_ffn;
+    favl_ffn = favl_ffn->par;
+    return node;
+}
 static extavltree_node_t *alloc_extavltree_node(void)
+{
     extavltree_node_t *node;
     node = extavl_ffn;
+{
     node->par = avl_ffn;
     avl_ffn = node;
+}
+static void free_favltree_node(favltree_node_t *node)
+{
+    node->par = favl_ffn;
+    favl_ffn = node;
+}
 static void free_extavltree_node(extavltree_node_t *node)
+{
     node->par = extavl_ffn;
     extavl_ffn = node;
+}
 /** Insert keys of ascending sequence and delete tree deleting root nodes.
  */
 static void test1(void)
+{
-    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
+    uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
-    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
+    uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
     unsigned int i,ii;
     avltree_node_t *a;
     extavltree_node_t *b;
     extavlreltree_node_t *c;
+    favltree_node_t *d;
     printf("INSERT nodes with keys of ascending sequence.\n");
     printf("Nodes:\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++) {
             extavlreltree_delete(&extavlreltree,c);
             free_extavlreltree_node(c);
+        }
         df[2][ii] = get_cycle();
+        /*
+         * FAVL INSERT
+         */
+        s[3][ii] = get_cycle();
+        favltree_create(&favltree);
+        for (i = 0; i < node_count[ii]; i++) {
+            favltree_insert(&favltree,alloc_favltree_node());
+        }
+        f[3][ii] = get_cycle();
+        /*
+         * FAVL DELETE
+         */
+        ds[3][ii] = get_cycle();
+        while ((d = favltree.root) != NULL) {
+            favltree_delete(&favltree,d);
+            free_favltree_node(d);
+        }
+        df[3][ii] = get_cycle();
+    }
     printf("\n----------------------------------------------------------------------------");
     printf("\nAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[0][ii]-s[0][ii]);
+    printf("\nFAVL\t\t");
+    for (ii = 0; ii < TEST_COUNT; ii++)
+        printf("%20llu",f[3][ii]-s[3][ii]);
     printf("\nExtAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[1][ii]-s[1][ii]);
     printf("\nExtAVLrel\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20u",node_count[ii]);
     printf("\n----------------------------------------------------------------------------");
     printf("\nAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",df[0][ii]-ds[0][ii]);
+    printf("\nAVL\t\t");
+    for (ii = 0; ii < TEST_COUNT; ii++)
+        printf("%20llu",df[3][ii]-ds[3][ii]);
     printf("\nExtAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",df[1][ii]-ds[1][ii]);
     printf("\nExtAVLrel\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
 /** Insert keys of ascending sequence and delete tree with delete_min functions.
  */
 static void test2(void)
+{
-    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
+    uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
-    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
+    uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
     unsigned int i,ii;
     avltree_node_t *a;
     extavltree_node_t *b;
     extavlreltree_node_t *c;
+    favltree_node_t *d;
     printf("INSERT nodes with keys of descending sequence.\n");
     printf("Nodes:\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++) {
             extavlreltree_delete_min(&extavlreltree);
             free_extavlreltree_node(c);
+        }
         df[2][ii] = get_cycle();
+        /*
+         * FAVL INSERT
+         */
+        s[3][ii] = get_cycle();
+        favltree_create(&favltree);
+        for (i = 0; i < node_count[ii]; i++) {
+            favltree_insert(&favltree,alloc_favltree_node());
+        }
+        f[3][ii] = get_cycle();
+        /*
+         * AVL DELETE
+         */
+        ds[3][ii] = get_cycle();
+        while (favltree.root != NULL) {
+            d = favltree_find_min(&favltree);
+            favltree_delete_min(&favltree);
+            free_favltree_node(d);
+        }
+        df[3][ii] = get_cycle();
+    }
     printf("\n----------------------------------------------------------------------------");
     printf("\nAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[0][ii]-s[0][ii]);
+    printf("\nFAVL\t\t");
+    for (ii = 0; ii < TEST_COUNT; ii++)
+        printf("%20llu",f[3][ii]-s[3][ii]);
     printf("\nExtAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[1][ii]-s[1][ii]);
     printf("\nExtAVLrel\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20u",node_count[ii]);
     printf("\n----------------------------------------------------------------------------");
     printf("\nAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",df[0][ii]-ds[0][ii]);
+    printf("\nFAVL\t\t");
+    for (ii = 0; ii < TEST_COUNT; ii++)
+        printf("%20llu",df[3][ii]-ds[3][ii]);
     printf("\nExtAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",df[1][ii]-ds[1][ii]);
     printf("\nExtAVLrel\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
 /** Insert keys of random sequence and delete tree with delete_min functions.
  */
 static void test3(void)
+{
-    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
+    uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
-    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
+    uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
     unsigned int i,ii;
     avltree_node_t *a;
     extavltree_node_t *b;
     extavlreltree_node_t *c;
+    favltree_node_t *d;
     printf("INSERT nodes with keys of random sequence 1-65536.\n");
     printf("Nodes:\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++) {
             extavlreltree_delete_min(&extavlreltree);
             free_extavlreltree_node(c);
+        }
         df[2][ii] = get_cycle();
+        /*
+         * FAVL INSERT
+         */
+        s[3][ii] = get_cycle();
+        favltree_create(&favltree);
+        for (i = 0; i < node_count[ii]; i++) {
+            favltree_insert(&favltree,alloc_favltree_node());
+        }
+        f[3][ii] = get_cycle();
+        /*
+         * AVL DELETE
+         */
+        ds[3][ii] = get_cycle();
+        while (favltree.root != NULL) {
+            d = favltree_find_min(&favltree);
+            favltree_delete_min(&favltree);
+            free_favltree_node(d);
+        }
+        df[3][ii] = get_cycle();
+    }
     printf("\n----------------------------------------------------------------------------");
     printf("\nAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[0][ii]-s[0][ii]);
+    printf("\nFAVL\t\t");
+    for (ii = 0; ii < TEST_COUNT; ii++)
+        printf("%20llu",f[3][ii]-s[3][ii]);
     printf("\nExtAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[1][ii]-s[1][ii]);
     printf("\nExtAVLrel\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20u",node_count[ii]);
     printf("\n----------------------------------------------------------------------------");
     printf("\nAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",df[0][ii]-ds[0][ii]);
+    printf("\nFAVL\t\t");
+    for (ii = 0; ii < TEST_COUNT; ii++)
+        printf("%20llu",df[3][ii]-ds[3][ii]);
     printf("\nExtAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",df[1][ii]-ds[1][ii]);
     printf("\nExtAVLrel\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
 /** Simulating timeout mechanismus with insert and delete_min operations.
  */
 static void test4(void)
+{
-    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
+    uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
     unsigned int i,ii;
     avltree_node_t *a;
     extavltree_node_t *b;
     extavlreltree_node_t *c;
+    favltree_node_t *d;
     uint64_t r;
     uint16_t rr;
     unsigned int mn,nc;
+        }
         f[0][ii] = get_cycle();
         /*
+         * FAVL
+         */
+        rr = r;
+        nc = 0;
+        s[3][ii] = get_cycle();
+        avltree_create(&avltree);
+        for (i = 0; i < OPERATION_COUNT; i++) {
+            if (((rr % mn) <= nc) && nc) {
+                /*
+                 * Delete min.
+                 */
+                d = favltree_find_min(&favltree);
+                favltree_delete_min(&favltree);
+                free_favltree_node(d);
+                nc--;
+            } else {
+                /*
+                 * Insert.
+                 */
+                d = alloc_favltree_node();
+                d->key = rr;
+                favltree_insert(&favltree,d);
+                nc++;
+            }
+            rr += GEN_NUM;
+        }
+        /*
+         * Delete rest tree.
+         */
+        while (favltree.root != NULL) {
+            d = favltree_find_min(&favltree);
+            favltree_delete_min(&favltree);
+            free_favltree_node(d);
+        }
+        f[3][ii] = get_cycle();
+        /*
          * ExtAVL
          */
         rr = r;
         nc = 0;
         s[1][ii] = get_cycle();
+    }
     printf("\n----------------------------------------------------------------------------");
     printf("\nAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[0][ii]-s[0][ii]);
+    printf("\nFAVL\t\t");
+    for (ii = 0; ii < TEST_COUNT; ii++)
+        printf("%20llu",f[3][ii]-s[3][ii]);
     printf("\nExtAVL\t\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
         printf("%20llu",f[1][ii]-s[1][ii]);
     printf("\nExtAVLrel\t");
     for (ii = 0; ii < TEST_COUNT; ii++)
     printf("\n\tBenchmark test of timeout data structures: AVL, ExtAVL and ExtAVLrel.\n"
         "Run test more than once for eliminating possible distortion due to caching!\n\n");
     avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
+    favl_slab = slab_cache_create("favl_slab",sizeof(favltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     if (!alloc_nodes(NODE_COUNT))
         return NULL;

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/timeout/timeoutbench1.c – Rev 2450 → 2461