Changed array expansion policy from 1.625x to 1.5x

7 files changed, 28 insertions, 29 deletions

diff --git a/benchmarks/others/old/sstr.h b/benchmarks/others/old/sstr.h
index 68b724a8..2ea1033d 100644
--- a/benchmarks/others/old/sstr.h
+++ b/benchmarks/others/old/sstr.h
@@ -274,7 +274,7 @@ STC_DEF void sstr_internal_move_(sstr* self, size_t pos1, size_t pos2) {
     sstr_rep_t rep = sstr_rep_(self);

     sstr_size_t newlen = rep.size + pos2 - pos1;

     if (newlen > rep.cap)

-        rep.data = sstr_reserve(self, (rep.size*13 >> 3) + pos2 - pos1);

+        rep.data = sstr_reserve(self, (rep.size*3 >> 1) + pos2 - pos1);

     memmove(&rep.data[pos2], &rep.data[pos1], rep.size - pos1);

     sstr_set_size_(self, newlen);

 }

@@ -368,7 +368,7 @@ STC_DEF void sstr_append_n(sstr* self, const char* str, sstr_size_t n) {
     sstr_rep_t rep = sstr_rep_(self);

     if (rep.size + n > rep.cap) {

         sstr_size_t off = (sstr_size_t)(str - rep.data); /* handle self append */

-        rep.data = sstr_reserve(self, (rep.size*13 >> 3) + n);

+        rep.data = sstr_reserve(self, (rep.size*3 >> 1) + n);

         if (off <= rep.size) str = rep.data + off;

     }

     memcpy(rep.data + rep.size, str, n);

@@ -388,7 +388,7 @@ STC_DEF bool sstr_getdelim(sstr *self, int delim, FILE *fp) {
         }

         if (pos == rep.cap) {

             sstr_set_size_(self, pos);

-            rep.data = sstr_reserve(self, (rep.cap = (rep.cap*13 >> 3) + 16));

+            rep.data = sstr_reserve(self, (rep.cap = (rep.cap*3 >> 1) + 16));

         }

         rep.data[pos++] = (char) c;

         c = fgetc(fp);

diff --git a/benchmarks/shootout2_cmap.cpp b/benchmarks/shootout2_cmap.cpp
index 60aed5b0..a2b65cdd 100644
--- a/benchmarks/shootout2_cmap.cpp
+++ b/benchmarks/shootout2_cmap.cpp
@@ -4,16 +4,21 @@
 #include <stc/cstr.h>
 #include "others/khash.h"
 
+enum {max_load_factor = 77};
+
 #ifdef __cplusplus
 #include <limits>
 #include <unordered_map>
 #include "others/robin_hood.hpp"
 #include "others/skarupke/bytell_hash_map.hpp"
-#include "others/tsl/hopscotch_map.h"
 #include "others/parallel_hashmap/phmap.h"
-template<typename C> inline void destroy_me(C& c) { C().swap(c); }
+template<typename C> inline void std_destroy(C& c) { C().swap(c); }
+
+template <class K, class V> using robin_hood_flat_map = robin_hood::unordered_flat_map<
+                                  K, V, robin_hood::hash<K>, std::equal_to<K>, max_load_factor>;
 #endif
 
+KHASH_MAP_INIT_INT64(ii, int64_t)
 
 // cmap and khash template expansion
 #define i_key int64_t
@@ -22,20 +27,14 @@ template<typename C> inline void destroy_me(C& c) { C().swap(c); }
 #define i_tag ii
 #include <stc/cmap.h>
 
-size_t seed;
-static const float max_load_factor = 0.77f;
-
-KHASH_MAP_INIT_INT64(ii, int64_t)
-template <class K, class V> using robin_hood_flat_map = robin_hood::unordered_flat_map<
-                                    K, V, robin_hood::hash<K>, std::equal_to<K>, 77>;
-
 stc64_t rng;
+size_t seed;
 #define SEED(s) rng = stc64_init(seed)
-#define RAND(N) (stc64_rand(&rng) & ((1 << N) - 1))
+#define RAND(N) (stc64_rand(&rng) & (((uint64_t)1 << N) - 1))
 
 
 #define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \
-                                  ; cmap_##X##_max_load_factor(&map, max_load_factor)
+                                  ; cmap_##X##_max_load_factor(&map, max_load_factor/100.0f)
 #define CMAP_PUT(X, key, val)     cmap_##X##_emplace_or_assign(&map, key, val).ref->second
 #define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val).ref->second
 #define CMAP_ERASE(X, key)        cmap_##X##_erase(&map, key)
@@ -57,7 +56,7 @@ stc64_t rng;
 #define KMAP_CLEAR(X)             kh_clear(ii, map)
 #define KMAP_DTOR(X)              kh_destroy(ii, map)
 
-#define UMAP_SETUP(X, Key, Value) std::unordered_map<Key, Value> map; map.max_load_factor(max_load_factor)
+#define UMAP_SETUP(X, Key, Value) std::unordered_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
 #define UMAP_PUT(X, key, val)     (map[key] = val)
 #define UMAP_EMPLACE(X, key, val) map.emplace(key, val).first->second
 #define UMAP_FIND(X, key)         int(map.find(key) != map.end())
@@ -67,9 +66,9 @@ stc64_t rng;
 #define UMAP_SIZE(X)              map.size()
 #define UMAP_BUCKETS(X)           map.bucket_count()
 #define UMAP_CLEAR(X)             map.clear()
-#define UMAP_DTOR(X)              ((void)0) // destroy_me(map)
+#define UMAP_DTOR(X)              std_destroy(map)
 
-#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)
+#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
 #define FMAP_PUT(X, key, val)     UMAP_PUT(X, key, val)
 #define FMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
 #define FMAP_FIND(X, key)         UMAP_FIND(X, key)
@@ -81,7 +80,7 @@ stc64_t rng;
 #define FMAP_CLEAR(X)             UMAP_CLEAR(X)
 #define FMAP_DTOR(X)              UMAP_DTOR(X)
 
-#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map<Key, Value> map; map.max_load_factor(max_load_factor)
+#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
 #define HMAP_PUT(X, key, val)     UMAP_PUT(X, key, val)
 #define HMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
 #define HMAP_FIND(X, key)         UMAP_FIND(X, key)
@@ -106,7 +105,7 @@ stc64_t rng;
 #define RMAP_CLEAR(X)             UMAP_CLEAR(X)
 #define RMAP_DTOR(X)              UMAP_DTOR(X)
 
-#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)
+#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
 #define PMAP_PUT(X, key, val)     UMAP_PUT(X, key, val)
 #define PMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
 #define PMAP_FIND(X, key)         UMAP_FIND(X, key)
diff --git a/include/stc/alt/cstr.h b/include/stc/alt/cstr.h
index 98a090e0..39da2e6a 100644
--- a/include/stc/alt/cstr.h
+++ b/include/stc/alt/cstr.h
@@ -274,7 +274,7 @@ STC_DEF void cstr_internal_move_(cstr* self, size_t pos1, size_t pos2) {
     cstr_rep_t rep = cstr_rep_(self);

     cstr_size_t newlen = rep.size + pos2 - pos1;

     if (newlen > rep.cap)

-        rep.data = cstr_reserve(self, (rep.size*13 >> 3) + pos2 - pos1);

+        rep.data = cstr_reserve(self, (rep.size*3 >> 1) + pos2 - pos1);

     memmove(&rep.data[pos2], &rep.data[pos1], rep.size - pos1);

     cstr_set_size_(self, newlen);

 }

@@ -368,7 +368,7 @@ STC_DEF void cstr_append_n(cstr* self, const char* str, cstr_size_t n) {
     cstr_rep_t rep = cstr_rep_(self);

     if (rep.size + n > rep.cap) {

         cstr_size_t off = (cstr_size_t)(str - rep.data); /* handle self append */

-        rep.data = cstr_reserve(self, (rep.size*13 >> 3) + n);

+        rep.data = cstr_reserve(self, (rep.size*3 >> 1) + n);

         if (off <= rep.size) str = rep.data + off;

     }

     memcpy(rep.data + rep.size, str, n);

@@ -388,7 +388,7 @@ STC_DEF bool cstr_getdelim(cstr *self, int delim, FILE *fp) {
         }

         if (pos == rep.cap) {

             cstr_set_size_(self, pos);

-            rep.data = cstr_reserve(self, (rep.cap = (rep.cap*13 >> 3) + 16));

+            rep.data = cstr_reserve(self, (rep.cap = (rep.cap*3 >> 1) + 16));

         }

         rep.data[pos++] = (char) c;

         c = fgetc(fp);

diff --git a/include/stc/cmap.h b/include/stc/cmap.h
index 1a0f28b4..1c9abea7 100644
--- a/include/stc/cmap.h
+++ b/include/stc/cmap.h
@@ -302,7 +302,7 @@ _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr) {
 STC_DEF _cx_result

 _cx_memb(_insert_entry_)(_cx_self* self, i_keyraw rkey) {

     if (self->size + 1 >= (_cx_size) (self->bucket_count * self->max_load_factor))

-        _cx_memb(_reserve)(self, 8 + (self->size*13ull >> 3));

+        _cx_memb(_reserve)(self, 8 + ((size_t)self->size*3 >> 1));

     chash_bucket_t b = _cx_memb(_bucket_)(self, &rkey);

     _cx_result res = {&self->table[b.idx], !self->_hashx[b.idx]};

     if (res.inserted) {

diff --git a/include/stc/csmap.h b/include/stc/csmap.h
index 34ff22d7..2a0e6b89 100644
--- a/include/stc/csmap.h
+++ b/include/stc/csmap.h
@@ -258,7 +258,7 @@ _cx_memb(_node_new_)(_cx_self* self, int level) {
         tn = rep->disp;

         rep->disp = self->nodes[tn].link[1];

     } else {

-        if ((tn = rep->head + 1) > rep->cap) _cx_memb(_reserve)(self, 4 + (tn*13 >> 3));

+        if ((tn = rep->head + 1) > rep->cap) _cx_memb(_reserve)(self, 4 + (tn*3 >> 1));

         ++_csmap_rep(self)->head; /* do after reserve */

     }

     _cx_node* dn = &self->nodes[tn];

diff --git a/include/stc/cstr.h b/include/stc/cstr.h
index c0a6650b..d07b3ce3 100644
--- a/include/stc/cstr.h
+++ b/include/stc/cstr.h
@@ -269,7 +269,7 @@ cstr_append_n(cstr* self, const char* str, size_t n) {
     size_t oldlen = _cstr_rep(self)->size, newlen = oldlen + n;

     if (newlen > _cstr_rep(self)->cap) {

         size_t off = (size_t) (str - self->str); /* handle self append */

-        cstr_reserve(self, (oldlen*13 >> 3) + n);

+        cstr_reserve(self, (oldlen*3 >> 1) + n);

         if (off <= oldlen) str = self->str + off;

     }

     memcpy(&self->str[oldlen], str, n);

@@ -282,7 +282,7 @@ STC_INLINE void _cstr_internal_move(cstr* self, size_t pos1, size_t pos2) {
         return;

     size_t len = _cstr_rep(self)->size, newlen = len + pos2 - pos1;

     if (newlen > _cstr_rep(self)->cap)

-        cstr_reserve(self, (len*13 >> 3) + pos2 - pos1);

+        cstr_reserve(self, (len*3 >> 1) + pos2 - pos1);

     memmove(&self->str[pos2], &self->str[pos1], len - pos1);

     self->str[_cstr_rep(self)->size = newlen] = '\0';

 }

@@ -343,7 +343,7 @@ cstr_getdelim(cstr *self, int delim, FILE *fp) {
             return true;

         }

         if (pos == cap)

-            cap = cstr_reserve(self, (cap*13 >> 3) + 16);

+            cap = cstr_reserve(self, (cap*3 >> 1) + 16);

         self->str[pos++] = (char) c;

         c = fgetc(fp);

     }

diff --git a/include/stc/cvec.h b/include/stc/cvec.h
index a650d277..e58e8793 100644
--- a/include/stc/cvec.h
+++ b/include/stc/cvec.h
@@ -280,7 +280,7 @@ STC_DEF _cx_value*
 _cx_memb(_push_back)(_cx_self* self, i_val value) {

     size_t len = cvec_rep_(self)->size;

     if (len == _cx_memb(_capacity)(*self))

-        _cx_memb(_reserve)(self, (len*13 >> 3) + 4);

+        _cx_memb(_reserve)(self, (len*3 >> 1) + 4);

     _cx_value *v = self->data + cvec_rep_(self)->size++;

     *v = value; return v;

 }

@@ -298,7 +298,7 @@ _cx_memb(_insert_space_)(_cx_self* self, _cx_value* pos, size_t len) {
     size_t idx = pos - self->data, size = cvec_rep_(self)->size;

     if (len == 0) return pos;

     if (size + len > _cx_memb(_capacity)(*self))

-        _cx_memb(_reserve)(self, (size*13 >> 3) + len),

+        _cx_memb(_reserve)(self, (size*3 >> 1) + len),

         pos = self->data + idx;

     cvec_rep_(self)->size += len;

     memmove(pos + len, pos, (size - idx) * sizeof(i_val));