include ../benchmarks.mk
BENCH := hashmap
-NORMAL_TESTS := testcase1 testcase2
+NORMAL_TESTS := testcase1 testcase2 testcase3
WILDCARD_TESTS := $(patsubst %, %_wildcard, $(NORMAL_TESTS))
// 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_END();
e = firstPtr;
while (e != NULL) {
else
break;
}
- // Loading the next entry
- e = e->next.load(acquire);
+ // Loading the next entry, this can be relaxed because the
+ // synchronization has been established by the load of head
+ e = e->next.load(relaxed);
}
// Recheck under synch if key apparently not there or interference
e = newFirstPtr;
while (e != NULL) {
if (e->hash == hash && eq(key, e->key)) {
- res = e->value.load(seq_cst);
+ // Protected by lock, no need to be SC
+ res = e->value.load(relaxed);
seg->unlock(); // Critical region ends
return res;
}
while (e != NULL) {
if (e->hash == hash && eq(key, e->key)) {
// FIXME: This could be a relaxed (because locking synchronize
- // with the previous put())??
- oldValue = e->value.load(acquire);
+ // 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
return oldValue;
}
// FIXME: This could be a relaxed (because locking synchronize
- // with the previous put())??
- oldValue = e->value.load(acquire);
+ // 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();
SC_BEGIN();
Entry *firstPtr = first->load(wildcard(3)); // acquire
- SC_KEEP();
SC_END();
e = firstPtr;
break;
}
// Loading the next entry
- e = e->next.load(wildcard(5)); // acquire
+ e = e->next.load(wildcard(5)); // relaxed
}
// Recheck under synch if key apparently not there or interference
e = newFirstPtr;
while (e != NULL) {
if (e->hash == hash && eq(key, e->key)) {
- res = e->value.load(wildcard(7)); // seq_cst
+ res = e->value.load(wildcard(7)); // relaxed
seg->unlock(); // Critical region ends
return res;
}
if (e->hash == hash && eq(key, e->key)) {
// FIXME: This could be a relaxed (because locking synchronize
// with the previous put())??
- oldValue = e->value.load(wildcard(10)); // acquire
+ oldValue = e->value.load(wildcard(10)); // relaxed
e->value.store(value, wildcard(11)); // seq_cst
seg->unlock(); // Don't forget to unlock before return
return oldValue;
// FIXME: This could be a relaxed (because locking synchronize
// with the previous put())??
- oldValue = e->value.load(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();
--- /dev/null
+#include <iostream>
+#include <threads.h>
+#include "hashmap.h"
+
+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[]) {
+ 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);
+ thrd_join(t2);
+
+ return 0;
+}
+
+
--- /dev/null
+Result 0:
+wildcard 1 -> memory_order_relaxed
+wildcard 2 -> memory_order_relaxed
+wildcard 3 -> memory_order_acquire
+wildcard 4 -> memory_order_relaxed
+wildcard 6 -> memory_order_relaxed
+wildcard 7 -> memory_order_relaxed
+wildcard 9 -> memory_order_relaxed
+wildcard 13 -> memory_order_release
--- /dev/null
+Result 0:
+wildcard 1 -> memory_order_relaxed
+wildcard 2 -> memory_order_relaxed
+wildcard 3 -> memory_order_acquire
+wildcard 4 -> memory_order_seq_cst
+wildcard 6 -> memory_order_relaxed
+wildcard 7 -> memory_order_relaxed
+wildcard 9 -> memory_order_relaxed
+wildcard 10 -> memory_order_relaxed
+wildcard 11 -> memory_order_seq_cst
+wildcard 13 -> memory_order_release
--- /dev/null
+#include <threads.h>
+
+#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) & Key(1, 1, 6) are hashed to the same slot -> 5
+// Key(2, 4, 8) & Key(1, 3, 8) -> 9
+// Key(1, 4, 8) -> 10
+// Key(1, 3, 7) -> 8
+// Key(1, 2, 7) -> 7
+// Key(1, 2, 6) -> 6
+
+void threadA(void *arg) {
+ Key *k1 = new Key(3, 4, 5);
+ Key *k2 = new Key(1, 4, 3);
+ Key *k3 = new Key(1, 1, 6);
+ Value *v2 = new Value(10, 10, 10);
+ Value *r1 = table->put(k2, v2);
+ //printValue(r1);
+ Value *r2 = table->get(k3);
+ printf("k1 -> %d:\n", table->hashKey(k1) % table->capacity);
+ printf("k2 -> %d:\n", table->hashKey(k2) % table->capacity);
+ printf("k3 -> %d:\n", table->hashKey(k3) % table->capacity);
+ //printValue(r2);
+}
+
+void threadB(void *arg) {
+ Key *k1 = new Key(3, 4, 5);
+ Key *k2 = new Key(1, 4, 3);
+ Key *k3 = new Key(1, 1, 6);
+ Value *v3 = new Value(30, 40, 50);
+ Value *r3 = table->put(k3, v3);
+ //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, 4, 5);
+ Key *k2 = new Key(1, 4, 3);
+ Key *k3 = new Key(1, 1, 6);
+ //Key *k2 = new Key(1, 3, 3);
+ 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;
+}
+
+
projects / model-checker-benchmarks.git / commitdiff