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

 /*
  * Copyright (c) 2007 Vojtech Mencl
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
+ *
  * - Redistributions of source code must retain the above copyright
  *   notice, this list of conditions and the following disclaimer.
  * - Redistributions in binary form must reproduce the above copyright
  *   notice, this list of conditions and the following disclaimer in the
  *   documentation and/or other materials provided with the distribution.
  * - The name of the author may not be used to endorse or promote products
  *   derived from this software without specific prior written permission.
+ *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 #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>
 #include <arch/asm.h>
 #include <panic.h>
 #include <mm/slab.h>
 /*
  * Node count must be more then 1000!
  */
 #define NODE_COUNT 100000
 #define GEN_NUM 275604541
 #define OPERATION_COUNT 1000000
 #define TEST_COUNT 3
 static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};
 /*
  * 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;
+    }
+}
 static bool alloc_nodes(int node_count)
+{
     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);
         if (!a) {
             printf("Not enough memory to allocate test arrays.");
             return false;
+        }
         b = (extavltree_node_t *) slab_alloc(extavl_slab,0);
         if (!b) {
             printf("Not enough memory to allocate test arrays.");
             return false;
+        }
         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)
+{
     avltree_node_t *node;
     node = avl_ffn;
     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;
     extavl_ffn = extavl_ffn->par;
     return node;
+}
 static extavlreltree_node_t *alloc_extavlreltree_node(void)
+{
     extavlreltree_node_t *node;
     node = extavlrel_ffn;
     extavlrel_ffn = extavlrel_ffn->par;
     return node;
+}
 static void free_avltree_node(avltree_node_t *node)
+{
     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;
+}
 static void free_extavlreltree_node(extavlreltree_node_t *node)
+{
     node->par = extavlrel_ffn;
     extavlrel_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++) {
         printf("%20u",node_count[ii]);
         keys_prepare(node_count[ii],1);
         /*
          * AVL INSERT
          */
         s[0][ii] = get_cycle();
         avltree_create(&avltree);
         for (i = 0; i < node_count[ii]; i++) {
             avltree_insert(&avltree,alloc_avltree_node());
+        }
         f[0][ii] = get_cycle();
         /*
          * AVL DELETE
          */
         ds[0][ii] = get_cycle();
         while ((a = avltree.root) != NULL) {
             avltree_delete(&avltree,a);
             free_avltree_node(a);
+        }
         df[0][ii] = get_cycle();
         /*
          * ExtAVL INSERT
          */
         s[1][ii] = get_cycle();
         extavltree_create(&extavltree);
         for (i = 0; i < node_count[ii]; i++) {
             extavltree_insert(&extavltree,alloc_extavltree_node());
+        }
         f[1][ii] = get_cycle();
         /*
          * ExtAVL DELETE
          */
         ds[1][ii] = get_cycle();
         while ((b = extavltree.root) != NULL) {
             extavltree_delete(&extavltree,b);
             free_extavltree_node(b);
+        }
         df[1][ii] = get_cycle();
         /*
          * ExtAVLrel INSERT
          */
         s[2][ii] = get_cycle();
         extavlreltree_create(&extavlreltree);
         for (i = 0; i < node_count[ii]; i++) {
             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
+        }
         f[2][ii] = get_cycle();
         /*
          * ExtAVLrel DELETE
          */
         ds[2][ii] = get_cycle();
         while ((c = extavlreltree.root) != NULL) {
             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("%20llu",f[2][ii]-s[2][ii]);
     printf("\n\n");
     printf("DELETE tree deleting root nodes\n");
     printf("Nodes:\t\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++)
         printf("%20llu",df[2][ii]-ds[2][ii]);
     printf("\n\n");
+}
 /** 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++) {
         printf("%20u",node_count[ii]);
         keys_prepare(node_count[ii],2);
         /*
          * AVL INSERT
          */
         s[0][ii] = get_cycle();
         avltree_create(&avltree);
         for (i = 0; i < node_count[ii]; i++) {
             avltree_insert(&avltree,alloc_avltree_node());
+        }
         f[0][ii] = get_cycle();
         /*
          * AVL DELETE
          */
         ds[0][ii] = get_cycle();
         while (avltree.root != NULL) {
             a = avltree_find_min(&avltree);
             avltree_delete_min(&avltree);
             free_avltree_node(a);
+        }
         df[0][ii] = get_cycle();
         /*
          * ExtAVL INSERT
          */
         s[1][ii] = get_cycle();
         extavltree_create(&extavltree);
         for (i = 0; i < node_count[ii]; i++) {
             extavltree_insert(&extavltree,alloc_extavltree_node());
+        }
         f[1][ii] = get_cycle();
         /*
          * ExtAVL DELETE
          */
         ds[1][ii] = get_cycle();
         while (extavltree.root != NULL) {
             b = extavltree.head.next;
             extavltree_delete_min(&extavltree);
             free_extavltree_node(b);
+        }
         df[1][ii] = get_cycle();
         /*
          * ExtAVLrel INSERT
          */
         s[2][ii] = get_cycle();
         extavlreltree_create(&extavlreltree);
         for (i = 0; i < node_count[ii]; i++) {
             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
+        }
         f[2][ii] = get_cycle();
         /*
          * ExtAVLrel DELETE
          */
         ds[2][ii] = get_cycle();
         while (extavlreltree.root != NULL) {
             c = extavlreltree.head.next;
             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("%20llu",f[2][ii]-s[2][ii]);
     printf("\n\n");
     printf("DELETE tree deleting nodes with minimal key\n");
     printf("Nodes:\t\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++)
         printf("%20llu",df[2][ii]-ds[2][ii]);
     printf("\n\n");
+}
 /** 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++) {
         printf("%20u",node_count[ii]);
         keys_prepare(node_count[ii],0);
         /*
          * AVL INSERT
          */
         s[0][ii] = get_cycle();
         avltree_create(&avltree);
         for (i = 0; i < node_count[ii]; i++) {
             avltree_insert(&avltree,alloc_avltree_node());
+        }
         f[0][ii] = get_cycle();
         /*
          * AVL DELETE
          */
         ds[0][ii] = get_cycle();
         while (avltree.root != NULL) {
             a = avltree_find_min(&avltree);
             avltree_delete_min(&avltree);
             free_avltree_node(a);
+        }
         df[0][ii] = get_cycle();
         /*
          * ExtAVL INSERT
          */
         s[1][ii] = get_cycle();
         extavltree_create(&extavltree);
         for (i = 0; i < node_count[ii]; i++) {
             extavltree_insert(&extavltree,alloc_extavltree_node());
+        }
         f[1][ii] = get_cycle();
         /*
          * ExtAVL DELETE
          */
         ds[1][ii] = get_cycle();
         while (extavltree.root != NULL) {
             b = extavltree.head.next;
             extavltree_delete_min(&extavltree);
             free_extavltree_node(b);
+        }
         df[1][ii] = get_cycle();
         /*
          * ExtAVLrel INSERT
          */
         s[2][ii] = get_cycle();
         extavlreltree_create(&extavlreltree);
         for (i = 0; i < node_count[ii]; i++) {
             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
+        }
         f[2][ii] = get_cycle();
         /*
          * ExtAVLrel DELETE
          */
         ds[2][ii] = get_cycle();
         while (extavlreltree.root != NULL) {
             c = extavlreltree.head.next;
             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("%20llu",f[2][ii]-s[2][ii]);
     printf("\n\n");
     printf("DELETE tree deleting nodes with minimal key\n");
     printf("Nodes:\t\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++)
         printf("%20llu",df[2][ii]-ds[2][ii]);
     printf("\n\n");
+}
 /** 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;
     printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT);
     printf("Maximum nodes:\t");
     for (ii = 0; ii < TEST_COUNT; ii++) {
         printf("%20u",node_count[ii]);
         r = (uint64_t) get_cycle();
         mn = node_count[ii];
         /*
          * AVL
          */
         rr = r;
         nc = 0;
         s[0][ii] = get_cycle();
         avltree_create(&avltree);
         for (i = 0; i < OPERATION_COUNT; i++) {
             if (((rr % mn) <= nc) && nc) {
                 /*
                  * Delete min.
                  */
                 a = avltree_find_min(&avltree);
                 avltree_delete_min(&avltree);
                 free_avltree_node(a);
                 nc--;
             } else {
                 /*
                  * Insert.
                  */
                 a = alloc_avltree_node();
                 a->key = rr;
                 avltree_insert(&avltree,a);
                 nc++;
+            }
             rr += GEN_NUM;
+        }
         /*
          * Delete rest tree.
          */
         while (avltree.root != NULL) {
             a = avltree_find_min(&avltree);
             avltree_delete_min(&avltree);
             free_avltree_node(a);
+        }
         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();
         extavltree_create(&extavltree);
         for (i = 0; i < OPERATION_COUNT; i++) {
             if (((rr % mn) <= nc) && nc) {
                 /*
                  * Delete min.
                  */
                 b = extavltree.head.next;
                 extavltree_delete_min(&extavltree);
                 free_extavltree_node(b);
                 nc--;
             } else {
                 /*
                  * Insert.
                  */
                 b = alloc_extavltree_node();
                 b->key = rr;
                 extavltree_insert(&extavltree,b);
                 nc++;
+            }
             rr += GEN_NUM;
+        }
         /*
          * Delete rest tree.
          */
         while (extavltree.root != NULL) {
             b = extavltree.head.next;
             extavltree_delete_min(&extavltree);
             free_extavltree_node(b);
+        }
         f[1][ii] = get_cycle();
         /*
          * ExtAVLrel
          */
         rr = r;
         nc = 0;
         s[2][ii] = get_cycle();
         extavlreltree_create(&extavlreltree);
         for (i = 0; i < OPERATION_COUNT; i++) {
             if (((rr % mn) <= nc) && nc) {
                 /*
                  * Delete min.
                  */
                 c = extavlreltree.head.next;
                 //if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i);
                 extavlreltree_delete_min(&extavlreltree);
                 free_extavlreltree_node(c);
                 nc--;
             } else {
                 /*
                  * Insert.
                  */
                 c = alloc_extavlreltree_node();
                 c->key = rr;
                 //if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i);
                 extavlreltree_insert(&extavlreltree,c);
                 nc++;
+            }
             rr += GEN_NUM;
+        }
         /*
          * Delete rest tree.
          */
         while (extavlreltree.root != NULL) {
             c = extavlreltree.head.next;
             extavlreltree_delete_min(&extavlreltree);
             free_extavlreltree_node(c);
+        }
         f[2][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("%20llu",f[2][ii]-s[2][ii]);
     printf("\n\n");
+}
 char * test_timeoutbench1(bool quiet)
+{
     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;
     /*
      * store initial cycle count,
      * do test,
      * store finish cycle count,
      * show results
      */
     test1();
     test2();
     test3();
     test4();
     /*
      * Deallocate arrays.
      */
     free_nodes(NODE_COUNT);
     return NULL;
+}

Subversion Repositories HelenOS

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