From 03f61e592c984f52536097af3684568fc171d722 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 26 Aug 2020 21:49:26 +0200 Subject: Updated benchmark. Some improvements in cmap iterator. cmap_try_emplace() API change. --- README.md | 2 +- examples/benchmark.c | 89 +++++++++++++++++++++++++++++++++++----------------- examples/words.c | 14 +++------ stc/cmap.h | 20 ++++++------ 4 files changed, 78 insertions(+), 47 deletions(-) diff --git a/README.md b/README.md index 00151960..2cafd2c5 100644 --- a/README.md +++ b/README.md @@ -142,7 +142,7 @@ Finally, cmap mimics c++17 unordered_map::try_emplace() and avoids cstr memory l ``` declare_cmap_str(ss, cstr_t, cstr_destroy); // cstr_t -> cstr_t ... -cmap_try_emplace(&map, ss, "already here", cstr_make("won't be called then")); // special: tag 'ss' is a parameter here. +cmap_try_emplace(ss, &map, "already here", cstr_make("won't be called then")); // note: tag 'ss' is a parameter here. ``` You may want to look at **examples/advanced.c**, it demonstrates how to use a custom struct as a hash map key, using the optional parameters to declare_cmap(). diff --git a/examples/benchmark.c b/examples/benchmark.c index 753f39b3..3ff193bc 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -11,6 +11,8 @@ #include "others/bytell_hash_map.hpp" #include "others/robin_hood.hpp" #include "others/hopscotch_map.h" +#include "others/sparsepp/spp.h" +template inline void destroy_me(C& c) { C().swap(c); } #endif // Visual Studio: compile with -TP to force C++: cl -TP -EHsc -O2 benchmark.c @@ -35,59 +37,90 @@ crandom_eng64_t rng; #define CMAP_SETUP(tt, Key, Value) cmap_##tt map = cmap_init \ ; cmap_##tt##_set_load_factors(&map, max_load_factor, 0.0) #define CMAP_PUT(tt, key, val) cmap_##tt##_put(&map, key, val)->value +#define CMAP_INSERT(tt, key, val) cmap_##tt##_insert(&map, key, val) +#define CMAP_EMPLACE(tt, key, val) cmap_try_emplace(tt, &map, key, val) #define CMAP_ERASE(tt, key) cmap_##tt##_erase(&map, key) #define CMAP_FIND(tt, key) (cmap_##tt##_find(map, key) != NULL) #define CMAP_SIZE(tt) cmap_size(map) -#define CMAP_BUCKETS(tt) (map).bucket_count -#define CMAP_CLEAR(tt) cmap_##tt##_destroy(&map) +#define CMAP_BUCKETS(tt) cmap_bucket_count(map) +#define CMAP_CLEAR(tt) cmap_##tt##_clear(&map) +#define CMAP_DTOR(tt) cmap_##tt##_destroy(&map) #define KMAP_SETUP(tt, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret #define KMAP_PUT(tt, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) +#define KMAP_INSERT(tt, key, val) (ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val) : val) #define KMAP_ERASE(tt, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) #define KMAP_FIND(tt, key) (kh_get(ii, map, key) != kh_end(map)) #define KMAP_SIZE(tt) kh_size(map) #define KMAP_BUCKETS(tt) kh_n_buckets(map) -#define KMAP_CLEAR(tt) kh_destroy(ii, map) +#define KMAP_CLEAR(tt) kh_clear(ii, map) +#define KMAP_DTOR(tt) kh_destroy(ii, map) #define UMAP_SETUP(tt, Key, Value) std::unordered_map map; map.max_load_factor(max_load_factor) #define UMAP_PUT(tt, key, val) (map[key] = val) +#define UMAP_INSERT(tt, key, val) map.insert(std::make_pair(key, val)) +#define UMAP_EMPLACE(tt, key, val) map.emplace(key, val) #define UMAP_FIND(tt, key) (map.find(key) != map.end()) #define UMAP_ERASE(tt, key) map.erase(key) #define UMAP_SIZE(tt) map.size() #define UMAP_BUCKETS(tt) map.bucket_count() #define UMAP_CLEAR(tt) map.clear() +#define UMAP_DTOR(tt) destroy_me(map) #define BMAP_SETUP(tt, Key, Value) ska::bytell_hash_map map; map.max_load_factor(max_load_factor) -#define BMAP_PUT(tt, key, val) (map[key] = val) -#define BMAP_FIND(tt, key) (map.find(key) != map.end()) -#define BMAP_ERASE(tt, key) map.erase(key) -#define BMAP_SIZE(tt) map.size() -#define BMAP_BUCKETS(tt) map.bucket_count() -#define BMAP_CLEAR(tt) map.clear() +#define BMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) +#define BMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) +#define BMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) +#define BMAP_FIND(tt, key) UMAP_FIND(tt, key) +#define BMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define BMAP_SIZE(tt) UMAP_SIZE(tt) +#define BMAP_BUCKETS(tt) UMAP_BUCKETS(tt) +#define BMAP_CLEAR(tt) UMAP_CLEAR(tt) +#define BMAP_DTOR(tt) UMAP_DTOR(tt) #define FMAP_SETUP(tt, Key, Value) ska::flat_hash_map map; map.max_load_factor(max_load_factor) -#define FMAP_PUT(tt, key, val) (map[key] = val) -#define FMAP_FIND(tt, key) (map.find(key) != map.end()) -#define FMAP_ERASE(tt, key) map.erase(key) -#define FMAP_SIZE(tt) map.size() -#define FMAP_BUCKETS(tt) map.bucket_count() -#define FMAP_CLEAR(tt) map.clear() +#define FMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) +#define FMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) +#define FMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) +#define FMAP_FIND(tt, key) UMAP_FIND(tt, key) +#define FMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define FMAP_SIZE(tt) UMAP_SIZE(tt) +#define FMAP_BUCKETS(tt) UMAP_BUCKETS(tt) +#define FMAP_CLEAR(tt) UMAP_CLEAR(tt) +#define FMAP_DTOR(tt) UMAP_DTOR(tt) #define HMAP_SETUP(tt, Key, Value) tsl::hopscotch_map map; map.max_load_factor(max_load_factor) -#define HMAP_PUT(tt, key, val) (map[key] = val) -#define HMAP_FIND(tt, key) (map.find(key) != map.end()) -#define HMAP_ERASE(tt, key) map.erase(key) -#define HMAP_SIZE(tt) map.size() -#define HMAP_BUCKETS(tt) map.bucket_count() -#define HMAP_CLEAR(tt) map.clear() +#define HMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) +#define HMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) +#define HMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) +#define HMAP_FIND(tt, key) UMAP_FIND(tt, key) +#define HMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define HMAP_SIZE(tt) UMAP_SIZE(tt) +#define HMAP_BUCKETS(tt) UMAP_BUCKETS(tt) +#define HMAP_CLEAR(tt) UMAP_CLEAR(tt) +#define HMAP_DTOR(tt) UMAP_DTOR(tt) #define RMAP_SETUP(tt, Key, Value) robin_hood::unordered_map map -#define RMAP_PUT(tt, key, val) (map[key] = val) -#define RMAP_FIND(tt, key) (map.find(key) != map.end()) -#define RMAP_ERASE(tt, key) map.erase(key) -#define RMAP_SIZE(tt) map.size() +#define RMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) +#define RMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) +#define RMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) +#define RMAP_FIND(tt, key) UMAP_FIND(tt, key) +#define RMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define RMAP_SIZE(tt) UMAP_SIZE(tt) #define RMAP_BUCKETS(tt) map.mask() -#define RMAP_CLEAR(tt) map.clear() +#define RMAP_CLEAR(tt) UMAP_CLEAR(tt) +#define RMAP_DTOR(tt) UMAP_DTOR(tt) + +#define SMAP_SETUP(tt, Key, Value) spp::sparse_hash_map map; map.max_load_factor(max_load_factor) +#define SMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) +#define SMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) +#define SMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) +#define SMAP_FIND(tt, key) UMAP_FIND(tt, key) +#define SMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define SMAP_SIZE(tt) UMAP_SIZE(tt) +#define SMAP_BUCKETS(tt) UMAP_BUCKETS(tt) +#define SMAP_CLEAR(tt) UMAP_CLEAR(tt) +#define SMAP_DTOR(tt) UMAP_DTOR(tt) const size_t N1 = 10000000 * 5; const size_t N2 = 10000000 * 5; @@ -145,9 +178,9 @@ int rr = RR; } #ifndef __cplusplus -#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) // MAP_TEST##n(KMAP, ii) +#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) #else -#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) MAP_TEST##n(UMAP, ii) \ +#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) MAP_TEST##n(UMAP, ii) MAP_TEST##n(SMAP, ii) \ MAP_TEST##n(BMAP, ii) MAP_TEST##n(FMAP, ii) MAP_TEST##n(RMAP, ii) MAP_TEST##n(HMAP, ii) #endif diff --git a/examples/words.c b/examples/words.c index f6182cbd..a10811c1 100644 --- a/examples/words.c +++ b/examples/words.c @@ -9,7 +9,7 @@ declare_clist_str(); declare_cmap_str(si, int); typedef const char* input_t; - + int main1() { clist_str lwords = clist_init; @@ -17,11 +17,7 @@ int main1() "this", "sentence", "is", "not", "a", "sentence", "this", "sentence", "is", "a", "hoax" )); - c_foreach (w, clist_str, lwords) { - printf("%s\n", w.item->value); - } - - + cvec_str words = cvec_init; c_push(&words, cvec_str, c_items( "this", "sentence", "is", "not", "a", "sentence", @@ -32,7 +28,7 @@ int main1() c_foreach (w, cvec_str, words) { ++cmap_si_insert(&word_map, w.item->str, 0)->value; } - + c_foreach (pair, cmap_si, word_map) { printf("%d occurrences of word '%s'\n", pair.item->value, @@ -56,12 +52,12 @@ int main2() "this", "sentence", "is", "not", "a", "sentence", "this", "sentence", "is", "a", "hoax" }; - + std::unordered_map word_map; for (const auto &w : words) { ++word_map[w]; } - + for (const auto &pair : word_map) { std::cout << pair.second << " occurrences of word '" diff --git a/stc/cmap.h b/stc/cmap.h index 211fea1a..6be45863 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -55,9 +55,11 @@ int main(void) { #define cmap_init {NULL, NULL, 0, 0, 0.85f, 0.15f} #define cmap_size(m) ((size_t) (m).size) +#define cmap_bucket_count(m) ((size_t) (m).bucket_count) #define cset_init cmap_init #define cset_size(s) cmap_size(s) -#define cmap_try_emplace(self, tag, k, v) do { \ +#define cset_bucket_count(s) cmap_bucket_count(s) +#define cmap_try_emplace(tag, self, k, v) do { \ struct cmap_##tag##_result __r = cmap_##tag##_insert_key(self, k); \ if (__r.inserted) __r.entry->value = v; \ } while (false) @@ -299,7 +301,7 @@ ctype##_##tag##_put(ctype##_##tag* self, OPT_2_##ctype(ctype##_##tag##_rawkey_t STC_API ctype##_##tag##_entry_t* \ ctype##_##tag##_insert(ctype##_##tag* self, OPT_2_##ctype(ctype##_##tag##_rawkey_t rawKey, Value value)) { \ struct ctype##_##tag##_result res = ctype##_##tag##_insert_key(self, rawKey); \ - OPT_1_##ctype( if (res.inserted) res.entry->value = value; ) \ + OPT_1_##ctype( if (res.inserted) res.entry->value = value; else valueDestroy(&value); ) \ return res.entry; \ } \ \ @@ -310,12 +312,12 @@ ctype##_##tag##_reserve(ctype##_##tag* self, size_t newcap) { \ newcap = (size_t) (newcap / self->max_load_factor) | 1; \ ctype##_##tag tmp = { \ c_new_n(ctype##_##tag##_entry_t, newcap), \ - (uint8_t *) calloc(newcap, sizeof(uint8_t)), \ + (uint8_t *) calloc(newcap + 1, sizeof(uint8_t)), \ self->size, (uint32_t) newcap, \ self->max_load_factor, self->shrink_limit_factor \ }; \ /* Rehash: */ \ - c_swap(ctype##_##tag, *self, tmp); \ + tmp._hashx[newcap] = 0xff; c_swap(ctype##_##tag, *self, tmp); \ ctype##_##tag##_entry_t* e = tmp.table, *slot = self->table; \ uint8_t* hashx = self->_hashx; \ uint32_t hx; \ @@ -375,7 +377,7 @@ ctype##_##tag##_begin(ctype##_##tag* map) { \ \ STC_API void \ ctype##_##tag##_next(ctype##_##tag##_iter_t* it) { \ - while (++it->item != it->end && *++it->_hx == 0) ; \ + while ((++it->item, *++it->_hx == 0)) ; \ } /* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ @@ -383,14 +385,14 @@ ctype##_##tag##_next(ctype##_##tag##_iter_t* it) { \ STC_API uint32_t c_default_hash16(const void *data, size_t len) { const volatile uint16_t *key = (const uint16_t *) data; uint64_t x = 0xc613fc15u; - while (len -= 2) x = ((*key++ + x) * 2654435769u) >> 13; + while (len -= 2) x = ((*key++ + x) * 2654435769ull) >> 13; return (uint32_t) x; } STC_API uint32_t c_default_hash32(const void* data, size_t len) { const volatile uint32_t *key = (const uint32_t *) data; - uint64_t x = *key++ * 2654435769u; - while (len -= 4) x ^= *key++ * 2654435769u; - return (uint32_t) x; + uint64_t x = *key++ * 2654435769ull; + while (len -= 4) x ^= *key++ * 2654435769ull; + return (uint32_t) (x >> 24); } #else -- cgit v1.2.3