From dd1ac09cd54e2632ec9d272ec578cde67a5edd01 Mon Sep 17 00:00:00 2001 From: Tyge Lovset Date: Thu, 5 Jan 2023 22:54:46 +0100 Subject: Updated external benchmark hash maps to latest, and improved example lower_bound.c --- misc/benchmarks/external/ankerl/unordered_dense.h | 56 ++++++++++++++++------- 1 file changed, 39 insertions(+), 17 deletions(-) (limited to 'misc/benchmarks/external/ankerl') 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 . @@ -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 using detect_iterator = typename T::iterator; +template +using detect_reserve = decltype(std::declval().reserve(size_t{})); + // enable_if helpers template @@ -374,6 +377,18 @@ constexpr bool is_transparent_v = is_detected_v&& i template constexpr bool is_neither_convertible_v = !std::is_convertible_v && !std::is_convertible_v; +template +constexpr bool has_reserve = is_detected_v; + +// base type for map has mapped_type +template +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 table { +class table : public std::conditional_t, base_table_type_map, base_table_type_set> { public: using value_container_type = std::conditional_t< is_detected_v, AllocatorOrContainer, - typename std::vector, Key, std::pair>, AllocatorOrContainer>>; + typename std::vector, std::pair, 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, 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) { - return vt; - } else { + if constexpr (is_map_v) { 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(value_idx_to_remove); } + template , 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) { + // 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) { - // set: only check that the key is here - if (a.end() == it) { + if constexpr (is_map_v) { + // 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; } } -- cgit v1.2.3