edits
authorPeizhao Ou <peizhaoo@uci.edu>
Tue, 17 Nov 2015 04:35:57 +0000 (20:35 -0800)
committerPeizhao Ou <peizhaoo@uci.edu>
Tue, 17 Nov 2015 04:35:57 +0000 (20:35 -0800)
benchmark/concurrent-hashmap/Makefile
benchmark/concurrent-hashmap/hashmap.h
benchmark/concurrent-hashmap/main.cc

index d379912..8fa9693 100644 (file)
@@ -1,7 +1,7 @@
 include ../benchmarks.mk
 
 BENCH := hashmap
-TESTS := testcase1 testcase2 
+TESTS := main 
 
 all: $(TESTS)
 
index 0d24925..e813d23 100644 (file)
@@ -4,18 +4,9 @@
 #include <iostream>
 #include <atomic>
 #include "stdio.h" 
-//#include <common.h>
-#ifdef STANDALONE
-#include <assert.h>
-#define MODEL_ASSERT assert 
-#else
-#include <model-assert.h>
-#endif
 #include <stdlib.h>
 #include <mutex>
-
 #include "common.h"
-#include "sc_annotation.h"
 
 #define relaxed memory_order_relaxed
 #define release memory_order_release
 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*> value;
+       int key;
+       atomic_int value;
        int hash;
        atomic<Entry*> 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<Entry*> *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<Entry*> *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<Entry*> *tab;
@@ -221,15 +161,15 @@ class HashMap {
 
                atomic<Entry*> *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<Entry*> *tab;
-
-               seg->lock(); // Critical region begins
-               tab = table;
-               int index = hash & (capacity - 1);
-
-               atomic<Entry*> *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;
        }
 };
 
index 084230e..4190075 100644 (file)
@@ -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);