From 78cb61301df13fee995d3afd1bd1d8d63310d819 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 17 Jul 2022 01:48:22 +0200 Subject: Tuned benchmark shootout_hashmaps.cpp and updated two external c++ hash tables to newest. Updated benchmarks/build_all.sh --- benchmarks/build_all.sh | 15 +- benchmarks/external/ankerl/unordered_dense.h | 226 +++++++++++++++++++-------- benchmarks/external/emhash/hash_table7.hpp | 7 +- benchmarks/shootout_hashmaps.cpp | 80 ++++++---- examples/new_pque.c | 12 +- 5 files changed, 213 insertions(+), 127 deletions(-) diff --git a/benchmarks/build_all.sh b/benchmarks/build_all.sh index e974b2cb..657f8cbf 100644 --- a/benchmarks/build_all.sh +++ b/benchmarks/build_all.sh @@ -1,10 +1,7 @@ #!/bin/bash -cc='g++ -Wall -pedantic -x c++ -std=c++20' -#cc='clang++ -Wall -pedantic -x c++ -std=c++20' -#cc='clang++ -Wall -pedantic -x c++ -std=c++20 -c -DSTC_HEADER' -#cc='cl -nologo' -#cc='cl -nologo -TP' -#cc='cl -nologo -std:c11' +cc='g++ -I../include -s -O3 -Wall -pedantic -x c++ -std=c++20' +#cc='clang++ -I../include -s -O3 -Wall -pedantic -x c++ -std=c++20' +#cc='cl -nologo -I../include -O2 -TP -EHsc -std:c++20' run=0 if [ "$1" == '-h' -o "$1" == '--help' ]; then echo usage: runall.sh [-run] [compiler + options] @@ -19,8 +16,8 @@ if [ ! -z "$1" ] ; then fi if [ $run = 0 ] ; then for i in *.cpp misc/*.c* picobench/*.cpp plotbench/*.cpp ; do - echo $cc -I../include $i - $cc -I../include $i + echo $cc -I../include $i -o $(basename -s .cpp $i).exe + $cc -I../include $i -o $(basename -s .cpp $i).exe done else for i in misc/*.c* picobench/*.cpp ; do @@ -32,4 +29,4 @@ else done fi -rm -f a.out *.o *.obj *.exe +rm -f a.out *.o *.obj # *.exe diff --git a/benchmarks/external/ankerl/unordered_dense.h b/benchmarks/external/ankerl/unordered_dense.h index 36d48f8e..304ef3bc 100644 --- a/benchmarks/external/ankerl/unordered_dense.h +++ b/benchmarks/external/ankerl/unordered_dense.h @@ -1,7 +1,7 @@ ///////////////////////// ankerl::unordered_dense::{map, set} ///////////////////////// // A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion. -// Version 1.0.0 +// Version 1.0.2 // https://github.com/martinus/unordered_dense // // Licensed under the MIT License . @@ -32,44 +32,48 @@ // see https://semver.org/spec/v2.0.0.html #define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 1 // incompatible API changes #define ANKERL_UNORDERED_DENSE_VERSION_MINOR 0 // add functionality in a backwards compatible manner -#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // backwards compatible bug fixes - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#define ANKERL_UNORDERED_DENSE_PMR 0 -#if defined(__has_include) -# if __has_include() -# undef ANKERL_UNORDERED_DENSE_PMR -# define ANKERL_UNORDERED_DENSE_PMR 1 -# include +#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 2 // backwards compatible bug fixes + +#if 0 // __cplusplus < 201703L +# error ankerl::unordered_dense requires C++17 or higher +#else + +# include +# include +# include +# include +# include +# include +# include +# include +# include +# include +# include +# include +# include +# include + +# define ANKERL_UNORDERED_DENSE_PMR 0 +# if defined(__has_include) +# if __has_include() +# undef ANKERL_UNORDERED_DENSE_PMR +# define ANKERL_UNORDERED_DENSE_PMR 1 +# include +# endif # endif -#endif -#if defined(_MSC_VER) && defined(_M_X64) -# include -# pragma intrinsic(_umul128) -#endif +# if defined(_MSC_VER) && defined(_M_X64) +# include +# pragma intrinsic(_umul128) +# endif -#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__) -# define ANKERL_UNORDERED_DENSE_LIKELY(x) __builtin_expect(x, 1) -# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) __builtin_expect(x, 0) -#else -# define ANKERL_UNORDERED_DENSE_LIKELY(x) (x) -# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) (x) -#endif +# if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__) +# define ANKERL_UNORDERED_DENSE_LIKELY(x) __builtin_expect(x, 1) +# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) __builtin_expect(x, 0) +# else +# define ANKERL_UNORDERED_DENSE_LIKELY(x) (x) +# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) (x) +# endif namespace ankerl::unordered_dense { @@ -81,14 +85,14 @@ namespace ankerl::unordered_dense { namespace detail::wyhash { static inline void mum(uint64_t* a, uint64_t* b) { -#if defined(__SIZEOF_INT128__) +# if defined(__SIZEOF_INT128__) __uint128_t r = *a; r *= *b; *a = static_cast(r); *b = static_cast(r >> 64U); -#elif defined(_MSC_VER) && defined(_M_X64) +# elif defined(_MSC_VER) && defined(_M_X64) *a = _umul128(*a, *b, b); -#else +# else uint64_t ha = *a >> 32U; uint64_t hb = *b >> 32U; uint64_t la = static_cast(*a); @@ -106,7 +110,7 @@ static inline void mum(uint64_t* a, uint64_t* b) { hi = rh + (rm0 >> 32U) + (rm1 >> 32U) + c; *a = lo; *b = hi; -#endif +# endif } // multiply and xor mix function, aka MUM @@ -133,7 +137,7 @@ static inline void mum(uint64_t* a, uint64_t* b) { return (static_cast(p[0]) << 16U) | (static_cast(p[k >> 1U]) << 8U) | p[k - 1]; } -[[nodiscard]] inline auto hash(void const* key, size_t len) -> uint64_t { +[[nodiscard]] static inline auto hash(void const* key, size_t len) -> uint64_t { static constexpr auto secret = std::array{UINT64_C(0xa0761d6478bd642f), UINT64_C(0xe7037ed1a0b428db), UINT64_C(0x8ebc6af09c88c6e3), @@ -180,6 +184,10 @@ static inline void mum(uint64_t* a, uint64_t* b) { return mix(secret[1] ^ len, mix(a ^ secret[1], b ^ seed)); } +[[nodiscard]] static inline auto hash(uint64_t x) -> uint64_t { + return detail::wyhash::mix(x, UINT64_C(0x9E3779B97F4A7C15)); +} + } // namespace detail::wyhash template @@ -187,7 +195,7 @@ struct hash : public std::hash { using is_avalanching = void; auto operator()(T const& obj) const noexcept(noexcept(std::declval>().operator()(std::declval()))) -> size_t { - return detail::wyhash::mix(std::hash::operator()(obj), UINT64_C(0x9E3779B97F4A7C15)); + return static_cast(detail::wyhash::hash(std::hash::operator()(obj))); } }; @@ -195,7 +203,7 @@ template struct hash> { using is_avalanching = void; auto operator()(std::basic_string const& str) const noexcept -> size_t { - return detail::wyhash::hash(str.data(), sizeof(CharT) * str.size()); + return static_cast(detail::wyhash::hash(str.data(), sizeof(CharT) * str.size())); } }; @@ -203,10 +211,80 @@ template struct hash> { using is_avalanching = void; auto operator()(std::basic_string_view const& sv) const noexcept -> size_t { - return detail::wyhash::hash(sv.data(), sizeof(CharT) * sv.size()); + return static_cast(detail::wyhash::hash(sv.data(), sizeof(CharT) * sv.size())); + } +}; + +template +struct hash { + using is_avalanching = void; + auto operator()(T* ptr) const noexcept -> size_t { + return static_cast(detail::wyhash::hash(reinterpret_cast(ptr))); } }; +template +struct hash> { + using is_avalanching = void; + auto operator()(std::unique_ptr const& ptr) const noexcept -> size_t { + return static_cast(detail::wyhash::hash(reinterpret_cast(ptr.get()))); + } +}; + +template +struct hash> { + using is_avalanching = void; + auto operator()(std::shared_ptr const& ptr) const noexcept -> size_t { + return static_cast(detail::wyhash::hash(reinterpret_cast(ptr.get()))); + } +}; + +template +struct hash::value>::type> { + using is_avalanching = void; + auto operator()(Enum e) const noexcept -> size_t { + using Underlying = typename std::underlying_type_t; + return static_cast(detail::wyhash::hash(static_cast(e))); + } +}; + +# define ANKERL_UNORDERED_DENSE_HASH_STATICCAST(T) \ + template <> \ + struct hash { \ + using is_avalanching = void; \ + auto operator()(T const& obj) const noexcept -> size_t { \ + return static_cast(detail::wyhash::hash(static_cast(obj))); \ + } \ + } + +# if defined(__GNUC__) && !defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wuseless-cast" +# endif +// see https://en.cppreference.com/w/cpp/utility/hash +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(bool); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(signed char); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned char); +# if __cplusplus >= 202002L +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char8_t); +# endif +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char16_t); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char32_t); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(wchar_t); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(short); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned short); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(int); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned int); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(long); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(long long); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned long); +ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned long long); + +# if defined(__GNUC__) && !defined(__clang__) +# pragma GCC diagnostic pop +# endif + namespace detail { struct nonesuch {}; @@ -255,7 +333,7 @@ class table { static constexpr uint32_t BUCKET_DIST_INC = 1U << 8U; // skip 1 byte fingerprint static constexpr uint32_t BUCKET_FINGERPRINT_MASK = BUCKET_DIST_INC - 1; // mask for 1 byte of fingerprint static constexpr uint8_t INITIAL_SHIFTS = 64 - 3; // 2^(64-m_shift) number of buckets - static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.8; + static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.8F; public: using key_type = Key; @@ -303,7 +381,7 @@ private: if constexpr (is_detected_v) { return m_hash(key); } else { - return wyhash::mix(m_hash(key), UINT64_C(0x9E3779B97F4A7C15)); + return wyhash::hash(m_hash(key)); } } @@ -400,12 +478,14 @@ private: } void clear_buckets() { - std::memset(m_buckets_start, 0, sizeof(Bucket) * bucket_count()); + if (m_buckets_start != nullptr) { + std::memset(m_buckets_start, 0, sizeof(Bucket) * bucket_count()); + } } void clear_and_fill_buckets_from_values() { clear_buckets(); - for (uint32_t value_idx = 0, end_idx = m_values.size(); value_idx < end_idx; ++value_idx) { + for (uint32_t value_idx = 0, end_idx = static_cast(m_values.size()); value_idx < end_idx; ++value_idx) { auto const& key = get_key(m_values[value_idx]); auto [dist_and_fingerprint, bucket] = next_while_less(key); @@ -453,6 +533,10 @@ private: template auto do_erase_key(K&& key) -> size_t { + if (empty()) { + return 0; + } + auto [dist_and_fingerprint, bucket] = next_while_less(key); while (dist_and_fingerprint == bucket->dist_and_fingerprint && !m_equal(key, get_key(m_values[bucket->value_idx]))) { @@ -839,7 +923,7 @@ public: } do_erase(bucket); - return it; + return begin() + value_idx_to_remove; } auto erase(const_iterator it) -> iterator { @@ -847,24 +931,27 @@ public: } auto erase(const_iterator first, const_iterator last) -> iterator { - auto const it_ret = begin() + (first - cbegin()); - - auto first_to_last = std::distance(first, last); - auto last_to_end = std::distance(last, cend()); + auto const idx_first = first - cbegin(); + auto const idx_last = last - cbegin(); + auto const first_to_last = std::distance(first, last); + auto const last_to_end = std::distance(last, cend()); // remove elements from left to right which moves elements from the end back - auto const mid = first + std::min(first_to_last, last_to_end); - while (first != mid) { - erase(first); - ++first; + auto const mid = idx_first + std::min(first_to_last, last_to_end); + auto idx = idx_first; + while (idx != mid) { + erase(begin() + idx); + ++idx; } // all elements from the right are moved, now remove the last element until all done - while (last != mid) { - erase(--last); + idx = idx_last; + while (idx != mid) { + --idx; + erase(begin() + idx); } - return it_ret; + return begin() + idx_first; } auto erase(Key const& key) -> size_t { @@ -1064,7 +1151,7 @@ using map = detail::table; template , class KeyEqual = std::equal_to, class Allocator = std::allocator> using set = detail::table; -#if ANKERL_UNORDERED_DENSE_PMR +# if ANKERL_UNORDERED_DENSE_PMR namespace pmr { @@ -1076,7 +1163,7 @@ using set = detail::table auto erase_if(ankerl::unordered_dense::detail::table& map, Pred pred) -> size_t { // going back to front because erase() invalidates the end iterator - auto old_size = map.size(); - - auto back_it = map.end(); - while (map.begin() != back_it) { - --back_it; - if (pred(*back_it)) { - map.erase(back_it); + auto const old_size = map.size(); + auto idx = old_size; + while (idx) { + --idx; + auto it = map.begin() + idx; + if (pred(*it)) { + map.erase(it); } } @@ -1107,3 +1194,4 @@ auto erase_if(ankerl::unordered_dense::detail::table inline void std_destroy(C& c) { C().swap(c); } @@ -25,12 +25,15 @@ template using robin_hood_flat_map = robin_hood::unordered_fl K, V, robin_hood::hash, std::equal_to, MAX_LOAD_FACTOR>; #endif +typedef int64_t IKey; +typedef int64_t IValue; + // khash template expansion -KHASH_MAP_INIT_INT64(ii, int64_t) +KHASH_MAP_INIT_INT64(ii, IValue) // cmap template expansion -#define i_key int64_t -#define i_val int64_t +#define i_key IKey +#define i_val IValue #define i_size uint32_t // optional, enables 2x expand #define i_hash(x) (*x * 0xc6a4a7935bd1e99d) // optional #define i_tag ii @@ -39,8 +42,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define SEED(s) rng = stc64_new(s) #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/100.0f) +#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init(); \ + cmap_##X##_max_load_factor(&map, MAX_LOAD_FACTOR/100.0f) #define CMAP_PUT(X, key, val) cmap_##X##_insert_or_assign(&map, key, val).ref->second #define CMAP_EMPLACE(X, key, val) cmap_##X##_insert(&map, key, val).ref->second #define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key) @@ -53,10 +56,14 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define CMAP_DTOR(X) cmap_##X##_drop(&map) #define KMAP_SETUP(X, Key, Value) khash_t(X)* map = kh_init(X); khiter_t ki; int ret -#define KMAP_PUT(X, key, val) (ki = kh_put(X, map, key, &ret), map->vals[ki] = val, map->vals[ki]) -#define KMAP_EMPLACE(X, key, val) (ki = kh_put(X, map, key, &ret), ret ? (map->vals[ki] = val, 0) : 1, map->vals[ki]) -#define KMAP_ERASE(X, key) ((ki = kh_get(X, map, key)) != kh_end(map) ? kh_del(X, map, ki), 1 : 0) -#define KMAP_FOR(X, i) for (khint_t i = kh_begin(map); i != kh_end(map); ++i) if (kh_exist(map, i)) +#define KMAP_PUT(X, key, val) (ki = kh_put(X, map, key, &ret), \ + map->vals[ki] = val, map->vals[ki]) +#define KMAP_EMPLACE(X, key, val) (ki = kh_put(X, map, key, &ret), \ + (ret ? map->vals[ki] = val, 1 : 0), map->vals[ki]) +#define KMAP_ERASE(X, key) (ki = kh_get(X, map, key), \ + ki != kh_end(map) ? (kh_del(X, map, ki), 1) : 0) +#define KMAP_FOR(X, i) for (khint_t i = kh_begin(map); i != kh_end(map); ++i) \ + if (kh_exist(map, i)) #define KMAP_ITEM(X, i) map->vals[i] #define KMAP_FIND(X, key) (kh_get(X, map, key) != kh_end(map)) #define KMAP_SIZE(X) kh_size(map) @@ -64,7 +71,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define KMAP_CLEAR(X) kh_clear(X, map) #define KMAP_DTOR(X) kh_destroy(X, map) -#define UMAP_SETUP(X, Key, Value) std::unordered_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) +#define UMAP_SETUP(X, Key, Value) std::unordered_map 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()) @@ -76,7 +84,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define UMAP_CLEAR(X) map.clear() #define UMAP_DTOR(X) std_destroy(map) -#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) +#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map 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) @@ -88,7 +97,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #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/100.0f) +#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map 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) map.emplace(key, val).first.value() #define HMAP_FIND(X, key) UMAP_FIND(X, key) @@ -100,7 +110,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define HMAP_CLEAR(X) UMAP_CLEAR(X) #define HMAP_DTOR(X) UMAP_DTOR(X) -#define TMAP_SETUP(X, Key, Value) tsl::robin_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) +#define TMAP_SETUP(X, Key, Value) tsl::robin_map map; \ + map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define TMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define TMAP_EMPLACE(X, key, val) map.emplace(key, val).first.value() #define TMAP_FIND(X, key) UMAP_FIND(X, key) @@ -124,7 +135,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define RMAP_CLEAR(X) UMAP_CLEAR(X) #define RMAP_DTOR(X) UMAP_DTOR(X) -#define DMAP_SETUP(X, Key, Value) ankerl::unordered_dense::map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) +#define DMAP_SETUP(X, Key, Value) ankerl::unordered_dense::map map; \ + map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define DMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define DMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) #define DMAP_FIND(X, key) UMAP_FIND(X, key) @@ -136,7 +148,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define DMAP_CLEAR(X) UMAP_CLEAR(X) #define DMAP_DTOR(X) UMAP_DTOR(X) -#define EMAP_SETUP(X, Key, Value) emhash7::HashMap map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) +#define EMAP_SETUP(X, Key, Value) emhash7::HashMap map; \ + map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define EMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define EMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) #define EMAP_FIND(X, key) UMAP_FIND(X, key) @@ -148,7 +161,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define EMAP_CLEAR(X) UMAP_CLEAR(X) #define EMAP_DTOR(X) UMAP_DTOR(X) -#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) +#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map 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) @@ -163,12 +177,12 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define MAP_TEST1(M, X, n) \ { /* Insert, update */ \ - M##_SETUP(X, int64_t, int64_t); \ + M##_SETUP(X, IKey, IValue); \ uint64_t sum = 0; \ SEED(seed); \ clock_t difference, before = clock(); \ for (size_t i = 0; i < n; ++i) { \ - sum += ++ M##_EMPLACE(X, RAND(keybits), i); \ + sum += ++ M##_PUT(X, RAND(keybits), i); \ } \ difference = clock() - before; \ printf(#M ": time: %5.03f, size: %" PRIuMAX ", buckets: %8" PRIuMAX ", sum: %" PRIuMAX "\n", \ @@ -178,11 +192,11 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define MAP_TEST2(M, X, n) \ { /* Insert sequential keys, then erase them */ \ - M##_SETUP(X, int64_t, int64_t); \ + M##_SETUP(X, IKey, IValue); \ size_t erased = 0; \ clock_t difference, before = clock(); \ for (size_t i = 0; i < n; ++i) \ - M##_PUT(X, i, i); \ + M##_EMPLACE(X, i, i); \ for (size_t i = 0; i < n; ++i) \ erased += M##_ERASE(X, i); \ difference = clock() - before; \ @@ -193,12 +207,12 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define MAP_TEST3(M, X, n) \ { /* Erase elements */ \ - M##_SETUP(X, int64_t, int64_t); \ + M##_SETUP(X, IKey, IValue); \ size_t erased = 0; \ clock_t difference, before; \ SEED(seed); \ for (size_t i = 0; i < n; ++i) \ - M##_PUT(X, RAND(keybits), i); \ + M##_EMPLACE(X, RAND(keybits), i); \ SEED(seed); \ before = clock(); \ for (size_t i = 0; i < n; ++i) \ @@ -211,33 +225,33 @@ KHASH_MAP_INIT_INT64(ii, int64_t) #define MAP_TEST4(M, X, n) \ { /* Iterate */ \ - M##_SETUP(X, int64_t, int64_t); \ + M##_SETUP(X, IKey, IValue); \ size_t sum = 0, m = 1ull << (keybits + 1), nn = n; \ if (nn < m) m = nn; \ SEED(seed); \ for (size_t i = 0; i < m; ++i) \ - M##_PUT(X, RAND(keybits), i); \ - size_t x = 100000000/M##_SIZE(X); \ + M##_EMPLACE(X, RAND(keybits), i); \ + size_t rep = 70000000/M##_SIZE(X); \ clock_t difference, before = clock(); \ - for (size_t k=0; k < x; k++) M##_FOR (X, it) \ + for (size_t k=0; k < rep; k++) M##_FOR (X, it) \ sum += M##_ITEM(X, it); \ difference = clock() - before; \ printf(#M ": time: %5.03f, size: %" PRIuMAX ", buckets: %8" PRIuMAX ", repeats: %" PRIuMAX ", sum: %" PRIuMAX "\n", \ - (float) difference / CLOCKS_PER_SEC, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X), x, sum); \ + (float) difference / CLOCKS_PER_SEC, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X), rep, sum); \ M##_DTOR(X); \ } #define MAP_TEST5(M, X, n) \ { /* Lookup */ \ - M##_SETUP(X, int64_t, int64_t); \ + M##_SETUP(X, IKey, IValue); \ size_t found = 0, m = 1ull << (keybits + 1), nn = n; \ clock_t difference, before; \ if (nn < m) m = nn; \ SEED(seed); \ for (size_t i = 0; i < m; ++i) \ - M##_PUT(X, RAND(keybits), i); \ + M##_EMPLACE(X, RAND(keybits), i); \ before = clock(); \ - size_t x = m * 8000000/M##_SIZE(X); \ + size_t x = m * 3000000/M##_SIZE(X); \ for (size_t i = 0; i < x; ++i) \ found += M##_FIND(X, RAND(keybits)); \ SEED(seed); \ @@ -269,7 +283,7 @@ int main(int argc, char* argv[]) unsigned n_mill = argc >= 2 ? atoi(argv[1]) : DEFAULT_N_MILL; unsigned keybits = argc >= 3 ? atoi(argv[2]) : DEFAULT_KEYBITS; unsigned n = n_mill * 1000000; - unsigned N1 = n/2, N2 = n/2, N3 = n, N4 = n, N5 = n/2; + unsigned N1 = n/2, N2 = n/2, N3 = n, N4 = n, N5 = n; stc64_t rng; size_t seed = time(NULL); diff --git a/examples/new_pque.c b/examples/new_pque.c index 1f968f4c..b6226582 100644 --- a/examples/new_pque.c +++ b/examples/new_pque.c @@ -1,15 +1,7 @@ -#include - -forward_cpque(cpque_pnt, struct Point); - -struct MyStruct { - cpque_pnt priority_queue; - int id; -}; +#include #define i_val int #include - #define i_val int #include @@ -22,11 +14,9 @@ int Point_cmp(const Point* a, const Point* b) { #define i_val Point #define i_cmp Point_cmp -#define i_opt c_is_fwd #define i_tag pnt #include -#include int main() { -- cgit v1.2.3