From 052506ff082f134f00834f666653819e18d9bddf Mon Sep 17 00:00:00 2001 From: jdybnis Date: Tue, 25 Nov 2008 06:24:14 +0000 Subject: [PATCH] use NULL instead of a sentinal node in skiplist and list optimizations for small skiplists --- include/runtime.h | 3 +- {runtime => include}/tls.h | 0 runtime/runtime.c | 12 +++ struct/list.c | 51 ++++++----- struct/skiplist.c | 167 ++++++++++++++++++++++--------------- todo | 2 +- 6 files changed, 140 insertions(+), 95 deletions(-) rename {runtime => include}/tls.h (100%) diff --git a/include/runtime.h b/include/runtime.h index 8d9638e..9ba7657 100644 --- a/include/runtime.h +++ b/include/runtime.h @@ -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 diff --git a/runtime/tls.h b/include/tls.h similarity index 100% rename from runtime/tls.h rename to include/tls.h diff --git a/runtime/runtime.c b/runtime/runtime.c index 8056660..c41a1bd 100644 --- a/runtime/runtime.c +++ b/runtime/runtime.c @@ -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; +} diff --git a/struct/list.c b/struct/list.c index d9e4612..124043d 100644 --- a/struct/list.c +++ b/struct/list.c @@ -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); + } + + // 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 matching the return its value. - return (item->key == key) ? item->value : DOES_NOT_EXIST; + return (item && item->key == key) ? item->value : DOES_NOT_EXIST; } // Insert the , if it doesn't already exist in the @@ -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 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; } diff --git a/struct/skiplist.c b/struct/skiplist.c index 9a26720..5e9066c 100644 --- a/struct/skiplist.c +++ b/struct/skiplist.c @@ -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 #include #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 matching the return its value. - return (item->key == key) ? item->value : DOES_NOT_EXIST; + return (item && item->key == key) ? item->value : DOES_NOT_EXIST; } // Insert the if it doesn't already exist in the -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 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 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 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 a54afec..805a9a5 100644 --- 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 -- 2.40.0