Added KHASH in benchmark, tuned cmap.

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 <unordered_map>

 #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<Key, Value> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<uint64_t, uint64_t>: 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<uint64_t, uint64_t>: 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 <stdint.h>

 #include <stdbool.h>

 

+#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; \

 } \