From 1745da92874e1799c7d60f6e6810b398e9ab9f15 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 24 Feb 2021 19:08:21 +0100 Subject: More docs and some file renames. --- README.md | 12 +- benchmarks/cmap_benchmark2.cpp | 325 ----------------------------------------- benchmarks/cmap_benchmark3.cpp | 252 -------------------------------- benchmarks/shootout1_cmap.cpp | 325 +++++++++++++++++++++++++++++++++++++++++ benchmarks/shootout2_cmap.cpp | 252 ++++++++++++++++++++++++++++++++ docs/ccommon_api.md | 21 ++- docs/cstr_api.md | 5 +- examples/crandom_ex.c | 2 +- examples/demos.c | 2 +- examples/ex_gauss1.c | 2 +- examples/ex_gauss2.c | 2 +- examples/random.c | 2 +- examples/replace.c | 4 +- 13 files changed, 602 insertions(+), 604 deletions(-) delete mode 100644 benchmarks/cmap_benchmark2.cpp delete mode 100644 benchmarks/cmap_benchmark3.cpp create mode 100644 benchmarks/shootout1_cmap.cpp create mode 100644 benchmarks/shootout2_cmap.cpp diff --git a/README.md b/README.md index 310a38a8..9e6960ba 100644 --- a/README.md +++ b/README.md @@ -40,7 +40,7 @@ has noticable faster lookup than *std::map*'s typical red-black tree implementat create a flatter structure (more balanced) than red-black trees. **cvec** is only slightly slower than *std::vector*. Notes: -- The barchart shows average test times from three platforms: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. +- The barchart shows average test times over three platforms: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. - Containers uses value types `uint64_t` and pairs of `uint64_t`for the maps. - Black bars indicates performance variation between various platforms/compilers. - Iterations are repeated 4 times over n elements. @@ -82,7 +82,7 @@ int main(void) { cvec_i_del(&vec); } ``` -And with multiple containers... +With six different containers: ```c #include #include @@ -207,8 +207,8 @@ elements using dynamic memory. | push_front() | emplace_front() | cvec, cdeq, clist | | insert_after() | emplace_after() | clist | -***Note***: For integral or trivial element types, **emplace** and corresponding non-emplace methods are -identical, so the following does not apply for containers of such types. +***Note***: For containers of integral or trivial element types, **emplace** and corresponding non-emplace methods are +identical, so the following does not apply for those. The **emplace** methods ***constructs*** or ***clones*** their own copy of the element to be added. In contrast, the non-emplace methods requires elements to be explicitly constructed or cloned before adding them. @@ -233,7 +233,7 @@ cstr_del(&s); cvec_del(&vec); ``` This is made possible because the **using**-declarations may be given an optional -convertion/"rawvalue"-type as template parameter, along with a back and forth convertion +conversion/"rawvalue"-type as template parameter, along with a back and forth conversion methods to the container value type. By default, *rawvalue has the same type as value*. Rawvalues are also beneficial for **find()** and *map insertions*. The **emplace()** methods constructs @@ -265,7 +265,7 @@ Memory efficiency - **clist**: Type size: one pointer. Each node allocates block storing value and next pointer. - **cdeq**: Type size: two pointers. Otherwise like *cvec*. - **cmap**: Type size: 4 pointers. *cmap* uses one table of keys+value, and one table of precomputed hash-value/used bucket, which occupies only one byte per bucket. The closed hashing has a default max load factor of 85%, and hash table scales by 1.5x when reaching that. -- **csmap**: Type size: 1 pointer. *csmap* manages its own array of tree-nodes for allocation efficiency. Each node uses two 32-bit words by default for left/right childs, and one byte for `level`. *csmap* can be configured to allow more than 2^32 elements, ie. 2^64, but it will double the overhead per node. +- **csmap**: Type size: 1 pointer. *csmap* manages its own array of tree-nodes for allocation efficiency. Each node uses two 32-bit words by default for left/right child, and one byte for `level`. *csmap* can be configured to allow more than 2^32 elements, ie. 2^64, but it will double the overhead per node. - **carray**: carray1, carray2 and carray3. Type size: One pointer plus one, two, or three size_t variables to store dimensions. Arrays are allocated as one contiguous block of heap memory. - **csptr**: a shared-pointer uses two pointers, one for the data and one for the reference counter. diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp deleted file mode 100644 index e16d4f41..00000000 --- a/benchmarks/cmap_benchmark2.cpp +++ /dev/null @@ -1,325 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include "others/bytell_hash_map.hpp" -#include "others/robin_hood.hpp" -#include "others/hopscotch_map.h" -#include "others/sparsepp/spp.h" - -#define PICOBENCH_IMPLEMENT_WITH_MAIN -#include "picobench.hpp" - -enum {N1 = 4000000, S1 = 1, MaxLoadFactor100 = 80}; -uint64_t seed = time(NULL); - -template using umap = std::unordered_map; -template using bmap = ska::bytell_hash_map; -template using fmap = ska::flat_hash_map; -template using hmap = tsl::hopscotch_map; -template using smap = spp::sparse_hash_map; -template using rmap = robin_hood::unordered_flat_map, - std::equal_to, MaxLoadFactor100>; -#define DEFMAP(map, ...) \ - using u##map = umap __VA_ARGS__; \ - using b##map = bmap __VA_ARGS__; \ - using f##map = fmap __VA_ARGS__; \ - using h##map = hmap __VA_ARGS__; \ - using s##map = smap __VA_ARGS__; \ - using r##map = rmap __VA_ARGS__ - -DEFMAP(map_i, ); -DEFMAP(map_x, ); -DEFMAP(map_s, ); - -using_cmap(i, int, int, c_default_equals, c_default_hash32); -using_cmap(x, uint64_t, uint64_t, c_default_equals, c_default_hash64); -using_cmap_str(); - -PICOBENCH_SUITE("Map1"); - -template -static void ctor_and_ins_one_i(picobench::state& s) -{ - size_t result = 0; - - picobench::scope scope(s); - c_forrange (n, s.iterations()) { - MapInt map; - map[n]; - result += map.size(); - } - s.set_result(result); -} - -static void ctor_and_ins_one_cmap_i(picobench::state& s) -{ - size_t result = 0; - - picobench::scope scope(s); - c_forrange (n, s.iterations()) { - cmap_i map = cmap_i_init(); - cmap_i_emplace(&map, n, 0); - result += cmap_i_size(map); - cmap_i_del(&map); - } - s.set_result(result); -} - -#define P samples(S1).iterations({N1}) -PICOBENCH(ctor_and_ins_one_i).P; -PICOBENCH(ctor_and_ins_one_i).P; -PICOBENCH(ctor_and_ins_one_i).P; -PICOBENCH(ctor_and_ins_one_i).P; -PICOBENCH(ctor_and_ins_one_i).P; -PICOBENCH(ctor_and_ins_one_i).P; -PICOBENCH(ctor_and_ins_one_cmap_i).P; -#undef P - -PICOBENCH_SUITE("Map2"); - -template -static void ins_and_erase_i(picobench::state& s) -{ - size_t result = 0; - MapInt map; - map.max_load_factor(MaxLoadFactor100 / 100.0); - stc64_srandom(seed); - - picobench::scope scope(s); - c_forrange (s.iterations()) - map[stc64_random()]; - map.clear(); - stc64_srandom(seed); - c_forrange (s.iterations()) - map[stc64_random()]; - stc64_srandom(seed); - c_forrange (s.iterations()) - map.erase(stc64_random()); - s.set_result(map.size()); -} - -static void ins_and_erase_cmap_i(picobench::state& s) -{ - cmap_i map = cmap_i_init(); - cmap_i_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); - stc64_srandom(seed); - - picobench::scope scope(s); - c_forrange (s.iterations()) - cmap_i_emplace(&map, stc64_random(), 0); - cmap_i_clear(&map); - stc64_srandom(seed); - c_forrange (s.iterations()) - cmap_i_emplace(&map, stc64_random(), 0); - stc64_srandom(seed); - c_forrange (s.iterations()) - cmap_i_erase(&map, stc64_random()); - s.set_result(cmap_i_size(map)); - cmap_i_del(&map); -} - -static void ins_and_erase_cmap_x(picobench::state& s) -{ - cmap_x map = cmap_x_init(); - cmap_x_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); - stc64_srandom(seed); - - picobench::scope scope(s); - c_forrange (s.iterations()) - cmap_x_emplace(&map, stc64_random(), 0); - cmap_x_clear(&map); - stc64_srandom(seed); - c_forrange (s.iterations()) - cmap_x_emplace(&map, stc64_random(), 0); - stc64_srandom(seed); - c_forrange (s.iterations()) - cmap_x_erase(&map, stc64_random()); - s.set_result(cmap_x_size(map)); - cmap_x_del(&map); -} - -#define P samples(S1).iterations({N1/4}) -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_cmap_x).P; -#undef P - -PICOBENCH_SUITE("Map3"); - -template -static void ins_and_access_i(picobench::state& s) -{ - uint64_t mask = (1ull << s.arg()) - 1; - size_t result = 0; - MapInt map; - map.max_load_factor(MaxLoadFactor100 / 100.0); - stc64_srandom(seed); - - picobench::scope scope(s); - c_forrange (N1) - result += ++map[stc64_random() & mask]; - s.set_result(result); -} - -static void ins_and_access_cmap_i(picobench::state& s) -{ - uint64_t mask = (1ull << s.arg()) - 1; - size_t result = 0; - cmap_i map = cmap_i_init(); - cmap_i_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); - stc64_srandom(seed); - - picobench::scope scope(s); - c_forrange (N1) - result += ++cmap_i_emplace(&map, stc64_random() & mask, 0).first->second; - s.set_result(result); - cmap_i_del(&map); -} - -#define P samples(S1).iterations({N1, N1, N1, N1}).args({18, 23, 25, 31}) -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_cmap_i).P; -#undef P - -PICOBENCH_SUITE("Map4"); - -static void randomize(char* str, size_t len) { - union {uint64_t i; char c[8];} r = {.i = stc64_random()}; - for (int i = len - 7, j = 0; i < len; ++j, ++i) - str[i] = (r.c[j] & 63) + 48; -} - -template -static void ins_and_access_s(picobench::state& s) -{ - std::string str(s.arg(), 'x'); - size_t result = 0; - MapStr map; - map.max_load_factor(MaxLoadFactor100 / 100.0); - stc64_srandom(seed); - - picobench::scope scope(s); - c_forrange (s.iterations()) { - randomize(&str[0], str.size()); - map.emplace(str, str); - randomize(&str[0], str.size()); - result += map.erase(str); - } - s.set_result(result + map.size()); -} - -static void ins_and_access_cmap_s(picobench::state& s) -{ - cstr str = cstr_with_size(s.arg(), 'x'); - size_t result = 0; - cmap_str map = cmap_str_init(); - cmap_str_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); - stc64_srandom(seed); - - picobench::scope scope(s); - c_forrange (s.iterations()) { - randomize(str.str, cstr_size(str)); - cmap_str_emplace(&map, str.str, str.str); - randomize(str.str, cstr_size(str)); - result += cmap_str_erase(&map, str.str); - } - s.set_result(result + cmap_str_size(map)); - cstr_del(&str); - cmap_str_del(&map); -} - -#define P samples(S1).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).args({13, 7, 8, 100, 1000}) -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_cmap_s).P; -#undef P - -PICOBENCH_SUITE("Map5"); - -template -static void iterate_x(picobench::state& s) -{ - MapX map; - map.max_load_factor(MaxLoadFactor100 / 100.0); - uint64_t K = (1ull << s.arg()) - 1; - - picobench::scope scope(s); - stc64_srandom(seed); - size_t result = 0; - - // measure insert then iterate whole map - c_forrange (n, s.iterations()) { - map[stc64_random()] = n; - if (!(n & K)) for (auto const& keyVal : map) - result += keyVal.second; - } - - // reset rng back to inital state - stc64_srandom(seed); - - // measure erase then iterate whole map - c_forrange (n, s.iterations()) { - map.erase(stc64_random()); - if (!(n & K)) for (auto const& keyVal : map) - result += keyVal.second; - } - s.set_result(result); -} - -static void iterate_cmap_x(picobench::state& s) -{ - cmap_x map = cmap_x_init(); - cmap_x_set_load_factors(&map, 0.3, MaxLoadFactor100 / 100.0); - uint64_t K = (1ull << s.arg()) - 1; - - picobench::scope scope(s); - stc64_srandom(seed); - size_t result = 0; - - // measure insert then iterate whole map - c_forrange (n, s.iterations()) { - cmap_x_emplace_or_assign(&map, stc64_random(), n); - if (!(n & K)) c_foreach (i, cmap_x, map) - result += i.ref->second; - } - - // reset rng back to inital state - stc64_srandom(seed); - - // measure erase then iterate whole map - c_forrange (n, s.iterations()) { - cmap_x_erase(&map, stc64_random()); - if (!(n & K)) c_foreach (i, cmap_x, map) - result += i.ref->second; - } - s.set_result(result); - cmap_x_del(&map); -} - - -#define P samples(S1).iterations({N1/20}).args({12}) -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_cmap_x).P; -#undef P diff --git a/benchmarks/cmap_benchmark3.cpp b/benchmarks/cmap_benchmark3.cpp deleted file mode 100644 index 13905a3f..00000000 --- a/benchmarks/cmap_benchmark3.cpp +++ /dev/null @@ -1,252 +0,0 @@ -#include -#include -#include -#include -#include -#include "others/khash.h" - -#ifdef __cplusplus -#include -#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 - -static inline uint32_t fibonacci_hash(const void* data, size_t len) { - return (uint32_t) (((*(const uint64_t *) data) * 11400714819323198485llu) >> 24); -} - -// cmap and khash template expansion -using_cmap(ii, int64_t, int64_t, c_default_equals, fibonacci_hash); // c_default_hash); -KHASH_MAP_INIT_INT64(ii, int64_t) - - -size_t seed; -static const float max_load_factor = 0.77f; - -stc64_t rng; -#define SEED(s) rng = stc64_init(seed) -#define RAND(N) (stc64_rand(&rng) & ((1 << N) - 1)) - - -#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \ - ; cmap_##X##_set_load_factors(&map, 0.0, max_load_factor) -#define CMAP_PUT(X, key, val) cmap_##X##_emplace_or_assign(&map, key, val).first->second -#define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val).first->second -#define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key) -#define CMAP_FIND(X, key) (cmap_##X##_find(map, key) != NULL) -#define CMAP_FOR(X, i) c_foreach (i, cmap_##X, map) -#define CMAP_ITEM(X, i) i.ref->second -#define CMAP_SIZE(X) cmap_##X##_size(map) -#define CMAP_BUCKETS(X) cmap_##X##_bucket_count(map) -#define CMAP_CLEAR(X) cmap_##X##_clear(&map) -#define CMAP_DTOR(X) cmap_##X##_del(&map) - -#define KMAP_SETUP(X, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret -#define KMAP_PUT(X, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) -#define KMAP_EMPLACE(X, key, val) (ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val, 0) : 0, map->vals[ki]) -#define KMAP_ERASE(X, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) -#define KMAP_FIND(X, key) (kh_get(ii, map, key) != kh_end(map)) -#define KMAP_SIZE(X) kh_size(map) -#define KMAP_BUCKETS(X) kh_n_buckets(map) -#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 map; map.max_load_factor(max_load_factor) -#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) (map.find(key) != map.end()) -#define UMAP_ERASE(X, key) map.erase(key) -#define UMAP_FOR(X, i) for (auto i: map) -#define UMAP_ITEM(X, i) i.second -#define UMAP_SIZE(X) map.size() -#define UMAP_BUCKETS(X) map.bucket_count() -#define UMAP_CLEAR(X) map.clear() -#define UMAP_DTOR(X) destroy_me(map) - -#define BMAP_SETUP(X, Key, Value) ska::bytell_hash_map map; map.max_load_factor(max_load_factor) -#define BMAP_PUT(X, key, val) UMAP_PUT(X, key, val) -#define BMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) -#define BMAP_FIND(X, key) UMAP_FIND(X, key) -#define BMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define BMAP_FOR(X, i) UMAP_FOR(X, i) -#define BMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define BMAP_SIZE(X) UMAP_SIZE(X) -#define BMAP_BUCKETS(X) UMAP_BUCKETS(X) -#define BMAP_CLEAR(X) UMAP_CLEAR(X) -#define BMAP_DTOR(X) UMAP_DTOR(X) - -#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map map; map.max_load_factor(max_load_factor) -#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) -#define FMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define FMAP_FOR(X, i) UMAP_FOR(X, i) -#define FMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define FMAP_SIZE(X) UMAP_SIZE(X) -#define FMAP_BUCKETS(X) UMAP_BUCKETS(X) -#define FMAP_CLEAR(X) UMAP_CLEAR(X) -#define FMAP_DTOR(X) UMAP_DTOR(X) - -#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map map; map.max_load_factor(max_load_factor) -#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) -#define HMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define HMAP_FOR(X, i) UMAP_FOR(X, i) -#define HMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define HMAP_SIZE(X) UMAP_SIZE(X) -#define HMAP_BUCKETS(X) UMAP_BUCKETS(X) -#define HMAP_CLEAR(X) UMAP_CLEAR(X) -#define HMAP_DTOR(X) UMAP_DTOR(X) - -#define RMAP_SETUP(X, Key, Value) robin_hood::unordered_map map -#define RMAP_PUT(X, key, val) UMAP_PUT(X, key, val) -#define RMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) -#define RMAP_FIND(X, key) UMAP_FIND(X, key) -#define RMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define RMAP_FOR(X, i) UMAP_FOR(X, i) -#define RMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define RMAP_SIZE(X) UMAP_SIZE(X) -#define RMAP_BUCKETS(X) map.mask() -#define RMAP_CLEAR(X) UMAP_CLEAR(X) -#define RMAP_DTOR(X) UMAP_DTOR(X) - -#define SMAP_SETUP(X, Key, Value) spp::sparse_hash_map map; map.max_load_factor(max_load_factor) -#define SMAP_PUT(X, key, val) UMAP_PUT(X, key, val) -#define SMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) -#define SMAP_FIND(X, key) UMAP_FIND(X, key) -#define SMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define SMAP_FOR(X, i) UMAP_FOR(X, i) -#define SMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define SMAP_SIZE(X) UMAP_SIZE(X) -#define SMAP_BUCKETS(X) UMAP_BUCKETS(X) -#define SMAP_CLEAR(X) UMAP_CLEAR(X) -#define SMAP_DTOR(X) UMAP_DTOR(X) - -enum { - FAC = 3, - N1 = 10000000 * FAC, - N2 = 10000000 * FAC, - N3 = 10000000 * FAC, - N4 = 10000000 * FAC, - RR = 24 -}; -int rr = RR; - - -#define MAP_TEST1(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - uint64_t checksum = 0, erased = 0; \ - SEED(seed); \ - clock_t difference, before = clock(); \ - for (size_t i = 0; i < N1; ++i) { \ - checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ - erased += M##_ERASE(X, RAND(rr)); \ - } \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, sum: %zu, erased %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, checksum, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#define MAP_TEST2(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - size_t erased = 0; \ - clock_t difference, before = clock(); \ - for (size_t i = 0; i < N2; ++i) \ - M##_PUT(X, i, i); \ - for (size_t i = 0; i < N2; ++i) \ - erased += M##_ERASE(X, i); \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#define MAP_TEST3(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - size_t erased = 0; \ - clock_t difference, before = clock(); \ - SEED(seed); \ - for (size_t i = 0; i < N3; ++i) \ - M##_PUT(X, RAND(rr), i); \ - SEED(seed); \ - for (size_t i = 0; i < N3; ++i) \ - erased += M##_ERASE(X, RAND(rr)); \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#define MAP_TEST4(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - size_t sum = 0; \ - SEED(seed); \ - for (size_t i = 0; i < N4; ++i) \ - M##_PUT(X, RAND(rr), i); \ - clock_t difference, before = clock(); \ - for (int k=0; k<5; k++) M##_FOR (X, i) \ - sum += M##_ITEM(X, i); \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, sum %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, sum, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#define MAP_TEST5(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - uint64_t checksum = 0; \ - SEED(seed); \ - clock_t difference, before = clock(); \ - for (size_t i = 0; i < N1; ++i) { \ - checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ - } \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, sum: %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, checksum, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#ifdef __cplusplus -#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)*/ -#define RUNX_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)*/ -#else -#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) -#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii) -#endif - - -int main(int argc, char* argv[]) -{ - rr = argc == 2 ? atoi(argv[1]) : RR; - seed = time(NULL); - - printf("\nUnordered maps: Insert %d random keys:\n", N3); - RUN_TEST(5) - - printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); - printf("\nUnordered maps: %d repeats of Insert random key + try to remove a random key:\n", N1); - RUN_TEST(1) - - printf("\nUnordered maps: Insert %d index keys, then remove them in same order:\n", N2); - RUN_TEST(2) - - printf("\nUnordered maps: Insert %d random keys, then remove them in same order:\n", N3); - RUN_TEST(3) - - printf("\nUnordered maps: Iterate %d random keys:\n", N4); - RUNX_TEST(4) -} diff --git a/benchmarks/shootout1_cmap.cpp b/benchmarks/shootout1_cmap.cpp new file mode 100644 index 00000000..e16d4f41 --- /dev/null +++ b/benchmarks/shootout1_cmap.cpp @@ -0,0 +1,325 @@ +#include +#include +#include +#include +#include +#include +#include +#include "others/bytell_hash_map.hpp" +#include "others/robin_hood.hpp" +#include "others/hopscotch_map.h" +#include "others/sparsepp/spp.h" + +#define PICOBENCH_IMPLEMENT_WITH_MAIN +#include "picobench.hpp" + +enum {N1 = 4000000, S1 = 1, MaxLoadFactor100 = 80}; +uint64_t seed = time(NULL); + +template using umap = std::unordered_map; +template using bmap = ska::bytell_hash_map; +template using fmap = ska::flat_hash_map; +template using hmap = tsl::hopscotch_map; +template using smap = spp::sparse_hash_map; +template using rmap = robin_hood::unordered_flat_map, + std::equal_to, MaxLoadFactor100>; +#define DEFMAP(map, ...) \ + using u##map = umap __VA_ARGS__; \ + using b##map = bmap __VA_ARGS__; \ + using f##map = fmap __VA_ARGS__; \ + using h##map = hmap __VA_ARGS__; \ + using s##map = smap __VA_ARGS__; \ + using r##map = rmap __VA_ARGS__ + +DEFMAP(map_i, ); +DEFMAP(map_x, ); +DEFMAP(map_s, ); + +using_cmap(i, int, int, c_default_equals, c_default_hash32); +using_cmap(x, uint64_t, uint64_t, c_default_equals, c_default_hash64); +using_cmap_str(); + +PICOBENCH_SUITE("Map1"); + +template +static void ctor_and_ins_one_i(picobench::state& s) +{ + size_t result = 0; + + picobench::scope scope(s); + c_forrange (n, s.iterations()) { + MapInt map; + map[n]; + result += map.size(); + } + s.set_result(result); +} + +static void ctor_and_ins_one_cmap_i(picobench::state& s) +{ + size_t result = 0; + + picobench::scope scope(s); + c_forrange (n, s.iterations()) { + cmap_i map = cmap_i_init(); + cmap_i_emplace(&map, n, 0); + result += cmap_i_size(map); + cmap_i_del(&map); + } + s.set_result(result); +} + +#define P samples(S1).iterations({N1}) +PICOBENCH(ctor_and_ins_one_i).P; +PICOBENCH(ctor_and_ins_one_i).P; +PICOBENCH(ctor_and_ins_one_i).P; +PICOBENCH(ctor_and_ins_one_i).P; +PICOBENCH(ctor_and_ins_one_i).P; +PICOBENCH(ctor_and_ins_one_i).P; +PICOBENCH(ctor_and_ins_one_cmap_i).P; +#undef P + +PICOBENCH_SUITE("Map2"); + +template +static void ins_and_erase_i(picobench::state& s) +{ + size_t result = 0; + MapInt map; + map.max_load_factor(MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (s.iterations()) + map[stc64_random()]; + map.clear(); + stc64_srandom(seed); + c_forrange (s.iterations()) + map[stc64_random()]; + stc64_srandom(seed); + c_forrange (s.iterations()) + map.erase(stc64_random()); + s.set_result(map.size()); +} + +static void ins_and_erase_cmap_i(picobench::state& s) +{ + cmap_i map = cmap_i_init(); + cmap_i_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (s.iterations()) + cmap_i_emplace(&map, stc64_random(), 0); + cmap_i_clear(&map); + stc64_srandom(seed); + c_forrange (s.iterations()) + cmap_i_emplace(&map, stc64_random(), 0); + stc64_srandom(seed); + c_forrange (s.iterations()) + cmap_i_erase(&map, stc64_random()); + s.set_result(cmap_i_size(map)); + cmap_i_del(&map); +} + +static void ins_and_erase_cmap_x(picobench::state& s) +{ + cmap_x map = cmap_x_init(); + cmap_x_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (s.iterations()) + cmap_x_emplace(&map, stc64_random(), 0); + cmap_x_clear(&map); + stc64_srandom(seed); + c_forrange (s.iterations()) + cmap_x_emplace(&map, stc64_random(), 0); + stc64_srandom(seed); + c_forrange (s.iterations()) + cmap_x_erase(&map, stc64_random()); + s.set_result(cmap_x_size(map)); + cmap_x_del(&map); +} + +#define P samples(S1).iterations({N1/4}) +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_cmap_x).P; +#undef P + +PICOBENCH_SUITE("Map3"); + +template +static void ins_and_access_i(picobench::state& s) +{ + uint64_t mask = (1ull << s.arg()) - 1; + size_t result = 0; + MapInt map; + map.max_load_factor(MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (N1) + result += ++map[stc64_random() & mask]; + s.set_result(result); +} + +static void ins_and_access_cmap_i(picobench::state& s) +{ + uint64_t mask = (1ull << s.arg()) - 1; + size_t result = 0; + cmap_i map = cmap_i_init(); + cmap_i_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (N1) + result += ++cmap_i_emplace(&map, stc64_random() & mask, 0).first->second; + s.set_result(result); + cmap_i_del(&map); +} + +#define P samples(S1).iterations({N1, N1, N1, N1}).args({18, 23, 25, 31}) +PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_cmap_i).P; +#undef P + +PICOBENCH_SUITE("Map4"); + +static void randomize(char* str, size_t len) { + union {uint64_t i; char c[8];} r = {.i = stc64_random()}; + for (int i = len - 7, j = 0; i < len; ++j, ++i) + str[i] = (r.c[j] & 63) + 48; +} + +template +static void ins_and_access_s(picobench::state& s) +{ + std::string str(s.arg(), 'x'); + size_t result = 0; + MapStr map; + map.max_load_factor(MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (s.iterations()) { + randomize(&str[0], str.size()); + map.emplace(str, str); + randomize(&str[0], str.size()); + result += map.erase(str); + } + s.set_result(result + map.size()); +} + +static void ins_and_access_cmap_s(picobench::state& s) +{ + cstr str = cstr_with_size(s.arg(), 'x'); + size_t result = 0; + cmap_str map = cmap_str_init(); + cmap_str_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (s.iterations()) { + randomize(str.str, cstr_size(str)); + cmap_str_emplace(&map, str.str, str.str); + randomize(str.str, cstr_size(str)); + result += cmap_str_erase(&map, str.str); + } + s.set_result(result + cmap_str_size(map)); + cstr_del(&str); + cmap_str_del(&map); +} + +#define P samples(S1).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).args({13, 7, 8, 100, 1000}) +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_cmap_s).P; +#undef P + +PICOBENCH_SUITE("Map5"); + +template +static void iterate_x(picobench::state& s) +{ + MapX map; + map.max_load_factor(MaxLoadFactor100 / 100.0); + uint64_t K = (1ull << s.arg()) - 1; + + picobench::scope scope(s); + stc64_srandom(seed); + size_t result = 0; + + // measure insert then iterate whole map + c_forrange (n, s.iterations()) { + map[stc64_random()] = n; + if (!(n & K)) for (auto const& keyVal : map) + result += keyVal.second; + } + + // reset rng back to inital state + stc64_srandom(seed); + + // measure erase then iterate whole map + c_forrange (n, s.iterations()) { + map.erase(stc64_random()); + if (!(n & K)) for (auto const& keyVal : map) + result += keyVal.second; + } + s.set_result(result); +} + +static void iterate_cmap_x(picobench::state& s) +{ + cmap_x map = cmap_x_init(); + cmap_x_set_load_factors(&map, 0.3, MaxLoadFactor100 / 100.0); + uint64_t K = (1ull << s.arg()) - 1; + + picobench::scope scope(s); + stc64_srandom(seed); + size_t result = 0; + + // measure insert then iterate whole map + c_forrange (n, s.iterations()) { + cmap_x_emplace_or_assign(&map, stc64_random(), n); + if (!(n & K)) c_foreach (i, cmap_x, map) + result += i.ref->second; + } + + // reset rng back to inital state + stc64_srandom(seed); + + // measure erase then iterate whole map + c_forrange (n, s.iterations()) { + cmap_x_erase(&map, stc64_random()); + if (!(n & K)) c_foreach (i, cmap_x, map) + result += i.ref->second; + } + s.set_result(result); + cmap_x_del(&map); +} + + +#define P samples(S1).iterations({N1/20}).args({12}) +PICOBENCH(iterate_x).P; +PICOBENCH(iterate_x).P; +PICOBENCH(iterate_x).P; +PICOBENCH(iterate_x).P; +PICOBENCH(iterate_x).P; +PICOBENCH(iterate_x).P; +PICOBENCH(iterate_cmap_x).P; +#undef P diff --git a/benchmarks/shootout2_cmap.cpp b/benchmarks/shootout2_cmap.cpp new file mode 100644 index 00000000..13905a3f --- /dev/null +++ b/benchmarks/shootout2_cmap.cpp @@ -0,0 +1,252 @@ +#include +#include +#include +#include +#include +#include "others/khash.h" + +#ifdef __cplusplus +#include +#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 + +static inline uint32_t fibonacci_hash(const void* data, size_t len) { + return (uint32_t) (((*(const uint64_t *) data) * 11400714819323198485llu) >> 24); +} + +// cmap and khash template expansion +using_cmap(ii, int64_t, int64_t, c_default_equals, fibonacci_hash); // c_default_hash); +KHASH_MAP_INIT_INT64(ii, int64_t) + + +size_t seed; +static const float max_load_factor = 0.77f; + +stc64_t rng; +#define SEED(s) rng = stc64_init(seed) +#define RAND(N) (stc64_rand(&rng) & ((1 << N) - 1)) + + +#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \ + ; cmap_##X##_set_load_factors(&map, 0.0, max_load_factor) +#define CMAP_PUT(X, key, val) cmap_##X##_emplace_or_assign(&map, key, val).first->second +#define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val).first->second +#define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key) +#define CMAP_FIND(X, key) (cmap_##X##_find(map, key) != NULL) +#define CMAP_FOR(X, i) c_foreach (i, cmap_##X, map) +#define CMAP_ITEM(X, i) i.ref->second +#define CMAP_SIZE(X) cmap_##X##_size(map) +#define CMAP_BUCKETS(X) cmap_##X##_bucket_count(map) +#define CMAP_CLEAR(X) cmap_##X##_clear(&map) +#define CMAP_DTOR(X) cmap_##X##_del(&map) + +#define KMAP_SETUP(X, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret +#define KMAP_PUT(X, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) +#define KMAP_EMPLACE(X, key, val) (ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val, 0) : 0, map->vals[ki]) +#define KMAP_ERASE(X, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) +#define KMAP_FIND(X, key) (kh_get(ii, map, key) != kh_end(map)) +#define KMAP_SIZE(X) kh_size(map) +#define KMAP_BUCKETS(X) kh_n_buckets(map) +#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 map; map.max_load_factor(max_load_factor) +#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) (map.find(key) != map.end()) +#define UMAP_ERASE(X, key) map.erase(key) +#define UMAP_FOR(X, i) for (auto i: map) +#define UMAP_ITEM(X, i) i.second +#define UMAP_SIZE(X) map.size() +#define UMAP_BUCKETS(X) map.bucket_count() +#define UMAP_CLEAR(X) map.clear() +#define UMAP_DTOR(X) destroy_me(map) + +#define BMAP_SETUP(X, Key, Value) ska::bytell_hash_map map; map.max_load_factor(max_load_factor) +#define BMAP_PUT(X, key, val) UMAP_PUT(X, key, val) +#define BMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) +#define BMAP_FIND(X, key) UMAP_FIND(X, key) +#define BMAP_ERASE(X, key) UMAP_ERASE(X, key) +#define BMAP_FOR(X, i) UMAP_FOR(X, i) +#define BMAP_ITEM(X, i) UMAP_ITEM(X, i) +#define BMAP_SIZE(X) UMAP_SIZE(X) +#define BMAP_BUCKETS(X) UMAP_BUCKETS(X) +#define BMAP_CLEAR(X) UMAP_CLEAR(X) +#define BMAP_DTOR(X) UMAP_DTOR(X) + +#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map map; map.max_load_factor(max_load_factor) +#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) +#define FMAP_ERASE(X, key) UMAP_ERASE(X, key) +#define FMAP_FOR(X, i) UMAP_FOR(X, i) +#define FMAP_ITEM(X, i) UMAP_ITEM(X, i) +#define FMAP_SIZE(X) UMAP_SIZE(X) +#define FMAP_BUCKETS(X) UMAP_BUCKETS(X) +#define FMAP_CLEAR(X) UMAP_CLEAR(X) +#define FMAP_DTOR(X) UMAP_DTOR(X) + +#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map map; map.max_load_factor(max_load_factor) +#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) +#define HMAP_ERASE(X, key) UMAP_ERASE(X, key) +#define HMAP_FOR(X, i) UMAP_FOR(X, i) +#define HMAP_ITEM(X, i) UMAP_ITEM(X, i) +#define HMAP_SIZE(X) UMAP_SIZE(X) +#define HMAP_BUCKETS(X) UMAP_BUCKETS(X) +#define HMAP_CLEAR(X) UMAP_CLEAR(X) +#define HMAP_DTOR(X) UMAP_DTOR(X) + +#define RMAP_SETUP(X, Key, Value) robin_hood::unordered_map map +#define RMAP_PUT(X, key, val) UMAP_PUT(X, key, val) +#define RMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) +#define RMAP_FIND(X, key) UMAP_FIND(X, key) +#define RMAP_ERASE(X, key) UMAP_ERASE(X, key) +#define RMAP_FOR(X, i) UMAP_FOR(X, i) +#define RMAP_ITEM(X, i) UMAP_ITEM(X, i) +#define RMAP_SIZE(X) UMAP_SIZE(X) +#define RMAP_BUCKETS(X) map.mask() +#define RMAP_CLEAR(X) UMAP_CLEAR(X) +#define RMAP_DTOR(X) UMAP_DTOR(X) + +#define SMAP_SETUP(X, Key, Value) spp::sparse_hash_map map; map.max_load_factor(max_load_factor) +#define SMAP_PUT(X, key, val) UMAP_PUT(X, key, val) +#define SMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) +#define SMAP_FIND(X, key) UMAP_FIND(X, key) +#define SMAP_ERASE(X, key) UMAP_ERASE(X, key) +#define SMAP_FOR(X, i) UMAP_FOR(X, i) +#define SMAP_ITEM(X, i) UMAP_ITEM(X, i) +#define SMAP_SIZE(X) UMAP_SIZE(X) +#define SMAP_BUCKETS(X) UMAP_BUCKETS(X) +#define SMAP_CLEAR(X) UMAP_CLEAR(X) +#define SMAP_DTOR(X) UMAP_DTOR(X) + +enum { + FAC = 3, + N1 = 10000000 * FAC, + N2 = 10000000 * FAC, + N3 = 10000000 * FAC, + N4 = 10000000 * FAC, + RR = 24 +}; +int rr = RR; + + +#define MAP_TEST1(M, X) \ +{ \ + M##_SETUP(X, int64_t, int64_t); \ + uint64_t checksum = 0, erased = 0; \ + SEED(seed); \ + clock_t difference, before = clock(); \ + for (size_t i = 0; i < N1; ++i) { \ + checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ + erased += M##_ERASE(X, RAND(rr)); \ + } \ + difference = clock() - before; \ + printf(#M ": time: %5.02f, sum: %zu, erased %zu, size: %zu, buckets: %8zu\n", \ + (float) difference / CLOCKS_PER_SEC, checksum, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ + M##_CLEAR(X); \ +} + +#define MAP_TEST2(M, X) \ +{ \ + M##_SETUP(X, int64_t, int64_t); \ + size_t erased = 0; \ + clock_t difference, before = clock(); \ + for (size_t i = 0; i < N2; ++i) \ + M##_PUT(X, i, i); \ + for (size_t i = 0; i < N2; ++i) \ + erased += M##_ERASE(X, i); \ + difference = clock() - before; \ + printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ + (float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ + M##_CLEAR(X); \ +} + +#define MAP_TEST3(M, X) \ +{ \ + M##_SETUP(X, int64_t, int64_t); \ + size_t erased = 0; \ + clock_t difference, before = clock(); \ + SEED(seed); \ + for (size_t i = 0; i < N3; ++i) \ + M##_PUT(X, RAND(rr), i); \ + SEED(seed); \ + for (size_t i = 0; i < N3; ++i) \ + erased += M##_ERASE(X, RAND(rr)); \ + difference = clock() - before; \ + printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ + (float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ + M##_CLEAR(X); \ +} + +#define MAP_TEST4(M, X) \ +{ \ + M##_SETUP(X, int64_t, int64_t); \ + size_t sum = 0; \ + SEED(seed); \ + for (size_t i = 0; i < N4; ++i) \ + M##_PUT(X, RAND(rr), i); \ + clock_t difference, before = clock(); \ + for (int k=0; k<5; k++) M##_FOR (X, i) \ + sum += M##_ITEM(X, i); \ + difference = clock() - before; \ + printf(#M ": time: %5.02f, sum %zu, size: %zu, buckets: %8zu\n", \ + (float) difference / CLOCKS_PER_SEC, sum, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ + M##_CLEAR(X); \ +} + +#define MAP_TEST5(M, X) \ +{ \ + M##_SETUP(X, int64_t, int64_t); \ + uint64_t checksum = 0; \ + SEED(seed); \ + clock_t difference, before = clock(); \ + for (size_t i = 0; i < N1; ++i) { \ + checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ + } \ + difference = clock() - before; \ + printf(#M ": time: %5.02f, sum: %zu, size: %zu, buckets: %8zu\n", \ + (float) difference / CLOCKS_PER_SEC, checksum, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ + M##_CLEAR(X); \ +} + +#ifdef __cplusplus +#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)*/ +#define RUNX_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)*/ +#else +#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) +#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii) +#endif + + +int main(int argc, char* argv[]) +{ + rr = argc == 2 ? atoi(argv[1]) : RR; + seed = time(NULL); + + printf("\nUnordered maps: Insert %d random keys:\n", N3); + RUN_TEST(5) + + printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); + printf("\nUnordered maps: %d repeats of Insert random key + try to remove a random key:\n", N1); + RUN_TEST(1) + + printf("\nUnordered maps: Insert %d index keys, then remove them in same order:\n", N2); + RUN_TEST(2) + + printf("\nUnordered maps: Insert %d random keys, then remove them in same order:\n", N3); + RUN_TEST(3) + + printf("\nUnordered maps: Iterate %d random keys:\n", N4); + RUNX_TEST(4) +} diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md index ed8ae3d4..4c40c998 100644 --- a/docs/ccommon_api.md +++ b/docs/ccommon_api.md @@ -1,6 +1,6 @@ # STC [ccommon](../stc/ccommon.h): Common definitions and handy macros -The following handy macros are completely safe to use, i.e. they have no side-effects. +The following handy macros are safe to use, i.e. have no side-effects. ### c_init, c_emplace_items **c_init** declares and initializes any container with an array of elements. **c_emplace_items** adds elements to any existing container: @@ -50,27 +50,26 @@ c_foreach (i, csset_x, it, csset_x_end(&set)) printf(" %d", *i.ref); ``` ### c_withfile, c_breakwith -Simplifies reading a file. Use **c_breakwith** if you need to break out of the block. Example: +Simplifies reading a file. Use only **c_breakwith** to break out of the block if needed. Example: ```c -// Put each line of a text file into a vector of strings +// Load each line of a text file into a vector of strings #include #include #include using_cvec_str(); -cvec_str // on return, check global errno variable for errors -readFile(const char* name) { +cvec_str readFile(const char* name) { cvec_str vec = cvec_str_init(); - // Next line handles declaring, opening, and closing a FILE* - c_withfile (f, fopen(name, "r")) { - cstr_t line = cstr_inits; - while (cstr_getline(&line, f)) + // Next line declares, opens, and closes the FILE* + c_withfile (fp, fopen(name, "r")) { + cstr_t line = cstr_init(); + while (cstr_getline(&line, fp)) cvec_str_emplace_back(&vec, line.str); cstr_del(&line); } - return vec; + return vec; // receiver should check errno variable } ``` @@ -94,4 +93,4 @@ Memory allocator for the entire library. Macros can be overloaded by the user. ### c_swap, c_arraylen - **c_swap(type, x, y)**: Simple macro for swapping internals of two objects. -- **c_arraylen(array)**: Return number of elements in an array, e.g. `int array[] = {1, 2, 3, 4}; +- **c_arraylen(array)**: Return number of elements in an array, e.g. `int array[] = {1, 2, 3, 4};` diff --git a/docs/cstr_api.md b/docs/cstr_api.md index de20e89e..11cd1214 100644 --- a/docs/cstr_api.md +++ b/docs/cstr_api.md @@ -91,7 +91,7 @@ Helper methods, used by other container types. | Type name | Type definition | Used to represent... | |:------------------|:---------------------------------|:-------------------------| -| `cstr, cstr_t` | `struct { const char *str; }` | The string type | +| `cstr` | `struct { const char *str; }` | The string type | | `cstr_value_t` | `char` | The string element type | | `cstr_iter_t` | `struct { cstr_value_t *ref; }` | cstr iterator | @@ -99,8 +99,7 @@ Helper methods, used by other container types. | Name | Value | |:------------------|:-----------------| -| `cstr_inits` | `{...}` | -| `cstr_npos` | `-1ull` | +| `cstr_npos` | `(-1ull)` | ## Example ```c diff --git a/examples/crandom_ex.c b/examples/crandom_ex.c index c923debd..4fa1d487 100644 --- a/examples/crandom_ex.c +++ b/examples/crandom_ex.c @@ -22,7 +22,7 @@ int main() sum += n; if (n >= 0 && n < R) ++hist[n]; } - cstr_t bar = cstr_inits; + cstr bar = cstr_init(); c_forrange (i, int, R) { cstr_resize(&bar, hist[i] * 25ull * R / N2, '*'); printf("%3d %s\n", i, bar.str); diff --git a/examples/demos.c b/examples/demos.c index f60355e2..4eac761c 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -8,7 +8,7 @@ void stringdemo1() { printf("\nSTRINGDEMO1\n"); - cstr_t cs = cstr_from("one-nine-three-seven-five"); + cstr cs = cstr_from("one-nine-three-seven-five"); printf("%s.\n", cs.str); cstr_insert(&cs, 3, "-two"); diff --git a/examples/ex_gauss1.c b/examples/ex_gauss1.c index 8ef08694..6536527d 100644 --- a/examples/ex_gauss1.c +++ b/examples/ex_gauss1.c @@ -41,7 +41,7 @@ int main() cvec_e_sort(&vhist); // Print the gaussian bar chart - cstr_t bar = cstr_init(); + cstr bar = cstr_init(); c_foreach (i, cvec_e, vhist) { size_t n = (size_t) (i.ref->second * StdDev * Scale * 2.5 / N); if (n > 0) { diff --git a/examples/ex_gauss2.c b/examples/ex_gauss2.c index e20c1768..616d7071 100644 --- a/examples/ex_gauss2.c +++ b/examples/ex_gauss2.c @@ -28,7 +28,7 @@ int main() } // Print the gaussian bar chart - cstr_t bar = cstr_init(); + cstr bar = cstr_init(); c_foreach (i, csmap_i, mhist) { size_t n = (size_t) (i.ref->second * StdDev * Scale * 2.5 / N); if (n > 0) { diff --git a/examples/random.c b/examples/random.c index c923debd..4fa1d487 100644 --- a/examples/random.c +++ b/examples/random.c @@ -22,7 +22,7 @@ int main() sum += n; if (n >= 0 && n < R) ++hist[n]; } - cstr_t bar = cstr_inits; + cstr bar = cstr_init(); c_forrange (i, int, R) { cstr_resize(&bar, hist[i] * 25ull * R / N2, '*'); printf("%3d %s\n", i, bar.str); diff --git a/examples/replace.c b/examples/replace.c index 53e916fc..fdf5a7df 100644 --- a/examples/replace.c +++ b/examples/replace.c @@ -11,9 +11,9 @@ int main () // replace signatures used in the same order as described above: // Ustring positions: 0123456789*123456789*12345 - cstr_t s = cstr_from(base); // "this is a test string." + cstr s = cstr_from(base); // "this is a test string." - cstr_t m = cstr_clone(s); + cstr m = cstr_clone(s); cstr_append(&m, m.str); cstr_append(&m, m.str); printf("%s\n", m.str); -- cgit v1.2.3