*
* Extreamly fast multi-threaded malloc.
*/
+#ifndef USE_SYSTEM_MALLOC
#define _BSD_SOURCE // so we get MAP_ANON on linux
-#include <sys/mman.h>
+#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
+#include <sys/mman.h>
#include "common.h"
#include "rlocal.h"
#include "lwt.h"
-#define GET_SCALE(n) (sizeof(void *)*__CHAR_BIT__ - __builtin_clzl((n) - 1)) // log2 of <n>, rounded up
+#define RECYCLE_PAGES
+
+#define MAX_SCALE 31 // allocate blocks up to 4GB (arbitrary, could be bigger)
#ifndef NBD32
+#define MIN_SCALE 3 // smallest allocated block is 8 bytes
#define MAX_POINTER_BITS 48
-#define REGION_SCALE 21 // 2mb regions
+#define PAGE_SCALE 21 // 2MB pages
#else
+#define MIN_SCALE 2 // smallest allocated block is 4 bytes
#define MAX_POINTER_BITS 32
-#define REGION_SCALE 12 // 4kb regions
+#define PAGE_SCALE 12 // 4KB pages
#endif
-#define REGION_SIZE (1 << REGION_SCALE)
-#define HEADER_REGION_SCALE ((MAX_POINTER_BITS - REGION_SCALE) + GET_SCALE(sizeof(header_t)))
-#define MAX_SCALE 31 // allocate blocks up to 4GB in size (arbitrary, could be bigger)
+#define PAGE_SIZE (1 << PAGE_SCALE)
+#define HEADERS_SIZE (((size_t)1 << (MAX_POINTER_BITS - PAGE_SCALE)) * sizeof(header_t))
typedef struct block {
struct block *next;
} block_t;
-// region header
+// TODO: Break the page header into two parts. The first part is located in the header region. The
+// second part is located on the page and is only used when there are free items.
typedef struct header {
+#ifdef RECYCLE_PAGES
+ struct header *next;
+ struct header *prev;
+ block_t *free_list; // list of free blocks
+ int num_in_use;
+#endif//RECYCLE_PAGES
uint8_t owner; // thread id of owner
uint8_t scale; // log2 of the block size
} header_t;
+#ifdef RECYCLE_PAGES
+typedef struct size_class {
+ header_t *active_page;
+ header_t *oldest_partial;
+ header_t *newest_partial;
+} size_class_t;
+#endif//RECYCLE_PAGES
+
typedef struct tl {
- block_t *free_blocks[MAX_SCALE+1];
+#ifndef RECYCLE_PAGES
+ block_t *free_list[MAX_SCALE+1];
+#else
+ header_t *free_pages;
+ size_class_t size_class[MAX_SCALE+1];
+#endif//RECYCLE_PAGES
block_t *blocks_from[MAX_NUM_THREADS];
block_t *blocks_to[MAX_NUM_THREADS];
-} __attribute__((aligned(CACHE_LINE_SIZE))) tl_t ;
+} __attribute__((aligned(CACHE_LINE_SIZE))) tl_t;
static header_t *headers_ = NULL;
static tl_t tl_[MAX_NUM_THREADS] = {};
static inline header_t *get_header (void *r) {
- return headers_ + ((size_t)r >> REGION_SCALE);
+ ASSERT(((size_t)r >> PAGE_SCALE) < HEADERS_SIZE);
+ return headers_ + ((size_t)r >> PAGE_SCALE);
}
static void *get_new_region (int block_scale) {
- size_t sz = (1 << block_scale);
- if (sz < REGION_SIZE) {
- sz = REGION_SIZE;
+ LOCALIZE_THREAD_LOCAL(tid_, int);
+#ifdef RECYCLE_PAGES
+ tl_t *tl = &tl_[tid_]; // thread-local data
+ if (block_scale <= PAGE_SCALE && tl->free_pages != NULL) {
+ void *region = tl->free_pages;
+ tl->free_pages = tl->free_pages->next;
+ get_header(region)->scale = block_scale;
+ return region;
+ }
+#endif//RECYCLE_PAGES
+ size_t region_size = (1 << block_scale);
+ if (region_size < PAGE_SIZE) {
+ region_size = PAGE_SIZE;
}
- void *region = mmap(NULL, sz, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
- TRACE("m1", "get_new_region: mmapped new region %p (size %p)", region, sz);
+ void *region = mmap(NULL, region_size, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
+ TRACE("m1", "get_new_region: mmapped new region %p (size %p)", region, region_size);
if (region == (void *)-1) {
perror("get_new_region: mmap");
exit(-1);
}
- if ((size_t)region & (sz - 1)) {
+ if ((size_t)region & (region_size - 1)) {
TRACE("m0", "get_new_region: region not aligned", 0, 0);
- munmap(region, sz);
- region = mmap(NULL, sz * 2, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
+ munmap(region, region_size);
+ region = mmap(NULL, region_size * 2, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
if (region == (void *)-1) {
perror("get_new_region: mmap");
exit(-1);
}
- TRACE("m0", "get_new_region: mmapped new region %p (size %p)", region, sz * 2);
- void *aligned = (void *)(((size_t)region + sz) & ~(sz - 1));
+ TRACE("m0", "get_new_region: mmapped new region %p (size %p)", region, region_size * 2);
+ void *aligned = (void *)(((size_t)region + region_size) & ~(region_size - 1));
size_t extra = (char *)aligned - (char *)region;
if (extra) {
munmap(region, extra);
TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", region, extra);
}
- extra = ((char *)region + sz) - (char *)aligned;
+ extra = ((char *)region + region_size) - (char *)aligned;
if (extra) {
- munmap((char *)aligned + sz, extra);
- TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", (char *)aligned + sz, extra);
+ munmap((char *)aligned + region_size, extra);
+ TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", (char *)aligned + region_size, extra);
}
region = aligned;
}
assert(region);
- if (headers_ != NULL) {
- LOCALIZE_THREAD_LOCAL(tid_, int);
- header_t *h = get_header(region);
- TRACE("m1", "get_new_region: header %p (%p)", h, h - headers_);
-
- assert(h->scale == 0);
- h->scale = block_scale;
- h->owner = tid_;
- }
+
+ header_t *h = get_header(region);
+ TRACE("m1", "get_new_region: header %p (%p)", h, h - headers_);
+ assert(h->scale == 0);
+ h->scale = block_scale;
+ h->owner = tid_;
return region;
}
void mem_init (void) {
-#ifdef USE_SYSTEM_MALLOC
- return;
-#endif
assert(headers_ == NULL);
- // Allocate a region for the region headers. This could be a big chunk of memory (256MB) on 64 bit systems,
- // but it just takes up virtual address space. Physical address space used by the headers is still proportional
- // to the amount of memory we alloc.
- headers_ = (header_t *)get_new_region(HEADER_REGION_SCALE);
- TRACE("m1", "mem_init: header region %p", headers_, 0);
- memset(headers_, 0, (1 << HEADER_REGION_SCALE));
+ // Allocate space for the page headers. This could be a big chunk of memory on 64 bit systems,
+ // but it just takes up virtual address space. Physical space used by the headers is still
+ // proportional to the amount of memory the user mallocs.
+ headers_ = (header_t *)malloc(HEADERS_SIZE);
+ TRACE("m1", "mem_init: header page %p", headers_, 0);
+ memset(headers_, 0, HEADERS_SIZE);
+
+ // initialize spsc queues
+ for (int i = 0; i < MAX_NUM_THREADS; ++i) {
+ for (int j = 0; j < MAX_NUM_THREADS; ++j) {
+ if (i != j) {
+ tl_[i].blocks_to[j] = (block_t *)&(tl_[j].blocks_from[i]);
+ }
+ }
+ }
}
-// Put <x> onto its owner's public free list (in the appropriate size bin).
-//
-// TODO: maybe we want to munmap() larger size blocks?
void nbd_free (void *x) {
-#ifdef USE_SYSTEM_MALLOC
- TRACE("m1", "nbd_free: %p", x, 0);
-#ifndef NDEBUG
- //memset(x, 0xcd, sizeof(void *)); // bear trap
-#endif//NDEBUG
- free(x);
- return;
-#endif//USE_SYSTEM_MALLOC
- TRACE("m1", "nbd_free: block %p region %p", x, (size_t)x & ~MASK(REGION_SCALE));
-
- assert(x);
+ TRACE("m1", "nbd_free: block %p page %p", x, (size_t)x & ~MASK(PAGE_SCALE));
+ ASSERT(x);
LOCALIZE_THREAD_LOCAL(tid_, int);
block_t *b = (block_t *)x;
header_t *h = get_header(x);
- TRACE("m1", "nbd_free: header %p scale %llu", h, h->scale);
- assert(h->scale && h->scale <= MAX_SCALE);
+ int b_scale = h->scale;
+ TRACE("m1", "nbd_free: header %p scale %llu", h, b_scale);
+ ASSERT(b_scale && b_scale <= MAX_SCALE);
+#ifdef RECYCLE_PAGES
+ if (b_scale > PAGE_SCALE) {
+ int rc = munmap(x, 1 << b_scale);
+ ASSERT(rc == 0);
+ rc = rc;
+ }
+#endif
#ifndef NDEBUG
- memset(b, 0xcd, (1 << h->scale)); // bear trap
+ memset(b, 0xcd, (1 << b_scale)); // bear trap
#endif
tl_t *tl = &tl_[tid_]; // thread-local data
if (h->owner == tid_) {
- TRACE("m1", "nbd_free: private block, old free list head %p", tl->free_blocks[h->scale], 0);
- b->next = tl->free_blocks[h->scale];
- tl->free_blocks[h->scale] = b;
+ TRACE("m1", "nbd_free: private block, old free list head %p", tl->free_list[b_scale], 0);
+
+#ifndef RECYCLE_PAGES
+ b->next = tl->free_list[b_scale];
+ tl->free_list[b_scale] = b;
+#else //RECYCLE_PAGES
+ b->next = h->free_list;
+ h->free_list = b;
+ h->num_in_use--;
+ size_class_t *sc = &tl->size_class[b_scale];
+ if (sc->active_page != h) {
+ if (h->num_in_use == 0) {
+ // remove <h> from the partial-page list
+ if (h->next != NULL) { h->next->prev = h->prev; }
+ if (h->prev != NULL) { h->prev->next = h->next; }
+ // put <h> on the free-page list
+ h->next = tl->free_pages;
+ tl->free_pages = h;
+ } else {
+ // move <h> to the top of the partial-page list
+ if (h->next != NULL) {
+ h->next->prev = h->prev;
+ if (h->prev != NULL) { h->prev->next = h->next; }
+ h->prev = sc->newest_partial;
+ h->next = NULL;
+ sc->newest_partial = h;
+ }
+ }
+ }
+#endif//RECYCLE_PAGES
} else {
- TRACE("m1", "nbd_free: owner %llu", h->owner, 0);
// push <b> onto it's owner's queue
- VOLATILE(b->next) = NULL;
- if (EXPECT_FALSE(tl->blocks_to[h->owner] == NULL)) {
- VOLATILE(tl_[h->owner].blocks_from[tid_]) = b;
- } else {
- VOLATILE(tl->blocks_to[h->owner]->next) = b;
+ int b_owner = h->owner;
+ TRACE("m1", "nbd_free: owner %llu", b_owner, 0);
+
+ // The assignment statements are volatile to prevent the compiler from reordering them.
+ VOLATILE_DEREF(b).next = NULL;
+ VOLATILE_DEREF(tl->blocks_to[b_owner]).next = b;
+
+ tl->blocks_to[b_owner] = b;
+ }
+}
+
+static inline void process_incoming_blocks (tl_t *tl) {
+ for (int p = 0; p < MAX_NUM_THREADS; ++p) {
+ block_t *b = tl->blocks_from[p];
+ if (EXPECT_FALSE(b == NULL)) continue; // the queue is completely empty
+
+ // Leave the last block on the queue. Removing the last block on the queue would create a
+ // race with the producer thread putting a new block on the queue.
+ for (block_t *next = b->next; next != NULL; b = next, next = b->next) {
+ // push <b> onto the appropriate free list
+#ifndef RECYCLE_PAGES
+ int b_scale = get_header(b)->scale;
+ b->next = tl->free_list[b_scale];
+ tl->free_list[b_scale] = b;
+#else //RECYCLE_PAGES
+ header_t *h = get_header(b);
+ b->next = h->free_list;
+ h->free_list = b;
+#endif//RECYCLE_PAGES
}
- tl->blocks_to[h->owner] = b;
+ tl->blocks_from[p] = b;
}
}
-// Allocate a block of memory at least size <n>. Blocks are binned in powers-of-two. Round up
-// <n> to the nearest power-of-two.
+static inline block_t *pop_free_list (tl_t *tl, int scale) {
+#ifndef RECYCLE_PAGES
+ block_t **free_list = &tl->free_list[scale];
+#else //RECYCLE_PAGES
+ size_class_t *sc = &tl->size_class[scale];
+ if (EXPECT_FALSE(sc->active_page == NULL))
+ return NULL;
+ block_t **free_list = &sc->active_page->free_list;
+#endif//RECYCLE_PAGES
+ block_t *b = *free_list;
+ if (EXPECT_FALSE(b == NULL))
+ return NULL;
+ ASSERT(get_header(b)->scale == scale);
+ *free_list = b->next;
+ return b;
+}
+
+// Allocate a block of memory at least size <n>. Blocks are binned in powers-of-two. Round up <n> to
+// the nearest power of two.
//
-// First check the current thread's private free list for an available block. If no blocks are on
-// the private free list, pull blocks off of the current thread's public free lists and put them
-// on the private free list. If we didn't find any blocks on the public free lists, allocate a new
-// region, break it up into blocks and put them on the private free list.
+// First check the current thread's free list for an available block. If there are no blocks on the
+// free list, pull items off of the current thread's incoming block queues and push them onto the
+// free list. If we didn't get an appropriate size block off of the block queues then allocate a new
+// page, break it up into blocks and push them onto the free list.
void *nbd_malloc (size_t n) {
-#ifdef USE_SYSTEM_MALLOC
- TRACE("m1", "nbd_malloc: request size %llu (scale %llu)", n, GET_SCALE(n));
- void *x = malloc(n);
- TRACE("m1", "nbd_malloc: returning %p", x, 0);
- return x;
-#endif
- if (EXPECT_FALSE(n == 0))
- return NULL;
- if (n < sizeof(block_t)) {
- n = sizeof(block_t);
- }
- int b_scale = GET_SCALE(n);
- assert(b_scale >= 2);
- assert(b_scale <= MAX_SCALE);
- TRACE("m1", "nbd_malloc: request size %llu (scale %llu)", n, b_scale);
+ // the scale is the log base 2 of <n>, rounded up
+ int b_scale = (sizeof(void *) * __CHAR_BIT__) - __builtin_clzl((n) - 1);
+ TRACE("m1", "nbd_malloc: size %llu (scale %llu)", n, b_scale);
+
+ if (EXPECT_FALSE(b_scale < MIN_SCALE)) { b_scale = MIN_SCALE; }
+ if (EXPECT_FALSE(b_scale > MAX_SCALE)) { return NULL; }
+
LOCALIZE_THREAD_LOCAL(tid_, int);
tl_t *tl = &tl_[tid_]; // thread-local data
- // If our private free list is empty, try to find blocks on our public free list. If that fails,
- // allocate a new region.
- if (EXPECT_FALSE(tl->free_blocks[b_scale] == NULL)) {
- for (int i = 0; i < MAX_NUM_THREADS; ++ i) {
- block_t *x = tl->blocks_from[i];
- if (x != NULL) {
- block_t *next = x->next;
- if (next != NULL) {
- do {
- header_t *h = get_header(x);
- x->next = tl->free_blocks[h->scale];
- tl->free_blocks[h->scale] = x;
- x = next;
- next = x->next;
- } while (next != NULL);
- tl->blocks_from[i] = x;
- }
- }
- }
- // allocate a new region
- if (tl->free_blocks[b_scale] == NULL) {
- char *region = get_new_region(b_scale);
- size_t b_size = 1 << b_scale;
- size_t region_size = (b_size < REGION_SIZE) ? REGION_SIZE : b_size;
- for (int i = region_size; i != 0; i -= b_size) {
- block_t *b = (block_t *)(region + i - b_size);
- b->next = tl->free_blocks[b_scale];
- tl->free_blocks[b_scale] = b;
- }
+ block_t *b = pop_free_list(tl, b_scale);
+ if (b != NULL) {
+ TRACE("m1", "nbd_malloc: returning block %p", b, 0);
+ return b;
+ }
+
+ // The free list is empty so process blocks freed from other threads and then check again.
+ process_incoming_blocks(tl);
+ b = pop_free_list(tl, b_scale);
+ if (b != NULL) {
+ TRACE("m1", "nbd_malloc: returning block %p", b, 0);
+ return b;
+ }
+
+#ifdef RECYCLE_PAGES
+ // The current active page is completely allocated. Make the oldest partially allocated page
+ // the new active page.
+ size_class_t *sc = &tl->size_class[b_scale];
+ if (sc->oldest_partial != NULL) {
+ sc->active_page = sc->oldest_partial;
+ sc->oldest_partial = sc->oldest_partial->next;
+ sc->oldest_partial->prev = NULL;
+ b = pop_free_list(tl, b_scale);
+ ASSERT(b != NULL);
+ TRACE("m1", "nbd_malloc: returning block %p", b, 0);
+ return b;
+ }
+ // There are no partially allocated pages so get a new page.
+
+#endif//RECYCLE_PAGES
+
+ // Get a new page.
+ char *page = get_new_region(b_scale);
+ b = (block_t *)page; // grab the first block on the page
+
+ // Break up the remainder of the page into blocks and put them on the free list. Start at the
+ // end of the page so that the free list ends up in increasing order, for ease of debugging.
+ if (b_scale < PAGE_SCALE) {
+ size_t block_size = (1 << b_scale);
+ block_t *head = NULL;
+ for (int offset = PAGE_SIZE - block_size; offset > 0; offset -= block_size) {
+ block_t *x = (block_t *)(page + offset);
+ x->next = head; head = x;
}
- assert(tl->free_blocks[b_scale] != NULL);
+#ifndef RECYCLE_PAGES
+ tl->free_list[b_scale] = head;
+#else //RECYCLE_PAGES
+ sc->active_page = get_header(page);
+ sc->active_page->free_list = head;
+#endif//RECYCLE_PAGES
}
- // Pull a block off of our private free list.
- block_t *b = tl->free_blocks[b_scale];
- TRACE("m1", "nbd_malloc: returning block %p (region %p) from private list", b, (size_t)b & ~MASK(REGION_SCALE));
- ASSERT(b);
- ASSERT(get_header(b)->scale == b_scale);
- tl->free_blocks[b_scale] = b->next;
+ TRACE("m1", "nbd_malloc: returning block %p from new region %p", b, (size_t)b & ~MASK(PAGE_SCALE));
return b;
}
+#else//USE_SYSTEM_MALLOC
+#include <stdlib.h>
+
+void mem_init (void) {
+ return;
+}
+
+void ndb_free (void *x) {
+ TRACE("m1", "nbd_free: %p", x, 0);
+#ifndef NDEBUG
+ memset(x, 0xcd, sizeof(void *)); // bear trap
+#endif//NDEBUG
+ free(x);
+ return;
+}
+
+void *nbd_malloc (size_t n) {
+ TRACE("m1", "nbd_malloc: request size %llu", n, 0);
+ void *x = malloc(n);
+ TRACE("m1", "nbd_malloc: returning %p", x, 0);
+ return x;
+}
+#endif//USE_SYSTEM_MALLOC
--- /dev/null
+#include <stdio.h>
+#include <errno.h>
+#include <unistd.h>
+#include <pthread.h>
+#include <sys/time.h>
+
+#include "common.h"
+#include "nstring.h"
+#include "runtime.h"
+#include "map.h"
+#include "rcu.h"
+#include "mem.h"
+#include "list.h"
+#include "skiplist.h"
+#include "hashtable.h"
+
+//#define TEST_STRING_KEYS
+
+static volatile int wait_;
+static volatile int stop_;
+static long num_threads_;
+static map_t *map_;
+static int get_range_;
+static int put_range_;
+static int num_keys_;
+static map_key_t *keys_ = NULL;
+static uint64_t times_[MAX_NUM_THREADS] = {};
+static int ops_[MAX_NUM_THREADS] = {};
+
+void *worker (void *arg) {
+ int tid = (int)(size_t)arg;
+ uint64_t s = nbd_rand_seed(tid);
+ int get_ops = 0, put_ops = 0, del_ops = 0;
+
+ // Wait for all the worker threads to be ready.
+ (void)SYNC_ADD(&wait_, -1);
+ do {} while (wait_);
+
+ uint64_t t1 = rdtsc();
+
+ while (!stop_) {
+ int r = nbd_next_rand(&s);
+ int x = r & ( (1 << 20) - 1 );
+ int i = nbd_next_rand(&s) & (num_keys_ - 1);
+ map_key_t key = keys_[i];
+ if (x < get_range_) {
+ map_val_t val = map_get(map_, key);
+#ifdef TEST_STRING_KEYS
+ ASSERT(val == DOES_NOT_EXIST || ns_cmp((nstring_t *)key, (nstring_t *)val) == 0);
+#else
+ ASSERT(val == DOES_NOT_EXIST || key == val);
+#endif
+ get_ops++;
+ } else if (x < put_range_) {
+ map_add(map_, key, key);
+ put_ops++;
+ } else {
+ map_remove(map_, key);
+ del_ops++;
+ }
+ rcu_update();
+ }
+
+ times_[tid] = rdtsc() - t1;
+ ops_[tid] = get_ops + put_ops + del_ops;
+
+ return NULL;
+}
+
+void run_test (void) {
+ wait_ = num_threads_ + 1;
+
+ // Quicky sanity check
+ int n = 100;
+ if (num_keys_ < n) { n = num_keys_; }
+ for (int i = 0; i < n; ++i) {
+ map_set(map_, keys_[i], keys_[i]);
+ for(int j = 0; j < i; ++j) {
+#ifdef TEST_STRING_KEYS
+ ASSERT(ns_cmp((nstring_t *)map_get(map_, keys_[i]), (nstring_t *)keys_[i]) == 0);
+#else
+ ASSERT(map_get(map_, keys_[i]) == keys_[i]);
+#endif
+ }
+ }
+
+ stop_ = 0;
+
+ pthread_t thread[MAX_NUM_THREADS];
+ for (int i = 0; i < num_threads_; ++i) {
+ int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i);
+ if (rc != 0) { perror("pthread_create"); exit(rc); }
+ }
+
+ do { /* nothing */ } while (wait_ != 1);
+
+ wait_ = 0;
+ sleep(2);
+ stop_ = 1;
+
+ for (int i = 0; i < num_threads_; ++i) {
+ pthread_join(thread[i], NULL);
+ }
+}
+
+int main (int argc, char **argv) {
+ char* program_name = argv[0];
+
+ if (argc > 2) {
+ fprintf(stderr, "Usage: %s num_threads\n", program_name);
+ return -1;
+ }
+
+ num_threads_ = 2;
+ if (argc == 2)
+ {
+ errno = 0;
+ num_threads_ = strtol(argv[1], NULL, 10);
+ if (errno) {
+ fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name);
+ return -1;
+ }
+ if (num_threads_ <= 0) {
+ fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name);
+ return -1;
+ }
+ if (num_threads_ > MAX_NUM_THREADS) {
+ fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS);
+ return -1;
+ }
+ }
+
+
+ int table_scale = 10;
+ int read_ratio = 95;
+ get_range_ = (read_ratio << 20) / 100;
+ put_range_ = (((1 << 20) - get_range_) >> 1) + get_range_;
+
+ static const map_impl_t *map_types[] = { &MAP_IMPL_HT };
+ for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
+#ifdef TEST_STRING_KEYS
+ map_ = map_alloc(map_types[i], &DATATYPE_NSTRING);
+#else
+ map_ = map_alloc(map_types[i], NULL);
+#endif
+
+ // Do some warmup
+ num_keys_ = 1 << table_scale;
+ keys_ = nbd_malloc(sizeof(map_key_t) * num_keys_);
+ for (int j = 0; j < num_keys_; ++j) {
+#ifdef TEST_STRING_KEYS
+ char tmp[64];
+ snprintf(tmp, sizeof(tmp), "%dabc%d", j, j*17+123);
+ int n = strlen(tmp);
+ keys_[j] = ns_alloc(n);
+ memcpy(keys_[j], tmp, n);
+#else
+ keys_[j] = j*17+123;
+#endif
+ }
+
+ struct timeval tv1, tv2;
+ gettimeofday(&tv1, NULL);
+
+ int num_trials = 1;
+ for (int i = 0; i < num_trials; ++i) {
+ run_test();
+ }
+
+ gettimeofday(&tv2, NULL);
+ int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
+ map_print(map_);
+ printf("Th:%ld Time:%dms\n\n", num_threads_, ms);
+ fflush(stdout);
+
+ map_free(map_);
+ }
+
+ return 0;
+}
projects / nbds / commitdiff