From 4a073a8a406ebcb1d64fea7bcd78a78b8a952c5c Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com> Date: Thu, 12 Mar 2020 00:53:55 +0100 Subject: Cleanup --- benchmark.cpp | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---- c_hashmap.h | 35 +++++++++++++++++----------------- 2 files changed, 75 insertions(+), 21 deletions(-) diff --git a/benchmark.cpp b/benchmark.cpp index d88a38fa..3f11703d 100644 --- a/benchmark.cpp +++ b/benchmark.cpp @@ -12,23 +12,61 @@ c_declare_Vector_string(s); int main() { c_Hashmap_ii map = c_hashmap_initializer; + int K = 300000; + printf("BEGIN\n"); + //c_hashmap_ii_reserve(&map, 50); + /* + c_hashmap_ii_setMaxLoadFactor(&map, 0.8); + for (size_t i = 0; i < K; ++i) { + c_hashmap_ii_put(&map, i*i, i); + } + for (size_t i = 0; i < K/2; ++i) { + c_hashmap_ii_erase(&map, i*i); + } + c_foreach (i, c_hashmap_ii, map) c_hashmap_ii_bucket(map, i.item->key); + for (size_t i = 0; i < K/2; ++i) { + c_hashmap_ii_put(&map, i, i*i); + } + c_foreach (i, c_hashmap_ii, map) c_hashmap_ii_bucket(map, i.item->key); + */ + uint64_t checksum = 0; clock_t before, difference; size_t fib1, fib2, fibx; const size_t N = 10000000; - printf("Starting\n"); + printf("Starting %llu\n", N); //c_hashmap_ii_reserve(&map, N * 1.25); before = clock(); - fib1 = 0, fib2 = 1; + fib1 = 0, fib2 = 1; checksum = 0; for (size_t i = 0; i < N; ++i) { checksum += ++c_hashmap_ii_put(&map, FIBONACCI_NEXT, i)->value; } difference = clock() - before; - printf("Check: %llu, size: %llu, time: %f\n", checksum, c_hashmap_size(map), 1.0 * difference / CLOCKS_PER_SEC); + printf("c_Hashmap_ii added: size: %llu, time: %f, check: %llu\n", c_hashmap_size(map), 1.0 * difference / CLOCKS_PER_SEC, checksum); + before = clock(); + fib1 = 0, fib2 = 1; + for (size_t i = 0; i < N*2/3; ++i) { + c_hashmap_ii_erase(&map, FIBONACCI_NEXT); + } + difference = clock() - before; + printf("c_Hashmap_ii removed: size: %llu, time: %f, check: %llu\n", c_hashmap_size(map), 1.0 * difference / CLOCKS_PER_SEC, checksum); + + before = clock(); + fib1 = 0, fib2 = 1; checksum = 0; + for (size_t i = 0; i < N; ++i) { + checksum += ++c_hashmap_ii_put(&map, i, i)->value; + } + difference = clock() - before; + printf("c_Hashmap_ii re-add: size: %llu, time: %f, check: %llu\n", c_hashmap_size(map), 1.0 * difference / CLOCKS_PER_SEC, checksum); + + size_t sum = 0; + c_foreach (i, c_hashmap_ii, map) sum += c_hashmap_ii_get(map, i.item->key)->value; + c_hashmap_ii_destroy(&map); + std::unordered_map map2; //map2.reserve(N); before = clock(); @@ -36,6 +74,21 @@ int main() for (size_t i = 0; i < N; ++i) checksum += ++(map2[FIBONACCI_NEXT] = i); difference = clock() - before; - printf("Check: %llu, size: %llu, time: %f\n", checksum, map2.size(), 1.0 * difference / CLOCKS_PER_SEC); + printf("std::unordered_map added: size: %llu, time: %f, check: %llu\n", map2.size(), 1.0 * difference / CLOCKS_PER_SEC, checksum); + + before = clock(); + fib1 = 0, fib2 = 1; checksum = 0; + for (size_t i = 0; i < N*2/3; ++i) + map2.erase(FIBONACCI_NEXT); + difference = clock() - before; + printf("std::unordered_map erased: size: %llu, time: %f\n", map2.size(), 1.0 * difference / CLOCKS_PER_SEC); + + before = clock(); + fib1 = 0, fib2 = 1; checksum = 0; + for (size_t i = 0; i < N; ++i) + checksum += ++(map2[i] = i); + difference = clock() - before; + printf("std::unordered_map re-add: size: %llu, time: %f, check: %llu\n", map2.size(), 1.0 * difference / CLOCKS_PER_SEC, checksum); + map2.clear(); } \ No newline at end of file diff --git a/c_hashmap.h b/c_hashmap.h index d0a0c8c7..1f81ff70 100644 --- a/c_hashmap.h +++ b/c_hashmap.h @@ -26,8 +26,8 @@ #include "c_vector.h" #define c_hashmap_initializer {c_vector_initializer, 0, 0.8f} -#define c_hashmap_size(cm) ((size_t) (cm)._size) -#define c_hashmap_buckets(cm) c_vector_capacity((cm)._vec) +#define c_hashmap_size(map) ((size_t) (map)._size) +#define c_hashmap_buckets(map) c_vector_capacity((map)._vec) // c_HashmapEntry: @@ -105,9 +105,9 @@ static inline void c_hashmap_##tag##_destroy(c_Hashmap_##tag* self) { \ static inline size_t c_hashmap_##tag##_reserve(c_Hashmap_##tag* self, size_t size); /* predeclared */ \ \ static inline void c_hashmap_##tag##_clear(c_Hashmap_##tag* self) { \ - c_Hashmap_##tag cm = c_hashmap_initializer; \ + c_Hashmap_##tag map = c_hashmap_initializer; \ c_hashmap_##tag##_destroy(self); \ - *self = cm; \ + *self = map; \ } \ \ static inline void c_hashmap_##tag##_swap(c_Hashmap_##tag* a, c_Hashmap_##tag* b) { \ @@ -121,20 +121,20 @@ static inline void c_hashmap_##tag##_setMaxLoadFactor(c_Hashmap_##tag* self, flo c_hashmap_##tag##_reserve(self, 1 + (size_t) (c_hashmap_size(*self) / fac)); \ } \ \ -static inline size_t c_hashmap_##tag##_bucket(c_Hashmap_##tag cm, KeyRaw rawKey) { \ - size_t cap = c_vector_capacity(cm._vec); \ +static inline size_t c_hashmap_##tag##_bucket(c_Hashmap_##tag map, KeyRaw rawKey) { \ + size_t cap = c_vector_capacity(map._vec); \ size_t idx = c_hashmap_reduce(keyHashRaw(&rawKey, sizeof(Key)), cap); \ size_t first = idx, erased_idx = cap; \ FIBONACCI_DECL; \ do { \ - switch (cm._vec.data[idx].state) { \ + switch (map._vec.data[idx].state) { \ case c_HashmapEntry_VACANT: \ return erased_idx != cap ? erased_idx : idx; \ case c_HashmapEntry_INUSE: \ - if (keyCompareRaw(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ + if (keyCompareRaw(&map._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ break; \ if (erased_idx != cap) { \ - c_defs_swap(c_HashmapEntry_##tag, cm._vec.data[erased_idx], cm._vec.data[idx]); \ + c_defs_swap(c_HashmapEntry_##tag, map._vec.data[erased_idx], map._vec.data[idx]); \ return erased_idx; \ } \ return idx; \ @@ -147,16 +147,16 @@ static inline size_t c_hashmap_##tag##_bucket(c_Hashmap_##tag cm, KeyRaw rawKey) } while (1); \ } \ \ -static inline c_HashmapEntry_##tag* c_hashmap_##tag##_get(c_Hashmap_##tag cm, KeyRaw rawKey) { \ - if (c_hashmap_size(cm) == 0) return NULL; \ - size_t idx = c_hashmap_##tag##_bucket(cm, rawKey); \ - return cm._vec.data[idx].state == c_HashmapEntry_INUSE ? &cm._vec.data[idx] : NULL; \ +static inline c_HashmapEntry_##tag* c_hashmap_##tag##_get(c_Hashmap_##tag map, KeyRaw rawKey) { \ + if (c_hashmap_size(map) == 0) return NULL; \ + size_t idx = c_hashmap_##tag##_bucket(map, rawKey); \ + return map._vec.data[idx].state == c_HashmapEntry_INUSE ? &map._vec.data[idx] : NULL; \ } \ \ static inline c_HashmapEntry_##tag* c_hashmap_##tag##_put(c_Hashmap_##tag* self, KeyRaw rawKey, Value value) { \ size_t cap = c_vector_capacity(self->_vec); \ if (c_hashmap_size(*self) >= cap * self->maxLoadFactor) \ - cap = c_hashmap_##tag##_reserve(self, (size_t) (cap * 1.8)); \ + cap = c_hashmap_##tag##_reserve(self, (size_t) 7 + (cap * 1.8)); \ size_t idx = c_hashmap_##tag##_bucket(*self, rawKey); \ c_HashmapEntry_##tag* e = &self->_vec.data[idx]; \ e->value = value; \ @@ -170,7 +170,7 @@ static inline c_HashmapEntry_##tag* c_hashmap_##tag##_put(c_Hashmap_##tag* self, } \ \ static inline size_t c_hashmap_##tag##_reserve(c_Hashmap_##tag* self, size_t size) { \ - size_t oldcap = c_vector_capacity(self->_vec), newcap = (oldcap ? 1 : 7) + (size / 2) * 2; \ + size_t oldcap = c_vector_capacity(self->_vec), newcap = 1 + (size / 2) * 2; \ if (oldcap >= newcap) return oldcap; \ c_Vector_map_##tag vec = c_vector_initializer; \ c_vector_map_##tag##_swap(&self->_vec, &vec); \ @@ -184,8 +184,9 @@ static inline size_t c_hashmap_##tag##_reserve(c_Hashmap_##tag* self, size_t siz } \ \ static inline bool c_hashmap_##tag##_erase(c_Hashmap_##tag* self, KeyRaw rawKey) { \ - c_HashmapEntry_##tag* e = c_hashmap_##tag##_get(*self, rawKey); \ - if (e) { \ + size_t idx = c_hashmap_##tag##_bucket(*self, rawKey); \ + c_HashmapEntry_##tag* e = &self->_vec.data[idx]; \ + if (e->state == c_HashmapEntry_INUSE) { \ c_hashmapentry_##tag##_destroy(e); \ e->state = c_HashmapEntry_ERASED; \ --self->_size; \ -- cgit v1.2.3