Updated external benchmark hash maps to latest, and improved example lower_bound.c

3 files changed, 80 insertions, 58 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;