use NULL instead of a sentinal node in skiplist and list
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Tue, 25 Nov 2008 06:24:14 +0000 (06:24 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Tue, 25 Nov 2008 06:24:14 +0000 (06:24 +0000)
optimizations for small skiplists

include/runtime.h
include/tls.h [moved from runtime/tls.h with 100% similarity]
runtime/runtime.c
struct/list.c
struct/skiplist.c
todo

index 8d9638ea055008b9182ca5bb1dd7ea76fe5323c4..9ba7657d92f5d800bcc4381ff98ea177643706f9 100644 (file)
@@ -6,9 +6,8 @@
 #define THREADS_H
 
 void nbd_init (void);
-
 int nbd_thread_create (pthread_t *restrict thread, int thread_id, void *(*start_routine)(void *), void *restrict arg);
-
+int nbd_rand (void);
 void rcu_update (void);
 
 #endif//THREADS_H
similarity index 100%
rename from runtime/tls.h
rename to include/tls.h
index 8056660694888b4b596e66a0c0c01655e2ac01ce..c41a1bdaa895364ee9440286de33315c31dacc98 100644 (file)
@@ -10,6 +10,7 @@
 #include "tls.h"
 
 DECLARE_THREAD_LOCAL(tid_, int);
+DECLARE_THREAD_LOCAL(rand_seed_, unsigned);
 
 typedef struct thread_info {
     int thread_id;
@@ -18,6 +19,8 @@ typedef struct thread_info {
 } thread_info_t;
 
 void nbd_init (void) {
+    sranddev();
+    INIT_THREAD_LOCAL(rand_seed_);
     INIT_THREAD_LOCAL(tid_);
     SET_THREAD_LOCAL(tid_, 0);
     mem_init();
@@ -28,6 +31,8 @@ void nbd_init (void) {
 static void *worker (void *arg) {
     thread_info_t *ti = (thread_info_t *)arg;
     SET_THREAD_LOCAL(tid_, ti->thread_id);
+    LOCALIZE_THREAD_LOCAL(tid_, int);
+    SET_THREAD_LOCAL(rand_seed_, tid_+1);
     lwt_thread_init(ti->thread_id);
     rcu_thread_init(ti->thread_id);
     void *ret = ti->start_routine(ti->arg);
@@ -42,3 +47,10 @@ int nbd_thread_create (pthread_t *restrict thread, int thread_id, void *(*start_
     ti->arg = arg;
     return pthread_create(thread, NULL, worker, ti);
 }
+
+int nbd_rand (void) {
+    LOCALIZE_THREAD_LOCAL(rand_seed_, unsigned);
+    unsigned r = rand_r(&rand_seed_);
+    SET_THREAD_LOCAL(rand_seed_, r);
+    return r;
+}
index d9e461260c6511bf16190c9d2323f0849b96eec1..124043d2b4363222c711c644a15a599869b86c51 100644 (file)
@@ -20,7 +20,6 @@ typedef struct node {
 
 typedef struct list {
     node_t *head;
-    node_t *last;
 } list_t;
 
 node_t *node_alloc (uint64_t key, uint64_t value) {
@@ -33,9 +32,8 @@ node_t *node_alloc (uint64_t key, uint64_t value) {
 
 list_t *ll_alloc (void) {
     list_t *list = (list_t *)nbd_malloc(sizeof(list_t));
-    list->head = node_alloc(0, 0);
-    list->last = node_alloc((uint64_t)-1, 0);
-    list->head->next = list->last;
+    list->head = node_alloc((uint64_t)-1, 0);
+    list->head->next = NULL;
     return list;
 }
 
@@ -43,11 +41,8 @@ static node_t *find_pred (node_t **pred_ptr, list_t *list, uint64_t key, int hel
     node_t *pred = list->head;
     node_t *item = pred->next;
     TRACE("l3", "find_pred: searching for key %p in list (head is %p)", key, pred);
-#ifndef NDEBUG
-    int count = 0;
-#endif
 
-    do {
+    while (item != NULL) {
         node_t *next = item->next;
         TRACE("l3", "find_pred: visiting item %p (next %p)", item, next);
         TRACE("l3", "find_pred: key %p", item->key, item->value);
@@ -58,6 +53,8 @@ static node_t *find_pred (node_t **pred_ptr, list_t *list, uint64_t key, int hel
             // Skip over partially removed items.
             if (!help_remove) {
                 item = (node_t *)STRIP_TAG(item->next);
+                if (EXPECT_FALSE(item == NULL))
+                    break;
                 next = item->next;
                 continue;
             }
@@ -66,6 +63,8 @@ static node_t *find_pred (node_t **pred_ptr, list_t *list, uint64_t key, int hel
             node_t *other;
             if ((other = SYNC_CAS(&pred->next, item, STRIP_TAG(next))) == item) {
                 item = (node_t *)STRIP_TAG(next);
+                if (EXPECT_FALSE(item == NULL))
+                    break;
                 next = item->next;
                 TRACE("l3", "find_pred: unlinked item %p from pred %p", item, pred);
                 TRACE("l3", "find_pred: now item is %p next is %p", item, next);
@@ -73,14 +72,19 @@ static node_t *find_pred (node_t **pred_ptr, list_t *list, uint64_t key, int hel
                 // The thread that completes the unlink should free the memory.
                 nbd_defer_free(other);
             } else {
-                TRACE("l3", "find_pred: lost race to unlink item from pred %p; its link changed to %p", pred, other);
+                TRACE("l3", "find_pred: lost race to unlink from pred %p; its link changed to %p", pred, other);
                 if (IS_TAGGED(other))
                     return find_pred(pred_ptr, list, key, help_remove); // retry
                 item = other;
+                if (EXPECT_FALSE(item == NULL))
+                    break;
                 next = item->next;
             }
         }
 
+        if (EXPECT_FALSE(item == NULL))
+            break;
+
         // If we reached the key (or passed where it should be), we found the right predesssor
         if (item->key >= key) {
             TRACE("l3", "find_pred: found pred %p item %p", pred, item);
@@ -90,11 +94,16 @@ static node_t *find_pred (node_t **pred_ptr, list_t *list, uint64_t key, int hel
             return item;
         }
 
-        assert(count++ < 18);
         pred = item;
         item = next;
 
-    } while (1);
+    }
+
+    // <key> is not in the list.
+    if (pred_ptr != NULL) {
+        *pred_ptr = pred;
+    }
+    return NULL;
 }
 
 // Fast find. Do not help unlink partially removed nodes and do not return the found item's predecessor.
@@ -103,7 +112,7 @@ uint64_t ll_lookup (list_t *list, uint64_t key) {
     node_t *item = find_pred(NULL, list, key, FALSE);
 
     // If we found an <item> matching the <key> return its value.
-    return (item->key == key) ? item->value : DOES_NOT_EXIST;
+    return (item && item->key == key) ? item->value : DOES_NOT_EXIST;
 }
 
 // Insert the <key>, if it doesn't already exist in the <list>
@@ -115,7 +124,7 @@ uint64_t ll_add (list_t *list, uint64_t key, uint64_t value) {
         node_t *next = find_pred(&pred, list, key, TRUE);
 
         // If a node matching <key> already exists in the list, return its value.
-        if (next->key == key) {
+        if (next != NULL && next->key == key) {
             TRACE("l3", "ll_add: there is already an item %p (value %p) with the same key", next, next->value);
             if (EXPECT_FALSE(item != NULL)) { nbd_free(item); }
             return next->value;
@@ -138,7 +147,7 @@ uint64_t ll_remove (list_t *list, uint64_t key) {
     TRACE("l3", "ll_remove: removing item with key %p from list %p", key, list);
     node_t *pred;
     node_t *item = find_pred(&pred, list, key, TRUE);
-    if (item->key != key) {
+    if (item == NULL || item->key != key) {
         TRACE("l3", "ll_remove: remove failed, an item with a matching key does not exist in the list", 0, 0);
         return DOES_NOT_EXIST;
     }
@@ -174,7 +183,7 @@ uint64_t ll_remove (list_t *list, uint64_t key) {
 
 void ll_print (list_t *list) {
     node_t *item;
-    item = list->head;
+    item = list->head->next;
     while (item) {
         printf("0x%llx ", item->key);
         fflush(stdout);
@@ -197,18 +206,15 @@ static long num_threads_;
 static list_t *ll_;
 
 void *worker (void *arg) {
-    int id = (int)(size_t)arg;
-
-    unsigned int rand_seed = id+1;//rdtsc_l();
 
     // Wait for all the worker threads to be ready.
     SYNC_ADD(&wait_, -1);
     do {} while (wait_); 
 
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
-        int n = rand_r(&rand_seed);
-        int key = (n & 0xF) + 1;
-        if (n & (1 << 8)) {
+        unsigned r = nbd_rand();
+        int key = (r & 0xF);
+        if (r & (1 << 8)) {
             ll_add(ll_, key, 1);
         } else {
             ll_remove(ll_, key);
@@ -269,9 +275,8 @@ int main (int argc, char **argv) {
 
     gettimeofday(&tv2, NULL);
     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
-    printf("Th:%ld Time:%dms\n", num_threads_, ms);
     ll_print(ll_);
-    lwt_dump("lwt.out");
+    printf("Th:%ld Time:%dms\n", num_threads_, ms);
 
     return 0;
 }
index 9a26720001474f2858b53a46530b30b3e3c20de2..5e9066c280165b078ddc3cbd5a7613d442df4502 100644 (file)
@@ -2,23 +2,28 @@
  * Written by Josh Dybnis and released to the public domain, as explained at
  * http://creativecommons.org/licenses/publicdomain
  *
- * C implementation of the lock-free skiplist data-structure created by Maurice Herlihy, 
- * Yossi Lev, and Nir Shavit. See "The Art of Multiprocessor Programming"
+ * Implementation of the lock-free skiplist data-structure created by Maurice Herlihy, Yossi Lev,
+ * and Nir Shavit. See Herlihy's and Shivit's book "The Art of Multiprocessor Programming".
  * http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916/
  *
- * See also Kir Fraser's dissertation "Practical Lock Freedom"
+ * See also Kir Fraser's dissertation "Practical Lock Freedom".
  * www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
  *
- * This code depends on certain stores and loads being ordered. Be careful on non-x86 platforms
- * with weaker memory-models. This code probably won't work without adding some memory barriers.
+ * This code is written for the x86 memory-model. The algorithim depends on certain stores and
+ * loads being ordered. Be careful, this code probably won't work correctly on platforms with
+ * weaker memory models if you don't add memory barriers in the right places.
  */
 #include <stdio.h>
 #include <string.h>
 
 #include "common.h"
+#include "runtime.h"
 #include "struct.h"
 #include "mem.h"
+#include "tls.h"
 
+// Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list
+// in list.c
 #define MAX_LEVEL 31
 
 typedef struct node {
@@ -30,57 +35,67 @@ typedef struct node {
 
 typedef struct skiplist {
     node_t *head;
-    node_t *last;
-    int top_level;
 } skiplist_t;
 
-static int random_level (int r) {
+static int random_level (void) {
+    unsigned r = nbd_rand();
     if (r&1)
         return 0;
-    int n = __builtin_ctz(r);
-    if (n < MAX_LEVEL)
-        return n;
-    return MAX_LEVEL;
+    int n = __builtin_ctz(r)-1;
+#if MAX_LEVEL < 31
+    if (n > MAX_LEVEL)
+        return MAX_LEVEL;
+#endif
+    assert(n <= MAX_LEVEL);
+    return n;
 }
 
-node_t *node_alloc (int top_level, uint64_t key, uint64_t value) {
-    assert(top_level >= 0 && top_level <= MAX_LEVEL);
-    size_t sz = sizeof(node_t) + (top_level + 1) * sizeof(node_t *);
+node_t *node_alloc (int level, uint64_t key, uint64_t value) {
+    assert(level >= 0 && level <= MAX_LEVEL);
+    size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *);
     node_t *item = (node_t *)nbd_malloc(sz);
     memset(item, 0, sz);
     item->key   = key;
     item->value = value;
-    item->top_level = top_level;
+    item->top_level = level;
     return item;
 }
 
 skiplist_t *sl_alloc (void) {
     skiplist_t *skiplist = (skiplist_t *)nbd_malloc(sizeof(skiplist_t));
     skiplist->head = node_alloc(MAX_LEVEL, 0, 0);
-    skiplist->last = node_alloc(MAX_LEVEL, (uint64_t)-1, 0);
-    for (int level = 0; level <= MAX_LEVEL; ++level) {
-        skiplist->head->next[level] = skiplist->last;
-    }
+    memset(skiplist->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *));
     return skiplist;
 }
 
-static node_t *find_preds (node_t **preds, skiplist_t *skiplist, uint64_t key, int help_remove) {
+static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *skiplist, uint64_t key, int help_remove) {
     node_t *pred = skiplist->head;
     node_t *item = NULL;
     TRACE("s3", "find_preds: searching for key %p in skiplist (head is %p)", key, pred);
-#ifndef NDEBUG
-    int count = 0;
-#endif
+
+    // Optimization for small lists. No need to traverse empty higher levels.
+    assert(MAX_LEVEL > 2);
+    int start_level = 2;
+    while (pred->next[start_level+1] != NULL) {
+        start_level += start_level - 1;
+        if (EXPECT_FALSE(start_level >= MAX_LEVEL)) {
+            start_level = MAX_LEVEL;
+            break;
+        }
+    }
+    if (EXPECT_FALSE(start_level < n)) {
+        start_level = n;
+    }
 
     // Traverse the levels of the skiplist from the top level to the bottom
-    for (int level = MAX_LEVEL; level >= 0; --level) {
+    for (int level = start_level; level >= 0; --level) {
         TRACE("s3", "find_preds: level %llu", level, 0);
         item = pred->next[level];
-        if (IS_TAGGED(item)) {
+        if (EXPECT_FALSE(IS_TAGGED(item))) {
             TRACE("s3", "find_preds: pred %p is marked for removal (item %p); retry", pred, item);
-            return find_preds(preds, skiplist, key, help_remove); // retry
+            return find_preds(preds, n, skiplist, key, help_remove); // retry
         }
-        do {
+        while (item != NULL) {
             node_t *next = item->next[level];
             TRACE("s3", "find_preds: visiting item %p (next %p)", item, next);
             TRACE("s3", "find_preds: key %p", item->key, 0);
@@ -91,6 +106,8 @@ static node_t *find_preds (node_t **preds, skiplist_t *skiplist, uint64_t key, i
                 // Skip over partially removed items.
                 if (!help_remove) {
                     item = (node_t *)STRIP_TAG(item->next);
+                    if (EXPECT_FALSE(item == NULL))
+                        break;
                     next = item->next[level];
                     continue;
                 }
@@ -99,6 +116,8 @@ static node_t *find_preds (node_t **preds, skiplist_t *skiplist, uint64_t key, i
                 node_t *other;
                 if ((other = SYNC_CAS(&pred->next[level], item, STRIP_TAG(next))) == item) {
                     item = (node_t *)STRIP_TAG(next);
+                    if (EXPECT_FALSE(item == NULL))
+                        break;
                     next = item->next[level];
                     TRACE("s3", "find_preds: unlinked item %p from pred %p", item, pred);
                     TRACE("s3", "find_preds: now item is %p next is %p", item, next);
@@ -106,28 +125,37 @@ static node_t *find_preds (node_t **preds, skiplist_t *skiplist, uint64_t key, i
                     // The thread that completes the unlink should free the memory.
                     if (level == 0) { nbd_defer_free(other); }
                 } else {
-                    TRACE("s3", "find_preds: lost race to unlink item from pred %p; its link changed to %p",pred,other);
+                    TRACE("s3", "find_preds: lost race to unlink from pred %p; its link changed to %p", pred, other);
                     if (IS_TAGGED(other))
-                        return find_preds(preds, skiplist, key, help_remove); // retry
+                        return find_preds(preds, n, skiplist, key, help_remove); // retry
                     item = other;
+                    if (EXPECT_FALSE(item == NULL))
+                        break;
                     next = item->next[level];
                 }
             }
 
+            if (EXPECT_FALSE(item == NULL))
+                break;
+
             // If we reached the key (or passed where it should be), we found a pred. Save it and continue down.
             if (item->key >= key) {
                 TRACE("s3", "find_preds: found pred %p item %p", pred, item);
-                if (preds != NULL) {
-                    preds[level] = pred;
-                }
                 break;
             }
 
-            assert(count++ < 18);
             pred = item;
             item = next;
-
-        } while (1);
+        }
+        if (preds != NULL) {
+            preds[level] = pred;
+        }
+    }
+    if (n == -1 && item != NULL) {
+        assert(preds != NULL);
+        for (int level = start_level + 1; level <= item->top_level; ++level) {
+            preds[level] = skiplist->head;
+        }
     }
     return item;
 }
@@ -135,35 +163,38 @@ static node_t *find_preds (node_t **preds, skiplist_t *skiplist, uint64_t key, i
 // Fast find that does not help unlink partially removed nodes and does not return the node's predecessors.
 uint64_t sl_lookup (skiplist_t *skiplist, uint64_t key) {
     TRACE("s3", "sl_lookup: searching for key %p in skiplist %p", key, skiplist);
-    node_t *item = find_preds(NULL, skiplist, key, FALSE);
+    node_t *item = find_preds(NULL, 0, skiplist, key, FALSE);
 
     // If we found an <item> matching the <key> return its value.
-    return (item->key == key) ? item->value : DOES_NOT_EXIST;
+    return (item && item->key == key) ? item->value : DOES_NOT_EXIST;
 }
 
 // Insert the <key> if it doesn't already exist in the <skiplist>
-uint64_t sl_add_r (int r, skiplist_t *skiplist, uint64_t key, uint64_t value) {
+uint64_t sl_add (skiplist_t *skiplist, uint64_t key, uint64_t value) {
     TRACE("s3", "sl_add: inserting key %p value %p", key, value);
     node_t *preds[MAX_LEVEL+1];
     node_t *item = NULL;
     do {
-        node_t *next = find_preds(preds, skiplist, key, TRUE);
+        int n = random_level();
+        node_t *next = find_preds(preds, n, skiplist, key, TRUE);
 
         // If a node matching <key> already exists in the skiplist, return its value.
-        if (next->key == key) {
+        if (next != NULL && next->key == key) {
             TRACE("s3", "sl_add: there is already an item %p (value %p) with the same key", next, next->value);
             if (EXPECT_FALSE(item != NULL)) { nbd_free(item); }
             return next->value;
         }
 
         // First insert <item> into the bottom level.
-        if (EXPECT_TRUE(item == NULL)) { item = node_alloc(random_level(r), key, value); }
+        if (EXPECT_TRUE(item == NULL)) { item = node_alloc(n, key, value); }
         TRACE("s3", "sl_add: attempting to insert item between %p and %p", preds[0], next);
         item->next[0] = next;
         for (int level = 1; level <= item->top_level; ++level) {
-            item->next[level] = preds[level]->next[level];
+            node_t *pred = preds[level];
+            item->next[level] = pred->next[level];
         }
-        node_t *other = SYNC_CAS(&preds[0]->next[0], next, item);
+        node_t *pred = preds[0];
+        node_t *other = SYNC_CAS(&pred->next[0], next, item);
         if (other == next) {
             TRACE("s3", "sl_add: successfully inserted item %p at level 0", item, 0);
             break; // success
@@ -175,13 +206,17 @@ uint64_t sl_add_r (int r, skiplist_t *skiplist, uint64_t key, uint64_t value) {
     // Insert <item> into the skiplist from the bottom level up.
     for (int level = 1; level <= item->top_level; ++level) {
         do {
-            node_t *pred = preds[level];
-            node_t *next = pred->next[level];
-            while (EXPECT_FALSE(IS_TAGGED(next) || next->key < key)) {
-                find_preds(preds, skiplist, key, TRUE);
+            node_t *pred;
+            node_t *next;
+            do {
                 pred = preds[level];
                 next = pred->next[level];
-            }
+                if (next == NULL) // item goes at the end of the list
+                    break;
+                if (!IS_TAGGED(next) && next->key > key) // pred's link changed
+                    break;
+                find_preds(preds, item->top_level, skiplist, key, TRUE);
+            } while (1);
 
             do {
                 // There in no need to continue linking in the item if another thread removed it.
@@ -210,8 +245,8 @@ uint64_t sl_add_r (int r, skiplist_t *skiplist, uint64_t key, uint64_t value) {
 uint64_t sl_remove (skiplist_t *skiplist, uint64_t key) {
     TRACE("s3", "sl_remove: removing item with key %p from skiplist %p", key, skiplist);
     node_t *preds[MAX_LEVEL+1];
-    node_t *item = find_preds(preds, skiplist, key, TRUE);
-    if (item->key != key) {
+    node_t *item = find_preds(preds, -1, skiplist, key, TRUE);
+    if (item == NULL || item->key != key) {
         TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the skiplist", 0, 0);
         return DOES_NOT_EXIST;
     }
@@ -261,12 +296,12 @@ uint64_t sl_remove (skiplist_t *skiplist, uint64_t key) {
 void sl_print (skiplist_t *skiplist) {
     for (int level = MAX_LEVEL; level >= 0; --level) {
         node_t *item = skiplist->head;
-        if (item->next[level] == skiplist->last)
+        if (item->next[level] == NULL)
             continue;
         printf("(%d) ", level);
         while (item) {
             node_t *next = item->next[level];
-            printf("%s%p:0x%llx ", IS_TAGGED(next) ? "*" : "", item, item->key);
+            printf("%s%p ", IS_TAGGED(next) ? "*" : "", item);
             item = (node_t *)STRIP_TAG(next);
         }
         printf("\n");
@@ -276,18 +311,16 @@ void sl_print (skiplist_t *skiplist) {
     printf("\n");
     node_t *item = skiplist->head;
     while (item) {
-        assert(item->top_level <= MAX_LEVEL);
         int is_marked = IS_TAGGED(item->next[0]);
-        printf("%s%p:0x%llx (%d", is_marked ? "*" : "", item, item->key, item->top_level);
+        printf("%s%p:0x%llx [%d]", is_marked ? "*" : "", item, item->key, item->top_level);
         for (int level = 1; level <= item->top_level; ++level) {
             node_t *next = (node_t *)STRIP_TAG(item->next[level]);
-            printf(" %p:0x%llx", item->next[level], next ? next->key : 0);
-            if (item == skiplist->head && item->next[level] == skiplist->last)
-                break;
-            if (item == skiplist->last && item->next[level] == NULL)
+            is_marked = IS_TAGGED(item->next[0]);
+            printf(" %p%s", next, is_marked ? "*" : "");
+            if (item == skiplist->head && item->next[level] == NULL)
                 break;
         }
-        printf(")\n");
+        printf("\n");
         fflush(stdout);
         item = (node_t *)STRIP_TAG(item->next[0]);
     }
@@ -307,19 +340,16 @@ static long num_threads_;
 static skiplist_t *sl_;
 
 void *worker (void *arg) {
-    int id = (int)(size_t)arg;
-
-    unsigned int rand_seed = id+1;//rdtsc_l();
 
     // Wait for all the worker threads to be ready.
     SYNC_ADD(&wait_, -1);
     do {} while (wait_); 
 
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
-        int n = rand_r(&rand_seed);
-        int key = (n & 0xF) + 1;
-        if (n & (1 << 8)) {
-            sl_add_r(n, sl_, key, 1);
+        unsigned r = nbd_rand();
+        int key = (r & 0xF) + 1;
+        if (r & (1 << 8)) {
+            sl_add(sl_, key, 1);
         } else {
             sl_remove(sl_, key);
         }
@@ -379,9 +409,8 @@ int main (int argc, char **argv) {
 
     gettimeofday(&tv2, NULL);
     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
-    printf("Th:%ld Time:%dms\n", num_threads_, ms);
     sl_print(sl_);
-    lwt_dump("lwt.out");
+    printf("Th:%ld Time:%dms\n", num_threads_, ms);
 
     return 0;
 }
diff --git a/todo b/todo
index a54afec7d03e81dcb4d357491ad1b54f61180386..805a9a55a7ecf8fb09054db3a9e2e409df02ba68 100644 (file)
--- a/todo
+++ b/todo
@@ -3,5 +3,5 @@
 - investigate 16 byte CAS; ht can store GUIDs inline instead of pointers to actual keys 
 - test ht
 + optimize tracing code, still too much overhead
-- use NULL instead of a sentinal node in skiplist and list
++ use NULL instead of a sentinal node in skiplist and list
 - make interfaces for all data structures consistent