From bfb84a32cb183c37bf4c7a4522f65a1173dcecd4 Mon Sep 17 00:00:00 2001 From: jdybnis Date: Wed, 26 Nov 2008 05:24:22 +0000 Subject: [PATCH] optimize 8 byte integer keys for list and skiplist --- struct/list.c | 17 +++++++++++++---- struct/skiplist.c | 24 +++++++++++++++++------- test/ll_test.c | 12 ++++++++++-- test/sl_test.c | 12 ++++++++++-- todo | 2 +- 5 files changed, 51 insertions(+), 16 deletions(-) diff --git a/struct/list.c b/struct/list.c index 02a7c2d..94822fc 100644 --- a/struct/list.c +++ b/struct/list.c @@ -26,7 +26,10 @@ struct ll { static node_t *node_alloc (const void *key_data, uint32_t key_len, uint64_t value) { node_t *item = (node_t *)nbd_malloc(sizeof(node_t)); memset(item, 0, sizeof(node_t)); - item->key = key_data ? ns_alloc(key_data, key_len) : NULL; + // If is -1 it indicates is an integer and not a pointer + item->key = (key_len == (unsigned)-1) + ? (void *)TAG_VALUE(key_data) + : ns_alloc(key_data, key_len); item->value = value; return item; } @@ -46,7 +49,7 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, const void *key_data, u while (item != NULL) { node_t *next = item->next; TRACE("l3", "find_pred: visiting item %p (next %p)", item, next); - TRACE("l3", "find_pred: key \"%s\"", ns_data(item->key), item->value); + TRACE("l3", "find_pred: key %p", STRIP_TAG(item->key), item->value); // A tag means an item is logically removed but not physically unlinked yet. while (EXPECT_FALSE(IS_TAGGED(next))) { @@ -87,7 +90,9 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, const void *key_data, u break; // If we reached the key (or passed where it should be), we found the right predesssor - int x = ns_cmp_raw(item->key, key_data, key_len); + int x = (IS_TAGGED(item->key)) + ? (STRIP_TAG(item->key) - (uint64_t)key_data) + : ns_cmp_raw(item->key, key_data, key_len); if (x >= 0) { TRACE("l3", "find_pred: found pred %p item %p", pred, item); if (pred_ptr != NULL) { @@ -188,7 +193,11 @@ void ll_print (list_t *ll) { node_t *item; item = ll->head->next; while (item) { - printf("%s ", (char *)ns_data(item->key)); + if (IS_TAGGED(item->key)) { + printf("0x%llx ", STRIP_TAG(item->key)); + } else { + printf("%s ", (char *)ns_data(item->key)); + } fflush(stdout); item = item->next; } diff --git a/struct/skiplist.c b/struct/skiplist.c index 7f8acee..f7cdf33 100644 --- a/struct/skiplist.c +++ b/struct/skiplist.c @@ -24,7 +24,7 @@ #include "tls.h" // Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list -// in list.c +// (in list.c). #define MAX_LEVEL 31 typedef struct node { @@ -56,7 +56,10 @@ node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t 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 = ns_alloc(key_data, key_len); + // If is -1 it indicates is an integer and not a pointer + item->key = (key_len == (unsigned)-1) + ? (void *)TAG_VALUE(key_data) + : ns_alloc(key_data, key_len); item->value = value; item->top_level = level; return item; @@ -101,7 +104,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl 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); + TRACE("s3", "find_preds: key %p", STRIP_TAG(item->key), item->value); // A tag means an item is logically removed but not physically unlinked yet. while (EXPECT_FALSE(IS_TAGGED(next))) { @@ -142,7 +145,9 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl break; // If we reached the key (or passed where it should be), we found a pred. Save it and continue down. - x = ns_cmp_raw(item->key, key_data, key_len); + x = (IS_TAGGED(item->key)) + ? (STRIP_TAG(item->key) - (uint64_t)key_data) + : ns_cmp_raw(item->key, key_data, key_len); if (x >= 0) { TRACE("s3", "find_preds: found pred %p item %p", pred, item); break; @@ -152,7 +157,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl item = next; } - // The comparison is unsigned for the case when n is -1. + // The cast to unsigned is for the case when n is -1. if ((unsigned)level <= (unsigned)n) { if (preds != NULL) { preds[level] = pred; @@ -181,7 +186,7 @@ uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len) { // Insert the if it doesn't already exist in uint64_t sl_add (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t value) { - TRACE("s3", "sl_add: inserting key %p value %p", key, value); + TRACE("s3", "sl_add: inserting key %p value %p", key_data, value); node_t *preds[MAX_LEVEL+1]; node_t *nexts[MAX_LEVEL+1]; node_t *item = NULL; @@ -315,7 +320,12 @@ void sl_print (skiplist_t *sl) { node_t *item = sl->head; while (item) { int is_marked = IS_TAGGED(item->next[0]); - printf("%s%p:%s ", is_marked ? "*" : "", item, (char *)ns_data(item->key)); + + if (IS_TAGGED(item->key)) { + printf("%s%p:%llx ", is_marked ? "*" : "", item, STRIP_TAG(item->key)); + } else { + printf("%s%p:%s ", is_marked ? "*" : "", item, (char *)ns_data(item->key)); + } if (item != sl->head) { printf("[%d]", item->top_level); } else { diff --git a/test/ll_test.c b/test/ll_test.c index 54ad96b..b907381 100644 --- a/test/ll_test.c +++ b/test/ll_test.c @@ -21,14 +21,22 @@ void *worker (void *arg) { for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { unsigned r = nbd_rand(); - int key = r & 0xF; + uint64_t key = r & 0xF; +#if 1 char key_str[10]; - sprintf(key_str, "%X", key); + sprintf(key_str, "%llX", key); if (r & (1 << 8)) { ll_add(ll_, key_str, strlen(key_str) + 1, 1); } else { ll_remove(ll_, key_str, strlen(key_str) + 1); } +#else + if (r & (1 << 8)) { + ll_add(ll_, (void *)key, -1, 1); + } else { + ll_remove(ll_, (void *)key, -1); + } +#endif rcu_update(); } diff --git a/test/sl_test.c b/test/sl_test.c index c06becb..6c2d4ab 100644 --- a/test/sl_test.c +++ b/test/sl_test.c @@ -21,14 +21,22 @@ void *worker (void *arg) { for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { unsigned r = nbd_rand(); - int key = r & 0xF; + uint64_t key = r & 0xF; +#if 1 char key_str[10]; - sprintf(key_str, "%X", key); + sprintf(key_str, "%llX", key); if (r & (1 << 8)) { sl_add(sl_, key_str, strlen(key_str) + 1, 1); } else { sl_remove(sl_, key_str, strlen(key_str) + 1); } +#else + if (r & (1 << 8)) { + sl_add(sl_, (void *)key, -1, 1); + } else { + sl_remove(sl_, (void *)key, -1); + } +#endif rcu_update(); } diff --git a/todo b/todo index 6586b87..86d19ab 100644 --- a/todo +++ b/todo @@ -6,4 +6,4 @@ + use NULL instead of a sentinal node in skiplist and list - make interfaces for all data structures consistent + make list and skiplist use string keys -- optimize integer keys ++ optimize integer keys -- 2.40.0