Some more docs. Renamed (half-)internal template parameter i_size => i_ssize. Updated external cpp maps for benchmarks.

4 files changed, 95 insertions, 22 deletions

diff --git a/misc/benchmarks/external/ankerl/robin_hood.h b/misc/benchmarks/external/ankerl/robin_hood.h
index 0af031f5..b4e0fbc5 100644
--- a/misc/benchmarks/external/ankerl/robin_hood.h
+++ b/misc/benchmarks/external/ankerl/robin_hood.h
@@ -206,7 +206,7 @@ static Counts& counts() {
 
 // workaround missing "is_trivially_copyable" in g++ < 5.0
 // See https://stackoverflow.com/a/31798726/48181
-#if defined(__GNUC__) && __GNUC__ < 5
+#if defined(__GNUC__) && __GNUC__ < 5 && !defined(__clang__)
 #    define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__)
 #else
 #    define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value
diff --git a/misc/benchmarks/external/ankerl/unordered_dense.h b/misc/benchmarks/external/ankerl/unordered_dense.h
index 05c7e928..faad051d 100644
--- a/misc/benchmarks/external/ankerl/unordered_dense.h
+++ b/misc/benchmarks/external/ankerl/unordered_dense.h
@@ -1,12 +1,12 @@
 ///////////////////////// ankerl::unordered_dense::{map, set} /////////////////////////
 
 // A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion.
-// Version 3.0.0
+// Version 3.1.0
 // https://github.com/martinus/unordered_dense
 //
 // Licensed under the MIT License <http://opensource.org/licenses/MIT>.
 // SPDX-License-Identifier: MIT
-// Copyright (c) 2022 Martin Leitner-Ankerl <[email protected]>
+// Copyright (c) 2022-2023 Martin Leitner-Ankerl <[email protected]>
 //
 // Permission is hereby granted, free of charge, to any person obtaining a copy
 // of this software and associated documentation files (the "Software"), to deal
@@ -31,7 +31,7 @@
 
 // see https://semver.org/spec/v2.0.0.html
 #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_MINOR 1 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
 #define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
 
 // API versioning with inline namespace, see https://www.foonathan.net/2018/11/inline-namespaces/
@@ -55,6 +55,18 @@
 #    define ANKERL_UNORDERED_DENSE_PACK(decl) __pragma(pack(push, 1)) decl __pragma(pack(pop))
 #endif
 
+// exceptions
+#if defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)
+#    define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() 1
+#else
+#    define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() 0
+#endif
+#ifdef _MSC_VER
+#    define ANKERL_UNORDERED_DENSE_NOINLINE __declspec(noinline)
+#else
+#    define ANKERL_UNORDERED_DENSE_NOINLINE __attribute__((noinline))
+#endif
+
 #if ANKERL_UNORDERED_DENSE_CPP_VERSION < 201703L
 #    error ankerl::unordered_dense requires C++17 or higher
 #else
@@ -73,13 +85,24 @@
 #    include <type_traits>      // for enable_if_t, declval, conditional_t, ena...
 #    include <utility>          // for forward, exchange, pair, as_const, piece...
 #    include <vector>           // for vector
+#    if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() == 0
+#        include <cstdlib> // for abort
+#    endif
 
 #    define ANKERL_UNORDERED_DENSE_PMR 0 // NOLINT(cppcoreguidelines-macro-usage)
 #    if defined(__has_include)
 #        if __has_include(<memory_resource>)
 #            undef ANKERL_UNORDERED_DENSE_PMR
 #            define ANKERL_UNORDERED_DENSE_PMR 1 // NOLINT(cppcoreguidelines-macro-usage)
-#            include <memory_resource>           // for polymorphic_allocator
+#            define ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR \
+                std::pmr::polymorphic_allocator // NOLINT(cppcoreguidelines-macro-usage)
+#            include <memory_resource>          // for polymorphic_allocator
+#        elif __has_include(<experimental/memory_resource>)
+#            undef ANKERL_UNORDERED_DENSE_PMR
+#            define ANKERL_UNORDERED_DENSE_PMR 1 // NOLINT(cppcoreguidelines-macro-usage)
+#            define ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR \
+                std::experimental::pmr::polymorphic_allocator // NOLINT(cppcoreguidelines-macro-usage)
+#            include <experimental/memory_resource>           // for polymorphic_allocator
 #        endif
 #    endif
 
@@ -99,6 +122,38 @@
 namespace ankerl::unordered_dense {
 inline namespace ANKERL_UNORDERED_DENSE_NAMESPACE {
 
+namespace detail {
+
+#    if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()
+
+// make sure this is not inlined as it is slow and dramatically enlarges code, thus making other
+// inlinings more difficult. Throws are also generally the slow path.
+[[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void on_error_key_not_found() {
+    throw std::out_of_range("ankerl::unordered_dense::map::at(): key not found");
+}
+[[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void on_error_bucket_overflow() {
+    throw std::overflow_error("ankerl::unordered_dense: reached max bucket size, cannot increase size");
+}
+[[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void on_error_too_many_elements() {
+    throw std::out_of_range("ankerl::unordered_dense::map::replace(): too many elements");
+}
+
+#    else
+
+[[noreturn]] inline void on_error_key_not_found() {
+    abort();
+}
+[[noreturn]] inline void on_error_bucket_overflow() {
+    abort();
+}
+[[noreturn]] inline void on_error_too_many_elements() {
+    abort();
+}
+
+#    endif
+
+} // namespace detail
+
 // hash ///////////////////////////////////////////////////////////////////////
 
 // This is a stripped-down implementation of wyhash: https://github.com/wangyi-fudan/wyhash
@@ -371,8 +426,10 @@ using detect_reserve = decltype(std::declval<T&>().reserve(size_t{}));
 template <typename Mapped>
 constexpr bool is_map_v = !std::is_void_v<Mapped>;
 
+// clang-format off
 template <typename Hash, typename KeyEqual>
 constexpr bool is_transparent_v = is_detected_v<detect_is_transparent, Hash>&& is_detected_v<detect_is_transparent, KeyEqual>;
+// clang-format on
 
 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>;
@@ -590,7 +647,7 @@ 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");
+            on_error_bucket_overflow();
         }
         --m_shifts;
         deallocate_buckets();
@@ -745,10 +802,10 @@ private:
 
     template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
     auto do_at(K const& key) -> Q& {
-        if (auto it = find(key); end() != it) {
+        if (auto it = find(key); ANKERL_UNORDERED_DENSE_LIKELY(end() != it)) {
             return it->second;
         }
-        throw std::out_of_range("ankerl::unordered_dense::map::at(): key not found");
+        on_error_key_not_found();
     }
 
     template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
@@ -842,8 +899,10 @@ public:
         : table(init, bucket_count, hash, KeyEqual(), alloc) {}
 
     ~table() {
-        auto ba = bucket_alloc(m_values.get_allocator());
-        bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
+        if (nullptr != m_buckets) {
+            auto ba = bucket_alloc(m_values.get_allocator());
+            bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
+        }
     }
 
     auto operator=(table const& other) -> table& {
@@ -985,10 +1044,9 @@ public:
     // 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");
+        if (ANKERL_UNORDERED_DENSE_UNLIKELY(container.size() > max_size())) {
+            on_error_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;
@@ -1479,10 +1537,10 @@ template <class Key,
           class Hash = hash<Key>,
           class KeyEqual = std::equal_to<Key>,
           class Bucket = bucket_type::standard>
-using map = detail::table<Key, T, Hash, KeyEqual, std::pmr::polymorphic_allocator<std::pair<Key, T>>, Bucket>;
+using map = detail::table<Key, T, Hash, KeyEqual, ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR<std::pair<Key, T>>, Bucket>;
 
 template <class Key, class Hash = hash<Key>, class KeyEqual = std::equal_to<Key>, class Bucket = bucket_type::standard>
-using set = detail::table<Key, void, Hash, KeyEqual, std::pmr::polymorphic_allocator<Key>, Bucket>;
+using set = detail::table<Key, void, Hash, KeyEqual, ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR<Key>, Bucket>;
 
 } // namespace pmr
 
@@ -1501,6 +1559,7 @@ using set = detail::table<Key, void, Hash, KeyEqual, std::pmr::polymorphic_alloc
 namespace std { // NOLINT(cert-dcl58-cpp)
 
 template <class Key, class T, class Hash, class KeyEqual, class AllocatorOrContainer, class Bucket, class Pred>
+// NOLINTNEXTLINE(cert-dcl58-cpp)
 auto erase_if(ankerl::unordered_dense::detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket>& map, Pred pred)
     -> size_t {
     using map_t = ankerl::unordered_dense::detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket>;
diff --git a/misc/benchmarks/external/emhash/hash_table7.hpp b/misc/benchmarks/external/emhash/hash_table7.hpp
index ced0f1d0..8f8982f9 100644
--- a/misc/benchmarks/external/emhash/hash_table7.hpp
+++ b/misc/benchmarks/external/emhash/hash_table7.hpp
@@ -1,10 +1,10 @@
 // emhash7::HashMap for C++11/14/17
-// version 2.2.3
+// version 2.2.4
 // https://github.com/ktprime/ktprime/blob/master/hash_table7.hpp
 //
 // Licensed under the MIT License <http://opensource.org/licenses/MIT>.
 // SPDX-License-Identifier: MIT
-// Copyright (c) 2019-2022 Huang Yuanbing & bailuzhou AT 163.com
+// Copyright (c) 2019-2023 Huang Yuanbing & bailuzhou AT 163.com
 //
 // Permission is hereby granted, free of charge, to any person obtaining a copy
 // of this software and associated documentation files (the "Software"), to deal
@@ -166,6 +166,11 @@ namespace emhash7 {
     static constexpr size_type INACTIVE = 0 - 0x1u;
 #endif
 
+#ifndef EMH_MALIGN
+    static constexpr uint32_t EMH_MALIGN = 16;
+#endif
+static_assert(EMH_MALIGN >= 16 && 0 == (EMH_MALIGN & (EMH_MALIGN - 1)));
+
 #ifndef EMH_SIZE_TYPE_16BIT
 static_assert((int)INACTIVE < 0, "INACTIVE must negative (to int)");
 #endif
@@ -535,15 +540,25 @@ public:
         init(bucket, mlf);
     }
 
-    size_t AllocSize(uint64_t num_buckets) const
+    static size_t AllocSize(uint64_t num_buckets)
     {
         return (num_buckets + EPACK_SIZE) * sizeof(PairT) + (num_buckets + 7) / 8 + BIT_PACK;
     }
 
+    static PairT* alloc_bucket(size_type num_buckets)
+    {
+#if _WIN32
+        auto* new_pairs = (PairT*)malloc(AllocSize(num_buckets));
+#else
+        auto* new_pairs = (PairT*)aligned_alloc(EMH_MALIGN, AllocSize(num_buckets));
+#endif
+        return new_pairs;
+    }
+
     HashMap(const HashMap& rhs) noexcept
     {
         if (rhs.load_factor() > EMH_MIN_LOAD_FACTOR) {
-            _pairs = (PairT*)malloc(AllocSize(rhs._num_buckets));
+            _pairs = (PairT*)alloc_bucket(rhs._num_buckets);
             clone(rhs);
         } else {
             init(rhs._num_filled + 2, EMH_DEFAULT_LOAD_FACTOR);
@@ -596,7 +611,7 @@ public:
 
         if (_num_buckets != rhs._num_buckets) {
             free(_pairs);
-            _pairs = (PairT*)malloc(AllocSize(rhs._num_buckets));
+            _pairs = alloc_bucket(rhs._num_buckets);
         }
 
         clone(rhs);
@@ -1355,7 +1370,7 @@ public:
         _num_buckets = num_buckets;
         _mask        = num_buckets - 1;
 
-        _pairs = (PairT*)malloc(AllocSize(_num_buckets));
+        _pairs = alloc_bucket(_num_buckets);
         memset((char*)(_pairs + _num_buckets), 0, sizeof(PairT) * EPACK_SIZE);
 
         _bitmask     = decltype(_bitmask)(_pairs + EPACK_SIZE + num_buckets);
diff --git a/misc/benchmarks/shootout_hashmaps.cpp b/misc/benchmarks/shootout_hashmaps.cpp
index 78d7bce2..da523d71 100644
--- a/misc/benchmarks/shootout_hashmaps.cpp
+++ b/misc/benchmarks/shootout_hashmaps.cpp
@@ -35,7 +35,6 @@ KHASH_MAP_INIT_INT64(ii, IValue)
 // cmap template expansion
 #define i_key IKey
 #define i_val IValue
-#define i_size uint32_t // optional, enables 2x expand
 #define i_tag ii
 #define i_max_load_factor MAX_LOAD_FACTOR / 100.0f
 #include <stc/cmap.h>