From bd3e45d7445721324c680635cb96879668af5c7f Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Wed, 11 Feb 2015 16:40:36 -0800 Subject: [PATCH] fixed hashmap, add better makefile --- concurrent-hashmap/Makefile | 17 +++-- concurrent-hashmap/hashmap.h | 11 +-- concurrent-hashmap/hashmap_wildcard.h | 4 +- concurrent-hashmap/{main.cc => testcase1.cc} | 37 ++++++---- concurrent-hashmap/testcase2.cc | 72 ++++++++++++++++++++ 5 files changed, 112 insertions(+), 29 deletions(-) rename concurrent-hashmap/{main.cc => testcase1.cc} (51%) create mode 100644 concurrent-hashmap/testcase2.cc diff --git a/concurrent-hashmap/Makefile b/concurrent-hashmap/Makefile index d39e831..e386b4d 100644 --- a/concurrent-hashmap/Makefile +++ b/concurrent-hashmap/Makefile @@ -1,17 +1,20 @@ include ../benchmarks.mk -TESTS := table table_wildcard1 +NORMAL_TESTS := testcase1 testcase2 + +WILDCARD_TESTS := $(patsubst %, %_wildcard, $(NORMAL_TESTS)) + +TESTS := $(NORMAL_TESTS) $(WILDCARD_TESTS) all: $(TESTS) -table: main.cc hashmap.h - $(CXX) -o $@ $^ $(SPEC_OBJ) $(CXXFLAGS) -std=c++0x $(LDFLAGS) +$(WILDCARD_TESTS): CXXFLAGS += -DWILDCARD -table_wildcard1: main_wildcard1.cc hashmap_wildcard.h - $(CXX) -o $@ $^ $(SPEC_OBJ) $(CXXFLAGS) -std=c++0x $(LDFLAGS) +$(WILDCARD_TESTS): %_wildcard : %.cc hashmap_wildcard.h + $(CXX) -o $@ $< $(SPEC_OBJ) $(CXXFLAGS) $(LDFLAGS) -table_wildcard2: main_wildcard1.cc hashmap_wildcard.h - $(CXX) -o $@ $^ $(SPEC_OBJ) $(CXXFLAGS) -std=c++0x $(LDFLAGS) +$(NORMAL_TESTS): % : %.cc hashmap.h + $(CXX) -o $@ $< $(SPEC_OBJ) $(CXXFLAGS) $(LDFLAGS) clean: rm -f *.o *.d $(TESTS) diff --git a/concurrent-hashmap/hashmap.h b/concurrent-hashmap/hashmap.h index 936f284..8e6f196 100644 --- a/concurrent-hashmap/hashmap.h +++ b/concurrent-hashmap/hashmap.h @@ -14,6 +14,7 @@ #include #include +#include "common.h" #include "sc_annotation.h" #define relaxed memory_order_relaxed @@ -164,10 +165,10 @@ class HashMap { // lock, we ignore this operation for the SC analysis, and otherwise we // take it into consideration - SC_BEGIN(); + //SC_BEGIN(); Entry *firstPtr = first->load(acquire); - SC_KEEP(); - SC_END(); + //SC_KEEP(); + //SC_END(); e = firstPtr; while (e != NULL) { @@ -177,9 +178,9 @@ class HashMap { return res; else break; - // Loading the next entry - e = e->next.load(acquire); } + // Loading the next entry + e = e->next.load(acquire); } // Recheck under synch if key apparently not there or interference diff --git a/concurrent-hashmap/hashmap_wildcard.h b/concurrent-hashmap/hashmap_wildcard.h index 557a918..0713b78 100644 --- a/concurrent-hashmap/hashmap_wildcard.h +++ b/concurrent-hashmap/hashmap_wildcard.h @@ -178,9 +178,9 @@ class HashMap { return res; else break; - // Loading the next entry - e = e->next.load(wildcard(5)); // acquire } + // Loading the next entry + e = e->next.load(wildcard(5)); // acquire } // Recheck under synch if key apparently not there or interference diff --git a/concurrent-hashmap/main.cc b/concurrent-hashmap/testcase1.cc similarity index 51% rename from concurrent-hashmap/main.cc rename to concurrent-hashmap/testcase1.cc index fcb1186..939e250 100644 --- a/concurrent-hashmap/main.cc +++ b/concurrent-hashmap/testcase1.cc @@ -1,12 +1,13 @@ -#include #include + +#ifdef WILDCARD +#include "hashmap_wildcard.h" +#else #include "hashmap.h" +#endif HashMap *table; -Key *k1, *k2; -Value *r1, *r2, *r3, *r4, *v1, *v2; - void printKey(Key *key) { if (key) printf("pos = (%d, %d, %d)\n", key->x, key->y, key->z); @@ -21,24 +22,30 @@ void printValue(Value *value) { 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) { - k1 = new Key(1, 1, 1); - k2 = new Key(3, 4, 5); - v1 = new Value(10, 10, 10); - r1 = table->put(k1, v1); + 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); - r2 = table->get(k2); - printf("Thrd A:\n"); + Value *r2 = table->get(k2); + //printf("Thrd A:\n"); printValue(r2); } void threadB(void *arg) { - k1 = new Key(1, 1, 1); - k2 = new Key(3, 4, 5); - v2 = new Value(30, 40, 50); - r3 = table->put(k2, v2); + 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); - r4 = table->get(k1); + Value *r4 = table->get(k1); printf("Thrd B:\n"); printValue(r4); } diff --git a/concurrent-hashmap/testcase2.cc b/concurrent-hashmap/testcase2.cc new file mode 100644 index 0000000..17f79d8 --- /dev/null +++ b/concurrent-hashmap/testcase2.cc @@ -0,0 +1,72 @@ +#include + +#ifdef WILDCARD +#include "hashmap_wildcard.h" +#else +#include "hashmap.h" +#endif + +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); +} + +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); +} + +int user_main(int argc, char *argv[]) { + + Key *k1 = new Key(3, 2, 6); + Key *k2 = new Key(1, 1, 1); + Value *v1 = new Value(111, 111, 111); + Value *v2 = new Value(222, 222, 222); + thrd_t t1, t2; + table = new HashMap; + table->put(k1, v1); + table->put(k2, v2); + + thrd_create(&t1, threadA, NULL); + thrd_create(&t2, threadB, NULL); + thrd_join(t1); + thrd_join(t2); + + return 0; +} + + -- 2.34.1