From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gdb-patches-bounces~public-inbox=simark.ca@sourceware.org>
Received: from simark.ca
	by simark.ca with LMTP
	id rs59BTqJhGp6EC8AWB0awg
	(envelope-from <gdb-patches-bounces~public-inbox=simark.ca@sourceware.org>)
	for <public-inbox@simark.ca>; Tue, 18 Aug 2026 12:32:58 -0400
Received: by simark.ca (Postfix, from userid 112)
	id 036181E033; Tue, 18 Aug 2026 12:32:58 -0400 (EDT)
X-Spam-Checker-Version: SpamAssassin 4.0.1 (2024-03-25) on simark.ca
X-Spam-Level: 
X-Spam-Status: No, score=-5.3 required=5.0 tests=ARC_SIGNED,ARC_VALID,BAYES_00,
	MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED autolearn=ham autolearn_force=no
	version=4.0.1
Received: from vm01.sourceware.org (vm01.sourceware.org [IPv6:2620:52:6:3111::32])
	(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
	 key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)
	(No client certificate requested)
	by simark.ca (Postfix) with ESMTPS id 07D801E033
	for <public-inbox@simark.ca>; Tue, 18 Aug 2026 12:32:55 -0400 (EDT)
Received: from vm01.sourceware.org (localhost [IPv6:::1])
	by sourceware.org (Postfix) with ESMTP id B174A4BA799C
	for <public-inbox@simark.ca>; Tue, 18 Aug 2026 16:32:53 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B174A4BA799C
Received: from simark.ca (simark.ca [158.69.221.121])
 by sourceware.org (Postfix) with ESMTPS id 0BB4B4BA2E26
 for <gdb-patches@sourceware.org>; Tue, 18 Aug 2026 16:32:17 +0000 (GMT)
DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0BB4B4BA2E26
Authentication-Results: sourceware.org;
 dmarc=fail (p=none dis=none) header.from=efficios.com
Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=efficios.com
ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0BB4B4BA2E26
Authentication-Results: sourceware.org; arc=none smtp.remote-ip=158.69.221.121
ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1787070737; cv=none;
 b=PgRBPJxKc4cXOChmehpAqv5TiEP9c7c186Xi+mBetrNSK642MvpgNxGMeVhjgv2v03V39c6Au0qm3NIhELCK4lFcUWTUHpYyCWKm4i5B2WqvJkZyXtR/Jf9dJk/qsmqLUWo8S6YSwvnLRldXR1gNO9CCwlHeKLsKl0k/1yk8TJ8=
ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key;
 t=1787070737; c=relaxed/simple;
 bh=FsZ7xWtDx+Hst46qRkC3CzZSBVEpFLsZEcSR6TZXt7c=;
 h=From:To:Subject:Date:Message-ID:MIME-Version;
 b=F2SAJLcNO9FxoGOREOTjvQm6i+Y+2LmRWcyD6V8bI/VVlIfnJySg8M8doogvNQhz4aihesUP1vNvaYUrzgTXLVUWIZn3WTSiNSr8z2fOecJHc7vpXYJK3YYSicTOEiJOa+UhgI55ZzOiU5sjoXsPcyJiByb25dtgu12QB8ZiwY8=
ARC-Authentication-Results: i=1; sourceware.org
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0BB4B4BA2E26
Received: by simark.ca (Postfix) id 303B61E033;
 Tue, 18 Aug 2026 12:32:15 -0400 (EDT)
From: Simon Marchi <simon.marchi@efficios.com>
To: gdb-patches@sourceware.org
Cc: Simon Marchi <simon.marchi@efficios.com>
Subject: [PATCH] gdbsupport: upgrade unordered_dense to v4.9.2
Date: Tue, 18 Aug 2026 12:31:59 -0400
Message-ID: <20260818163214.77765-1-simon.marchi@efficios.com>
X-Mailer: git-send-email 2.55.0
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-BeenThere: gdb-patches@sourceware.org
X-Mailman-Version: 2.1.30
Precedence: list
List-Id: Gdb-patches mailing list <gdb-patches.sourceware.org>
List-Unsubscribe: <https://sourceware.org/mailman/options/gdb-patches>,
 <mailto:gdb-patches-request@sourceware.org?subject=unsubscribe>
List-Archive: <https://sourceware.org/pipermail/gdb-patches/>
List-Post: <mailto:gdb-patches@sourceware.org>
List-Help: <mailto:gdb-patches-request@sourceware.org?subject=help>
List-Subscribe: <https://sourceware.org/mailman/listinfo/gdb-patches>,
 <mailto:gdb-patches-request@sourceware.org?subject=subscribe>
Errors-To: gdb-patches-bounces~public-inbox=simark.ca@sourceware.org

Synchronize with upstream [1], tag v4.9.2 (commit aa9af528227ab).

There is one change I am particularly happy about (even though it
doesn't change anything functionally), because I did file the issue for
that:

👉 A default-constructed map allocates nothing, and copying or move-
   assigning an empty one drops two further allocations.

Ppotentially interesting new features:

👉 map.hash_for(key) returns a precomputed hash that find, contains,
   count, equal_range and at now accept, so it's now possible for
   repeated lookups of the same key to hash it only once.

👉 hash_is_avalanching<Hash> can be used to mark a third-party
   hash as high quality without editing it, or as false_type to force
   mixing on a hash that overpromises.  The only way to mark a hash as
   avalanching before that was to define the is_avalanching type in the
   hash type itself.

Behaviour changes that could affect us:

👉 The is_avalanching marker is now read as a compile-time bool, the way
   Boost.Unordered reads it.  "using is_avalanching = std::false_type;"
   previously meant yes here and now correctly means no.  "= void" still
   works.  Anything else is now a compile error rather than a guess.

There are some claimed performance improvements, and some bug fixes, but
nothing that I could see for things we actually use.

I did a test run on Linux, didn't spot any regression.

[1] https://github.com/martinus/unordered_dense/

Change-Id: I8b2dda1a74b59f78a7dcc9f1b1931a03e8781393
---
 gdbsupport/unordered_dense/stl.h             |    8 +-
 gdbsupport/unordered_dense/unordered_dense.h | 1037 +++++++++++++++---
 2 files changed, 873 insertions(+), 172 deletions(-)

diff --git a/gdbsupport/unordered_dense/stl.h b/gdbsupport/unordered_dense/stl.h
index 8c198773195e..2389d0c8cf0a 100644
--- a/gdbsupport/unordered_dense/stl.h
+++ b/gdbsupport/unordered_dense/stl.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 4.8.0
+// Version 4.9.2
 // https://github.com/martinus/unordered_dense
 //
 // Licensed under the MIT License <http://opensource.org/licenses/MIT>.
 // SPDX-License-Identifier: MIT
-// Copyright (c) 2022-2024 Martin Leitner-Ankerl <martin.ankerl@gmail.com>
+// Copyright (c) 2022 Martin Leitner-Ankerl <martin.ankerl@gmail.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
@@ -77,7 +77,9 @@
 
 #if defined(_MSC_VER) && defined(_M_X64)
 #    include <intrin.h>
-#    pragma intrinsic(_umul128)
+#    if !defined(_M_ARM64EC)
+#        pragma intrinsic(_umul128)
+#    endif
 #endif
 
 #endif
diff --git a/gdbsupport/unordered_dense/unordered_dense.h b/gdbsupport/unordered_dense/unordered_dense.h
index 56383b6ce8f7..58bb57da12ca 100644
--- a/gdbsupport/unordered_dense/unordered_dense.h
+++ b/gdbsupport/unordered_dense/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 4.8.0
+// Version 4.9.2
 // https://github.com/martinus/unordered_dense
 //
 // Licensed under the MIT License <http://opensource.org/licenses/MIT>.
 // SPDX-License-Identifier: MIT
-// Copyright (c) 2022-2024 Martin Leitner-Ankerl <martin.ankerl@gmail.com>
+// Copyright (c) 2022 Martin Leitner-Ankerl <martin.ankerl@gmail.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
@@ -31,8 +31,8 @@
 
 // see https://semver.org/spec/v2.0.0.html
 #define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 4 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes
-#define ANKERL_UNORDERED_DENSE_VERSION_MINOR 8 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
-#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
+#define ANKERL_UNORDERED_DENSE_VERSION_MINOR 9 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
+#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 2 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
 
 // API versioning with inline namespace, see https://www.foonathan.net/2018/11/inline-namespaces/
 
@@ -70,6 +70,13 @@
 #    define ANKERL_UNORDERED_DENSE_NOINLINE __attribute__((noinline))
 #endif
 
+// data prefetch hint, a no-op when not supported
+#if defined(__GNUC__) || defined(__clang__)
+#    define ANKERL_UNORDERED_DENSE_PREFETCH(addr) __builtin_prefetch(addr) // NOLINT(cppcoreguidelines-macro-usage)
+#else
+#    define ANKERL_UNORDERED_DENSE_PREFETCH(addr) static_cast<void>(addr) // NOLINT(cppcoreguidelines-macro-usage)
+#endif
+
 #if defined(__clang__) && defined(__has_attribute)
 #    if __has_attribute(__no_sanitize__)
 #        define ANKERL_UNORDERED_DENSE_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK \
@@ -212,28 +219,35 @@ inline void mum(std::uint64_t* a, std::uint64_t* b) {
     static constexpr auto secret = std::array{UINT64_C(0xa0761d6478bd642f),
                                               UINT64_C(0xe7037ed1a0b428db),
                                               UINT64_C(0x8ebc6af09c88c6e3),
-                                              UINT64_C(0x589965cc75374cc3)};
+                                              UINT64_C(0x589965cc75374cc3),
+                                              UINT64_C(0x2d358dccaa6c78a5),
+                                              UINT64_C(0x8bb84b93962eacc9),
+                                              UINT64_C(0x4b33a62ed433d4a3)};
 
-    auto const* p = static_cast<uint8_t const*>(key);
+    auto const* p = static_cast<std::uint8_t const*>(key);
     std::uint64_t seed = secret[0];
     std::uint64_t a{};
     std::uint64_t b{};
     if (ANKERL_UNORDERED_DENSE_LIKELY(len <= 16))
         ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
-            if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 4))
+            if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 8))
                 ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
-                    a = (r4(p) << 32U) | r4(p + ((len >> 3U) << 2U));
-                    b = (r4(p + len - 4) << 32U) | r4(p + len - 4 - ((len >> 3U) << 2U));
+                    // two (potentially overlapping) 8 byte reads cover the whole input
+                    a = r8(p);
+                    b = r8(p + len - 8);
                 }
-            else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0))
+            else if (len >= 4) {
+                a = r4(p);
+                b = r4(p + len - 4);
+            } else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0))
                 ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
+                    // b stays zero: r3 packs all len bytes it is given into a, and there are at
+                    // most three of them.
                     a = r3(p, len);
-                    b = 0;
                 }
-            else {
-                a = 0;
-                b = 0;
-            }
+            // ... and an empty input needs no branch of its own: it hashes whatever a and b were
+            // declared with, which is the zero it has to be. Assigning it again here is what a
+            // deletion sweep of this file kept pointing at.
         }
     else {
         std::size_t i = len;
@@ -241,14 +255,41 @@ inline void mum(std::uint64_t* a, std::uint64_t* b) {
             ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
                 std::uint64_t see1 = seed;
                 std::uint64_t see2 = seed;
-                do {
+                if (i > 96) {
+                    // 6 independent lanes: twice the instruction level parallelism of the 48 byte loop below
+                    std::uint64_t see3 = seed;
+                    std::uint64_t see4 = seed;
+                    std::uint64_t see5 = seed;
+                    do {
+                        seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
+                        see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);
+                        see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);
+                        see3 = mix(r8(p + 48) ^ secret[4], r8(p + 56) ^ see3);
+                        see4 = mix(r8(p + 64) ^ secret[5], r8(p + 72) ^ see4);
+                        see5 = mix(r8(p + 80) ^ secret[6], r8(p + 88) ^ see5);
+                        p += 96;
+                        i -= 96;
+                    } while (ANKERL_UNORDERED_DENSE_LIKELY(i > 96));
+                    seed ^= see3 ^ see4 ^ see5;
+                }
+                while (i > 48) {
                     seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
                     see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);
                     see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);
                     p += 48;
                     i -= 48;
-                } while (ANKERL_UNORDERED_DENSE_LIKELY(i > 48));
+                }
                 seed ^= see1 ^ see2;
+                while (i > 16) {
+                    seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
+                    i -= 16;
+                    p += 16;
+                }
+
+                // the tail lane only depends on the input, not on seed, so it can execute in parallel
+                // with the lane loops above, and a single dependent mix finishes the hash
+                auto tail = mix(r8(p + i - 16) ^ secret[2], r8(p + i - 8) ^ secret[3]);
+                return mix(secret[1] ^ len, seed ^ tail);
             }
         while (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 16))
             ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
@@ -269,6 +310,85 @@ inline void mum(std::uint64_t* a, std::uint64_t* b) {
 
 } // namespace detail::wyhash
 
+namespace detail {
+
+struct nonesuch {};
+
+template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
+struct detector {
+    using value_t = std::false_type;
+    using type = Default;
+};
+
+template <class Default, template <class...> class Op, class... Args>
+struct detector<Default, std::void_t<Op<Args...>>, Op, Args...> {
+    using value_t = std::true_type;
+    using type = Op<Args...>;
+};
+
+template <template <class...> class Op, class... Args>
+using is_detected = typename detail::detector<detail::nonesuch, void, Op, Args...>::value_t;
+
+template <template <class...> class Op, class... Args>
+constexpr bool is_detected_v = is_detected<Op, Args...>::value;
+
+template <typename>
+constexpr bool dependent_false = false;
+
+template <typename T>
+using detect_avalanching = typename T::is_avalanching;
+
+// The member written as a value instead of a type, which is the near miss that would otherwise
+// answer "not avalanching" and say nothing about why.
+template <typename T>
+using detect_avalanching_as_value = decltype((void)T::is_avalanching);
+
+template <typename T>
+using detect_bool_value = std::enable_if_t<std::is_convertible_v<decltype(T::value), bool>>;
+
+// What a hash's is_avalanching member means. void is this library's spelling, and Boost's original
+// one; a type carrying a compile time bool is what Boost's documentation asks for now. Saying
+// std::false_type there has to mean no rather than yes -- reading the member as a bare "it is
+// there" would take a hash that declares itself ordinary and use it unmixed, which is the one
+// answer that costs the table its distribution.
+//
+// Anything else is a mistake, and is said to be one rather than guessed at.
+template <typename Hash>
+[[nodiscard]] constexpr auto is_avalanching_member() -> bool {
+    if constexpr (!is_detected_v<detect_avalanching, Hash>) {
+        static_assert(!is_detected_v<detect_avalanching_as_value, Hash>,
+                      "is_avalanching must be a type: write 'using is_avalanching = std::true_type;' "
+                      "rather than 'static constexpr bool is_avalanching = true;'");
+        return false;
+    } else if constexpr (std::is_void_v<detect_avalanching<Hash>>) {
+        return true;
+    } else if constexpr (is_detected_v<detect_bool_value, detect_avalanching<Hash>>) {
+        return static_cast<bool>(detect_avalanching<Hash>::value);
+    } else {
+        static_assert(dependent_false<Hash>,
+                      "is_avalanching must be void, or a type with a compile time bool value such "
+                      "as std::true_type or std::false_type");
+        return false;
+    }
+}
+
+} // namespace detail
+
+// Whether a hash is high quality -- every bit of its result independently well distributed -- so
+// that a table can index with those bits as they come instead of mixing them first. The default
+// answer is the member typedef a hash can carry, `using is_avalanching = void;` or the equivalent
+// `= std::true_type`. For a hash you cannot edit, specialize this instead; `std::false_type` is
+// allowed too, and forces the mixing back on for a hash that promises more than it delivers.
+//
+// Deliberately the same name, the same two ways of answering and the same meaning as Boost's
+// boost::hash_is_avalanching, so that a hash annotated for either library is read correctly by the
+// other. See README 3.2.7.
+template <typename Hash>
+struct hash_is_avalanching : std::bool_constant<detail::is_avalanching_member<Hash>()> {};
+
+template <typename Hash>
+constexpr bool hash_is_avalanching_v = hash_is_avalanching<Hash>::value;
+
 template <typename T, typename Enable = void>
 struct hash {
     auto operator()(T const& obj) const noexcept(noexcept(std::declval<std::hash<T>>().operator()(std::declval<T const&>())))
@@ -277,8 +397,12 @@ struct hash {
     }
 };
 
+// Asked of hash_is_avalanching rather than of std::hash<T>::is_avalanching directly, so that there
+// is one reader of the marker and not two: a std::hash spelling its marker the way Boost asks, or
+// named avalanching by a specialization because it cannot be edited, reaches the table through here
+// as well.
 template <typename T>
-struct hash<T, typename std::hash<T>::is_avalanching> {
+struct hash<T, std::enable_if_t<hash_is_avalanching_v<std::hash<T>>>> {
     using is_avalanching = void;
     auto operator()(T const& obj) const noexcept(noexcept(std::declval<std::hash<T>>().operator()(std::declval<T const&>())))
         -> std::uint64_t {
@@ -334,7 +458,7 @@ struct hash<Enum, typename std::enable_if_t<std::is_enum_v<Enum>>> {
     using is_avalanching = void;
     auto operator()(Enum e) const noexcept -> std::uint64_t {
         using underlying = std::underlying_type_t<Enum>;
-        return detail::wyhash::hash(static_cast<underlying>(e));
+        return detail::wyhash::hash(static_cast<std::uint64_t>(static_cast<underlying>(e)));
     }
 };
 
@@ -446,30 +570,8 @@ ANKERL_UNORDERED_DENSE_PACK(struct big {
 
 namespace detail {
 
-struct nonesuch {};
 struct default_container_t {};
 
-template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
-struct detector {
-    using value_t = std::false_type;
-    using type = Default;
-};
-
-template <class Default, template <class...> class Op, class... Args>
-struct detector<Default, std::void_t<Op<Args...>>, Op, Args...> {
-    using value_t = std::true_type;
-    using type = Op<Args...>;
-};
-
-template <template <class...> class Op, class... Args>
-using is_detected = typename detail::detector<detail::nonesuch, void, Op, Args...>::value_t;
-
-template <template <class...> class Op, class... Args>
-constexpr bool is_detected_v = is_detected<Op, Args...>::value;
-
-template <typename T>
-using detect_avalanching = typename T::is_avalanching;
-
 template <typename T>
 using detect_is_transparent = typename T::is_transparent;
 
@@ -504,8 +606,52 @@ struct base_table_type_map {
 // base type for set doesn't have mapped_type
 struct base_table_type_set {};
 
+// A key's hash, finalized and ready for a table to index with, as produced by hash_for(). See the
+// lookup section of table for what it is for; this is spelled table::precomputed_hash.
+//
+// Templated on the hasher and nothing else, because the hasher is all a hash depends on: a map, a
+// set and a segmented_map that hash the key the same way can pass one around between them. It is a
+// type of its own rather than a plain integer so that an integer does not convert to it by
+// accident -- in particular what hash_function() returns, which is not this number.
+template <typename Hash>
+struct precomputed_hash {
+    std::uint64_t m_mixed_hash;
+};
+
 } // namespace detail
 
+// A hash that has to be a high quality one, for a codebase where they all are meant to be and
+// forgetting to say so is the easy mistake:
+//
+//     template <class Key, class T>
+//     using my_map = ankerl::unordered_dense::map<Key, T, require_avalanching<my_hash<Key>>>;
+//
+// Written into the alias rather than next to the hash so that the check is part of what the map
+// is, and survives my_hash being reimplemented without its marker.
+//
+// It inherits, which is what keeps the hash's own operator() overloads and its is_transparent, and
+// costs nothing: the wrapper is the same size as the hash and compiles to the same code.
+template <typename Hash>
+struct require_avalanching : Hash {
+    static_assert(hash_is_avalanching_v<Hash>,
+                  "hash is not avalanching: give it 'using is_avalanching = void;', or specialize "
+                  "ankerl::unordered_dense::hash_is_avalanching for it, or stop requiring it here");
+    static_assert(!std::is_final_v<Hash>,
+                  "hash is final, so it cannot be wrapped: specialize "
+                  "ankerl::unordered_dense::hash_is_avalanching for it instead");
+
+    require_avalanching() = default;
+
+    // So that a stateful hash can be handed over by value as well as braced into place -- an
+    // aggregate would take require_avalanching<H>{h} but not require_avalanching<H>(h).
+    explicit require_avalanching(Hash const& hash)
+        : Hash(hash) {}
+
+    // Restated rather than inherited, because a hash named avalanching by a specialization of
+    // hash_is_avalanching has no member typedef to inherit.
+    using is_avalanching = void;
+};
+
 // Very much like std::deque, but faster for indexing (in most cases). As of now this doesn't implement the full std::vector
 // API, but merely what's necessary to work as an underlying container for ankerl::unordered_dense::{map, set}.
 // It allocates blocks of equal size and puts them into the m_blocks vector. That means it can grow simply by adding a new
@@ -530,6 +676,16 @@ class segmented_vector {
 
 private:
     using vec_alloc = typename std::allocator_traits<Allocator>::template rebind_alloc<pointer>;
+    using vec_alloc_traits = std::allocator_traits<vec_alloc>;
+
+    // The allocator lives in m_blocks, so these are what the assignment operators below act on --
+    // and what their noexcept specifications are written over, so that the condition and the
+    // promise cannot drift apart.
+    static constexpr bool propagates_on_copy_assign = vec_alloc_traits::propagate_on_container_copy_assignment::value;
+    static constexpr bool propagates_on_move_assign = vec_alloc_traits::propagate_on_container_move_assignment::value;
+    static constexpr bool allocators_always_equal = vec_alloc_traits::is_always_equal::value;
+    static constexpr bool propagates_on_swap = vec_alloc_traits::propagate_on_container_swap::value;
+
     std::vector<pointer, vec_alloc> m_blocks{};
     std::size_t m_size{};
 
@@ -564,7 +720,11 @@ class segmented_vector {
         using value_type = segmented_vector::value_type;
         using reference = std::conditional_t<IsConst, value_type const&, value_type&>;
         using pointer = std::conditional_t<IsConst, segmented_vector::const_pointer, segmented_vector::pointer>;
-        using iterator_category = std::forward_iterator_tag;
+        // Everything a random access iterator needs is right here -- the position is an index, so jumping and
+        // subtracting are single operations. Saying "forward" instead meant std::distance walked the whole container
+        // one element at a time to compute what operator-() answers directly, and every algorithm that requires
+        // random access, std::sort over values() among them, was ill-formed over an iterator that can do the job.
+        using iterator_category = std::random_access_iterator_tag;
 
         iter_t() noexcept = default;
 
@@ -611,17 +771,25 @@ class segmented_vector {
             return {m_data, static_cast<std::size_t>(static_cast<difference_type>(m_idx) + diff)};
         }
 
+        // n + it, which a random access iterator has to support just as it + n does
+        [[nodiscard]] friend constexpr auto operator+(difference_type diff, iter_t const& it) noexcept -> iter_t {
+            return it + diff;
+        }
+
+        // The cast is the one operator+() already does. Nothing instantiated these two before, because no algorithm
+        // could reach them through a forward iterator, so the implicit signed-to-unsigned conversion sat here
+        // unnoticed until clang's -Wsign-conversion saw std::sort use it.
         constexpr auto operator+=(difference_type diff) noexcept -> iter_t& {
-            m_idx += diff;
+            m_idx = static_cast<std::size_t>(static_cast<difference_type>(m_idx) + diff);
             return *this;
         }
 
         [[nodiscard]] constexpr auto operator-(difference_type diff) const noexcept -> iter_t {
-            return {m_data, static_cast<size_t>(static_cast<difference_type>(m_idx) - diff)};
+            return {m_data, static_cast<std::size_t>(static_cast<difference_type>(m_idx) - diff)};
         }
 
         constexpr auto operator-=(difference_type diff) noexcept -> iter_t& {
-            m_idx -= diff;
+            m_idx = static_cast<std::size_t>(static_cast<difference_type>(m_idx) - diff);
             return *this;
         }
 
@@ -634,6 +802,10 @@ class segmented_vector {
             return m_data[m_idx >> num_bits][m_idx & mask];
         }
 
+        [[nodiscard]] constexpr auto operator[](difference_type diff) const noexcept -> reference {
+            return *(*this + diff);
+        }
+
         constexpr auto operator->() const noexcept -> pointer {
             return &m_data[m_idx >> num_bits][m_idx & mask];
         }
@@ -672,6 +844,16 @@ class segmented_vector {
     // slow path: need to allocate a new segment every once in a while
     void increase_capacity() {
         auto ba = Allocator(m_blocks.get_allocator());
+
+        // Room for the pointer first. push_back is the other thing here that can throw -- it
+        // reallocates -- and it used to do so with the block already allocated and owned by
+        // nobody, which leaked it. Reserving first means the only allocation still outstanding
+        // when something fails is one that has not happened yet, and the push_back below cannot
+        // fail because the capacity is already there. Grow geometrically to avoid reallocation
+        // on every new segment.
+        if (m_blocks.size() == m_blocks.capacity()) {
+            m_blocks.reserve((std::max)(std::size_t{1}, m_blocks.capacity() * 2));
+        }
         pointer block = std::allocator_traits<Allocator>::allocate(ba, num_elements_in_block);
         m_blocks.push_back(block);
     }
@@ -703,9 +885,9 @@ class segmented_vector {
         return (capacity + num_elements_in_block - 1U) / num_elements_in_block;
     }
 
-    void resize_shrink(size_t new_size) {
+    void resize_shrink(std::size_t new_size) {
         if constexpr (!std::is_trivially_destructible_v<T>) {
-            for (size_t ix = new_size; ix < m_size; ++ix) {
+            for (std::size_t ix = new_size; ix < m_size; ++ix) {
                 operator[](ix).~T();
             }
         }
@@ -719,9 +901,19 @@ class segmented_vector {
     segmented_vector(Allocator alloc)
         : m_blocks(vec_alloc(alloc)) {}
 
-    segmented_vector(segmented_vector&& other, Allocator alloc)
-        : segmented_vector(alloc) {
-        *this = std::move(other);
+    // Uses alloc, unconditionally -- that is the whole point of an extended move constructor. It
+    // used to delegate to move assignment, which cannot express it: assignment has to consult
+    // propagate_on_container_move_assignment, so with a propagating allocator it adopted other's
+    // and the allocator the caller named was quietly dropped.
+    segmented_vector(segmented_vector&& other, Allocator alloc) noexcept(allocators_always_equal)
+        : m_blocks(vec_alloc(alloc)) {
+        if (allocators_always_equal || alloc == other.get_allocator()) {
+            // Nothing to move element by element, the blocks just change hands.
+            m_blocks = std::move(other.m_blocks);
+            m_size = std::exchange(other.m_size, {});
+        } else {
+            append_everything_from(std::move(other));
+        }
     }
 
     segmented_vector(segmented_vector const& other, Allocator alloc)
@@ -732,7 +924,8 @@ class segmented_vector {
     segmented_vector(segmented_vector&& other) noexcept
         : segmented_vector(std::move(other), other.get_allocator()) {}
 
-    segmented_vector(segmented_vector const& other) {
+    segmented_vector(segmented_vector const& other)
+        : m_blocks(vec_alloc_traits::select_on_container_copy_construction(other.m_blocks.get_allocator())) {
         append_everything_from(other);
     }
 
@@ -741,19 +934,42 @@ class segmented_vector {
             return *this;
         }
         clear();
+        if constexpr (propagates_on_copy_assign) {
+            if (m_blocks.get_allocator() != other.m_blocks.get_allocator()) {
+                // Everything still held has to go back through the old allocator before the new
+                // one is adopted. Copy assignment and not move: which of the two propagates is
+                // the inner vector's own pocca/pocma, and only pocca is known true here, so
+                // assigning a temporary would consult pocma and silently keep the old allocator.
+                dealloc();
+                auto const empty_with_other_allocator = std::vector<pointer, vec_alloc>(other.m_blocks.get_allocator());
+                m_blocks = empty_with_other_allocator;
+            }
+        }
         append_everything_from(other);
         return *this;
     }
 
-    auto operator=(segmented_vector&& other) noexcept -> segmented_vector& {
+    // Not unconditionally noexcept. When the allocator neither propagates nor compares equal --
+    // std::pmr::polymorphic_allocator, for one -- the elements are moved one at a time into memory
+    // this container allocates, so running out of it here has to be allowed to throw rather than
+    // terminate. std::vector spells the condition the same way.
+    auto operator=(segmented_vector&& other) noexcept(propagates_on_move_assign || allocators_always_equal)
+        -> segmented_vector& {
+        if (this == &other) {
+            return *this;
+        }
         clear();
-        dealloc();
-        if (other.get_allocator() == get_allocator()) {
+        // Either the allocator comes along with the blocks or it is already the same one, and
+        // either way the blocks can be taken over; std::vector's own move assignment does the
+        // propagating in the first case.
+        if (propagates_on_move_assign || m_blocks.get_allocator() == other.m_blocks.get_allocator()) {
+            dealloc();
             m_blocks = std::move(other.m_blocks);
             m_size = std::exchange(other.m_size, {});
         } else {
-            // make sure to construct with other's allocator!
-            m_blocks = std::vector<pointer, vec_alloc>(vec_alloc(other.get_allocator()));
+            // Keeps its own allocator, because nothing said to take other's -- so the blocks it
+            // already holds came from that same allocator and are reused rather than handed back
+            // and immediately asked for again.
             append_everything_from(std::move(other));
         }
         return *this;
@@ -824,25 +1040,25 @@ class segmented_vector {
         }
     }
 
-    void resize(size_t const count) {
+    void resize(std::size_t const count) {
         if (count < m_size) {
             resize_shrink(count);
         } else if (count > m_size) {
-            size_t const new_elems = count - m_size;
+            std::size_t const new_elems = count - m_size;
             reserve(count);
-            for (size_t ix = 0; ix < new_elems; ++ix) {
+            for (std::size_t ix = 0; ix < new_elems; ++ix) {
                 emplace_back();
             }
         }
     }
 
-    void resize(size_t const count, value_type const& value) {
+    void resize(std::size_t const count, value_type const& value) {
         if (count < m_size) {
             resize_shrink(count);
         } else if (count > m_size) {
-            size_t const new_elems = count - m_size;
+            std::size_t const new_elems = count - m_size;
             reserve(count);
-            for (size_t ix = 0; ix < new_elems; ++ix) {
+            for (std::size_t ix = 0; ix < new_elems; ++ix) {
                 emplace_back(value);
             }
         }
@@ -852,6 +1068,22 @@ class segmented_vector {
         return allocator_type{m_blocks.get_allocator()};
     }
 
+    // Exchanging two pointers and a size, and the inner vector's own swap exchanges the allocators
+    // exactly when propagate_on_container_swap says to -- so this answers the allocator question
+    // the way std::vector does, and a map gets the same answer whichever container backs it.
+    // Without a member swap, std::swap fell back to a move construction and two move assignments:
+    // O(n) for an operation that needs none, able to throw from inside a noexcept swap, and a
+    // different answer from the flat container for the same map.
+    void swap(segmented_vector& other) noexcept(propagates_on_swap || allocators_always_equal) {
+        using std::swap;
+        swap(m_blocks, other.m_blocks);
+        swap(m_size, other.m_size);
+    }
+
+    friend void swap(segmented_vector& a, segmented_vector& b) noexcept(noexcept(a.swap(b))) {
+        a.swap(b);
+    }
+
     template <class... Args>
     auto emplace_back(Args&&... args) -> reference {
         if (m_size == capacity()) {
@@ -917,6 +1149,15 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     static constexpr std::uint8_t initial_shifts = 64 - 2; // 2^(64-m_shift) number of buckets
     static constexpr float default_max_load_factor = 0.8F;
 
+    // Named, and covering both containers, so that the promise and the recovery that exists for
+    // when the promise cannot be made are spelled the same way and cannot drift apart -- the same
+    // reason segmented_vector names its propagation traits. Covering only m_values would be wrong
+    // twice over: it would leave m_buckets free to throw out of a noexcept function, and it would
+    // compile a rethrow into one, which gcc rejects outright.
+    static constexpr bool move_assign_is_nothrow =
+        std::is_nothrow_move_assignable_v<value_container_type> && std::is_nothrow_move_assignable_v<bucket_container_type> &&
+        std::is_nothrow_move_assignable_v<Hash> && std::is_nothrow_move_assignable_v<KeyEqual>;
+
 public:
     using key_type = Key;
     using value_type = typename value_container_type::value_type;
@@ -933,6 +1174,11 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     using iterator = std::conditional_t<is_map_v<T>, typename value_container_type::iterator, const_iterator>;
     using bucket_type = Bucket;
 
+    // What hash_for() returns; see the lookup section below. Shared by every table with this
+    // hasher, whatever else it is made of, because that is exactly the set of tables the hash is
+    // good for.
+    using precomputed_hash = detail::precomputed_hash<Hash>;
+
 private:
     using value_idx_type = decltype(Bucket::m_value_idx);
     using dist_and_fingerprint_type = decltype(Bucket::m_dist_and_fingerprint);
@@ -940,21 +1186,33 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     static_assert(std::is_trivially_destructible_v<Bucket>, "assert there's no need to call destructor / std::destroy");
     static_assert(std::is_trivially_copyable_v<Bucket>, "assert we can just memset / memcpy");
 
+    // m_dist_and_fingerprint packs two fields into one integer, and these are what keeps them from
+    // reaching into each other. A bucket type is something a user can supply, so this is checked
+    // here rather than assumed.
+    //
+    // The fingerprint has to stay strictly below dist_inc. A mask that overlaps it lets hash bits
+    // add to the distance a bucket claims, which silently reorders the robin hood sequence that
+    // every probe depends on -- and a mask that reaches the bit above turns a fresh bucket into one
+    // that reads as further from home than it is. Fewer fingerprint bits than dist_inc allows is
+    // merely a weaker fingerprint, so the bound is one-sided.
+    static_assert(Bucket::fingerprint_mask < Bucket::dist_inc,
+                  "the fingerprint must fit strictly below dist_inc, or it changes the distance");
+    // And dist_inc has to be a single bit, because the distance is incremented by adding it: two
+    // bits set would carry into the fingerprint on the very first step away from home.
+    static_assert(0 != Bucket::dist_inc && 0 == (Bucket::dist_inc & (Bucket::dist_inc - 1)),
+                  "dist_inc must be a power of two, so that adding it only touches the distance");
+
     value_container_type m_values{}; // Contains all the key-value pairs in one densely stored container. No holes.
     bucket_container_type m_buckets{};
     std::size_t m_max_bucket_capacity = 0;
+    value_idx_type m_bucket_mask = 0; // bucket_count() - 1; works because bucket_count() is always a power of two
     float m_max_load_factor = default_max_load_factor;
     Hash m_hash{};
     KeyEqual m_equal{};
     std::uint8_t m_shifts = initial_shifts;
 
     [[nodiscard]] auto next(value_idx_type bucket_idx) const -> value_idx_type {
-        if (ANKERL_UNORDERED_DENSE_UNLIKELY(bucket_idx + 1U == bucket_count()))
-            ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
-                return 0;
-            }
-
-        return static_cast<value_idx_type>(bucket_idx + 1U);
+        return static_cast<value_idx_type>((bucket_idx + 1U) & m_bucket_mask);
     }
 
     // Helper to access bucket through pointer types
@@ -978,7 +1236,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     // The goal of mixed_hash is to always produce a high quality 64bit hash.
     template <typename K>
     [[nodiscard]] constexpr auto mixed_hash(K const& key) const -> std::uint64_t {
-        if constexpr (is_detected_v<detect_avalanching, Hash>) {
+        if constexpr (hash_is_avalanching_v<Hash>) {
             // we know that the hash is good because is_avalanching.
             if constexpr (sizeof(decltype(m_hash(key))) < sizeof(std::uint64_t)) {
                 // 32bit hash and is_avalanching => multiply with a constant to avalanche bits upwards
@@ -1023,21 +1281,26 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     }
 
     void place_and_shift_up(Bucket bucket, value_idx_type place) {
+        // cache mask in a local so the bucket stores can't alias it
+        auto const mask = m_bucket_mask;
         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 = static_cast<value_idx_type>((place + 1U) & mask);
         }
         at(m_buckets, place) = bucket;
     }
 
     void erase_and_shift_down(value_idx_type bucket_idx) {
+        // cache mask in a local so the bucket stores can't alias it
+        auto const mask = m_bucket_mask;
+
         // shift down until either empty or an element with correct spot is found
-        auto next_bucket_idx = next(bucket_idx);
+        auto next_bucket_idx = static_cast<value_idx_type>((bucket_idx + 1U) & mask);
         while (at(m_buckets, next_bucket_idx).m_dist_and_fingerprint >= Bucket::dist_inc * 2) {
             auto& next_bucket = at(m_buckets, next_bucket_idx);
             at(m_buckets, bucket_idx) = {dist_dec(next_bucket.m_dist_and_fingerprint), next_bucket.m_value_idx};
-            bucket_idx = std::exchange(next_bucket_idx, next(next_bucket_idx));
+            bucket_idx = std::exchange(next_bucket_idx, static_cast<value_idx_type>((next_bucket_idx + 1U) & mask));
         }
         at(m_buckets, bucket_idx) = {};
     }
@@ -1048,7 +1311,16 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
 
     [[nodiscard]] constexpr auto calc_shifts_for_size(std::size_t s) const -> std::uint8_t {
         auto shifts = initial_shifts;
-        while (shifts > 0 && static_cast<std::size_t>(static_cast<float>(calc_num_buckets(shifts)) * max_load_factor()) < s) {
+        // Stopping once the array is as large as it may get is what keeps this from running off the
+        // end. calc_num_buckets() saturates at max_bucket_count(), so past that point the capacity
+        // being compared stops growing while the loop keeps decrementing -- and for any size above
+        // max_bucket_count() * max_load_factor() it used to walk all the way to zero. A shift of
+        // zero then asks calc_num_buckets() for `1 << 64`, which is undefined and in practice one:
+        // a table sized for billions of elements would come back with a single bucket and a mask of
+        // zero, and the next probe reads past the end of it. Reachable from rehash(), which does not
+        // allocate the values and so has nothing to fail first.
+        while (shifts > 0 && calc_num_buckets(shifts) < max_bucket_count() &&
+               static_cast<std::size_t>(static_cast<float>(calc_num_buckets(shifts)) * max_load_factor()) < s) {
             --shifts;
         }
         return shifts;
@@ -1058,22 +1330,113 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     void copy_buckets(table const& other) {
         // assumes m_values has already the correct data copied over.
         if (empty()) {
-            // when empty, at least allocate an initial buckets and clear them.
-            allocate_buckets_from_shift();
-            clear_buckets();
+            // Nothing to index, so stay in the state a default constructed table is in and let the
+            // first insert allocate. Copying an empty table therefore allocates nothing either.
+            m_shifts = initial_shifts;
         } else {
-            m_shifts = other.m_shifts;
-            allocate_buckets_from_shift();
             if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
+                allocate_buckets_from_shift(other.m_shifts);
                 for (auto i = 0UL; i < bucket_count(); ++i) {
                     at(m_buckets, i) = at(other.m_buckets, i);
                 }
             } else {
-                std::memcpy(m_buckets.data(), other.m_buckets.data(), sizeof(Bucket) * bucket_count());
+                // One pass, not two. This used to grow the array with resize(), which value
+                // initialises every bucket it adds, and then memcpy over all of it -- so every byte
+                // of the bucket array was written twice, and for a large map the wasted half is a
+                // memset of megabytes. assign() copies straight into the new storage.
+                //
+                // assign() and not m_buckets = other.m_buckets, which would consult pocca: the
+                // allocator question is answered by the caller, and this is also reached from the
+                // move assignment's differing-allocator branch, where adopting other's would be
+                // exactly wrong.
+                m_buckets.assign(other.m_buckets.begin(), other.m_buckets.end());
+                m_shifts = other.m_shifts;
+                describe_buckets(m_buckets.size());
             }
         }
     }
 
+    // The part of copy assignment that can throw, kept separate so the operator can put the table
+    // back together if it does.
+    void copy_everything_from(table const& other) {
+        // The assignment below takes other's allocator (pocca), and the buckets have to follow it,
+        // or the container's two halves end up on different allocators and get_allocator() -- which
+        // reports m_values' -- stops describing the bucket array, which the "same allocator" check
+        // in the move assignment relies on it doing.
+        //
+        // Done before the copy rather than after: it is the same allocator either way, both
+        // containers are empty here so it cannot throw, and doing it first means a copy that fails
+        // part way through cannot leave the two halves disagreeing. Copy assignment and not move:
+        // move would consult pocma, a different question, and not the one answered true here.
+        if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value) {
+            // Rebound explicitly: m_values' allocator and m_buckets' are different types, and
+            // comparing them directly is ambiguous rather than merely unusual.
+            auto const wanted = typename bucket_container_type::allocator_type(other.m_values.get_allocator());
+            if (m_buckets.get_allocator() != wanted) {
+                auto const empty_with_other_allocator = bucket_container_type(wanted);
+                m_buckets = empty_with_other_allocator;
+            }
+        }
+
+        m_values = other.m_values;
+        m_max_load_factor = other.m_max_load_factor;
+        m_hash = other.m_hash;
+        m_equal = other.m_equal;
+        copy_buckets(other); // sets m_shifts on both of its branches
+    }
+
+    // The half of move assignment that can throw, so the caller can put the table back together if
+    // it does. Its twin for copies is above.
+    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved) -- moved from member by member
+    void move_everything_from(table&& other) {
+        m_values = std::move(other.m_values);
+        other.m_values.clear();
+
+        // we can only reuse m_buckets when both maps have the same allocator!
+        if (get_allocator() == other.get_allocator()) {
+            m_buckets = std::move(other.m_buckets);
+            other.m_buckets.clear();
+            m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0);
+            m_bucket_mask = std::exchange(other.m_bucket_mask, 0);
+            m_shifts = std::exchange(other.m_shifts, initial_shifts);
+            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, {});
+            // The exchanges above leave "other" exactly as a default constructed table looks, so it
+            // is already usable and does not need buckets handed back to it. It used to get a
+            // freshly allocated set here, which is an allocation -- and a way to throw -- inside an
+            // operation that is otherwise noexcept and needs neither.
+        } else {
+            // set max_load_factor *before* copying the other's buckets, so we have the same behavior
+            m_max_load_factor = other.m_max_load_factor;
+
+            // copy_buckets sets m_buckets, m_num_buckets, m_max_bucket_capacity, m_shifts
+            copy_buckets(other);
+            // clear's the other's buckets so other is now already usable.
+            other.clear_buckets();
+            m_hash = other.m_hash;
+            m_equal = other.m_equal;
+        }
+        // map "other" is now already usable, it's empty.
+    }
+
+    // Back to what a default constructed table holds. An assignment gives the buckets back before
+    // it knows whether it can build new ones, and in between the table holds values it has no way
+    // to find -- size() elements and no bucket array at all, which no operation is prepared for. If
+    // an exception leaves that window this is where it lands: assignment owes the basic guarantee,
+    // which means valid and not merely non-leaking, and with no buckets the only valid state is
+    // empty. Every step is noexcept, so the recovery cannot fail on its way out.
+    // Deliberately not deallocate_buckets(), which is otherwise the same three stores: that one
+    // also calls shrink_to_fit(), which is allowed to allocate and is not noexcept, and this runs
+    // while an exception is already in flight.
+    void reset_to_empty() noexcept {
+        m_values.clear();
+        m_buckets.clear();
+        m_max_bucket_capacity = 0;
+        m_bucket_mask = 0;
+        m_shifts = initial_shifts;
+    }
+
     /**
      * True when no element can be added any more without increasing the size
      */
@@ -1085,20 +1448,57 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         m_buckets.clear();
         m_buckets.shrink_to_fit();
         m_max_bucket_capacity = 0;
+        m_bucket_mask = 0;
     }
 
-    void allocate_buckets_from_shift() {
-        auto num_buckets = calc_num_buckets(m_shifts);
+    // Takes the shift rather than reading m_shifts, so that nothing describing the bucket array is
+    // written until an array of that size exists. Callers used to assign m_shifts and then
+    // allocate, which left a gap for a failed allocation to stop in.
+    void allocate_buckets_from_shift(std::uint8_t shifts) {
+        auto num_buckets = calc_num_buckets(shifts);
         if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
-            if constexpr (has_reserve<bucket_container_type>) {
-                m_buckets.reserve(num_buckets);
-            }
-            for (std::size_t i = m_buckets.size(); i < num_buckets; ++i) {
-                m_buckets.emplace_back();
+            if (num_buckets < m_buckets.size()) {
+                // Shrinking, which rehash does. This used to work because the caller emptied the
+                // array first and the loop below then grew it from nothing; without that it would
+                // keep the larger size. Shrinking rather than emptying is what keeps the array and
+                // the mask agreeing at every point: it hands memory back instead of asking for it,
+                // so unlike a clear-then-regrow it has no failure to stop in.
+                m_buckets.resize(num_buckets);
+            } else {
+                if constexpr (has_reserve<bucket_container_type>) {
+                    m_buckets.reserve(num_buckets);
+                }
+                // Growing in place leaves the old buckets where they are, so a failure part way
+                // through leaves an array that is merely larger than the mask below describes,
+                // which nothing reads.
+                for (std::size_t i = m_buckets.size(); i < num_buckets; ++i) {
+                    m_buckets.emplace_back();
+                }
             }
         } else {
-            m_buckets.resize(num_buckets);
+            // Built beside the old array rather than over it, so that a failure here leaves the
+            // table exactly as it was. Callers used to give the old array back first, which made
+            // this the only allocation alive -- and made a failure leave them holding values with
+            // no buckets to find them by, which is not a state anything can recover from without
+            // allocating again.
+            auto fresh = bucket_container_type(m_buckets.get_allocator());
+            fresh.resize(num_buckets);
+            m_buckets = std::move(fresh);
         }
+        // All three commit here, together, and only once the array they describe exists. They have
+        // to move as one: do_find indexes its first probe with hash >> m_shifts and does not mask,
+        // so a shift that has run ahead of the array reads past the end of it, and a mask published
+        // ahead of an allocation that then failed does the same. This is the one function every
+        // bucket-allocating path goes through, which is what makes a failed growth leave the old
+        // buckets intact and consistent rather than unusable.
+        m_shifts = shifts;
+        describe_buckets(num_buckets);
+    }
+
+    // The two values derived from the bucket array's size. Only ever called once the array of that
+    // size exists; see the note above.
+    void describe_buckets(std::size_t num_buckets) {
+        m_bucket_mask = static_cast<value_idx_type>(num_buckets - 1);
         if (num_buckets == max_bucket_count()) {
             // reached the maximum, make sure we can use each bucket
             m_max_bucket_capacity = max_bucket_count();
@@ -1107,7 +1507,29 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         }
     }
 
+    // The bucket array is not allocated until the first element goes in, so that a default
+    // constructed table does not allocate. Every path that probes the buckets either returns early
+    // while the table is empty (do_find and do_find_hashed's callers, do_erase_key), or needs an
+    // iterator into m_values and so
+    // cannot be reached in this state (erase, extract, replace_key), or calls this first -- which
+    // is the three insert entry points, the only ones that reach the buckets without a prior
+    // emptiness check.
+    void allocate_buckets_if_none() {
+        if (ANKERL_UNORDERED_DENSE_UNLIKELY(0 == bucket_count()))
+            ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
+                allocate_buckets_from_shift(m_shifts);
+                clear_buckets();
+            }
+    }
+
     void clear_buckets() {
+        // Reachable now that a table can have no buckets at all -- extract() clears them on the way
+        // out whether or not there are any. data() is null in that state, and memset's pointer has
+        // to be valid even for a zero length. Neither sanitizer in CI objects, so this is on the
+        // language rule rather than on a diagnostic.
+        if (0 == bucket_count()) {
+            return;
+        }
         if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
             for (auto&& e : m_buckets) {
                 std::memset(&e, 0, sizeof(e));
@@ -1119,13 +1541,17 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
 
     void clear_and_fill_buckets_from_values() {
         clear_buckets();
-        for (value_idx_type value_idx = 0, end_idx = static_cast<value_idx_type>(m_values.size()); value_idx < end_idx;
-             ++value_idx) {
+        // Counted in std::size_t, for the reason spelled out in replace(): max_size() is exactly
+        // what value_idx_type can hold, so a container of precisely that many has a size that is
+        // not representable in it and the cast wraps to zero. Latent here rather than live -- a
+        // table at max_size() already has the smallest shift, so rehash() and reserve() early out
+        // before reaching this -- but the rule is the same and only one place was following it.
+        for (std::size_t value_idx = 0, end_idx = 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);
 
             // we know for certain that key has not yet been inserted, so no need to check it.
-            place_and_shift_up({dist_and_fingerprint, value_idx}, bucket);
+            place_and_shift_up({dist_and_fingerprint, static_cast<value_idx_type>(value_idx)}, bucket);
         }
     }
 
@@ -1135,28 +1561,37 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
             m_values.pop_back();
             on_error_bucket_overflow();
         }
-        --m_shifts;
-        if constexpr (!IsSegmented || std::is_same_v<BucketContainer, default_container_t>) {
-            deallocate_buckets();
+        // Both callers have already appended the new element to m_values, which is why the branch
+        // above takes it back out before reporting the overflow. A bucket array that cannot be
+        // grown is the same situation: the element is in m_values with no bucket pointing at it,
+        // and never will have one, so size() would count an element that find() cannot reach.
+        // Taking it back out is what makes a failed insert have no effect, which is what the
+        // unordered containers promise for inserting a single element.
+        if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()) {
+            try {
+                allocate_buckets_from_shift(static_cast<std::uint8_t>(m_shifts - 1));
+            } catch (...) {
+                m_values.pop_back();
+                throw;
+            }
+        } else {
+            allocate_buckets_from_shift(static_cast<std::uint8_t>(m_shifts - 1));
         }
-        allocate_buckets_from_shift();
         clear_and_fill_buckets_from_values();
     }
 
-    template <typename Op>
-    void do_erase(value_idx_type bucket_idx, Op handle_erased_value) {
-        auto const value_idx_to_remove = at(m_buckets, bucket_idx).m_value_idx;
-        erase_and_shift_down(bucket_idx);
-        handle_erased_value(std::move(m_values[value_idx_to_remove]));
-
-        // update m_values
+    // Closes the hole that the erased value left in m_values, by moving the last value into it and repointing that
+    // value's bucket. Runs after the erased value has been handed over, and has to run even when handing it over threw:
+    // by that point the bucket is already gone, so leaving the value in place would mean size() counts an element that
+    // nothing can find.
+    void finish_erase(value_idx_type value_idx_to_remove) {
         if (value_idx_to_remove != m_values.size() - 1) {
             // no luck, we'll have to replace the value with the last one and update the index accordingly
             auto& val = m_values[value_idx_to_remove];
             val = std::move(m_values.back());
 
             // update the values_idx of the moved entry. No need to play the info game, just look until we find the values_idx
-            bucket_idx = bucket_idx_from_hash(mixed_hash(get_key(val)));
+            auto bucket_idx = bucket_idx_from_hash(mixed_hash(get_key(val)));
             auto const values_idx_back = static_cast<value_idx_type>(m_values.size() - 1);
             while (values_idx_back != at(m_buckets, bucket_idx).m_value_idx) {
                 bucket_idx = next(bucket_idx);
@@ -1166,6 +1601,33 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         m_values.pop_back();
     }
 
+    template <typename Op>
+    void do_erase(value_idx_type bucket_idx, Op handle_erased_value) {
+        auto const value_idx_to_remove = at(m_buckets, bucket_idx).m_value_idx;
+
+        // both values are needed after the shift down; start fetching them now to overlap the latencies
+        ANKERL_UNORDERED_DENSE_PREFETCH(&m_values[value_idx_to_remove]);
+        ANKERL_UNORDERED_DENSE_PREFETCH(&m_values.back());
+
+        erase_and_shift_down(bucket_idx);
+        auto&& erased_value = std::move(m_values[value_idx_to_remove]);
+
+        // erase() hands the value to a callback that cannot throw, so the branch below is not even instantiated for it.
+        // extract() moves the value out into the caller's storage, and that move is the one that can throw.
+        if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() && !noexcept(handle_erased_value(std::move(erased_value)))) {
+            try {
+                handle_erased_value(std::move(erased_value));
+            } catch (...) {
+                finish_erase(value_idx_to_remove);
+                throw;
+            }
+        } else {
+            handle_erased_value(std::move(erased_value));
+        }
+
+        finish_erase(value_idx_to_remove);
+    }
+
     template <typename K, typename Op>
     auto do_erase_key(K&& key, Op handle_erased_value) -> std::size_t { // NOLINT(cppcoreguidelines-missing-std-forward)
         if (empty()) {
@@ -1218,6 +1680,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
 
     template <typename K, typename... Args>
     auto do_try_emplace(K&& key, Args&&... args) -> std::pair<iterator, bool> {
+        allocate_buckets_if_none();
         auto hash = mixed_hash(key);
         auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
         auto bucket_idx = bucket_idx_from_hash(hash);
@@ -1247,7 +1710,14 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
                 return end();
             }
 
-        auto mh = mixed_hash(key);
+        return do_find_hashed(key, mixed_hash(key));
+    }
+
+    // Same lookup with the hashing already done. Requires the bucket array to be allocated, which
+    // !empty() implies; the callers test empty() rather than this function so that a lookup in an
+    // empty table returns without hashing anything.
+    template <typename K>
+    auto do_find_hashed(K const& key, std::uint64_t mh) -> iterator {
         auto dist_and_fingerprint = dist_and_fingerprint_from_hash(mh);
         auto bucket_idx = bucket_idx_from_hash(mh);
         auto* bucket = &at(m_buckets, bucket_idx);
@@ -1286,6 +1756,21 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         return const_cast<table*>(this)->do_find(key); // NOLINT(cppcoreguidelines-pro-type-const-cast)
     }
 
+    template <typename K>
+    auto do_find(K const& key, precomputed_hash ph) -> iterator {
+        if (ANKERL_UNORDERED_DENSE_UNLIKELY(empty()))
+            ANKERL_UNORDERED_DENSE_UNLIKELY_ATTR {
+                return end();
+            }
+
+        return do_find_hashed(key, ph.m_mixed_hash);
+    }
+
+    template <typename K>
+    auto do_find(K const& key, precomputed_hash ph) const -> const_iterator {
+        return const_cast<table*>(this)->do_find(key, ph); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+    }
+
     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); ANKERL_UNORDERED_DENSE_LIKELY(end() != it))
@@ -1300,6 +1785,20 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         return const_cast<table*>(this)->at(key); // NOLINT(cppcoreguidelines-pro-type-const-cast)
     }
 
+    template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+    auto do_at(K const& key, precomputed_hash ph) -> Q& {
+        if (auto it = find(key, ph); ANKERL_UNORDERED_DENSE_LIKELY(end() != it))
+            ANKERL_UNORDERED_DENSE_LIKELY_ATTR {
+                return it->second;
+            }
+        on_error_key_not_found();
+    }
+
+    template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+    auto do_at(K const& key, precomputed_hash ph) const -> Q const& {
+        return const_cast<table*>(this)->do_at(key, ph); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+    }
+
 public:
     explicit table(std::size_t bucket_count,
                    Hash const& hash = Hash(),
@@ -1309,11 +1808,11 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         , m_buckets(alloc_or_container)
         , m_hash(hash)
         , m_equal(equal) {
+        // No bucket_count asked for means no buckets yet: the first insert allocates them. See
+        // allocate_buckets_if_none(). A default constructed table therefore costs no allocation at
+        // all, so one can sit in a scope that may never use it without paying for it.
         if (0 != bucket_count) {
             reserve(bucket_count);
-        } else {
-            allocate_buckets_from_shift();
-            clear_buckets();
         }
     }
 
@@ -1348,23 +1847,60 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     table(InputIt first, InputIt last, size_type bucket_count, Hash const& hash, allocator_type const& alloc)
         : table(first, last, bucket_count, hash, KeyEqual(), alloc) {}
 
+    // Asks the allocator whether it wants to come along, which is what allocator_traits' default
+    // does and what an allocator like std::pmr::polymorphic_allocator declines: a copy of a map
+    // living in an arena should not silently keep that arena alive and keep allocating into it.
     table(table const& other)
-        : table(other, other.m_values.get_allocator()) {}
+        : table(other,
+                std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.m_values.get_allocator())) {
+    }
 
+    // m_buckets takes the allocator too. Leaving it to its default member initialiser put the
+    // bucket array in the default resource while the values went where the caller asked, so half
+    // the container escaped the arena it was given -- and get_allocator(), which reports m_values'
+    // allocator, could not be used to reason about the buckets any more.
     table(table const& other, allocator_type const& alloc)
         : m_values(other.m_values, alloc)
+        , m_buckets(alloc)
         , m_max_load_factor(other.m_max_load_factor)
         , m_hash(other.m_hash)
         , m_equal(other.m_equal) {
         copy_buckets(other);
     }
 
+    // Unconditionally noexcept, and honestly so: it hands over other's own allocator, so the
+    // assignment below always takes the branch that takes the buffers over rather than the one
+    // that moves elements into freshly allocated memory.
     table(table&& other) noexcept
         : table(std::move(other), other.m_values.get_allocator()) {}
 
-    table(table&& other, allocator_type const& alloc) noexcept
-        : m_values(alloc) {
-        *this = std::move(other);
+    // Uses alloc, unconditionally. It used to construct empty and then move-assign, which cannot
+    // express that: assignment has to consult propagate_on_container_move_assignment, so with a
+    // propagating allocator this ended up holding other's and the allocator the caller asked for
+    // was quietly dropped -- while std::vector, given the same allocator, kept it.
+    //
+    // Not unconditionally noexcept, unlike the plain move constructor above: this is the one whose
+    // whole purpose is a *differing* allocator, so the containers below may have to move the
+    // elements one at a time, and that allocates. The specification is theirs.
+    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved) -- moved from member by member
+    table(table&& other, allocator_type const& alloc) noexcept(
+        std::is_nothrow_constructible_v<value_container_type, value_container_type&&, allocator_type const&> &&
+        std::is_nothrow_constructible_v<bucket_container_type, bucket_container_type&&, allocator_type const&> &&
+        std::is_nothrow_move_constructible_v<Hash> && std::is_nothrow_move_constructible_v<KeyEqual>)
+        : m_values(std::move(other.m_values), alloc)
+        , m_buckets(std::move(other.m_buckets), alloc)
+        , m_max_bucket_capacity(std::exchange(other.m_max_bucket_capacity, 0))
+        , m_bucket_mask(std::exchange(other.m_bucket_mask, 0))
+        , m_max_load_factor(std::exchange(other.m_max_load_factor, default_max_load_factor))
+        , m_hash(std::move(other.m_hash))
+        , m_equal(std::move(other.m_equal))
+        , m_shifts(std::exchange(other.m_shifts, initial_shifts)) {
+        // When the allocators differ the two containers above moved element by element, so other
+        // still holds them. Either way it has to come out of this as an empty, usable table, which
+        // the exchanges above have already made the rest of it -- and an empty table needs no
+        // buckets, so this hands nothing back to it.
+        other.m_values.clear();
+        other.m_buckets.clear();
     }
 
     table(std::initializer_list<value_type> ilist,
@@ -1387,48 +1923,47 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     auto operator=(table const& other) -> table& {
         if (&other != this) {
             deallocate_buckets(); // deallocate before m_values is set (might have another allocator)
-            m_values = other.m_values;
-            m_max_load_factor = other.m_max_load_factor;
-            m_hash = other.m_hash;
-            m_equal = other.m_equal;
-            m_shifts = initial_shifts;
-            copy_buckets(other);
+
+            // Copying the values, and building the buckets for them, both allocate. Until both have
+            // happened the table holds values with no buckets to find them by; a throw in there
+            // used to leave it that way, so size() counted elements that find() could not reach and
+            // the next lookup probed a bucket array that was not there. See reset_to_empty().
+            if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()) {
+                try {
+                    copy_everything_from(other);
+                } catch (...) {
+                    reset_to_empty();
+                    throw;
+                }
+            } else {
+                copy_everything_from(other);
+            }
         }
         return *this;
     }
 
-    auto operator=(table&& other) noexcept(noexcept(std::is_nothrow_move_assignable_v<value_container_type> &&
-                                                    std::is_nothrow_move_assignable_v<Hash> &&
-                                                    std::is_nothrow_move_assignable_v<KeyEqual>)) -> table& {
+    // The condition used to be wrapped in another noexcept(), which asks whether evaluating a bool expression can
+    // throw. It cannot, so the specification was noexcept(true) whatever the traits said, and a type with a throwing
+    // move assignment terminated instead of propagating.
+    auto operator=(table&& other) noexcept(move_assign_is_nothrow) -> table& {
         if (&other != this) {
             deallocate_buckets(); // deallocate before m_values is set (might have another allocator)
-            m_values = std::move(other.m_values);
-            other.m_values.clear();
 
-            // we can only reuse m_buckets when both maps have the same allocator!
-            if (get_allocator() == other.get_allocator()) {
-                m_buckets = std::move(other.m_buckets);
-                other.m_buckets.clear();
-                m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0);
-                m_shifts = std::exchange(other.m_shifts, initial_shifts);
-                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, {});
-                other.allocate_buckets_from_shift();
-                other.clear_buckets();
+            // Same window as the copy assignment above, and reachable for the same reason: with an
+            // allocator that neither propagates nor compares equal the move below moves the
+            // elements one at a time into memory it has to allocate. See reset_to_empty().
+            // Exactly when this operator does not promise noexcept, which is what makes the
+            // recovery reachable rather than a rethrow inside a noexcept function.
+            if constexpr (ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() && !move_assign_is_nothrow) {
+                try {
+                    move_everything_from(std::move(other));
+                } catch (...) {
+                    reset_to_empty();
+                    throw;
+                }
             } else {
-                // set max_load_factor *before* copying the other's buckets, so we have the same
-                // behavior
-                m_max_load_factor = other.m_max_load_factor;
-
-                // copy_buckets sets m_buckets, m_num_buckets, m_max_bucket_capacity, m_shifts
-                copy_buckets(other);
-                // clear's the other's buckets so other is now already usable.
-                other.clear_buckets();
-                m_hash = other.m_hash;
-                m_equal = other.m_equal;
+                move_everything_from(std::move(other));
             }
-            // map "other" is now already usable, it's empty.
         }
         return *this;
     }
@@ -1490,8 +2025,10 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     // modifiers //////////////////////////////////////////////////////////////
 
     void clear() {
-        m_values.clear();
-        clear_buckets();
+        if (!empty()) {
+            m_values.clear();
+            clear_buckets();
+        }
     }
 
     auto insert(value_type const& value) -> std::pair<iterator, bool> {
@@ -1535,7 +2072,14 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     // 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);
+        auto values = std::move(m_values);
+
+        // Moving the values out does not empty the buckets, and they index into the container that just left. Emptying
+        // them here is what makes "*this is emptied" true: without it the table looks empty -- size() is 0, find()
+        // returns end() -- and then the next insert probes a bucket pointing at an element that is no longer there.
+        m_values.clear();
+        clear_buckets();
+        return values;
     }
 
     // nonstandard API:
@@ -1547,19 +2091,23 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
             }
         auto shifts = calc_shifts_for_size(container.size());
         if (0 == bucket_count() || shifts < m_shifts || container.get_allocator() != m_values.get_allocator()) {
-            m_shifts = shifts;
-            deallocate_buckets();
-            allocate_buckets_from_shift();
+            allocate_buckets_from_shift(shifts);
         }
         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{};
+        //
+        // Counted in std::size_t rather than in value_idx_type. max_size() is exactly the number
+        // values that type can hold, so a container of precisely that many has a size that is not
+        // representable in it: the cast wrapped to zero, the loop below never ran once, and the
+        // table came back reporting size() elements with no bucket pointing at any of them. Every
+        // index the loop produces is representable -- it is the count that is not.
+        auto value_idx = std::size_t{};
 
         // loop until we reach the end of the container. duplicated entries will be replaced with back().
-        while (value_idx != static_cast<value_idx_type>(m_values.size())) {
+        while (value_idx != m_values.size()) {
             auto const& key = get_key(m_values[value_idx]);
 
             auto hash = mixed_hash(key);
@@ -1582,12 +2130,12 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
             }
 
             if (key_found) {
-                if (value_idx != static_cast<value_idx_type>(m_values.size() - 1)) {
+                if (value_idx != 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);
+                place_and_shift_up({dist_and_fingerprint, static_cast<value_idx_type>(value_idx)}, bucket_idx);
                 ++value_idx;
             }
         }
@@ -1640,6 +2188,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
               typename KE = KeyEqual,
               std::enable_if_t<!is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
     auto emplace(K&& key) -> std::pair<iterator, bool> {
+        allocate_buckets_if_none();
         auto hash = mixed_hash(key);
         auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
         auto bucket_idx = bucket_idx_from_hash(hash);
@@ -1660,6 +2209,8 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
 
     template <class... Args>
     auto emplace(Args&&... args) -> std::pair<iterator, bool> {
+        allocate_buckets_if_none();
+
         // we have to instantiate the value_type to be able to access the key.
         // 1. emplace_back the object so it is constructed. 2. If the key is already there, pop it later in the loop.
         auto& key = get_key(m_values.emplace_back(std::forward<Args>(args)...));
@@ -1802,7 +2353,9 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
             bucket_idx = next(bucket_idx);
         }
 
-        do_erase(bucket_idx, [](value_type const& /*unused*/) {
+        // The noexcept here and on the other two erase callbacks is what keeps erase() out of do_erase()'s exception
+        // guard: a call expression is noexcept only if the callee says so, an empty body is not enough.
+        do_erase(bucket_idx, [](value_type const& /*unused*/) noexcept -> void {
         });
         return begin() + static_cast<difference_type>(value_idx_to_remove);
     }
@@ -1817,7 +2370,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         }
 
         auto tmp = std::optional<value_type>{};
-        do_erase(bucket_idx, [&tmp](value_type&& val) {
+        do_erase(bucket_idx, [&tmp](value_type&& val) -> void {
             tmp = std::move(val);
         });
         return std::move(tmp).value();
@@ -1858,13 +2411,13 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     }
 
     auto erase(Key const& key) -> std::size_t {
-        return do_erase_key(key, [](value_type const& /*unused*/) {
+        return do_erase_key(key, [](value_type const& /*unused*/) noexcept -> void {
         });
     }
 
     auto extract(Key const& key) -> std::optional<value_type> {
         auto tmp = std::optional<value_type>{};
-        do_erase_key(key, [&tmp](value_type&& val) {
+        do_erase_key(key, [&tmp](value_type&& val) -> void {
             tmp = std::move(val);
         });
         return tmp;
@@ -1872,23 +2425,42 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
 
     template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
     auto erase(K&& key) -> std::size_t {
-        return do_erase_key(std::forward<K>(key), [](value_type const& /*unused*/) {
+        return do_erase_key(std::forward<K>(key), [](value_type const& /*unused*/) noexcept -> void {
         });
     }
 
     template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
     auto extract(K&& key) -> std::optional<value_type> {
         auto tmp = std::optional<value_type>{};
-        do_erase_key(std::forward<K>(key), [&tmp](value_type&& val) {
+        do_erase_key(std::forward<K>(key), [&tmp](value_type&& val) -> void {
             tmp = std::move(val);
         });
         return tmp;
     }
 
-    void swap(table& other) noexcept(noexcept(std::is_nothrow_swappable_v<value_container_type> &&
-                                              std::is_nothrow_swappable_v<Hash> && std::is_nothrow_swappable_v<KeyEqual>)) {
+    void swap(table& other) noexcept(std::is_nothrow_swappable_v<value_container_type> &&
+                                     std::is_nothrow_swappable_v<bucket_container_type> && std::is_nothrow_swappable_v<Hash> &&
+                                     std::is_nothrow_swappable_v<KeyEqual>) {
+        // There is no free swap() for table, so "swap(other, *this)" used to resolve to the generic std::swap: three
+        // move assignments, each of which hands the moved-from table a freshly allocated set of buckets. That is three
+        // allocations for an operation that needs none, and three ways to throw out of a noexcept function.
+        //
+        // segmented_vector has a swap of its own now, so both container choices answer the allocator
+        // question the same way; see its definition for what the generic std::swap did instead.
+        //
+        // Calling it as a member rather than unqualified is not what fixes that -- the free swap
+        // beside it is found by ADL just the same. It is so that a BucketContainer supplied from
+        // some other namespace cannot quietly fall back to the three-move std::swap: every
+        // container is required to have the member, none is required to have the free function.
+        m_values.swap(other.m_values);
+        m_buckets.swap(other.m_buckets);
         using std::swap;
-        swap(other, *this);
+        swap(m_max_bucket_capacity, other.m_max_bucket_capacity);
+        swap(m_bucket_mask, other.m_bucket_mask);
+        swap(m_max_load_factor, other.m_max_load_factor);
+        swap(m_hash, other.m_hash);
+        swap(m_equal, other.m_equal);
+        swap(m_shifts, other.m_shifts);
     }
 
     // lookup /////////////////////////////////////////////////////////////////
@@ -1998,6 +2570,127 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         return {it, it == end() ? end() : it + 1};
     }
 
+    // lookup with a precomputed hash /////////////////////////////////////////
+
+    // Looking the same key up over and over -- a handful of string literals against a map parsed
+    // out of a document, say -- hashes it every time, and for a long key that hashing is most of
+    // the cost of the lookup. Hashing it once instead is what hash_for() and these overloads are
+    // for:
+    //
+    //     auto const h = map.hash_for("some-long-key"); // once
+    //     auto it = map.find("some-long-key", h);       // as often as you like
+    //
+    // The key is still needed, because a lookup that found a bucket still has to compare keys to
+    // know it found the right one. What is saved is the hashing, not the comparison.
+    //
+    // The number a lookup wants is the one hash_for() returns, and nothing else: it is the hasher's
+    // output finalized the way a lookup finalizes it, which for most hashers is not the same number
+    // the hasher gave. An integer will not convert to a precomputed_hash, which is the mistake
+    // worth blocking; the value inside stays open, since a caller may want to keep or move one.
+    // Every table with this hasher takes it, so one hash can serve a map and a set together, and a
+    // stateless hasher makes it good for the life of the program. What it does not survive is the
+    // key changing -- pass the hash of a different key and the lookup quietly finds nothing.
+    //
+    // Only lookups take one. Insertion never will: a lookup handed the wrong hash merely misses,
+    // while an insertion handed one files the element under a probe chain it is not on, which
+    // loses it for good and lets a second copy of the same key in beside it. Erase is left out for
+    // a duller reason -- it hashes the moved element as well as the key, so precomputing the key's
+    // hash saves it only half its hashing.
+    [[nodiscard]] auto hash_for(Key const& key) const -> precomputed_hash {
+        return {mixed_hash(key)};
+    }
+
+    template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+    [[nodiscard]] auto hash_for(K const& key) const -> precomputed_hash {
+        return {mixed_hash(key)};
+    }
+
+    auto find(Key const& key, precomputed_hash ph) -> iterator {
+        return do_find(key, ph);
+    }
+
+    auto find(Key const& key, precomputed_hash ph) const -> const_iterator {
+        return do_find(key, ph);
+    }
+
+    template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+    auto find(K const& key, precomputed_hash ph) -> iterator {
+        return do_find(key, ph);
+    }
+
+    template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+    auto find(K const& key, precomputed_hash ph) const -> const_iterator {
+        return do_find(key, ph);
+    }
+
+    auto contains(Key const& key, precomputed_hash ph) const -> bool {
+        return find(key, ph) != end();
+    }
+
+    template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+    auto contains(K const& key, precomputed_hash ph) const -> bool {
+        return find(key, ph) != end();
+    }
+
+    auto count(Key const& key, precomputed_hash ph) const -> std::size_t {
+        return find(key, ph) == end() ? 0 : 1;
+    }
+
+    template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+    auto count(K const& key, precomputed_hash ph) const -> std::size_t {
+        return find(key, ph) == end() ? 0 : 1;
+    }
+
+    auto equal_range(Key const& key, precomputed_hash ph) -> std::pair<iterator, iterator> {
+        auto it = do_find(key, ph);
+        return {it, it == end() ? end() : it + 1};
+    }
+
+    auto equal_range(Key const& key, precomputed_hash ph) const -> std::pair<const_iterator, const_iterator> {
+        auto it = do_find(key, ph);
+        return {it, it == end() ? end() : it + 1};
+    }
+
+    template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+    auto equal_range(K const& key, precomputed_hash ph) -> std::pair<iterator, iterator> {
+        auto it = do_find(key, ph);
+        return {it, it == end() ? end() : it + 1};
+    }
+
+    template <class K, class H = Hash, class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
+    auto equal_range(K const& key, precomputed_hash ph) const -> std::pair<const_iterator, const_iterator> {
+        auto it = do_find(key, ph);
+        return {it, it == end() ? end() : it + 1};
+    }
+
+    template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+    auto at(key_type const& key, precomputed_hash ph) -> Q& {
+        return do_at(key, ph);
+    }
+
+    template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
+    auto at(key_type const& key, precomputed_hash ph) const -> Q const& {
+        return do_at(key, ph);
+    }
+
+    template <typename K,
+              typename Q = T,
+              typename H = Hash,
+              typename KE = KeyEqual,
+              std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
+    auto at(K const& key, precomputed_hash ph) -> Q& {
+        return do_at(key, ph);
+    }
+
+    template <typename K,
+              typename Q = T,
+              typename H = Hash,
+              typename KE = KeyEqual,
+              std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
+    auto at(K const& key, precomputed_hash ph) const -> Q const& {
+        return do_at(key, ph);
+    }
+
     // bucket interface ///////////////////////////////////////////////////////
 
     auto bucket_count() const noexcept -> std::size_t { // NOLINT(modernize-use-nodiscard)
@@ -2019,7 +2712,11 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     }
 
     void max_load_factor(float ml) {
-        m_max_load_factor = ml;
+        // A load factor above 1 is meaningful for a container that chains, and std::unordered_map takes one. Open
+        // addressing cannot use it: m_max_bucket_capacity would exceed bucket_count(), is_full() would never fire, the
+        // table would fill completely, and place_and_shift_up() would then probe forever for an empty bucket that does
+        // not exist. Exactly 1 is fine, because is_full() is checked after the value is appended.
+        m_max_load_factor = (std::min)(ml, 1.0F);
         if (bucket_count() != max_bucket_count()) {
             m_max_bucket_capacity = static_cast<value_idx_type>(static_cast<float>(bucket_count()) * max_load_factor());
         }
@@ -2029,10 +2726,8 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         count = (std::min)(count, max_size());
         auto shifts = calc_shifts_for_size((std::max)(count, size()));
         if (shifts != m_shifts) {
-            m_shifts = shifts;
-            deallocate_buckets();
+            allocate_buckets_from_shift(shifts);
             m_values.shrink_to_fit();
-            allocate_buckets_from_shift();
             clear_and_fill_buckets_from_values();
         }
     }
@@ -2045,9 +2740,7 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
         }
         auto shifts = calc_shifts_for_size((std::max)(capa, size()));
         if (0 == bucket_count() || shifts < m_shifts) {
-            m_shifts = shifts;
-            deallocate_buckets();
-            allocate_buckets_from_shift();
+            allocate_buckets_from_shift(shifts);
             clear_and_fill_buckets_from_values();
         }
     }
@@ -2096,6 +2789,12 @@ class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, bas
     friend auto operator!=(table const& a, table const& b) -> bool {
         return !(a == b);
     }
+
+    // Standard containers provide this, and generic code written as "using std::swap; swap(a, b);" needs it to find
+    // the member. Without it that call lands on the generic std::swap and moves three times.
+    friend void swap(table& a, table& b) noexcept(noexcept(a.swap(b))) {
+        a.swap(b);
+    }
 };
 
 } // namespace detail

base-commit: afa6db16e6508d8ea269557085bc7c301e824382
-- 
2.55.0