diff options
| -rw-r--r-- | misc/benchmarks/external/ankerl/unordered_dense.h | 56 | ||||
| -rw-r--r-- | misc/benchmarks/external/emhash/hash_table7.hpp | 64 | ||||
| -rw-r--r-- | misc/benchmarks/external/tsl/robin_hash.h | 18 | ||||
| -rw-r--r-- | misc/examples/lower_bound.c | 52 |
4 files changed, 109 insertions, 81 deletions
diff --git a/misc/benchmarks/external/ankerl/unordered_dense.h b/misc/benchmarks/external/ankerl/unordered_dense.h index ff902ad4..05c7e928 100644 --- a/misc/benchmarks/external/ankerl/unordered_dense.h +++ b/misc/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 2.0.0 +// Version 3.0.0 // https://github.com/martinus/unordered_dense // // Licensed under the MIT License <http://opensource.org/licenses/MIT>. @@ -30,7 +30,7 @@ #define ANKERL_UNORDERED_DENSE_H // see https://semver.org/spec/v2.0.0.html -#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 2 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes +#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 3 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes #define ANKERL_UNORDERED_DENSE_VERSION_MINOR 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality #define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes @@ -363,6 +363,9 @@ using detect_is_transparent = typename T::is_transparent; template <typename T> using detect_iterator = typename T::iterator; +template <typename T> +using detect_reserve = decltype(std::declval<T&>().reserve(size_t{})); + // enable_if helpers template <typename Mapped> @@ -374,6 +377,18 @@ constexpr bool is_transparent_v = is_detected_v<detect_is_transparent, Hash>&& i template <typename From, typename To1, typename To2> constexpr bool is_neither_convertible_v = !std::is_convertible_v<From, To1> && !std::is_convertible_v<From, To2>; +template <typename T> +constexpr bool has_reserve = is_detected_v<detect_reserve, T>; + +// base type for map has mapped_type +template <class T> +struct base_table_type_map { + using mapped_type = T; +}; + +// base type for set doesn't have mapped_type +struct base_table_type_set {}; + // This is it, the table. Doubles as map and set, and uses `void` for T when its used as a set. template <class Key, class T, // when void, treat it as a set. @@ -381,12 +396,12 @@ template <class Key, class KeyEqual, class AllocatorOrContainer, class Bucket> -class table { +class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, base_table_type_set> { public: using value_container_type = std::conditional_t< is_detected_v<detect_iterator, AllocatorOrContainer>, AllocatorOrContainer, - typename std::vector<typename std::conditional_t<std::is_void_v<T>, Key, std::pair<Key, T>>, AllocatorOrContainer>>; + typename std::vector<typename std::conditional_t<is_map_v<T>, std::pair<Key, T>, Key>, AllocatorOrContainer>>; private: using bucket_alloc = @@ -398,7 +413,6 @@ private: public: using key_type = Key; - using mapped_type = T; using value_type = typename value_container_type::value_type; using size_type = typename value_container_type::size_type; using difference_type = typename value_container_type::difference_type; @@ -409,8 +423,8 @@ public: using const_reference = typename value_container_type::const_reference; using pointer = typename value_container_type::pointer; using const_pointer = typename value_container_type::const_pointer; - using iterator = typename value_container_type::iterator; using const_iterator = typename value_container_type::const_iterator; + using iterator = std::conditional_t<is_map_v<T>, typename value_container_type::iterator, const_iterator>; using bucket_type = Bucket; private: @@ -477,10 +491,10 @@ private: } [[nodiscard]] static constexpr auto get_key(value_type const& vt) -> key_type const& { - if constexpr (std::is_void_v<T>) { - return vt; - } else { + if constexpr (is_map_v<T>) { return vt.first; + } else { + return vt; } } @@ -746,13 +760,17 @@ public: table() : table(0) {} - explicit table(size_t /*bucket_count*/, + explicit table(size_t bucket_count, Hash const& hash = Hash(), KeyEqual const& equal = KeyEqual(), allocator_type const& alloc_or_container = allocator_type()) : m_values(alloc_or_container) , m_hash(hash) - , m_equal(equal) {} + , m_equal(equal) { + if (0 != bucket_count) { + reserve(bucket_count); + } + } table(size_t bucket_count, allocator_type const& alloc) : table(bucket_count, Hash(), KeyEqual(), alloc) {} @@ -1184,6 +1202,7 @@ public: return begin() + static_cast<difference_type>(value_idx_to_remove); } + template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true> auto erase(const_iterator it) -> iterator { return erase(begin() + (it - cbegin())); } @@ -1375,7 +1394,10 @@ public: void reserve(size_t capa) { capa = std::min(capa, max_size()); - m_values.reserve(capa); + if constexpr (has_reserve<value_container_type>) { + // std::deque doesn't have reserve(). Make sure we only call when available + m_values.reserve(capa); + } auto shifts = calc_shifts_for_size(std::max(capa, size())); if (0 == m_num_buckets || shifts < m_shifts) { m_shifts = shifts; @@ -1411,14 +1433,14 @@ public: } for (auto const& b_entry : b) { auto it = a.find(get_key(b_entry)); - if constexpr (std::is_void_v<T>) { - // set: only check that the key is here - if (a.end() == it) { + if constexpr (is_map_v<T>) { + // map: check that key is here, then also check that value is the same + if (a.end() == it || !(b_entry.second == it->second)) { return false; } } else { - // map: check that key is here, then also check that value is the same - if (a.end() == it || !(b_entry.second == it->second)) { + // set: only check that the key is here + if (a.end() == it) { return false; } } diff --git a/misc/benchmarks/external/emhash/hash_table7.hpp b/misc/benchmarks/external/emhash/hash_table7.hpp index fdc33fe1..ced0f1d0 100644 --- a/misc/benchmarks/external/emhash/hash_table7.hpp +++ b/misc/benchmarks/external/emhash/hash_table7.hpp @@ -171,7 +171,7 @@ static_assert((int)INACTIVE < 0, "INACTIVE must negative (to int)"); #endif //count the leading zero bit -inline static int CTZ(size_t n) +static int CTZ(size_t n) { #if defined(__x86_64__) || defined(_WIN32) || (__BYTE_ORDER__ && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) @@ -418,7 +418,7 @@ public: private: void goto_next_element() { - if (EMH_LIKELY(_bmask != 0)) { + if (_bmask != 0) { _bucket = _from + CTZ(_bmask); return; } @@ -502,7 +502,7 @@ public: void goto_next_element() { _bmask &= _bmask - 1; - if (EMH_LIKELY(_bmask != 0)) { + if (_bmask != 0) { _bucket = _from + CTZ(_bmask); return; } @@ -718,30 +718,30 @@ public: return {this, bucket, true}; } - const_iterator begin() const noexcept { return cbegin(); } + inline const_iterator begin() const noexcept { return cbegin(); } - iterator end() noexcept { return {this, _num_buckets}; } - const_iterator cend() const { return {this, _num_buckets}; } - const_iterator end() const { return cend(); } + inline iterator end() noexcept { return {this, _num_buckets}; } + inline const_iterator cend() const { return {this, _num_buckets}; } + inline const_iterator end() const { return cend(); } - size_type size() const { return _num_filled; } - bool empty() const { return _num_filled == 0; } + inline size_type size() const { return _num_filled; } + inline bool empty() const { return _num_filled == 0; } - size_type bucket_count() const { return _num_buckets; } - float load_factor() const { return static_cast<float>(_num_filled) / (_mask + 1); } + inline size_type bucket_count() const { return _num_buckets; } + inline float load_factor() const { return static_cast<float>(_num_filled) / (_mask + 1); } - HashT& hash_function() const { return _hasher; } - EqT& key_eq() const { return _eq; } + inline HashT& hash_function() const { return _hasher; } + inline EqT& key_eq() const { return _eq; } - void max_load_factor(float mlf) + inline void max_load_factor(float mlf) { if (mlf < 0.999f && mlf > EMH_MIN_LOAD_FACTOR) _mlf = (uint32_t)((1 << 27) / mlf); } - constexpr float max_load_factor() const { return (1 << 27) / (float)_mlf; } - constexpr size_type max_size() const { return 1ull << (sizeof(size_type) * 8 - 1); } - constexpr size_type max_bucket_count() const { return max_size(); } + inline constexpr float max_load_factor() const { return (1 << 27) / (float)_mlf; } + inline constexpr size_type max_size() const { return 1ull << (sizeof(size_type) * 8 - 1); } + inline constexpr size_type max_bucket_count() const { return max_size(); } size_type bucket_main() const { @@ -913,25 +913,25 @@ public: // ------------------------------------------------------------ template<typename Key = KeyT> - iterator find(const Key& key, size_t key_hash) noexcept + inline iterator find(const Key& key, size_t key_hash) noexcept { return {this, find_filled_hash(key, key_hash)}; } template<typename Key = KeyT> - const_iterator find(const Key& key, size_t key_hash) const noexcept + inline const_iterator find(const Key& key, size_t key_hash) const noexcept { return {this, find_filled_hash(key, key_hash)}; } template<typename Key=KeyT> - iterator find(const Key& key) noexcept + inline iterator find(const Key& key) noexcept { return {this, find_filled_bucket(key)}; } template<typename Key = KeyT> - const_iterator find(const Key& key) const noexcept + inline const_iterator find(const Key& key) const noexcept { return {this, find_filled_bucket(key)}; } @@ -953,13 +953,13 @@ public: } template<typename Key = KeyT> - bool contains(const Key& key) const noexcept + inline bool contains(const Key& key) const noexcept { return find_filled_bucket(key) != _num_buckets; } template<typename Key = KeyT> - size_type count(const Key& key) const noexcept + inline size_type count(const Key& key) const noexcept { return find_filled_bucket(key) != _num_buckets ? 1 : 0; } @@ -1120,23 +1120,23 @@ public: #endif template<typename K, typename V> - size_type insert_unique(K&& key, V&& val) + inline size_type insert_unique(K&& key, V&& val) { return do_insert_unqiue(std::forward<K>(key), std::forward<V>(val)); } - size_type insert_unique(value_type&& value) + inline size_type insert_unique(value_type&& value) { return do_insert_unqiue(std::move(value.first), std::move(value.second)); } - size_type insert_unique(const value_type& value) + inline size_type insert_unique(const value_type& value) { return do_insert_unqiue(value.first, value.second); } template<typename K, typename V> - inline size_type do_insert_unqiue(K&& key, V&& val) + size_type do_insert_unqiue(K&& key, V&& val) { check_expand_need(); auto bucket = find_unique_bucket(key); @@ -1148,7 +1148,7 @@ public: std::pair<iterator, bool> insert_or_assign(KeyT&& key, ValueT&& val) { return do_assign(std::move(key), std::forward<ValueT>(val)); } template <typename... Args> - inline std::pair<iterator, bool> emplace(Args&&... args) noexcept + std::pair<iterator, bool> emplace(Args&&... args) noexcept { check_expand_need(); return do_insert(std::forward<Args>(args)...); @@ -1177,7 +1177,7 @@ public: } template <class... Args> - inline size_type emplace_unique(Args&&... args) noexcept + size_type emplace_unique(Args&&... args) noexcept { return insert_unique(std::forward<Args>(args)...); } @@ -1674,7 +1674,7 @@ private: #endif const auto qmask = _mask / SIZE_BIT; - if (1) { + if (0) { const size_type step = (main_bucket - SIZE_BIT / 4) & qmask; const auto bmask3 = *((size_t*)_bitmask + step); if (bmask3 != 0) @@ -1682,7 +1682,7 @@ private: } for (; ;) { - auto& _last = EMH_BUCKET(_pairs, _num_buckets); + auto& _last = EMH_BUCKET(_pairs, _num_buckets); const auto bmask2 = *((size_t*)_bitmask + _last); if (bmask2 != 0) return _last * SIZE_BIT + CTZ(bmask2); @@ -1779,7 +1779,7 @@ private: #if EMH_INT_HASH static constexpr uint64_t KC = UINT64_C(11400714819323198485); - static inline uint64_t hash64(uint64_t key) + inline uint64_t hash64(uint64_t key) { #if __SIZEOF_INT128__ && EMH_INT_HASH == 1 __uint128_t r = key; r *= KC; diff --git a/misc/benchmarks/external/tsl/robin_hash.h b/misc/benchmarks/external/tsl/robin_hash.h index 89c7c96f..5fdc07f9 100644 --- a/misc/benchmarks/external/tsl/robin_hash.h +++ b/misc/benchmarks/external/tsl/robin_hash.h @@ -324,19 +324,16 @@ class bucket_entry : public bucket_entry_hash<StoreHash> { public: static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1; - static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT = 4096; + static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT = 8192; static_assert(DIST_FROM_IDEAL_BUCKET_LIMIT <= std::numeric_limits<distance_type>::max() - 1, "DIST_FROM_IDEAL_BUCKET_LIMIT must be <= " "std::numeric_limits<distance_type>::max() - 1."); private: - using storage = typename std::aligned_storage<sizeof(value_type), - alignof(value_type)>::type; - distance_type m_dist_from_ideal_bucket; bool m_last_bucket; - storage m_value; + alignas(value_type) unsigned char m_value[sizeof(value_type)]; }; /** @@ -1234,7 +1231,7 @@ class robin_hash : private Hash, private KeyEqual, private GrowthPolicy { dist_from_ideal_bucket++; } - if (rehash_on_extreme_load()) { + while (rehash_on_extreme_load(dist_from_ideal_bucket)) { ibucket = bucket_for_hash(hash); dist_from_ideal_bucket = 0; @@ -1296,7 +1293,7 @@ class robin_hash : private Hash, private KeyEqual, private GrowthPolicy { while (!m_buckets[ibucket].empty()) { if (dist_from_ideal_bucket > m_buckets[ibucket].dist_from_ideal_bucket()) { - if (dist_from_ideal_bucket >= + if (dist_from_ideal_bucket > bucket_entry::DIST_FROM_IDEAL_BUCKET_LIMIT) { /** * The number of probes is really high, rehash the map on the next @@ -1382,8 +1379,11 @@ class robin_hash : private Hash, private KeyEqual, private GrowthPolicy { * * Return true if the table has been rehashed. */ - bool rehash_on_extreme_load() { - if (m_grow_on_next_insert || size() >= m_load_threshold) { + bool rehash_on_extreme_load(distance_type curr_dist_from_ideal_bucket) { + if (m_grow_on_next_insert || + curr_dist_from_ideal_bucket > + bucket_entry::DIST_FROM_IDEAL_BUCKET_LIMIT || + size() >= m_load_threshold) { rehash_impl(GrowthPolicy::next_bucket_count()); m_grow_on_next_insert = false; diff --git a/misc/examples/lower_bound.c b/misc/examples/lower_bound.c index 2b6f3cc6..dde9d93a 100644 --- a/misc/examples/lower_bound.c +++ b/misc/examples/lower_bound.c @@ -18,20 +18,24 @@ int main() cvec_int_sort(&vec); - key = 500; + key = 100; res = cvec_int_lower_bound(&vec, key).ref; - if (res != cvec_int_end(&vec).ref) - printf("Sorted Vec %d: lower bound: %d\n", key, *res); // 600 + if (res) + printf("Sorted Vec %d: lower bound: %d\n", key, *res); // 500 - key = 550; - res = cvec_int_lower_bound(&vec, key).ref; - if (res != cvec_int_end(&vec).ref) - printf("Sorted Vec %d: lower_bound: %d\n", key, *res); // 500 + key = 10; + cvec_int_iter it1 = cvec_int_lower_bound(&vec, key); + if (res) + printf("Sorted Vec %3d: lower_bound: %d\n", key, *it1.ref); // 30 + + key = 600; + cvec_int_iter it2 = cvec_int_binary_search(&vec, key); + if (res) + printf("Sorted Vec %d: bin. search: %d\n", key, *it2.ref); // 600 + + c_FOREACH (i, cvec_int, it1, it2) + printf(" %d\n", *i.ref); - key = 500; - res = cvec_int_binary_search(&vec, key).ref; - if (res != cvec_int_end(&vec).ref) - printf("Sorted Vec %d: bin. search: %d\n", key, *res); // 500 puts(""); } @@ -43,20 +47,22 @@ int main() c_FORLIST (i, int, {40, 600, 1, 7000, 2, 500, 30}) csset_int_push(&set, *i.ref); - key = 500; + key = 100; res = csset_int_lower_bound(&set, key).ref; - if (res != csset_int_end(&set).ref) - printf("Sorted Set %d: lower bound: %d\n", key, *res); // 600 + if (res) + printf("Sorted Set %d: lower bound: %d\n", key, *res); // 500 - key = 550; - res = csset_int_lower_bound(&set, key).ref; - if (res != csset_int_end(&set).ref) - printf("Sorted Set %d: lower bound: %d\n", key, *res); // 600 + key = 10; + csset_int_iter it1 = csset_int_lower_bound(&set, key); + if (res) + printf("Sorted Set %3d: lower bound: %d\n", key, *it1.ref); // 30 + + key = 600; + csset_int_iter it2 = csset_int_find(&set, key); + if (res) + printf("Sorted Set %d: find : %d\n", key, *it2.ref); // 600 - key = 500; - res = csset_int_find(&set, key).ref; - if (res != csset_int_end(&set).ref) - printf("Sorted Set %d: find : %d\n", key, *res); // 600 + c_FOREACH (i, csset_int, it1, it2) + printf(" %d\n", *i.ref); } - return 0; } |