From 234aeb5ad6f4ea56e4fed7f038052a702d319d45 Mon Sep 17 00:00:00 2001 From: Tyge Date: Thu, 30 Apr 2020 10:40:12 +0200 Subject: Added KHASH in benchmark, tuned cmap. --- benchmark.c | 41 +++++++++++++++++++++++++++-------------- stc/cdefs.h | 9 ++++++++- stc/cmap.h | 33 ++++++++++++++------------------- 3 files changed, 49 insertions(+), 34 deletions(-) diff --git a/benchmark.c b/benchmark.c index 2e5d2b34..81107a19 100644 --- a/benchmark.c +++ b/benchmark.c @@ -4,6 +4,7 @@ #include "stc/cstring.h" #include "stc/cmap.h" +#include "others/khash.h" #ifdef __cplusplus #include #include "others/bytell_hash_map.hpp" @@ -15,47 +16,57 @@ declare_CMap(ii, int64_t, int64_t, c_noDestroy, c_lowbias32Hash); declare_CMap(ix, short, short); // sizeof(CMapEntry_ix) = 6 bytes only! +KHASH_MAP_INIT_INT64(ii, uint64_t) + const size_t seed = 123; // time(NULL); const double maxLoadFactor = 0.77; #define RAND(N) ((rand() << ((N) - 15)) ^ rand()) // N=16-30 #define CMAP_SETUP(tag, Key, Value) CMap_##tag map = cmap_init; \ cmap_##tag##_setMaxLoadFactor(&map, maxLoadFactor) -#define CMAP_PUT(tag, __key, __value) cmap_##tag##_put(&map, __key, __value)->value -#define CMAP_DEL(tag, key) cmap_##tag##_erase(&map, key) +#define CMAP_PUT(tag, key, val) cmap_##tag##_put(&map, key, val)->value +#define CMAP_ERASE(tag, key) cmap_##tag##_erase(&map, key) #define CMAP_FIND(tag, key) (cmap_##tag##_get(map, key) != NULL) #define CMAP_SIZE(tag) cmap_size(map) #define CMAP_BUCKETS(tag) cmap_bucketCount(map) #define CMAP_CLEAR(tag) cmap_##tag##_destroy(&map) +#define KMAP_SETUP(tag, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret +#define KMAP_PUT(tag, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) +#define KMAP_ERASE(tag, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) +#define KMAP_FIND(tag, key) (kh_get(ii, map, key) != kh_end(map)) +#define KMAP_SIZE(tag) ((size_t) kh_size(map)) +#define KMAP_BUCKETS(tag) ((size_t) kh_n_buckets(map)) +#define KMAP_CLEAR(tag) kh_destroy(ii, map) + #define UMAP_SETUP(tag, Key, Value) std::unordered_map map; map.max_load_factor(maxLoadFactor) -#define UMAP_PUT(tag, key, value) (map[key] = value) +#define UMAP_PUT(tag, key, val) (map[key] = val) #define UMAP_FIND(tag, key) (map.find(key) != map.end()) -#define UMAP_DEL(tag, key) map.erase(key) +#define UMAP_ERASE(tag, key) map.erase(key) #define UMAP_SIZE(tag) map.size() #define UMAP_BUCKETS(tag) map.bucket_count() #define UMAP_CLEAR(tag) map.clear() #define BMAP_SETUP(tag, Key, Value) ska::bytell_hash_map map; map.max_load_factor(maxLoadFactor) -#define BMAP_PUT(tag, key, value) (map[key] = value) +#define BMAP_PUT(tag, key, val) (map[key] = val) #define BMAP_FIND(tag, key) (map.find(key) != map.end()) -#define BMAP_DEL(tag, key) map.erase(key) +#define BMAP_ERASE(tag, key) map.erase(key) #define BMAP_SIZE(tag) map.size() #define BMAP_BUCKETS(tag) map.bucket_count() #define BMAP_CLEAR(tag) map.clear() #define FMAP_SETUP(tag, Key, Value) ska::flat_hash_map map; map.max_load_factor(maxLoadFactor) -#define FMAP_PUT(tag, key, value) (map[key] = value) +#define FMAP_PUT(tag, key, val) (map[key] = val) #define FMAP_FIND(tag, key) (map.find(key) != map.end()) -#define FMAP_DEL(tag, key) map.erase(key) +#define FMAP_ERASE(tag, key) map.erase(key) #define FMAP_SIZE(tag) map.size() #define FMAP_BUCKETS(tag) map.bucket_count() #define FMAP_CLEAR(tag) map.clear() #define RMAP_SETUP(tag, Key, Value) robin_hood::unordered_map map -#define RMAP_PUT(tag, key, value) (map[key] = value) +#define RMAP_PUT(tag, key, val) (map[key] = val) #define RMAP_FIND(tag, key) (map.find(key) != map.end()) -#define RMAP_DEL(tag, key) map.erase(key) +#define RMAP_ERASE(tag, key) map.erase(key) #define RMAP_SIZE(tag) map.size() #define RMAP_BUCKETS(tag) map.bucket_count() #define RMAP_CLEAR(tag) map.clear() @@ -65,6 +76,7 @@ const size_t N2 = 10000000; #define RR 24 int rr = RR; + #define MAP_TEST1(M, tag) \ { \ M##_SETUP(tag, int64_t, int64_t); \ @@ -72,8 +84,8 @@ int rr = RR; srand(seed); \ clock_t difference, before = clock(); \ for (size_t i = 0; i < N1; ++i) { \ - checksum += ++M##_PUT(tag, RAND(rr), i); \ - erased += M##_DEL(tag, RAND(rr)); \ + checksum += ++ M##_PUT(tag, RAND(rr), i); \ + erased += M##_ERASE(tag, RAND(rr)); \ } \ difference = clock() - before; \ printf(#M "(" #tag "): sz: %llu, bucks: %llu, time: %.02f, sum: %llu, erase: %llu\n", M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, checksum, erased); \ @@ -89,7 +101,7 @@ int rr = RR; for (size_t i = 0; i < N2; ++i) \ M##_PUT(tag, i*17, i); \ for (size_t i = 0; i < N2; ++i) \ - erased += M##_DEL(tag, i*17); \ + erased += M##_ERASE(tag, i*17); \ difference = clock() - before; \ printf(#M "(" #tag "): sz: %llu, bucks: %llu, time: %.02f, erase %llu\n", M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ M##_CLEAR(tag); \ @@ -101,6 +113,7 @@ int main(int argc, char* argv[]) rr = argc == 2 ? atoi(argv[1]) : RR; printf("\nmap: Insert + remove %llu random keys in range 0 - 2^%d:\n", N1, rr); MAP_TEST1(CMAP, ii) + MAP_TEST1(KMAP, ii) #ifdef __cplusplus MAP_TEST1(UMAP, ii) MAP_TEST1(BMAP, ii) @@ -110,11 +123,11 @@ int main(int argc, char* argv[]) printf("\nmap: Insert %llu keys, THEN remove them in same order:\n", N2); MAP_TEST2(CMAP, ii) + MAP_TEST2(KMAP, ii) #ifdef __cplusplus MAP_TEST2(UMAP, ii) MAP_TEST2(BMAP, ii) MAP_TEST2(FMAP, ii) MAP_TEST2(RMAP, ii) #endif - } diff --git a/stc/cdefs.h b/stc/cdefs.h index 1c75abcc..249089fa 100644 --- a/stc/cdefs.h +++ b/stc/cdefs.h @@ -26,10 +26,17 @@ #include #include +#if defined(_MSC_VER) +# define STC_INLINE __forceinline +#elif defined(__GNUC__) +# define STC_INLINE inline __attribute((always_inline)) +#else +# define STC_INLINE inline +#endif #if defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define STC_API extern #else -#define STC_API static inline +#define STC_API static STC_INLINE #endif /* Macro overloading feature support: https://rextester.com/ONP80107 */ diff --git a/stc/cmap.h b/stc/cmap.h index 95b1ee13..0ab8cb48 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -25,9 +25,9 @@ #include "cvector.h" -#define cmap_init {cvector_init, 0, 90, 0} +#define cmap_init {cvector_init, 0, 0, 90, 0} #define cmap_size(map) ((size_t) (map)._size) -#define cmap_bucketCount(map) cvector_capacity((map)._table) +#define cmap_bucketCount(map) ((size_t) (map)._cap) /* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ #define cmap_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) @@ -90,7 +90,7 @@ enum {cmapentry_HASH=0x7fff, cmapentry_USED=0x8000}; \ typedef struct CMap_##tag { \ CVector_map_##tag _table; \ - size_t _size; \ + uint32_t _size, _cap; \ uint8_t maxLoadPercent; \ uint8_t shrinkLimitPercent; \ } CMap_##tag; \ @@ -147,7 +147,7 @@ typedef Value cmap_##tag##_value_t STC_API void \ cmap_##tag##_destroy(CMap_##tag* self) { \ if (cmap_size(*self)) { \ - size_t cap = _cvector_capacity(self->_table); \ + size_t cap = cmap_bucketCount(*self); \ CMapEntry_##tag* e = self->_table.data, *end = e + cap; \ for (; e != end; ++e) if (e->hashx) cmapentry_##tag##_destroy(e); \ } \ @@ -155,7 +155,7 @@ cmap_##tag##_destroy(CMap_##tag* self) { \ } \ \ STC_API void cmap_##tag##_clear(CMap_##tag* self) { \ - memset(self->_table.data, 0, sizeof(CMapEntry_##tag) * _cvector_capacity(self->_table)); \ + memset(self->_table.data, 0, sizeof(CMapEntry_##tag) * cmap_bucketCount(*self)); \ self->_size = 0; \ } \ \ @@ -176,7 +176,7 @@ cmap_##tag##_setShrinkLimitFactor(CMap_##tag* self, double limit) { \ static inline size_t \ cmap_##tag##_bucket(CMap_##tag* self, const cmap_##tag##_rawkey_t* rawKeyPtr, uint32_t* hxPtr) { \ uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(cmap_##tag##_rawkey_t)), sx, hx = (hash & cmapentry_HASH) | cmapentry_USED; \ - size_t cap = cvector_capacity(self->_table); \ + size_t cap = cmap_bucketCount(*self); \ size_t idx = cmap_reduce(hash, cap); \ CMapEntry_##tag* slot = self->_table.data; \ while ((sx = slot[idx].hashx)) { \ @@ -198,16 +198,10 @@ cmap_##tag##_get(CMap_##tag map, cmap_##tag##_rawkey_t rawKey) { \ return map._table.data[idx].hashx ? &map._table.data[idx] : NULL; \ } \ \ -static inline void \ -cmap_##tag##_expand(CMap_##tag* self) { \ - size_t cap = cvector_capacity(self->_table); \ - if (cmap_size(*self) + 1 >= cap * self->maxLoadPercent * 0.01) \ - cmap_##tag##_reserve(self, (size_t) 7 + (1.6 * cap)); \ -} \ - \ STC_API CMapEntry_##tag* \ cmap_##tag##_put(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey, Value value) { \ - cmap_##tag##_expand(self); \ + if (cmap_size(*self) + 1 >= cmap_bucketCount(*self) * self->maxLoadPercent * 0.01) \ + cmap_##tag##_reserve(self, (size_t) 7 + (1.6 * cmap_bucketCount(*self))); \ uint32_t hx; \ size_t idx = cmap_##tag##_bucket(self, &rawKey, &hx); \ CMapEntry_##tag* e = &self->_table.data[idx]; \ @@ -224,7 +218,8 @@ cmap_##tag##_put(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey, Value value) { \ STC_API CMapEntry_##tag* \ cmap_##tag##_insert(CMap_##tag* self, CMapEntry_##tag entry) { \ - cmap_##tag##_expand(self); \ + if (cmap_size(*self) + 1 >= cmap_bucketCount(*self) * self->maxLoadPercent * 0.01) \ + cmap_##tag##_reserve(self, (size_t) 7 + (1.6 * cmap_bucketCount(*self))); \ uint32_t hx; \ cmap_##tag##_rawkey_t r = keyGetRaw(&entry.key); \ size_t idx = cmap_##tag##_bucket(self, &r, &hx); \ @@ -247,10 +242,10 @@ cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \ \ STC_API size_t \ cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \ - size_t oldcap = cvector_capacity(self->_table), newcap = 1 + (size / 2) * 2; \ + size_t oldcap = cmap_bucketCount(*self), newcap = 1 + (size / 2) * 2; \ if (cmap_size(*self) >= newcap * self->maxLoadPercent * 0.01) return oldcap; \ CVector_map_##tag vec = cvector_init; \ - cvector_map_##tag##_reserve(&vec, newcap); \ + cvector_map_##tag##_reserve(&vec, (self->_cap = newcap)); \ memset(vec.data, 0, sizeof(CMapEntry_##tag) * newcap); \ cvector_map_##tag##_swap(&self->_table, &vec); \ \ @@ -268,7 +263,7 @@ STC_API bool \ cmap_##tag##_erase(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey) { \ if (cmap_size(*self) == 0) \ return false; \ - size_t cap = cvector_capacity(self->_table); \ + size_t cap = cmap_bucketCount(*self); \ if (cmap_size(*self) < cap * self->shrinkLimitPercent * 0.01) \ cap = cmap_##tag##_reserve(self, cmap_size(*self) * 120 / self->maxLoadPercent); \ uint32_t hx; \ @@ -293,7 +288,7 @@ cmap_##tag##_erase(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey) { \ \ STC_API cmap_##tag##_iter_t \ cmap_##tag##_begin(CMap_##tag* map) { \ - CMapEntry_##tag* e = map->_table.data, *end = e + _cvector_capacity(map->_table); \ + CMapEntry_##tag* e = map->_table.data, *end = e + cmap_bucketCount(*map); \ while (e != end && !e->hashx) ++e; \ cmap_##tag##_iter_t it = {e == end ? NULL : e, end}; return it; \ } \ -- cgit v1.2.3