From: Peizhao Ou Date: Tue, 17 Nov 2015 04:35:57 +0000 (-0800) Subject: edits X-Git-Url: http://demsky.eecs.uci.edu/git/?p=cdsspec-compiler.git;a=commitdiff_plain;h=9998905e5af5313d3ef3f01fe8de492b456b1b0a edits --- diff --git a/benchmark/concurrent-hashmap/Makefile b/benchmark/concurrent-hashmap/Makefile index d379912..8fa9693 100644 --- a/benchmark/concurrent-hashmap/Makefile +++ b/benchmark/concurrent-hashmap/Makefile @@ -1,7 +1,7 @@ include ../benchmarks.mk BENCH := hashmap -TESTS := testcase1 testcase2 +TESTS := main all: $(TESTS) diff --git a/benchmark/concurrent-hashmap/hashmap.h b/benchmark/concurrent-hashmap/hashmap.h index 0d24925..e813d23 100644 --- a/benchmark/concurrent-hashmap/hashmap.h +++ b/benchmark/concurrent-hashmap/hashmap.h @@ -4,18 +4,9 @@ #include #include #include "stdio.h" -//#include -#ifdef STANDALONE -#include -#define MODEL_ASSERT assert -#else -#include -#endif #include #include - #include "common.h" -#include "sc_annotation.h" #define relaxed memory_order_relaxed #define release memory_order_release @@ -26,63 +17,19 @@ using namespace std; /** - For the sake of simplicity, we do not use template but some toy structs to - represent the Key and Value. + For the sake of simplicity, we map Integer -> Integer. */ -struct Key { - // Probably represent the coordinate (x, y, z) - int x; - int y; - int z; - - int hashCode() { - return x + 31 * y + 31 * 31 * z; - } - - bool equals(Key *other) { - if (!other) - return false; - return x == other->x && y == other->y && z == other->z; - } - - Key(int x, int y, int z) : - x(x), - y(y), - z(z) - { - - } -}; - -struct Value { - // Probably represent the speed vector (vX, vY, vZ) - int vX; - int vY; - int vZ; - - Value(int vX, int vY, int vZ) : - vX(vX), - vY(vY), - vZ(vZ) - { - } - bool equals(Value *other) { - if (!other) - return false; - return vX == other->vX && vY == other->vY && vZ == other->vZ; - } -}; class Entry { public: - Key *key; - atomic value; + int key; + atomic_int value; int hash; atomic next; - Entry(int h, Key *k, Value *v, Entry *n) { + Entry(int h, int k, int v, Entry *n) { this->hash = h; this->key = k; this->value.store(v, relaxed); @@ -108,6 +55,10 @@ class Segment { } }; +/** + @Begin + @Class_begin + @End*/ class HashMap { public: atomic *table; @@ -115,7 +66,7 @@ class HashMap { int capacity; int size; - static const int CONCURRENCY_LEVEL = 16; + static const int CONCURRENCY_LEVEL = 4; static const int SEGMENT_MASK = CONCURRENCY_LEVEL - 1; @@ -137,19 +88,12 @@ class HashMap { } } - int hashKey(Key *x) { - int h = x->hashCode(); - // Use logical right shift - unsigned int tmp = (unsigned int) h; - return ((h << 7) - h + (tmp >> 9) + (tmp >> 17)); - } - - bool eq(Key *x, Key *y) { - return x == y || x->equals(y); + int hashKey(int key) { + return key; } - Value* get(Key *key) { - MODEL_ASSERT (key); + int get(int key) { + ASSERT (key); int hash = hashKey(key); // Try first without locking... @@ -157,7 +101,7 @@ class HashMap { int index = hash & (capacity - 1); atomic *first = &tab[index]; Entry *e; - Value *res = NULL; + int res = 0; // Should be a load acquire // This load action here makes it problematic for the SC analysis, what @@ -165,15 +109,13 @@ class HashMap { // lock, we ignore this operation for the SC analysis, and otherwise we // take it into consideration - SC_BEGIN(); Entry *firstPtr = first->load(acquire); - SC_END(); e = firstPtr; while (e != NULL) { - if (e->hash == hash && eq(key, e->key)) { + if (key, e->key) { res = e->value.load(seq_cst); - if (res != NULL) + if (res != 0) return res; else break; @@ -193,7 +135,7 @@ class HashMap { if (e != NULL || firstPtr != newFirstPtr) { e = newFirstPtr; while (e != NULL) { - if (e->hash == hash && eq(key, e->key)) { + if (key == e->key) { // Protected by lock, no need to be SC res = e->value.load(relaxed); seg->unlock(); // Critical region ends @@ -204,13 +146,11 @@ class HashMap { } } seg->unlock(); // Critical region ends - return NULL; + return 0; } - Value* put(Key *key, Value *value) { - // Don't allow NULL key or value - MODEL_ASSERT (key && value); - + int put(int key, int value) { + ASSERT (key && value); int hash = hashKey(key); Segment *seg = segments[hash & SEGMENT_MASK]; atomic *tab; @@ -221,15 +161,15 @@ class HashMap { atomic *first = &tab[index]; Entry *e; - Value *oldValue = NULL; + int oldValue = 0; // The written of the entry is synchronized by locking Entry *firstPtr = first->load(relaxed); e = firstPtr; while (e != NULL) { - if (e->hash == hash && eq(key, e->key)) { - // FIXME: This could be a relaxed (because locking synchronize - // with the previous put())?? no need to be acquire + if (key == e->key) { + // This could be a relaxed (because locking synchronize + // with the previous put()), no need to be acquire oldValue = e->value.load(relaxed); e->value.store(value, seq_cst); seg->unlock(); // Don't forget to unlock before return @@ -244,64 +184,7 @@ class HashMap { // Publish the newEntry to others first->store(newEntry, release); seg->unlock(); // Critical region ends - return NULL; - } - - Value* remove(Key *key, Value *value) { - MODEL_ASSERT (key); - int hash = hashKey(key); - Segment *seg = segments[hash & SEGMENT_MASK]; - atomic *tab; - - seg->lock(); // Critical region begins - tab = table; - int index = hash & (capacity - 1); - - atomic *first = &tab[index]; - Entry *e; - Value *oldValue = NULL; - - // The written of the entry is synchronized by locking - Entry *firstPtr = first->load(relaxed); - e = firstPtr; - - while (true) { - if (e != NULL) { - seg->unlock(); // Don't forget to unlock - return NULL; - } - if (e->hash == hash && eq(key, e->key)) - break; - // Synchronized by locking - e = e->next.load(relaxed); - } - - // FIXME: This could be a relaxed (because locking synchronize - // with the previous put())?? No need to be acquire - oldValue = e->value.load(relaxed); - // If the value parameter is NULL, we will remove the entry anyway - if (value != NULL && value->equals(oldValue)) { - seg->unlock(); - return NULL; - } - - // Force the get() to grab the lock and retry - e->value.store(NULL, relaxed); - - // The strategy to remove the entry is to keep the entries after the - // removed one and copy the ones before it - Entry *head = e->next.load(relaxed); - Entry *p; - p = first->load(relaxed); - while (p != e) { - head = new Entry(p->hash, p->key, p->value.load(relaxed), head); - p = p->next.load(relaxed); - } - - // Publish the new head to readers - first->store(head, release); - seg->unlock(); // Critical region ends - return oldValue; + return 0; } }; diff --git a/benchmark/concurrent-hashmap/main.cc b/benchmark/concurrent-hashmap/main.cc index 084230e..4190075 100644 --- a/benchmark/concurrent-hashmap/main.cc +++ b/benchmark/concurrent-hashmap/main.cc @@ -4,66 +4,25 @@ HashMap *table; - -void printKey(Key *key) { - if (key) - printf("pos = (%d, %d, %d)\n", key->x, key->y, key->z); - else - printf("pos = NULL\n"); -} - -void printValue(Value *value) { - if (value) - printf("velocity = (%d, %d, %d)\n", value->vX, value->vY, value->vZ); - else - printf("velocity = NULL\n"); -} - -// Key(3, 2, 6) & Key(1, 3, 3) are hashed to the same slot -> 4 -// Key(1, 1, 1) & Key(3, 2, 2) are hashed to the same slot -> 0 -// Key(2, 4, 1) & Key(3, 4, 2) are hashed to the same slot -> 3 -// Key(3, 4, 5) & Key(1, 4, 3) are hashed to the same slot -> 5 - - void threadA(void *arg) { - Key *k1 = new Key(3, 2, 6); - Key *k2 = new Key(1, 1, 1); - Value *v1 = new Value(10, 10, 10); - Value *r1 = table->put(k1, v1); - //printValue(r1); - Value *r2 = table->get(k2); - //printf("Thrd A:\n"); - printValue(r2); + table->put(1, 1); + printf("Thrd A: Put %d -> %d\n", 1, 1); + int r1 = table->get(2); + printf("Thrd A: Get %d\n", r1); } void threadB(void *arg) { - Key *k1 = new Key(3, 2, 6); - Key *k2 = new Key(1, 1, 1); - Value *v2 = new Value(30, 40, 50); - Value *r3 = table->put(k2, v2); - //printValue(r3); - Value *r4 = table->get(k1); - printf("Thrd B:\n"); - printValue(r4); + table->put(2, 2); + printf("Thrd B: Put %d -> %d\n", 2, 2); + int r2 = table->get(1); + printf("Thrd B: Get %d\n", r2); } int user_main(int argc, char *argv[]) { thrd_t t1, t2; - Key *k1 = new Key(1, 3, 3); - Key *k1_prime = new Key(3, 2, 6); - Key *k2 = new Key(3, 2, 2); - Key *k2_prime = new Key(1, 1, 1); - Value *v1 = new Value(111, 111, 111); - Value *v2 = new Value(222, 222, 222); - table = new HashMap; - printf("Key1: %d\n", table->hashKey(k1) % table->capacity); - printf("Key1': %d\n", table->hashKey(k1_prime) % table->capacity); - printf("Key2: %d\n", table->hashKey(k2) % table->capacity); - printf("Key2': %d\n", table->hashKey(k2_prime) % table->capacity); - thrd_create(&t1, threadA, NULL); thrd_create(&t2, threadB, NULL); thrd_join(t1);