From d31f686e20c0f3731b1dc931f7f8e1d69c07ed4c Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 16 Sep 2022 11:43:02 +0200 Subject: Update external c++ unordered maps for benchmarking. --- benchmarks/external/ankerl/unordered_dense.h | 712 +++++++++++++++++---------- benchmarks/external/emhash/hash_table7.hpp | 277 +++++------ benchmarks/external/emhash/wyhash.h | 272 ---------- benchmarks/external/update.sh | 2 +- 4 files changed, 578 insertions(+), 685 deletions(-) delete mode 100644 benchmarks/external/emhash/wyhash.h diff --git a/benchmarks/external/ankerl/unordered_dense.h b/benchmarks/external/ankerl/unordered_dense.h index 304ef3bc..220c65b8 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.2 +// Version 1.3.1 // https://github.com/martinus/unordered_dense // // Licensed under the MIT License . @@ -30,35 +30,56 @@ #define ANKERL_UNORDERED_DENSE_H // 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 2 // backwards compatible bug fixes +#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 1 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes +#define ANKERL_UNORDERED_DENSE_VERSION_MINOR 3 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality +#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 1 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes + +// API versioning with inline namespace, see https://www.foonathan.net/2018/11/inline-namespaces/ +#define ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch) v##major##_##minor##_##patch +#define ANKERL_UNORDERED_DENSE_VERSION_CONCAT(major, minor, patch) ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch) +#define ANKERL_UNORDERED_DENSE_NAMESPACE \ + ANKERL_UNORDERED_DENSE_VERSION_CONCAT( \ + ANKERL_UNORDERED_DENSE_VERSION_MAJOR, ANKERL_UNORDERED_DENSE_VERSION_MINOR, ANKERL_UNORDERED_DENSE_VERSION_PATCH) + +#if defined(_MSVC_LANG) +# define ANKERL_UNORDERED_DENSE_CPP_VERSION _MSVC_LANG +#else +# define ANKERL_UNORDERED_DENSE_CPP_VERSION __cplusplus +#endif + +#if defined(__GNUC__) +// NOLINTNEXTLINE(cppcoreguidelines-macro-usage) +# define ANKERL_UNORDERED_DENSE_PACK(decl) decl __attribute__((__packed__)) +#elif defined(_MSC_VER) +// NOLINTNEXTLINE(cppcoreguidelines-macro-usage) +# define ANKERL_UNORDERED_DENSE_PACK(decl) __pragma(pack(push, 1)) decl __pragma(pack(pop)) +#endif -#if 0 // __cplusplus < 201703L +#if ANKERL_UNORDERED_DENSE_CPP_VERSION < 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 +# include // for array +# include // for uint64_t, uint32_t, uint8_t, UINT64_C +# include // for size_t, memcpy, memset +# include // for equal_to, hash +# include // for initializer_list +# include // for pair, distance +# include // for numeric_limits +# include // for allocator, allocator_traits, shared_ptr +# include // for out_of_range +# include // for basic_string +# include // for basic_string_view, hash +# include // for forward_as_tuple +# include // for enable_if_t, declval, conditional_t, ena... +# include // for forward, exchange, pair, as_const, piece... +# include // for vector + +# define ANKERL_UNORDERED_DENSE_PMR 0 // NOLINT(cppcoreguidelines-macro-usage) # if defined(__has_include) # if __has_include() # undef ANKERL_UNORDERED_DENSE_PMR -# define ANKERL_UNORDERED_DENSE_PMR 1 -# include +# define ANKERL_UNORDERED_DENSE_PMR 1 // NOLINT(cppcoreguidelines-macro-usage) +# include // for polymorphic_allocator # endif # endif @@ -68,14 +89,15 @@ # 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) +# define ANKERL_UNORDERED_DENSE_LIKELY(x) __builtin_expect(x, 1) // NOLINT(cppcoreguidelines-macro-usage) +# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) __builtin_expect(x, 0) // NOLINT(cppcoreguidelines-macro-usage) # else -# define ANKERL_UNORDERED_DENSE_LIKELY(x) (x) -# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) (x) +# define ANKERL_UNORDERED_DENSE_LIKELY(x) (x) // NOLINT(cppcoreguidelines-macro-usage) +# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) (x) // NOLINT(cppcoreguidelines-macro-usage) # endif namespace ankerl::unordered_dense { +inline namespace ANKERL_UNORDERED_DENSE_NAMESPACE { // hash /////////////////////////////////////////////////////////////////////// @@ -122,7 +144,7 @@ static inline void mum(uint64_t* a, uint64_t* b) { // read functions. WARNING: we don't care about endianness, so results are different on big endian! [[nodiscard]] static inline auto r8(const uint8_t* p) -> uint64_t { uint64_t v{}; - std::memcpy(&v, p, 8); + std::memcpy(&v, p, 8U); return v; } @@ -137,7 +159,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]] static inline auto hash(void const* key, size_t len) -> uint64_t { +[[maybe_unused]] [[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), @@ -191,70 +213,74 @@ static inline void mum(uint64_t* a, uint64_t* b) { } // namespace detail::wyhash template -struct hash : public std::hash { +struct hash { using is_avalanching = void; auto operator()(T const& obj) const noexcept(noexcept(std::declval>().operator()(std::declval()))) - -> size_t { - return static_cast(detail::wyhash::hash(std::hash::operator()(obj))); + -> uint64_t { + return detail::wyhash::hash(std::hash{}(obj)); } }; template struct hash> { using is_avalanching = void; - auto operator()(std::basic_string const& str) const noexcept -> size_t { - return static_cast(detail::wyhash::hash(str.data(), sizeof(CharT) * str.size())); + auto operator()(std::basic_string const& str) const noexcept -> uint64_t { + return detail::wyhash::hash(str.data(), sizeof(CharT) * str.size()); } }; template struct hash> { using is_avalanching = void; - auto operator()(std::basic_string_view const& sv) const noexcept -> size_t { - return static_cast(detail::wyhash::hash(sv.data(), sizeof(CharT) * sv.size())); + auto operator()(std::basic_string_view const& sv) const noexcept -> uint64_t { + return 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))); + auto operator()(T* ptr) const noexcept -> uint64_t { + // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) + return 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()))); + auto operator()(std::unique_ptr const& ptr) const noexcept -> uint64_t { + // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) + return 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()))); + auto operator()(std::shared_ptr const& ptr) const noexcept -> uint64_t { + // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) + return 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))); + auto operator()(Enum e) const noexcept -> uint64_t { + using underlying = typename std::underlying_type_t; + return 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))); \ - } \ +// NOLINTNEXTLINE(cppcoreguidelines-macro-usage) +# define ANKERL_UNORDERED_DENSE_HASH_STATICCAST(T) \ + template <> \ + struct hash { \ + using is_avalanching = void; \ + auto operator()(T const& obj) const noexcept -> uint64_t { \ + return detail::wyhash::hash(static_cast(obj)); \ + } \ } # if defined(__GNUC__) && !defined(__clang__) @@ -266,7 +292,7 @@ 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 +# if ANKERL_UNORDERED_DENSE_CPP_VERSION >= 202002L ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char8_t); # endif ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char16_t); @@ -285,6 +311,28 @@ ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned long long); # pragma GCC diagnostic pop # endif +// bucket_type ////////////////////////////////////////////////////////// + +namespace bucket_type { + +struct standard { + static constexpr uint32_t dist_inc = 1U << 8U; // skip 1 byte fingerprint + static constexpr uint32_t fingerprint_mask = dist_inc - 1; // mask for 1 byte of fingerprint + + uint32_t m_dist_and_fingerprint; // upper 3 byte: distance to original bucket. lower byte: fingerprint from hash + uint32_t m_value_idx; // index into the m_values vector. +}; + +ANKERL_UNORDERED_DENSE_PACK(struct big { + static constexpr uint32_t dist_inc = 1U << 8U; // skip 1 byte fingerprint + static constexpr uint32_t fingerprint_mask = dist_inc - 1; // mask for 1 byte of fingerprint + + uint32_t m_dist_and_fingerprint; // upper 3 byte: distance to original bucket. lower byte: fingerprint from hash + size_t m_value_idx; // index into the m_values vector. +}); + +} // namespace bucket_type + namespace detail { struct nonesuch {}; @@ -313,6 +361,9 @@ using detect_avalanching = typename T::is_avalanching; template using detect_is_transparent = typename T::is_transparent; +template +using detect_iterator = typename T::iterator; + template using is_transparent = std::enable_if_t && is_detected_v, bool>; @@ -322,79 +373,101 @@ template + class AllocatorOrContainer, + class Bucket> class table { - struct Bucket; - using ValueContainer = - typename std::vector, Key, std::pair>, Allocator>; - using BucketAlloc = typename std::allocator_traits::template rebind_alloc; - using BucketAllocTraits = std::allocator_traits; +public: + using value_container_type = std::conditional_t< + is_detected_v, + AllocatorOrContainer, + typename std::vector, Key, std::pair>, AllocatorOrContainer>>; - 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.8F; +private: + using bucket_alloc = + typename std::allocator_traits::template rebind_alloc; + using bucket_alloc_traits = std::allocator_traits; + + static constexpr uint8_t initial_shifts = 64 - 3; // 2^(64-m_shift) number of buckets + static constexpr float default_max_load_factor = 0.8F; public: using key_type = Key; using mapped_type = T; - using value_type = typename ValueContainer::value_type; - using size_type = typename ValueContainer::size_type; - using difference_type = typename ValueContainer::difference_type; + 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; using hasher = Hash; using key_equal = KeyEqual; - using allocator_type = typename ValueContainer::allocator_type; - using reference = typename ValueContainer::reference; - using const_reference = typename ValueContainer::const_reference; - using pointer = typename ValueContainer::pointer; - using const_pointer = typename ValueContainer::const_pointer; - using iterator = typename ValueContainer::iterator; - using const_iterator = typename ValueContainer::const_iterator; + using allocator_type = typename value_container_type::allocator_type; + using reference = typename value_container_type::reference; + 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 bucket_type = Bucket; private: - struct Bucket { - uint32_t dist_and_fingerprint; // upper 3 byte: distance to original bucket. lower byte: fingerprint from hash - uint32_t value_idx; // index into the m_values vector. - }; + using value_idx_type = decltype(Bucket::m_value_idx); + using dist_and_fingerprint_type = decltype(Bucket::m_dist_and_fingerprint); + static_assert(std::is_trivially_destructible_v, "assert there's no need to call destructor / std::destroy"); static_assert(std::is_trivially_copyable_v, "assert we can just memset / memcpy"); - ValueContainer m_values{}; // Contains all the key-value pairs in one densely stored container. No holes. - Bucket* m_buckets_start = nullptr; - Bucket* m_buckets_end = nullptr; - uint32_t m_max_bucket_capacity = 0; - float m_max_load_factor = DEFAULT_MAX_LOAD_FACTOR; + value_container_type m_values{}; // Contains all the key-value pairs in one densely stored container. No holes. + typename std::allocator_traits::pointer m_buckets{}; + size_t m_num_buckets = 0; + size_t m_max_bucket_capacity = 0; + float m_max_load_factor = default_max_load_factor; Hash m_hash{}; KeyEqual m_equal{}; - uint8_t m_shifts = INITIAL_SHIFTS; + uint8_t m_shifts = initial_shifts; - [[nodiscard]] auto next(Bucket const* bucket) const -> Bucket const* { - return ANKERL_UNORDERED_DENSE_UNLIKELY(bucket + 1 == m_buckets_end) ? m_buckets_start : bucket + 1; + [[nodiscard]] auto next(value_idx_type bucket_idx) const -> value_idx_type { + return ANKERL_UNORDERED_DENSE_UNLIKELY(bucket_idx + 1U == m_num_buckets) + ? 0 + : static_cast(bucket_idx + 1U); } - [[nodiscard]] auto next(Bucket* bucket) -> Bucket* { - return ANKERL_UNORDERED_DENSE_UNLIKELY(bucket + 1 == m_buckets_end) ? m_buckets_start : bucket + 1; + // Helper to access bucket through pointer types + [[nodiscard]] static constexpr auto at(typename std::allocator_traits::pointer bucket_ptr, size_t offset) + -> Bucket& { + return *(bucket_ptr + static_cast::difference_type>(offset)); } + // use the dist_inc and dist_dec functions so that uint16_t types work without warning + [[nodiscard]] static constexpr auto dist_inc(dist_and_fingerprint_type x) -> dist_and_fingerprint_type { + return static_cast(x + Bucket::dist_inc); + } + + [[nodiscard]] static constexpr auto dist_dec(dist_and_fingerprint_type x) -> dist_and_fingerprint_type { + return static_cast(x - Bucket::dist_inc); + } + + // The goal of mixed_hash is to always produce a high quality 64bit hash. template [[nodiscard]] constexpr auto mixed_hash(K const& key) const -> uint64_t { if constexpr (is_detected_v) { - return m_hash(key); + // we know that the hash is good because is_avalanching. + if constexpr (sizeof(decltype(m_hash(key))) < sizeof(uint64_t)) { + // 32bit hash and is_avalanching => multiply with a constant to avalanche bits upwards + return m_hash(key) * UINT64_C(0x9ddfea08eb382d69); + } else { + // 64bit and is_avalanching => only use the hash itself. + return m_hash(key); + } } else { + // not is_avalanching => apply wyhash return wyhash::hash(m_hash(key)); } } - [[nodiscard]] constexpr auto dist_and_fingerprint_from_hash(uint64_t hash) const -> uint32_t { - return BUCKET_DIST_INC | (hash & BUCKET_FINGERPRINT_MASK); + [[nodiscard]] constexpr auto dist_and_fingerprint_from_hash(uint64_t hash) const -> dist_and_fingerprint_type { + return Bucket::dist_inc | (static_cast(hash) & Bucket::fingerprint_mask); } - [[nodiscard]] constexpr auto bucket_from_hash(uint64_t hash) const -> Bucket const* { - return m_buckets_start + (hash >> m_shifts); - } - - [[nodiscard]] constexpr auto bucket_from_hash(uint64_t hash) -> Bucket* { - return m_buckets_start + (hash >> m_shifts); + [[nodiscard]] constexpr auto bucket_idx_from_hash(uint64_t hash) const -> value_idx_type { + return static_cast(hash >> m_shifts); } [[nodiscard]] static constexpr auto get_key(value_type const& vt) -> key_type const& { @@ -406,51 +479,45 @@ private: } template - [[nodiscard]] auto next_while_less(K const& key) -> std::pair { - auto const& pair = std::as_const(*this).next_while_less(key); - return {pair.first, const_cast(pair.second)}; // NOLINT(cppcoreguidelines-pro-type-const-cast) - } - - template - [[nodiscard]] auto next_while_less(K const& key) const -> std::pair { + [[nodiscard]] auto next_while_less(K const& key) const -> Bucket { auto hash = mixed_hash(key); auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash); - auto const* bucket = bucket_from_hash(hash); + auto bucket_idx = bucket_idx_from_hash(hash); - while (dist_and_fingerprint < bucket->dist_and_fingerprint) { - dist_and_fingerprint += BUCKET_DIST_INC; - bucket = next(bucket); + while (dist_and_fingerprint < at(m_buckets, bucket_idx).m_dist_and_fingerprint) { + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); } - return {dist_and_fingerprint, bucket}; + return {dist_and_fingerprint, bucket_idx}; } - void place_and_shift_up(Bucket bucket, Bucket* place) { - while (0 != place->dist_and_fingerprint) { - bucket = std::exchange(*place, bucket); - bucket.dist_and_fingerprint += BUCKET_DIST_INC; + void place_and_shift_up(Bucket bucket, value_idx_type place) { + while (0 != at(m_buckets, place).m_dist_and_fingerprint) { + bucket = std::exchange(at(m_buckets, place), bucket); + bucket.m_dist_and_fingerprint = dist_inc(bucket.m_dist_and_fingerprint); place = next(place); } - *place = bucket; + at(m_buckets, place) = bucket; } - [[nodiscard]] static constexpr auto calc_num_buckets(uint8_t shifts) -> uint64_t { - return UINT64_C(1) << (64U - shifts); + [[nodiscard]] static constexpr auto calc_num_buckets(uint8_t shifts) -> size_t { + return std::min(max_bucket_count(), size_t{1} << (64U - shifts)); } [[nodiscard]] constexpr auto calc_shifts_for_size(size_t s) const -> uint8_t { - auto shifts = INITIAL_SHIFTS; - while (shifts > 0 && static_cast(calc_num_buckets(shifts) * max_load_factor()) < s) { + auto shifts = initial_shifts; + while (shifts > 0 && static_cast(static_cast(calc_num_buckets(shifts)) * max_load_factor()) < s) { --shifts; } return shifts; } - // assumes m_values has data, m_buckets_start=m_buckets_end=nullptr, m_shifts is INITIAL_SHIFTS + // assumes m_values has data, m_buckets=m_buckets_end=nullptr, m_shifts is INITIAL_SHIFTS void copy_buckets(table const& other) { if (!empty()) { m_shifts = other.m_shifts; allocate_buckets_from_shift(); - std::memcpy(m_buckets_start, other.m_buckets_start, sizeof(Bucket) * bucket_count()); + std::memcpy(m_buckets, other.m_buckets, sizeof(Bucket) * bucket_count()); } } @@ -462,30 +529,37 @@ private: } void deallocate_buckets() { - auto bucket_alloc = BucketAlloc(m_values.get_allocator()); - BucketAllocTraits::deallocate(bucket_alloc, m_buckets_start, bucket_count()); - m_buckets_start = nullptr; - m_buckets_end = nullptr; + auto ba = bucket_alloc(m_values.get_allocator()); + if (nullptr != m_buckets) { + bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count()); + } + m_buckets = nullptr; + m_num_buckets = 0; m_max_bucket_capacity = 0; } void allocate_buckets_from_shift() { - auto bucket_alloc = BucketAlloc(m_values.get_allocator()); - auto num_buckets = calc_num_buckets(m_shifts); - m_buckets_start = BucketAllocTraits::allocate(bucket_alloc, num_buckets); - m_buckets_end = m_buckets_start + num_buckets; - m_max_bucket_capacity = static_cast(num_buckets * max_load_factor()); + auto ba = bucket_alloc(m_values.get_allocator()); + m_num_buckets = calc_num_buckets(m_shifts); + m_buckets = bucket_alloc_traits::allocate(ba, m_num_buckets); + if (m_num_buckets == max_bucket_count()) { + // reached the maximum, make sure we can use each bucket + m_max_bucket_capacity = max_bucket_count(); + } else { + m_max_bucket_capacity = static_cast(static_cast(m_num_buckets) * max_load_factor()); + } } void clear_buckets() { - if (m_buckets_start != nullptr) { - std::memset(m_buckets_start, 0, sizeof(Bucket) * bucket_count()); + if (m_buckets != nullptr) { + std::memset(&*m_buckets, 0, sizeof(Bucket) * bucket_count()); } } void clear_and_fill_buckets_from_values() { clear_buckets(); - for (uint32_t value_idx = 0, end_idx = static_cast(m_values.size()); value_idx < end_idx; ++value_idx) { + for (value_idx_type 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); @@ -495,22 +569,26 @@ private: } void increase_size() { + if (ANKERL_UNORDERED_DENSE_UNLIKELY(m_max_bucket_capacity == max_bucket_count())) { + throw std::overflow_error("ankerl::unordered_dense: reached max bucket size, cannot increase size"); + } --m_shifts; deallocate_buckets(); allocate_buckets_from_shift(); clear_and_fill_buckets_from_values(); } - void do_erase(Bucket* bucket) { - auto const value_idx_to_remove = bucket->value_idx; + void do_erase(value_idx_type bucket_idx) { + auto const value_idx_to_remove = at(m_buckets, bucket_idx).m_value_idx; // shift down until either empty or an element with correct spot is found - auto* next_bucket = next(bucket); - while (next_bucket->dist_and_fingerprint >= BUCKET_DIST_INC * 2) { - *bucket = {next_bucket->dist_and_fingerprint - BUCKET_DIST_INC, next_bucket->value_idx}; - bucket = std::exchange(next_bucket, next(next_bucket)); + auto next_bucket_idx = next(bucket_idx); + while (at(m_buckets, next_bucket_idx).m_dist_and_fingerprint >= Bucket::dist_inc * 2) { + at(m_buckets, bucket_idx) = {dist_dec(at(m_buckets, next_bucket_idx).m_dist_and_fingerprint), + at(m_buckets, next_bucket_idx).m_value_idx}; + bucket_idx = std::exchange(next_bucket_idx, next(next_bucket_idx)); } - *bucket = {}; + at(m_buckets, bucket_idx) = {}; // update m_values if (value_idx_to_remove != m_values.size() - 1) { @@ -520,13 +598,13 @@ private: // update the values_idx of the moved entry. No need to play the info game, just look until we find the values_idx auto mh = mixed_hash(get_key(val)); - bucket = bucket_from_hash(mh); + bucket_idx = bucket_idx_from_hash(mh); - auto const values_idx_back = static_cast(m_values.size() - 1); - while (values_idx_back != bucket->value_idx) { - bucket = next(bucket); + auto const values_idx_back = static_cast(m_values.size() - 1); + while (values_idx_back != at(m_buckets, bucket_idx).m_value_idx) { + bucket_idx = next(bucket_idx); } - bucket->value_idx = value_idx_to_remove; + at(m_buckets, bucket_idx).m_value_idx = value_idx_to_remove; } m_values.pop_back(); } @@ -537,17 +615,18 @@ private: return 0; } - auto [dist_and_fingerprint, bucket] = next_while_less(key); + auto [dist_and_fingerprint, bucket_idx] = next_while_less(key); - while (dist_and_fingerprint == bucket->dist_and_fingerprint && !m_equal(key, get_key(m_values[bucket->value_idx]))) { - dist_and_fingerprint += BUCKET_DIST_INC; - bucket = next(bucket); + while (dist_and_fingerprint == at(m_buckets, bucket_idx).m_dist_and_fingerprint && + !m_equal(key, get_key(m_values[at(m_buckets, bucket_idx).m_value_idx]))) { + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); } - if (dist_and_fingerprint != bucket->dist_and_fingerprint) { + if (dist_and_fingerprint != at(m_buckets, bucket_idx).m_dist_and_fingerprint) { return 0; } - do_erase(bucket); + do_erase(bucket_idx); return 1; } @@ -560,66 +639,83 @@ private: return it_isinserted; } + template + auto do_place_element(dist_and_fingerprint_type dist_and_fingerprint, value_idx_type bucket_idx, K&& key, Args&&... args) + -> std::pair { + + // emplace the new value. If that throws an exception, no harm done; index is still in a valid state + m_values.emplace_back(std::piecewise_construct, + std::forward_as_tuple(std::forward(key)), + std::forward_as_tuple(std::forward(args)...)); + + // place element and shift up until we find an empty spot + auto value_idx = static_cast(m_values.size() - 1); + place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx); + return {begin() + static_cast(value_idx), true}; + } + template auto do_try_emplace(K&& key, Args&&... args) -> std::pair { - if (is_full()) { + if (ANKERL_UNORDERED_DENSE_UNLIKELY(is_full())) { increase_size(); } auto hash = mixed_hash(key); auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash); - auto* bucket = bucket_from_hash(hash); + auto bucket_idx = bucket_idx_from_hash(hash); - while (dist_and_fingerprint <= bucket->dist_and_fingerprint) { - if (dist_and_fingerprint == bucket->dist_and_fingerprint && m_equal(key, m_values[bucket->value_idx].first)) { - return {begin() + bucket->value_idx, false}; + while (true) { + auto* bucket = &at(m_buckets, bucket_idx); + if (dist_and_fingerprint == bucket->m_dist_and_fingerprint) { + if (m_equal(key, m_values[bucket->m_value_idx].first)) { + return {begin() + static_cast(bucket->m_value_idx), false}; + } + } else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint) { + return do_place_element(dist_and_fingerprint, bucket_idx, std::forward(key), std::forward(args)...); } - dist_and_fingerprint += BUCKET_DIST_INC; - bucket = next(bucket); + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); } - - // emplace the new value. If that throws an exception, no harm done; index is still in a valid state - m_values.emplace_back(std::piecewise_construct, - std::forward_as_tuple(std::forward(key)), - std::forward_as_tuple(std::forward(args)...)); - - // place element and shift up until we find an empty spot - uint32_t value_idx = static_cast(m_values.size()) - 1; - place_and_shift_up({dist_and_fingerprint, value_idx}, bucket); - return {begin() + value_idx, true}; } template auto do_find(K const& key) -> iterator { - if (empty()) { + if (ANKERL_UNORDERED_DENSE_UNLIKELY(empty())) { return end(); } auto mh = mixed_hash(key); auto dist_and_fingerprint = dist_and_fingerprint_from_hash(mh); - auto const* bucket = bucket_from_hash(mh); + auto bucket_idx = bucket_idx_from_hash(mh); + auto* bucket = &at(m_buckets, bucket_idx); // unrolled loop. *Always* check a few directly, then enter the loop. This is faster. - if (dist_and_fingerprint == bucket->dist_and_fingerprint && m_equal(key, get_key(m_values[bucket->value_idx]))) { - return begin() + bucket->value_idx; + if (dist_and_fingerprint == bucket->m_dist_and_fingerprint && m_equal(key, get_key(m_values[bucket->m_value_idx]))) { + return begin() + static_cast(bucket->m_value_idx); } - dist_and_fingerprint += BUCKET_DIST_INC; - bucket = next(bucket); + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); + bucket = &at(m_buckets, bucket_idx); - if (dist_and_fingerprint == bucket->dist_and_fingerprint && m_equal(key, get_key(m_values[bucket->value_idx]))) { - return begin() + bucket->value_idx; + if (dist_and_fingerprint == bucket->m_dist_and_fingerprint && m_equal(key, get_key(m_values[bucket->m_value_idx]))) { + return begin() + static_cast(bucket->m_value_idx); } - dist_and_fingerprint += BUCKET_DIST_INC; - bucket = next(bucket); - - do { - if (dist_and_fingerprint == bucket->dist_and_fingerprint && m_equal(key, get_key(m_values[bucket->value_idx]))) { - return begin() + bucket->value_idx; + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); + bucket = &at(m_buckets, bucket_idx); + + while (true) { + if (dist_and_fingerprint == bucket->m_dist_and_fingerprint) { + if (m_equal(key, get_key(m_values[bucket->m_value_idx]))) { + return begin() + static_cast(bucket->m_value_idx); + } + } else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint) { + return end(); } - dist_and_fingerprint += BUCKET_DIST_INC; - bucket = next(bucket); - } while (dist_and_fingerprint <= bucket->dist_and_fingerprint); - return end(); + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); + bucket = &at(m_buckets, bucket_idx); + } } template @@ -634,19 +730,22 @@ public: explicit table(size_t /*bucket_count*/, Hash const& hash = Hash(), KeyEqual const& equal = KeyEqual(), - Allocator const& alloc = Allocator()) - : m_values(alloc) + AllocatorOrContainer const& alloc_or_container = AllocatorOrContainer()) + : m_values(alloc_or_container) , m_hash(hash) - , m_equal(equal) {} + , m_equal(equal) { + // If alloc_or_container is a container with elements, we don't want the data that was in it + m_values.clear(); + } - table(size_t bucket_count, Allocator const& alloc) - : table(bucket_count, Hash(), KeyEqual(), alloc) {} + table(size_t bucket_count, AllocatorOrContainer const& alloc_or_container) + : table(bucket_count, Hash(), KeyEqual(), alloc_or_container) {} - table(size_t bucket_count, Hash const& hash, Allocator const& alloc) - : table(bucket_count, hash, KeyEqual(), alloc) {} + table(size_t bucket_count, Hash const& hash, AllocatorOrContainer const& alloc_or_container) + : table(bucket_count, hash, KeyEqual(), alloc_or_container) {} - explicit table(Allocator const& alloc) - : table(0, Hash(), KeyEqual(), alloc) {} + explicit table(AllocatorOrContainer const& alloc_or_container) + : table(0, Hash(), KeyEqual(), alloc_or_container) {} template table(InputIt first, @@ -654,24 +753,25 @@ public: size_type bucket_count = 0, Hash const& hash = Hash(), KeyEqual const& equal = KeyEqual(), - Allocator const& alloc = Allocator()) - : table(bucket_count, hash, equal, alloc) { + AllocatorOrContainer const& alloc_or_container = AllocatorOrContainer()) + : table(bucket_count, hash, equal, alloc_or_container) { insert(first, last); } template - table(InputIt first, InputIt last, size_type bucket_count, Allocator const& alloc) - : table(first, last, bucket_count, Hash(), KeyEqual(), alloc) {} + table(InputIt first, InputIt last, size_type bucket_count, AllocatorOrContainer const& alloc_or_container) + : table(first, last, bucket_count, Hash(), KeyEqual(), alloc_or_container) {} template - table(InputIt first, InputIt last, size_type bucket_count, Hash const& hash, Allocator const& alloc) - : table(first, last, bucket_count, hash, KeyEqual(), alloc) {} + table( + InputIt first, InputIt last, size_type bucket_count, Hash const& hash, AllocatorOrContainer const& alloc_or_container) + : table(first, last, bucket_count, hash, KeyEqual(), alloc_or_container) {} table(table const& other) : table(other, other.m_values.get_allocator()) {} - table(table const& other, Allocator const& alloc) - : m_values(other.m_values, alloc) + table(table const& other, AllocatorOrContainer const& alloc_or_container) + : m_values(other.m_values, alloc_or_container) , m_max_load_factor(other.m_max_load_factor) , m_hash(other.m_hash) , m_equal(other.m_equal) { @@ -681,15 +781,15 @@ public: table(table&& other) noexcept : table(std::move(other), other.m_values.get_allocator()) {} - table(table&& other, Allocator const& alloc) noexcept - : m_values(std::move(other.m_values), alloc) - , m_buckets_start(std::exchange(other.m_buckets_start, nullptr)) - , m_buckets_end(std::exchange(other.m_buckets_end, nullptr)) + table(table&& other, AllocatorOrContainer const& alloc_or_container) noexcept + : m_values(std::move(other.m_values), alloc_or_container) + , m_buckets(std::exchange(other.m_buckets, nullptr)) + , m_num_buckets(std::exchange(other.m_num_buckets, 0)) , m_max_bucket_capacity(std::exchange(other.m_max_bucket_capacity, 0)) - , m_max_load_factor(std::exchange(other.m_max_load_factor, DEFAULT_MAX_LOAD_FACTOR)) + , m_max_load_factor(std::exchange(other.m_max_load_factor, default_max_load_factor)) , m_hash(std::exchange(other.m_hash, {})) , m_equal(std::exchange(other.m_equal, {})) - , m_shifts(std::exchange(other.m_shifts, INITIAL_SHIFTS)) { + , m_shifts(std::exchange(other.m_shifts, initial_shifts)) { other.m_values.clear(); } @@ -697,20 +797,23 @@ public: size_t bucket_count = 0, Hash const& hash = Hash(), KeyEqual const& equal = KeyEqual(), - Allocator const& alloc = Allocator()) - : table(bucket_count, hash, equal, alloc) { + AllocatorOrContainer const& alloc_or_container = AllocatorOrContainer()) + : table(bucket_count, hash, equal, alloc_or_container) { insert(ilist); } - table(std::initializer_list ilist, size_type bucket_count, const Allocator& alloc) - : table(ilist, bucket_count, Hash(), KeyEqual(), alloc) {} + table(std::initializer_list ilist, size_type bucket_count, AllocatorOrContainer const& alloc_or_container) + : table(ilist, bucket_count, Hash(), KeyEqual(), alloc_or_container) {} - table(std::initializer_list init, size_type bucket_count, Hash const& hash, Allocator const& alloc) - : table(init, bucket_count, hash, KeyEqual(), alloc) {} + table(std::initializer_list init, + size_type bucket_count, + Hash const& hash, + AllocatorOrContainer const& alloc_or_container) + : table(init, bucket_count, hash, KeyEqual(), alloc_or_container) {} ~table() { - auto bucket_alloc = BucketAlloc(m_values.get_allocator()); - BucketAllocTraits::deallocate(bucket_alloc, m_buckets_start, bucket_count()); + auto ba = bucket_alloc(m_values.get_allocator()); + bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count()); } auto operator=(table const& other) -> table& { @@ -720,25 +823,25 @@ public: m_max_load_factor = other.m_max_load_factor; m_hash = other.m_hash; m_equal = other.m_equal; - m_shifts = INITIAL_SHIFTS; + m_shifts = initial_shifts; copy_buckets(other); } return *this; } auto operator=(table&& other) noexcept( - noexcept(std::is_nothrow_move_assignable_v&& std::is_nothrow_move_assignable_v&& + noexcept(std::is_nothrow_move_assignable_v&& std::is_nothrow_move_assignable_v&& std::is_nothrow_move_assignable_v)) -> table& { if (&other != this) { deallocate_buckets(); // deallocate before m_values is set (might have another allocator) m_values = std::move(other.m_values); - m_buckets_start = std::exchange(other.m_buckets_start, nullptr); - m_buckets_end = std::exchange(other.m_buckets_end, nullptr); + m_buckets = std::exchange(other.m_buckets, nullptr); + m_num_buckets = std::exchange(other.m_num_buckets, 0); m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0); - m_max_load_factor = std::exchange(other.m_max_load_factor, DEFAULT_MAX_LOAD_FACTOR); + m_max_load_factor = std::exchange(other.m_max_load_factor, default_max_load_factor); m_hash = std::exchange(other.m_hash, {}); m_equal = std::exchange(other.m_equal, {}); - m_shifts = std::exchange(other.m_shifts, INITIAL_SHIFTS); + m_shifts = std::exchange(other.m_shifts, initial_shifts); other.m_values.clear(); } return *this; @@ -790,8 +893,12 @@ public: return m_values.size(); } - [[nodiscard]] auto max_size() const noexcept -> size_t { - return std::numeric_limits::max(); + [[nodiscard]] static constexpr auto max_size() noexcept -> size_t { + if constexpr (std::numeric_limits::max() == std::numeric_limits::max()) { + return size_t{1} << (sizeof(value_idx_type) * 8 - 1); + } else { + return size_t{1} << (sizeof(value_idx_type) * 8); + } } // modifiers ////////////////////////////////////////////////////////////// @@ -839,6 +946,67 @@ public: insert(ilist.begin(), ilist.end()); } + // nonstandard API: *this is emptied. + // Also see "A Standard flat_map" https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0429r9.pdf + auto extract() && -> value_container_type { + return std::move(m_values); + } + + // nonstandard API: + // Discards the internally held container and replaces it with the one passed. Erases non-unique elements. + auto replace(value_container_type&& container) { + if (container.size() > max_size()) { + throw std::out_of_range("ankerl::unordered_dense::map::replace(): too many elements"); + } + + auto shifts = calc_shifts_for_size(container.size()); + if (0 == m_num_buckets || shifts < m_shifts || container.get_allocator() != m_values.get_allocator()) { + m_shifts = shifts; + deallocate_buckets(); + allocate_buckets_from_shift(); + } + clear_buckets(); + + m_values = std::move(container); + + // can't use clear_and_fill_buckets_from_values() because container elements might not be unique + auto value_idx = value_idx_type{}; + + // loop until we reach the end of the container. duplicated entries will be replaced with back(). + while (value_idx != static_cast(m_values.size())) { + auto const& key = get_key(m_values[value_idx]); + + auto hash = mixed_hash(key); + auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash); + auto bucket_idx = bucket_idx_from_hash(hash); + + bool key_found = false; + while (true) { + auto const& bucket = at(m_buckets, bucket_idx); + if (dist_and_fingerprint > bucket.m_dist_and_fingerprint) { + break; + } + if (dist_and_fingerprint == bucket.m_dist_and_fingerprint && + m_equal(key, m_values[bucket.m_value_idx].first)) { + key_found = true; + break; + } + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); + } + + if (key_found) { + if (value_idx != static_cast(m_values.size() - 1)) { + m_values[value_idx] = std::move(m_values.back()); + } + m_values.pop_back(); + } else { + place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx); + ++value_idx; + } + } + } + template , bool> = true> auto insert_or_assign(Key const& key, M&& mapped) -> std::pair { return do_insert_or_assign(key, std::forward(mapped)); @@ -869,23 +1037,23 @@ public: auto& val = m_values.emplace_back(std::forward(args)...); auto hash = mixed_hash(get_key(val)); auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash); - auto* bucket = bucket_from_hash(hash); + auto bucket_idx = bucket_idx_from_hash(hash); - while (dist_and_fingerprint <= bucket->dist_and_fingerprint) { - if (dist_and_fingerprint == bucket->dist_and_fingerprint && - m_equal(get_key(val), get_key(m_values[bucket->value_idx]))) { + while (dist_and_fingerprint <= at(m_buckets, bucket_idx).m_dist_and_fingerprint) { + if (dist_and_fingerprint == at(m_buckets, bucket_idx).m_dist_and_fingerprint && + m_equal(get_key(val), get_key(m_values[at(m_buckets, bucket_idx).m_value_idx]))) { m_values.pop_back(); // value was already there, so get rid of it - return {begin() + bucket->value_idx, false}; + return {begin() + static_cast(at(m_buckets, bucket_idx).m_value_idx), false}; } - dist_and_fingerprint += BUCKET_DIST_INC; - bucket = next(bucket); + dist_and_fingerprint = dist_inc(dist_and_fingerprint); + bucket_idx = next(bucket_idx); } // value is new, place the bucket and shift up until we find an empty spot - uint32_t value_idx = static_cast(m_values.size()) - 1; - place_and_shift_up({dist_and_fingerprint, value_idx}, bucket); + auto value_idx = static_cast(m_values.size() - 1); + place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx); - return {begin() + value_idx, true}; + return {begin() + static_cast(value_idx), true}; } template @@ -915,15 +1083,15 @@ public: auto erase(iterator it) -> iterator { auto hash = mixed_hash(get_key(*it)); - auto* bucket = bucket_from_hash(hash); + auto bucket_idx = bucket_idx_from_hash(hash); - auto const value_idx_to_remove = static_cast(it - cbegin()); - while (bucket->value_idx != value_idx_to_remove) { - bucket = next(bucket); + auto const value_idx_to_remove = static_cast(it - cbegin()); + while (at(m_buckets, bucket_idx).m_value_idx != value_idx_to_remove) { + bucket_idx = next(bucket_idx); } - do_erase(bucket); - return begin() + value_idx_to_remove; + do_erase(bucket_idx); + return begin() + static_cast(value_idx_to_remove); } auto erase(const_iterator it) -> iterator { @@ -963,8 +1131,8 @@ public: return do_erase_key(std::forward(key)); } - void swap(table& other) noexcept(noexcept(std::is_nothrow_swappable_v&& std::is_nothrow_swappable_v&& - std::is_nothrow_swappable_v)) { + void swap(table& other) noexcept(noexcept(std::is_nothrow_swappable_v&& + std::is_nothrow_swappable_v&& std::is_nothrow_swappable_v)) { using std::swap; swap(other, *this); } @@ -1055,17 +1223,17 @@ public: // bucket interface /////////////////////////////////////////////////////// auto bucket_count() const noexcept -> size_t { // NOLINT(modernize-use-nodiscard) - return m_buckets_end - m_buckets_start; + return m_num_buckets; } - auto max_bucket_count() const noexcept -> size_t { // NOLINT(modernize-use-nodiscard) - return std::numeric_limits::max(); + static constexpr auto max_bucket_count() noexcept -> size_t { // NOLINT(modernize-use-nodiscard) + return max_size(); } // hash policy //////////////////////////////////////////////////////////// [[nodiscard]] auto load_factor() const -> float { - return bucket_count() ? static_cast(size()) / bucket_count() : 0.0F; + return bucket_count() ? static_cast(size()) / static_cast(bucket_count()) : 0.0F; } [[nodiscard]] auto max_load_factor() const -> float { @@ -1074,10 +1242,13 @@ public: void max_load_factor(float ml) { m_max_load_factor = ml; - m_max_bucket_capacity = static_cast(bucket_count() * max_load_factor()); + if (m_num_buckets != max_bucket_count()) { + m_max_bucket_capacity = static_cast(static_cast(bucket_count()) * max_load_factor()); + } } void rehash(size_t count) { + count = std::min(count, max_size()); auto shifts = calc_shifts_for_size(std::max(count, size())); if (shifts != m_shifts) { m_shifts = shifts; @@ -1089,8 +1260,10 @@ public: } void reserve(size_t capa) { + capa = std::min(capa, max_size()); + m_values.reserve(capa); auto shifts = calc_shifts_for_size(std::max(capa, size())); - if (shifts < m_shifts) { + if (0 == m_num_buckets || shifts < m_shifts) { m_shifts = shifts; deallocate_buckets(); allocate_buckets_from_shift(); @@ -1108,6 +1281,11 @@ public: return m_equal; } + // nonstandard API: expose the underlying values container + [[nodiscard]] auto values() const noexcept -> value_container_type const& { + return m_values; + } + // non-member functions /////////////////////////////////////////////////// friend auto operator==(table const& a, table const& b) -> bool { @@ -1145,21 +1323,30 @@ template , class KeyEqual = std::equal_to, - class Allocator = std::allocator>> -using map = detail::table; + class AllocatorOrContainer = std::allocator>, + class Bucket = bucket_type::standard> +using map = detail::table; -template , class KeyEqual = std::equal_to, class Allocator = std::allocator> -using set = detail::table; +template , + class KeyEqual = std::equal_to, + class AllocatorOrContainer = std::allocator, + class Bucket = bucket_type::standard> +using set = detail::table; # if ANKERL_UNORDERED_DENSE_PMR namespace pmr { -template , class KeyEqual = std::equal_to> -using map = detail::table>>; +template , + class KeyEqual = std::equal_to, + class Bucket = bucket_type::standard> +using map = detail::table>, Bucket>; -template , class KeyEqual = std::equal_to> -using set = detail::table>; +template , class KeyEqual = std::equal_to, class Bucket = bucket_type::standard> +using set = detail::table, Bucket>; } // namespace pmr @@ -1167,22 +1354,27 @@ using set = detail::table -auto erase_if(ankerl::unordered_dense::detail::table& map, Pred pred) -> size_t { +template +auto erase_if(ankerl::unordered_dense::detail::table& map, Pred pred) + -> size_t { + using map_t = ankerl::unordered_dense::detail::table; + // going back to front because erase() invalidates the end iterator auto const old_size = map.size(); auto idx = old_size; while (idx) { --idx; - auto it = map.begin() + idx; + auto it = map.begin() + static_cast(idx); if (pred(*it)) { map.erase(it); } diff --git a/benchmarks/external/emhash/hash_table7.hpp b/benchmarks/external/emhash/hash_table7.hpp index 7daedff2..c4761a0a 100644 --- a/benchmarks/external/emhash/hash_table7.hpp +++ b/benchmarks/external/emhash/hash_table7.hpp @@ -1,5 +1,5 @@ // emhash7::HashMap for C++11/14/17 -// version 2.1.2 +// version 2.2.3 // https://github.com/ktprime/ktprime/blob/master/hash_table7.hpp // // Licensed under the MIT License . @@ -159,10 +159,9 @@ of resizing granularity. Ignoring variance, the expected occurrences of list siz namespace emhash7 { - constexpr static float EMH_DEFAULT_LOAD_FACTOR = 0.80f; #ifdef EMH_SIZE_TYPE_16BIT typedef uint16_t size_type; - static constexpr size_type INACTIVE = 0xFFFE; + static constexpr size_type INACTIVE = 0xFFFF; #elif EMH_SIZE_TYPE_64BIT typedef uint64_t size_type; static constexpr size_type INACTIVE = 0 - 0x1ull; @@ -298,21 +297,25 @@ struct entry { std::swap(first, o.first); } -#ifndef EMH_ORDER_KV - Second second;//int +#if EMH_ORDER_KV || EMH_SIZE_TYPE_64BIT + Second second; size_type bucket; - First first; //long + First first; #else - First first; //long + First first; size_type bucket; - Second second;//int + Second second; #endif -};// __attribute__ ((packed)); +}; /// A cache-friendly hash table with open addressing, linear/qua probing and power-of-two capacity template , typename EqT = std::equal_to> class HashMap { +#ifndef EMH_DEFAULT_LOAD_FACTOR + constexpr static float EMH_DEFAULT_LOAD_FACTOR = 0.80f; +#endif + public: typedef HashMap htype; typedef std::pair value_type; @@ -350,7 +353,11 @@ public: iterator() : _map(nullptr) { } iterator(const const_iterator& it) : _map(it._map), _bucket(it._bucket), _from(it._from), _bmask(it._bmask) { } iterator(const htype* hash_map, size_type bucket, bool) : _map(hash_map), _bucket(bucket) { init(); } +#if EMH_ITER_SAFE + iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { init(); } +#else iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { _bmask = _from = 0; } +#endif void init() { @@ -445,7 +452,11 @@ public: const_iterator(const iterator& it) : _map(it._map), _bucket(it._bucket), _from(it._from), _bmask(it._bmask) { } const_iterator(const htype* hash_map, size_type bucket, bool) : _map(hash_map), _bucket(bucket) { init(); } +#if EMH_ITER_SAFE + const_iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { init(); } +#else const_iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { _bmask = _from = 0; } +#endif void init() { @@ -522,23 +533,23 @@ public: rehash(bucket); } - HashMap(size_type bucket = 2, float mlf = EMH_DEFAULT_LOAD_FACTOR) + HashMap(size_type bucket = 2, float mlf = EMH_DEFAULT_LOAD_FACTOR) noexcept { init(bucket, mlf); } - size_type AllocSize(size_type num_buckets) const + size_t AllocSize(uint64_t num_buckets) const { - return num_buckets * sizeof(PairT) + EPACK_SIZE * sizeof(PairT) + (num_buckets + 7) / 8 + BIT_PACK; + return (num_buckets + EPACK_SIZE) * sizeof(PairT) + (num_buckets + 7) / 8 + BIT_PACK; } - HashMap(const HashMap& rhs) + HashMap(const HashMap& rhs) noexcept { _pairs = (PairT*)malloc(AllocSize(rhs._num_buckets)); clone(rhs); } - HashMap(HashMap&& rhs) + HashMap(HashMap&& rhs) noexcept { #ifndef EMH_ZERO_MOVE init(4); @@ -564,7 +575,7 @@ public: emplace(*first); } - HashMap& operator=(const HashMap& rhs) + HashMap& operator= (const HashMap& rhs) noexcept { if (this == &rhs) return *this; @@ -581,7 +592,7 @@ public: return *this; } - HashMap& operator=(HashMap&& rhs) + HashMap& operator= (HashMap&& rhs) noexcept { if (this != &rhs) { swap(rhs); @@ -621,7 +632,7 @@ public: void clone(const HashMap& rhs) { _hasher = rhs._hasher; -// _eq = rhs._eq; + //_eq = rhs._eq; _num_filled = rhs._num_filled; _mask = rhs._mask; @@ -646,18 +657,17 @@ public: void swap(HashMap& rhs) { std::swap(_hasher, rhs._hasher); - // std::swap(_eq, rhs._eq); + //std::swap(_eq, rhs._eq); std::swap(_pairs, rhs._pairs); std::swap(_num_buckets, rhs._num_buckets); std::swap(_num_filled, rhs._num_filled); std::swap(_mask, rhs._mask); std::swap(_mlf, rhs._mlf); std::swap(_bitmask, rhs._bitmask); - //std::swap(EMH_BUCKET(_pairs, _num_buckets), EMH_BUCKET(rhs._pairs, rhs._num_buckets)); } // ------------------------------------------------------------- - iterator begin() + iterator begin() noexcept { #ifdef EMH_ZERO_MOVE if (0 == _num_filled) @@ -672,7 +682,7 @@ public: return it.next(); } - const_iterator cbegin() const + const_iterator cbegin() const noexcept { #ifdef EMH_ZERO_MOVE if (0 == _num_filled) @@ -697,9 +707,9 @@ public: return {this, bucket, true}; } - const_iterator begin() const { return cbegin(); } + const_iterator begin() const noexcept { return cbegin(); } - iterator end() { return {this, _num_buckets}; } + iterator end() noexcept { return {this, _num_buckets}; } const_iterator cend() const { return {this, _num_buckets}; } const_iterator end() const { return cend(); } @@ -719,10 +729,9 @@ public: } constexpr float max_load_factor() const { return (1 << 27) / (float)_mlf; } - constexpr size_type max_size() const { return (1ull << (sizeof(size_type) * 8 - 2)); } + constexpr size_type max_size() const { return 1ull << (sizeof(size_type) * 8 - 1); } constexpr size_type max_bucket_count() const { return max_size(); } -#if EMH_STATIS size_type bucket_main() const { auto main_size = 0; @@ -733,6 +742,7 @@ public: return main_size; } +#if EMH_STATIS //Returns the bucket number where the element with key k is located. size_type bucket(const KeyT& key) const { @@ -981,7 +991,7 @@ public: } } - /// Returns false if key isn't found. +#ifdef EMH_EXT bool try_get(const KeyT& key, ValueT& val) const noexcept { const auto bucket = find_filled_bucket(key); @@ -1012,6 +1022,7 @@ public: const auto bucket = find_filled_bucket(key); return bucket == _num_buckets ? ValueT() : EMH_VAL(_pairs, bucket); } +#endif // ----------------------------------------------------- template @@ -1066,7 +1077,7 @@ public: return do_insert(value); } - std::pair insert(value_type && value) + std::pair insert(value_type&& value) { check_expand_need(); return do_insert(std::move(value)); @@ -1087,34 +1098,6 @@ public: do_insert(it->first, it->second); } -#if 0 - template - void insert2(Iter begin, Iter end) - { - Iter citbeg = begin; - Iter citend = begin; - reserve(std::distance(begin, end) + _num_filled); - for (; begin != end; ++begin) { - if (try_insert_mainbucket(begin->first, begin->second) == INACTIVE) { - std::swap(*begin, *citend++); - } - } - - for (; citbeg != citend; ++citbeg) - insert(*citbeg); - } - - size_type try_insert_mainbucket(const KeyT& key, const ValueT& val) - { - const auto bucket = hash_key(key) & _mask; - if (!EMH_EMPTY(_pairs, bucket)) - return INACTIVE; - - EMH_NEW(key, val, bucket); - return bucket; - } -#endif - template void insert_unique(Iter begin, Iter end) { @@ -1123,15 +1106,10 @@ public: do_insert_unqiue(*begin); } - /// Same as above, but contains(key) MUST be false - size_type insert_unique(KeyT&& key, ValueT&& val) - { - return do_insert_unqiue(std::move(key), std::forward(val)); - } - - size_type insert_unique(const KeyT& key, ValueT&& val) + template + size_type insert_unique(K&& key, V&& val) { - return do_insert_unqiue(key, std::forward(val)); + return do_insert_unqiue(std::forward(key), std::forward(val)); } size_type insert_unique(value_type&& value) @@ -1157,7 +1135,7 @@ public: std::pair insert_or_assign(KeyT&& key, ValueT&& val) { return do_assign(std::move(key), std::forward(val)); } template - inline std::pair emplace(Args&&... args) + inline std::pair emplace(Args&&... args) noexcept { check_expand_need(); return do_insert(std::forward(args)...); @@ -1186,13 +1164,13 @@ public: } template - inline size_type emplace_unique(Args&&... args) + inline size_type emplace_unique(Args&&... args) noexcept { return insert_unique(std::forward(args)...); } /* Check if inserting a new value rather than overwriting an old entry */ - ValueT& operator[](const KeyT& key) + ValueT& operator[](const KeyT& key) noexcept { check_expand_need(); @@ -1205,7 +1183,7 @@ public: return EMH_VAL(_pairs, bucket); } - ValueT& operator[](KeyT&& key) + ValueT& operator[](KeyT&& key) noexcept { check_expand_need(); @@ -1261,16 +1239,6 @@ public: clear_bucket(bucket); } - iterator erase(const_iterator first, const_iterator last) - { - auto iend = cend(); - auto next = first; - for (; next.bucket() < last.bucket() && next != iend; ) - next = erase(next); - - return {this, next.bucket()}; - } - template size_type erase_if(Pred pred) { @@ -1313,8 +1281,10 @@ public: /// Remove all elements, keeping full capacity. void clear() { - if (!is_triviall_destructable() && _num_filled) + if (!is_triviall_destructable() && _num_filled) { memset(_bitmask, 0xFFFFFFFF, (_num_buckets + 7) / 8); + if (_num_buckets < 8) _bitmask[0] = (1 << _num_buckets) - 1; + } else if (_num_filled) clearkv(); @@ -1351,10 +1321,12 @@ public: if (required_buckets < _num_filled) return; - auto num_buckets = _num_filled > (1u << 16) ? (1u << 16) : 2u; - while (num_buckets < required_buckets) { num_buckets *= 2; } - + uint64_t buckets = _num_filled > (1u << 16) ? (1u << 16) : 2u; + while (buckets < required_buckets) { buckets *= 2; } + assert(buckets < max_size() && buckets > _num_filled); //TODO: throwOverflowError + + auto num_buckets = (size_type)buckets; auto old_num_filled = _num_filled; auto old_mask = _num_buckets - 1; auto old_pairs = _pairs; @@ -1391,8 +1363,9 @@ public: if (_num_filled > EMH_REHASH_LOG) { auto mbucket = bucket_main(); char buff[255] = {0}; - sprintf(buff, " _num_filled/aver_size/K.V/pack/ = %u/%2.lf/%s.%s/%zd", - _num_filled, double (_num_filled) / mbucket, typeid(KeyT).name(), typeid(ValueT).name(), sizeof(_pairs[0])); + sprintf(buff, " _num_filled/collision/main/K.V/pack/ = %u/%.2lf%%(%.2lf%%)/%s.%s/%zd", + _num_filled, 200.0f * (_num_filled - mbucket) / _mask, 100.0f * mbucket / _mask, + typeid(KeyT).name(), typeid(ValueT).name(), sizeof(_pairs[0])); #ifdef EMH_LOG static size_t ihashs = 0; EMH_LOG << "rhash_nums = " << ihashs ++ << "|" <<__FUNCTION__ << "|" << buff << endl; @@ -1538,12 +1511,7 @@ private: if (EMH_EMPTY(_pairs, bucket)) return _num_buckets; - auto next_bucket = EMH_BUCKET(_pairs, bucket); - if (_eq(key, EMH_KEY(_pairs, bucket))) - return bucket; - else if (next_bucket == bucket) - return _num_buckets; - + auto next_bucket = bucket; while (true) { if (_eq(key, EMH_KEY(_pairs, next_bucket))) return next_bucket; @@ -1565,36 +1533,7 @@ private: if (EMH_EMPTY(_pairs, bucket)) return _num_buckets; -#if 1 - if (_eq(key, EMH_KEY(_pairs, bucket))) - return bucket; - - auto next_bucket = EMH_BUCKET(_pairs, bucket); - if (next_bucket == bucket) - return _num_buckets; -#elif 0 - else if (_eq(key, EMH_KEY(_pairs, bucket))) - return bucket; - else if (next_bucket == bucket) - return _num_buckets; - - else if (_eq(key, EMH_KEY(_pairs, next_bucket))) - return next_bucket; - const auto nbucket = EMH_BUCKET(_pairs, next_bucket); - if (nbucket == next_bucket) - return _num_buckets; - next_bucket = nbucket; -#elif 0 - const auto bucket = hash_key(key) & _mask; - if (EMH_EMPTY(_pairs, bucket)) - return _num_buckets; - else if (_eq(key, EMH_KEY(_pairs, bucket))) - return bucket; - - auto next_bucket = EMH_BUCKET(_pairs, bucket); - if (next_bucket == bucket) - return _num_buckets; -#endif + auto next_bucket = bucket; // else if (bucket != (hash_key(bucket_key) & _mask)) // return _num_buckets; @@ -1628,11 +1567,7 @@ private: EMH_BUCKET(_pairs, new_bucket) = new_bucket; EMH_BUCKET(_pairs, prev_bucket) = new_bucket; - //set new bucket bit EMH_SET(new_bucket); - - //clear kickout bit - //EMH_CLS(kbucket); return kbucket; } @@ -1643,8 +1578,8 @@ private: ** put new key in its main position; otherwise (colliding bucket is in its main ** position), new key goes to an empty position. ***/ - template - size_type find_or_allocate(const Key& key, bool& isempty) +// template + size_type find_or_allocate(const KeyT& key, bool& isempty) { const auto bucket = hash_key(key) & _mask; const auto& bucket_key = EMH_KEY(_pairs, bucket); @@ -1699,28 +1634,36 @@ private: // key is not in this map. Find a place to put it. size_type find_empty_bucket(const size_type bucket_from, const size_t main_bucket) { -#if 1 || __arm64__ || __aarch64__ +#ifdef EMH_ALIGN64 // only works 64bit const auto boset = bucket_from % MASK_BIT; auto* const align = _bitmask + bucket_from / MASK_BIT; const auto bmask = ((size_t)align[1] << (MASK_BIT - boset)) | (align[0] >> boset); -#else - const auto boset = bucket_from % 8; - auto* const align = (uint8_t*)_bitmask + bucket_from / 8; - const auto bmask = *(size_t*)(align) >> boset; -#endif if (EMH_LIKELY(bmask != 0)) return bucket_from + CTZ(bmask); +#elif EMH_ITER_SAFE + const auto boset = bucket_from % 8; + auto* const start = (uint8_t*)_bitmask + bucket_from / 8; + size_t bmask; memcpy(&bmask, start + 0, sizeof(bmask)); bmask >>= boset;// bmask |= ((size_t)start[8] << (SIZE_BIT - boset)); + if (EMH_LIKELY(bmask != 0)) + return bucket_from + CTZ(bmask); +#else + const auto boset = main_bucket % 8; + auto* const align = (uint8_t*)_bitmask + main_bucket / 8; + const size_t bmask = (*(size_t*)(align) >> boset);// & 0xF0F0F0F0FF0FF0FFull;// + if (EMH_LIKELY(bmask != 0)) + return main_bucket + CTZ(bmask); +#endif const auto qmask = _mask / SIZE_BIT; if (1) { - const auto step = (bucket_from - SIZE_BIT / 2) & qmask; + const auto step = (main_bucket - SIZE_BIT / 4) & qmask; const auto bmask3 = *((size_t*)_bitmask + step); if (bmask3 != 0) return step * SIZE_BIT + CTZ(bmask3); } auto& _last = EMH_BUCKET(_pairs, _num_buckets); - for (; ; ) { //2.4.7 + for (; ;) { const auto bmask2 = *((size_t*)_bitmask + _last); if (bmask2 != 0) return _last * SIZE_BIT + CTZ(bmask2); @@ -1733,6 +1676,38 @@ private: } _last = (_last + 1) & qmask; } + + return 0; + } + + // key is not in this map. Find a place to put it. + size_type find_unique_empty(const size_type bucket_from, const size_t main_bucket) + { +#ifdef EMH_ALIGN64 + const auto boset = bucket_from % MASK_BIT; + auto* const align = _bitmask + bucket_from / MASK_BIT; + const auto bmask = ((size_t)align[1] << (MASK_BIT - boset)) | (align[0] >> boset); + static_assert(sizeof(size_t) > 4); +#elif EMH_ITER_SAFE + const auto boset = bucket_from % 8; + auto* const start = (uint8_t*)_bitmask + bucket_from / 8; + size_t bmask; memcpy(&bmask, start + 0, sizeof(bmask)); bmask >>= boset; +#else + const auto boset = bucket_from % 8; + auto* const align = (uint8_t*)_bitmask + bucket_from / 8; + const auto bmask = (*(size_t*)(align) >> boset); //maybe not aligned and warning +#endif + if (EMH_LIKELY(bmask != 0)) + return bucket_from + CTZ(bmask); + + const auto qmask = _mask / SIZE_BIT; + for (auto last = (bucket_from + _mask) & qmask; ;) { + const auto bmask2 = *((size_t*)_bitmask + last);// & 0xF0F0F0F0FF0FF0FFull; + if (EMH_LIKELY(bmask2 != 0)) + return last * SIZE_BIT + CTZ(bmask2); + last = (last + 1) & qmask; + } + return 0; } @@ -1780,16 +1755,17 @@ private: next_bucket = find_last_bucket(next_bucket); //find a new empty and link it to tail - return EMH_BUCKET(_pairs, next_bucket) = find_empty_bucket(next_bucket, bucket); + return EMH_BUCKET(_pairs, next_bucket) = find_unique_empty(next_bucket, bucket); } +#if EMH_INT_HASH static constexpr uint64_t KC = UINT64_C(11400714819323198485); static inline uint64_t hash64(uint64_t key) { -#if __SIZEOF_INT128__ && EMH_FIBONACCI_HASH == 1 +#if __SIZEOF_INT128__ && EMH_INT_HASH == 1 __uint128_t r = key; r *= KC; return (uint64_t)(r >> 64) + (uint64_t)r; -#elif EMH_FIBONACCI_HASH == 2 +#elif EMH_INT_HASH == 2 //MurmurHash3Mixer uint64_t h = key; h ^= h >> 33; @@ -1798,18 +1774,20 @@ private: h *= 0xc4ceb9fe1a85ec53; h ^= h >> 33; return h; -#elif _WIN64 && EMH_FIBONACCI_HASH == 1 +#elif _WIN64 && EMH_INT_HASH == 1 uint64_t high; return _umul128(key, KC, &high) + high; -#elif EMH_FIBONACCI_HASH == 3 +#elif EMH_INT_HASH == 3 auto ror = (key >> 32) | (key << 32); auto low = key * 0xA24BAED4963EE407ull; auto high = ror * 0x9FB21C651E98DF25ull; auto mix = low + high; return mix; -#elif EMH_FIBONACCI_HASH == 1 +#elif EMH_INT_HASH == 1 uint64_t r = key * UINT64_C(0xca4bcaa75ec3f625); return (r >> 32) + r; +#elif EMH_WYHASH64 + return wyhash64(key, KC); #else uint64_t x = key; x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9); @@ -1818,16 +1796,15 @@ private: return x; #endif } +#endif template::value, size_type>::type = 0> inline size_type hash_key(const UType key) const { -#ifdef EMH_FIBONACCI_HASH +#if EMH_INT_HASH return hash64(key); #elif EMH_IDENTITY_HASH return key + (key >> (sizeof(UType) * 4)); -#elif EMH_WYHASH64 - return wyhash64(key, KC); #else return (size_type)_hasher(key); #endif @@ -1836,7 +1813,7 @@ private: template::value, size_type>::type = 0> inline size_type hash_key(const UType& key) const { -#ifdef WYHASH_LITTLE_ENDIAN +#if WYHASH_LITTLE_ENDIAN return wyhash(key.data(), key.size(), key.size()); #else return (size_type)_hasher(key); @@ -1846,11 +1823,7 @@ private: template::value && !std::is_same::value, size_type>::type = 0> inline size_type hash_key(const UType& key) const { -#ifdef EMH_FIBONACCI_HASH - return _hasher(key) * KC; -#else return (size_type)_hasher(key); -#endif } private: @@ -1870,15 +1843,15 @@ private: static constexpr uint32_t SIZE_BIT = sizeof(size_t) * 8; static constexpr uint32_t EPACK_SIZE = sizeof(PairT) >= sizeof(size_t) == 0 ? 1 : 2; // > 1 }; -} // namespace emhash +} +// namespace emhash7 #if __cplusplus >= 201103L -//template using emhash7 = emhash7::HashMap, std::equal_to>; +//template using ehmap7 = emhash7::HashMap, std::equal_to>; #endif //TODO //2. improve rehash and find miss performance(reduce peak memory) //3. dump or Serialization interface //4. node hash map support -//5. support load_factor > 1.0 -//6. add grow ration -//8. ... https://godbolt.org/ +//5. load_factor > 1.0 && add grow ration +//... https://godbolt.org/ diff --git a/benchmarks/external/emhash/wyhash.h b/benchmarks/external/emhash/wyhash.h deleted file mode 100644 index b89352a7..00000000 --- a/benchmarks/external/emhash/wyhash.h +++ /dev/null @@ -1,272 +0,0 @@ -// This is free and unencumbered software released into the public domain under The Unlicense (http://unlicense.org/) -// main repo: https://github.com/wangyi-fudan/wyhash -// author: 王一 Wang Yi -// contributors: Reini Urban, Dietrich Epp, Joshua Haberman, Tommy Ettinger, Daniel Lemire, Otmar Ertl, cocowalla, leo-yuriev, Diego Barrios Romero, paulie-g, dumblob, Yann Collet, ivte-ms, hyb, James Z.M. Gao, easyaspi314 (Devin), TheOneric - -/* quick example: - uint64_t _wyp[4]; - make_secret(time(NULL),_wyp); - string s="fjsakfdsjkf"; - uint64_t hash=wyhash(s.c_str(), s.size(), 0, _wyp); -*/ - -#ifndef wyhash_final_version_3 -#define wyhash_final_version_3 - -#ifndef WYHASH_CONDOM -//protections that produce different results: -//1: normal valid behavior -//2: extra protection against entropy loss (probability=2^-63), aka. "blind multiplication" -#define WYHASH_CONDOM 1 -#endif - -#ifndef WYHASH_32BIT_MUM -//0: normal version, slow on 32 bit systems -//1: faster on 32 bit systems but produces different results, incompatible with wy2u0k function -#define WYHASH_32BIT_MUM 0 -#endif - -//includes -#include -#include -#if defined(_MSC_VER) && defined(_M_X64) - #include - #pragma intrinsic(_umul128) -#endif - -//likely and unlikely macros -#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__) - #define _likely_(x) __builtin_expect(x,1) - #define _unlikely_(x) __builtin_expect(x,0) -#else - #define _likely_(x) (x) - #define _unlikely_(x) (x) -#endif - -//128bit multiply function -static inline uint64_t _wyrot(uint64_t x) { return (x>>32)|(x<<32); } -static inline void _wymum(uint64_t *A, uint64_t *B){ -#if(WYHASH_32BIT_MUM) - uint64_t hh=(*A>>32)*(*B>>32), hl=(*A>>32)*(uint32_t)*B, lh=(uint32_t)*A*(*B>>32), ll=(uint64_t)(uint32_t)*A*(uint32_t)*B; - #if(WYHASH_CONDOM>1) - *A^=_wyrot(hl)^hh; *B^=_wyrot(lh)^ll; - #else - *A=_wyrot(hl)^hh; *B=_wyrot(lh)^ll; - #endif -#elif defined(__SIZEOF_INT128__) - __uint128_t r=*A; r*=*B; - #if(WYHASH_CONDOM>1) - *A^=(uint64_t)r; *B^=(uint64_t)(r>>64); - #else - *A=(uint64_t)r; *B=(uint64_t)(r>>64); - #endif -#elif defined(_MSC_VER) && defined(_M_X64) - #if(WYHASH_CONDOM>1) - uint64_t a, b; - a=_umul128(*A,*B,&b); - *A^=a; *B^=b; - #else - *A=_umul128(*A,*B,B); - #endif -#else - uint64_t ha=*A>>32, hb=*B>>32, la=(uint32_t)*A, lb=(uint32_t)*B, hi, lo; - uint64_t rh=ha*hb, rm0=ha*lb, rm1=hb*la, rl=la*lb, t=rl+(rm0<<32), c=t>32)+(rm1>>32)+c; - #if(WYHASH_CONDOM>1) - *A^=lo; *B^=hi; - #else - *A=lo; *B=hi; - #endif -#endif -} - -//multiply and xor mix function, aka MUM -static inline uint64_t _wymix(uint64_t A, uint64_t B){ _wymum(&A,&B); return A^B; } - -//endian macros -#ifndef WYHASH_LITTLE_ENDIAN - #if defined(_WIN32) || defined(__LITTLE_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) - #define WYHASH_LITTLE_ENDIAN 1 - #elif defined(__BIG_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) - #define WYHASH_LITTLE_ENDIAN 0 - #else - #warning could not determine endianness! Falling back to little endian. - #define WYHASH_LITTLE_ENDIAN 1 - #endif -#endif - -//read functions -#if (WYHASH_LITTLE_ENDIAN) -static inline uint64_t _wyr8(const uint8_t *p) { uint64_t v; memcpy(&v, p, 8); return v;} -static inline uint64_t _wyr4(const uint8_t *p) { uint32_t v; memcpy(&v, p, 4); return v;} -#elif defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__) -static inline uint64_t _wyr8(const uint8_t *p) { uint64_t v; memcpy(&v, p, 8); return __builtin_bswap64(v);} -static inline uint64_t _wyr4(const uint8_t *p) { uint32_t v; memcpy(&v, p, 4); return __builtin_bswap32(v);} -#elif defined(_MSC_VER) -static inline uint64_t _wyr8(const uint8_t *p) { uint64_t v; memcpy(&v, p, 8); return _byteswap_uint64(v);} -static inline uint64_t _wyr4(const uint8_t *p) { uint32_t v; memcpy(&v, p, 4); return _byteswap_ulong(v);} -#else -static inline uint64_t _wyr8(const uint8_t *p) { - uint64_t v; memcpy(&v, p, 8); - return (((v >> 56) & 0xff)| ((v >> 40) & 0xff00)| ((v >> 24) & 0xff0000)| ((v >> 8) & 0xff000000)| ((v << 8) & 0xff00000000)| ((v << 24) & 0xff0000000000)| ((v << 40) & 0xff000000000000)| ((v << 56) & 0xff00000000000000)); -} -static inline uint64_t _wyr4(const uint8_t *p) { - uint32_t v; memcpy(&v, p, 4); - return (((v >> 24) & 0xff)| ((v >> 8) & 0xff00)| ((v << 8) & 0xff0000)| ((v << 24) & 0xff000000)); -} -#endif -static inline uint64_t _wyr3(const uint8_t *p, size_t k) { return (((uint64_t)p[0])<<16)|(((uint64_t)p[k>>1])<<8)|p[k-1];} -//wyhash main function -static inline uint64_t wyhash(const void *key, size_t len, uint64_t seed, const uint64_t *secret){ - const uint8_t *p=(const uint8_t *)key; seed^=*secret; uint64_t a, b; - if(_likely_(len<=16)){ - if(_likely_(len>=4)){ a=(_wyr4(p)<<32)|_wyr4(p+((len>>3)<<2)); b=(_wyr4(p+len-4)<<32)|_wyr4(p+len-4-((len>>3)<<2)); } - else if(_likely_(len>0)){ a=_wyr3(p,len); b=0;} - else a=b=0; - } - else{ - size_t i=len; - if(_unlikely_(i>48)){ - uint64_t see1=seed, see2=seed; - do{ - seed=_wymix(_wyr8(p)^secret[1],_wyr8(p+8)^seed); - see1=_wymix(_wyr8(p+16)^secret[2],_wyr8(p+24)^see1); - see2=_wymix(_wyr8(p+32)^secret[3],_wyr8(p+40)^see2); - p+=48; i-=48; - }while(_likely_(i>48)); - seed^=see1^see2; - } - while(_unlikely_(i>16)){ seed=_wymix(_wyr8(p)^secret[1],_wyr8(p+8)^seed); i-=16; p+=16; } - a=_wyr8(p+i-16); b=_wyr8(p+i-8); - } - return _wymix(secret[1]^len,_wymix(a^secret[1],b^seed)); -} - -//the default secret parameters -static const uint64_t _wyp[4] = {0xa0761d6478bd642full, 0xe7037ed1a0b428dbull, 0x8ebc6af09c88c6e3ull, 0x589965cc75374cc3ull}; - -static inline uint64_t wyhash(const void *key, size_t len, uint64_t seed) { return wyhash(key, len, seed, _wyp); } - -//a useful 64bit-64bit mix function to produce deterministic pseudo random numbers that can pass BigCrush and PractRand -static inline uint64_t wyhash64(uint64_t A, uint64_t B){ A^=0xa0761d6478bd642full; B^=0xe7037ed1a0b428dbull; _wymum(&A,&B); return _wymix(A^0xa0761d6478bd642full,B^0xe7037ed1a0b428dbull);} - -//The wyrand PRNG that pass BigCrush and PractRand -static inline uint64_t wyrand(uint64_t *seed){ *seed+=0xa0761d6478bd642full; return _wymix(*seed,*seed^0xe7037ed1a0b428dbull);} - -//convert any 64 bit pseudo random numbers to uniform distribution [0,1). It can be combined with wyrand, wyhash64 or wyhash. -static inline double wy2u01(uint64_t r){ const double _wynorm=1.0/(1ull<<52); return (r>>12)*_wynorm;} - -//convert any 64 bit pseudo random numbers to APPROXIMATE Gaussian distribution. It can be combined with wyrand, wyhash64 or wyhash. -static inline double wy2gau(uint64_t r){ const double _wynorm=1.0/(1ull<<20); return ((r&0x1fffff)+((r>>21)&0x1fffff)+((r>>42)&0x1fffff))*_wynorm-3.0;} - -#if(!WYHASH_32BIT_MUM) -//fast range integer random number generation on [0,k) credit to Daniel Lemire. May not work when WYHASH_32BIT_MUM=1. It can be combined with wyrand, wyhash64 or wyhash. -static inline uint64_t wy2u0k(uint64_t r, uint64_t k){ _wymum(&r,&k); return k; } -#endif - -//make your own secret -static inline void make_secret(uint64_t seed, uint64_t *secret){ - uint8_t c[] = {15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240 }; - for(size_t i=0;i<4;i++){ - uint8_t ok; - do{ - ok=1; secret[i]=0; - for(size_t j=0;j<64;j+=8) secret[i]|=((uint64_t)c[wyrand(&seed)%sizeof(c)])<> 1) & 0x5555555555555555; - x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); - x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f; - x = (x * 0x0101010101010101) >> 56; - if(x!=32){ ok=0; break; } -#endif - } - }while(!ok); - } -} - -/* This is world's fastest hash map: 2x faster than bytell_hash_map. - It does not store the keys, but only the hash/signature of keys. - First we use pos=hash1(key) to approximately locate the bucket. - Then we search signature=hash2(key) from pos linearly. - If we find a bucket with matched signature we report the bucket - Or if we meet a bucket whose signature=0, we report a new position to insert - The signature collision probability is very low as we usually searched N~10 buckets. - By combining hash1 and hash2, we acturally have 128 bit anti-collision strength. - hash1 and hash2 can be the same function, resulting lower collision resistance but faster. - The signature is 64 bit, but can be modified to 32 bit if necessary for save space. - The above two can be activated by define WYHASHMAP_WEAK_SMALL_FAST - simple examples: - const size_t size=213432; - vector idx(size); // allocate the index of fixed size. idx MUST be zeroed. - vector value(size); // we only care about the index, user should maintain his own value vectors. - string key="dhskfhdsj" // the object to be inserted into idx - size_t pos=wyhashmap(idx.data(), idx.size(), key.c_str(), key.size(), 1); // get the position and insert - if(pos -*/ diff --git a/benchmarks/external/update.sh b/benchmarks/external/update.sh index c9681485..45b472b1 100644 --- a/benchmarks/external/update.sh +++ b/benchmarks/external/update.sh @@ -18,7 +18,7 @@ wget "$tsl_r/robin_growth_policy.h" -O "tsl/robin_growth_policy.h" wget "$tsl_r/robin_hash.h" -O "tsl/robin_hash.h" wget "$tsl_r/robin_map.h" -O "tsl/robin_map.h" -wget "$ktprime/thirdparty/wyhash.h" -O "emhash/wyhash.h" +#wget "$ktprime/thirdparty/wyhash.h" -O "emhash/wyhash.h" wget "$ktprime/hash_table7.hpp" -O "emhash/hash_table7.hpp" #wget "$tsl_h/hopscotch_growth_policy.h" -O "tsl/hopscotch_growth_policy.h" -- cgit v1.2.3