removed overzealous inlines

.drone.jsonnet

@@ -138,217 +138,31 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
     ),
 
     linux_pipeline(
-        "Linux 16.04 GCC 5* 32/64",
-        "cppalliance/droneubuntu1604:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 18.04 GCC 6 32/64",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-6', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-        "g++-6-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 18.04 GCC 7* 32/64",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 18.04 GCC 8 32/64",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-8', CXXSTD: '03,11,14,17', ADDRMD: '32,64' },
-        "g++-8-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 9* 32/64",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 9* ARM64",
+        "Linux 20.04 GCC 9* ARM64 32",
         "cppalliance/droneubuntu2004:multiarch",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32' },
         arch="arm64",
     ),
 
     linux_pipeline(
-        "Linux 20.04 GCC 9* S390x",
+        "Linux 20.04 GCC 9* ARM64 64",
         "cppalliance/droneubuntu2004:multiarch",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '64' },
+        arch="arm64",
+    ),
+
+    linux_pipeline(
+        "Linux 20.04 GCC 9* S390x 32",
+        "cppalliance/droneubuntu2004:multiarch",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32' },
         arch="s390x",
     ),
 
     linux_pipeline(
-        "Linux 20.04 GCC 10 32/64",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '03,11,14,17,20', ADDRMD: '32,64' },
-        "g++-10-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 11* 32/64",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (03,11,14)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '03,11,14', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (17,20,2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17,20,2b', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (03,11,14)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '03,11,14', ADDRMD: '64' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (17,20,2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17,20,2b', ADDRMD: '64' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 16.04 Clang 3.5",
-        "cppalliance/droneubuntu1604:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-3.5', CXXSTD: '03,11' },
-        "clang-3.5",
-    ),
-
-    linux_pipeline(
-        "Linux 16.04 Clang 3.6",
-        "cppalliance/droneubuntu1604:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-3.6', CXXSTD: '03,11,14' },
-        "clang-3.6",
-    ),
-
-    linux_pipeline(
-        "Linux 16.04 Clang 3.7",
-        "cppalliance/droneubuntu1604:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-3.7', CXXSTD: '03,11,14' },
-        "clang-3.7",
-    ),
-
-    linux_pipeline(
-        "Linux 16.04 Clang 3.8",
-        "cppalliance/droneubuntu1604:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-3.8', CXXSTD: '03,11,14' },
-        "clang-3.8",
-    ),
-
-    linux_pipeline(
-        "Linux 18.04 Clang 3.9",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-3.9', CXXSTD: '03,11,14' },
-        "clang-3.9",
-    ),
-
-    linux_pipeline(
-        "Linux 18.04 Clang 4.0",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-4.0', CXXSTD: '03,11,14' },
-        "clang-4.0",
-    ),
-
-    linux_pipeline(
-        "Linux 18.04 Clang 5.0",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-5.0', CXXSTD: '03,11,14,1z' },
-        "clang-5.0",
-    ),
-
-    linux_pipeline(
-        "Linux 18.04 Clang 6.0",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-6.0', CXXSTD: '03,11,14,17' },
-        "clang-6.0",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 Clang 7",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-7', CXXSTD: '03,11,14,17' },
-        "clang-7",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 Clang 8",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-8', CXXSTD: '03,11,14,17' },
-        "clang-8",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 Clang 9",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-9', CXXSTD: '03,11,14,17,2a' },
-        "clang-9",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 Clang 10",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-10', CXXSTD: '03,11,14,17,2a' },
-        "clang-10",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 Clang 11",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-11', CXXSTD: '03,11,14,17,2a' },
-        "clang-11",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 Clang 12",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-12', CXXSTD: '03,11,14,17,2a' },
-        "clang-12",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 13",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-13', CXXSTD: '03,11,14,17,20' },
-        "clang-13",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 14 UBSAN",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20' } + ubsan,
-        "clang-14",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 14 ASAN",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20' } + asan,
-        "clang-14",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 15",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-15', CXXSTD: '03,11,14,17,20,2b' },
-        "clang-15",
-        ["deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy-15 main"],
+        "Linux 20.04 GCC 9* S390x 64",
+        "cppalliance/droneubuntu2004:multiarch",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '64' },
+        arch="s390x",
     ),
 
     macos_pipeline(
@@ -362,27 +176,9 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
         xcode_version = "13.4.1", osx_version = "monterey",
     ),
 
-    windows_pipeline(
-        "Windows VS2015 msvc-14.0",
-        "cppalliance/dronevs2015",
-        { TOOLSET: 'msvc-14.0', CXXSTD: '14,latest' },
-    ),
-
     windows_pipeline(
         "Windows VS2017 msvc-14.1",
         "cppalliance/dronevs2017",
         { TOOLSET: 'msvc-14.1', CXXSTD: '14,17,latest' },
     ),
-
-    windows_pipeline(
-        "Windows VS2019 msvc-14.2",
-        "cppalliance/dronevs2019",
-        { TOOLSET: 'msvc-14.2', CXXSTD: '14,17,20,latest' },
-    ),
-
-    windows_pipeline(
-        "Windows VS2022 msvc-14.3",
-        "cppalliance/dronevs2022:1",
-        { TOOLSET: 'msvc-14.3', CXXSTD: '14,17,20,latest' },
-    ),
 ]

.github/workflows/ci.yml

@@ -42,37 +42,45 @@ jobs:
       matrix:
         include:
           # Linux, gcc
-          - { compiler: gcc-7,     cxxstd: '03,11,14,17',    os: ubuntu-20.04, install: 'g++-7' }
-          - { compiler: gcc-8,     cxxstd: '03,11,14,17',    os: ubuntu-20.04, install: 'g++-8' }
-          - { compiler: gcc-9,     cxxstd: '03,11,14,17',    os: ubuntu-20.04, install: 'g++-9' }
-          - { compiler: gcc-10,    cxxstd: '03,11,14,17,20', os: ubuntu-22.04, install: 'g++-10' }
-          - { compiler: gcc-11,    cxxstd: '03,11,14,17,20', os: ubuntu-22.04, install: 'g++-11' }
-          - { name: "gcc-12 w/ sanitizers (03,11,14)", sanitize: yes,
-              compiler: gcc-12,    cxxstd: '03,11,14',       os: ubuntu-22.04, ccache_key: "san1" }
-          - { name: "gcc-12 w/ sanitizers (17,20,2b)", sanitize: yes,
-              compiler: gcc-12,    cxxstd: '17,20,2b',       os: ubuntu-22.04, ccache_key: "san2" }
+          - { compiler: gcc-4.8,   cxxstd: '03,11',          os: ubuntu-18.04, install: 'g++-4.8-multilib', address-model: '32,64' }
+          - { compiler: gcc-4.9,   cxxstd: '03,11',          os: ubuntu-20.04, container: 'ubuntu:16.04' }
+          - { compiler: gcc-5,     cxxstd: '03,11,14,1z',    os: ubuntu-18.04, install: 'g++-5-multilib', address-model: '32,64' }
+          - { compiler: gcc-6,     cxxstd: '03,11,14,17',    os: ubuntu-18.04, install: 'g++-6-multilib', address-model: '32,64' }
+          - { compiler: gcc-7,     cxxstd: '03,11,14,17',    os: ubuntu-18.04, install: 'g++-7-multilib', address-model: '32,64' }
+          - { compiler: gcc-8,     cxxstd: '03,11,14,17,2a', os: ubuntu-18.04, install: 'g++-8-multilib', address-model: '32,64' }
+          - { compiler: gcc-9,     cxxstd: '03,11,14,17,2a', os: ubuntu-18.04, install: 'g++-9-multilib', address-model: '32,64' }
+          - { compiler: gcc-10,    cxxstd: '03,11,14,17,20', os: ubuntu-20.04, install: 'g++-10-multilib', address-model: '32,64' }
+          - { compiler: gcc-11,    cxxstd: '03,11,14,17,20', os: ubuntu-20.04, install: 'g++-11-multilib', address-model: '32,64' }
+          - { compiler: gcc-12,    cxxstd: '03,11,14,17,20', os: ubuntu-22.04, install: 'g++-12-multilib', address-model: '32,64' }
+          - { name: GCC w/ sanitizers, sanitize: yes,
+              compiler: gcc-12,    cxxstd: '03,11,14,17,20', os: ubuntu-22.04 }
           - { name: Collect coverage, coverage: yes,
-              compiler: gcc-8,     cxxstd: '03,11',          os: ubuntu-20.04, install: 'g++-8-multilib', address-model: '32,64', ccache_key: "cov" }
+              compiler: gcc-8,     cxxstd: '03,11',          os: ubuntu-20.04, install: 'g++-8-multilib', address-model: '32,64' }
 
-          # Linux, clang, libc++
-          - { compiler: clang-7,   cxxstd: '03,11,14,17',       os: ubuntu-20.04, stdlib: libc++, install: 'clang-7 libc++-7-dev libc++abi-7-dev' }
-          - { compiler: clang-10,  cxxstd: '03,11,14,17,20',    os: ubuntu-20.04, stdlib: libc++, install: 'clang-10 libc++-10-dev libc++abi-10-dev' }
-          - { compiler: clang-11,  cxxstd: '03,11,14,17,20',    os: ubuntu-22.04, stdlib: libc++, install: 'clang-11 libc++-11-dev libc++abi-11-dev' }
-          # clang-12 doesn't work on ubuntu-22.04, the linker can't find -lunwind for some reason
-          - { name: "clang-12 w/ sanitizers (03,11,14)", sanitize: yes,
-              compiler: clang-12,  cxxstd: '03,11,14',          os: ubuntu-20.04, stdlib: libc++, install: 'clang-12 libc++-12-dev libc++abi-12-dev', ccache_key: "san1" }
-          - { name: "clang-12 w/ sanitizers (17,20,2b)", sanitize: yes,
-              compiler: clang-12,  cxxstd: '17,20,2b',          os: ubuntu-20.04, stdlib: libc++, install: 'clang-12 libc++-12-dev libc++abi-12-dev', ccache_key: "san2" }
-          - { compiler: clang-13,  cxxstd: '03,11,14,17,20,2b', os: ubuntu-22.04, stdlib: libc++, install: 'clang-13 libc++-13-dev libc++abi-13-dev' }
-          - { compiler: clang-14,  cxxstd: '03,11,14,17,20,2b', os: ubuntu-22.04, stdlib: libc++, install: 'clang-14 libc++-14-dev libc++abi-14-dev' }
-          # not using libc++ because of https://github.com/llvm/llvm-project/issues/52771
-          - { name: "clang-14 w/ sanitizers (03,11,14)", sanitize: yes,
-              compiler: clang-14,  cxxstd: '03,11,14',          os: ubuntu-22.04, ccache_key: "san1" }
-          - { name: "clang-14 w/ sanitizers (17,20,2b)", sanitize: yes,
-              compiler: clang-14,  cxxstd: '17,20,2b',          os: ubuntu-22.04, ccache_key: "san2" }
+          # Linux, clang
+          - { compiler: clang-3.7, cxxstd: '03,11,14',       os: ubuntu-20.04, container: 'ubuntu:16.04' }
+          - { compiler: clang-3.8, cxxstd: '03,11,14',       os: ubuntu-20.04, container: 'ubuntu:16.04' }
+          - { compiler: clang-3.9, cxxstd: '03,11,14',       os: ubuntu-18.04 }
+          - { compiler: clang-4.0, cxxstd: '03,11,14',       os: ubuntu-18.04 }
+          - { compiler: clang-5.0, cxxstd: '03,11,14,1z',    os: ubuntu-18.04 }
+          - { compiler: clang-6.0, cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
+          - { compiler: clang-7,   cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
+          - { compiler: clang-8,   cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
+          - { compiler: clang-9,   cxxstd: '03,11,14,17,2a', os: ubuntu-20.04 }
+          - { compiler: clang-10,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04 }
+          - { compiler: clang-11,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04 }
+          - { compiler: clang-12,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04 }
+          - { compiler: clang-13,  cxxstd: '03,11,14,17,20', os: ubuntu-22.04 }
+          - { compiler: clang-14,  cxxstd: '03,11,14,17,20', os: ubuntu-22.04 }
+
+          # libc++
+          - { compiler: clang-6.0, cxxstd: '03,11,14',       os: ubuntu-18.04, stdlib: libc++, install: 'clang-6.0 libc++-dev libc++abi-dev' }
+          - { compiler: clang-12,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04, stdlib: libc++, install: 'clang-12 libc++-12-dev libc++abi-12-dev' }
+          - { name: Clang w/ sanitizers, sanitize: yes,
+              compiler: clang-12,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04, stdlib: libc++, install: 'clang-12 libc++-12-dev libc++abi-12-dev' }
 
           # OSX, clang
-          - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-11, sanitize: yes }
+          - { compiler: clang,     cxxstd: '03,11,14,17,2a', os: macos-11, sanitize: yes }
 
     timeout-minutes: 120
     runs-on: ${{matrix.os}}
@@ -111,8 +119,8 @@ jobs:
         if: env.B2_USE_CCACHE
         with:
           path: ~/.ccache
-          key: ${{matrix.os}}-${{matrix.container}}-${{matrix.compiler}}-${{matrix.ccache_key}}-${{github.sha}}
-          restore-keys: ${{matrix.os}}-${{matrix.container}}-${{matrix.compiler}}-${{matrix.ccache_key}}-
+          key: ${{matrix.os}}-${{matrix.container}}-${{matrix.compiler}}-${{github.sha}}
+          restore-keys: ${{matrix.os}}-${{matrix.container}}-${{matrix.compiler}}-
 
       - name: Fetch Boost.CI
         uses: actions/checkout@v3
@@ -217,13 +225,11 @@ jobs:
       fail-fast: false
       matrix:
         include:
-          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
-          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
-          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
-          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '64',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '/RTCc'              }
-          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '32',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '"/RTCc /arch:IA32"' }
-          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
-          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019, variant: 'debug,release' }
+          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019 }
+          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019 }
+          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022 }
+          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022 }
+          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019 }
 
     runs-on: ${{matrix.os}}
 
@@ -252,9 +258,6 @@ jobs:
           B2_TOOLSET: ${{matrix.toolset}}
           B2_CXXSTD: ${{matrix.cxxstd}}
           B2_ADDRESS_MODEL: ${{matrix.addrmd}}
-          B2_DEFINES: ${{matrix.defines}}
-          B2_VARIANT: ${{matrix.variant}}
-          B2_CXXFLAGS: ${{matrix.cxxflags}}
 
       - name: Collect coverage
         shell: powershell

benchmark/.gitignore

@@ -1,3 +0,0 @@
-enwik8
-enwik9
-*.exe

benchmark/string.cpp

@@ -3,18 +3,22 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -262,6 +266,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -272,9 +294,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -285,10 +304,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -334,10 +366,7 @@ template<> struct fnv1a_hash_impl<64>
     }
 };
 
-struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
-{
-    using is_avalanching = void;
-};
+struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits > {};
 
 template<class K, class V> using std_unordered_map_fnv1a =
 std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
@@ -345,8 +374,13 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
-template<class K, class V> using boost_unordered_flat_map_fnv1a =
-    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
+template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
+  >,
+  ::allocator< pair<K, V> >
+>;
 
 #ifdef HAVE_ABSEIL
 
@@ -358,10 +392,23 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map_fnv1a =
+    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
+    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map_fnv1a =
+    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map_fnv1a =
+    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -371,15 +418,11 @@ int main()
 {
     init_indices();
 
+#if 0
+
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
@@ -388,28 +431,52 @@ int main()
 
 #endif
 
-    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
-    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
+#ifdef HAVE_TSL_HOPSCOTCH
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
 
 #endif
 
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
+#endif
+
+#endif
+
+    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
+    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
+
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
+    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
+    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 31 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/string_view.cpp

@@ -3,18 +3,22 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <string_view>
@@ -263,6 +267,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -273,9 +295,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -286,10 +305,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -335,10 +367,7 @@ template<> struct fnv1a_hash_impl<64>
     }
 };
 
-struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
-{
-    using is_avalanching = void;
-};
+struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits > {};
 
 template<class K, class V> using std_unordered_map_fnv1a =
 std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
@@ -346,8 +375,13 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
-template<class K, class V> using boost_unordered_flat_map_fnv1a =
-    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
+template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
+  >,
+  ::allocator< pair<K, V> >
+>;
 
 #ifdef HAVE_ABSEIL
 
@@ -359,10 +393,23 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map_fnv1a =
+    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
+    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map_fnv1a =
+    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map_fnv1a =
+    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -372,15 +419,11 @@ int main()
 {
     init_indices();
 
+#if 0
+
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
@@ -389,28 +432,52 @@ int main()
 
 #endif
 
-    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
-    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
+#ifdef HAVE_TSL_HOPSCOTCH
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
 
 #endif
 
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
+#endif
+
+#endif
+
+    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
+    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
+
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
+    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
+    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 31 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint32.cpp

@@ -3,10 +3,11 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -14,8 +15,11 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -279,6 +283,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -289,9 +311,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -302,10 +321,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -315,26 +347,34 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 25 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint64.cpp

@@ -3,10 +3,11 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -14,8 +15,11 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -279,6 +283,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -289,9 +311,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -302,10 +321,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -313,38 +345,36 @@ int main()
 {
     init_indices();
 
-#if defined(BOOST_LIBSTDCXX_VERSION) && __SIZE_WIDTH__ == 32
-
-    // Pathological behavior:
-    // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104945
-
-#else
-
     test<std_unordered_map>( "std::unordered_map" );
-
-#endif
-
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 25 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uuid.cpp

@@ -1,397 +0,0 @@
-// Copyright 2021, 2022 Peter Dimov.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/endian/conversion.hpp>
-#include <boost/core/detail/splitmix64.hpp>
-#include <boost/container_hash/hash.hpp>
-#include <boost/config.hpp>
-#ifdef HAVE_ABSEIL
-# include "absl/container/node_hash_map.h"
-# include "absl/container/flat_hash_map.h"
-#endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <cstring>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::uint64_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-constexpr unsigned N = 2'000'000;
-constexpr int K = 10;
-
-struct uuid
-{
-    unsigned char data[ 16 ];
-
-    uuid(): data()
-    {
-    }
-
-    uuid( std::uint64_t low, std::uint64_t high ) noexcept
-    {
-        boost::endian::store_little_u64( data + 0, low );
-        boost::endian::store_little_u64( data + 8, high );
-    }
-
-    inline friend std::size_t hash_value( uuid const& u ) noexcept
-    {
-        std::uint64_t low  = boost::endian::load_little_u64( u.data + 0 );
-        std::uint64_t high = boost::endian::load_little_u64( u.data + 8 );
-
-        std::size_t r = 0;
-
-        boost::hash_combine( r, low );
-        boost::hash_combine( r, high );
-
-        return r;
-    }
-
-    inline friend bool operator==( uuid const& u1, uuid const& u2 ) noexcept
-    {
-        return std::memcmp( u1.data, u2.data, 16 ) == 0;
-    }
-};
-
-namespace std
-{
-
-template<> struct hash< ::uuid >
-{
-    std::size_t operator()( uuid const& u ) const noexcept
-    {
-        return hash_value( u );
-    }
-};
-
-} // namespace std
-
-static std::vector< uuid > indices1, indices2, indices3;
-
-static void init_indices()
-{
-    indices1.push_back( {} );
-
-    for( unsigned i = 1; i <= N*2; ++i )
-    {
-        indices1.push_back( { i, 0 } );
-    }
-
-    indices2.push_back( {} );
-
-    {
-        boost::detail::splitmix64 rng;
-
-        for( unsigned i = 1; i <= N*2; ++i )
-        {
-            indices2.push_back( { rng(), rng() } );
-        }
-    }
-
-    indices3.push_back( {} );
-
-    for( unsigned i = 1; i <= N*2; ++i )
-    {
-        uuid k( i, 0 );
-        std::reverse( k.data + 0, k.data + 16 );
-
-        indices3.push_back( k );
-    }
-}
-
-template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.insert( { indices1[ i ], i } );
-    }
-
-    print_time( t1, "Consecutive insert",  0, map.size() );
-
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.insert( { indices2[ i ], i } );
-    }
-
-    print_time( t1, "Random insert",  0, map.size() );
-
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.insert( { indices3[ i ], i } );
-    }
-
-    print_time( t1, "Consecutive reversed insert",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::uint64_t s;
-
-    s = 0;
-
-    for( int j = 0; j < K; ++j )
-    {
-        for( unsigned i = 1; i <= N * 2; ++i )
-        {
-            auto it = map.find( indices1[ i ] );
-            if( it != map.end() ) s += it->second;
-        }
-    }
-
-    print_time( t1, "Consecutive lookup",  s, map.size() );
-
-    s = 0;
-
-    for( int j = 0; j < K; ++j )
-    {
-        for( unsigned i = 1; i <= N * 2; ++i )
-        {
-            auto it = map.find( indices2[ i ] );
-            if( it != map.end() ) s += it->second;
-        }
-    }
-
-    print_time( t1, "Random lookup",  s, map.size() );
-
-    s = 0;
-
-    for( int j = 0; j < K; ++j )
-    {
-        for( unsigned i = 1; i <= N * 2; ++i )
-        {
-            auto it = map.find( indices3[ i ] );
-            if( it != map.end() ) s += it->second;
-        }
-    }
-
-    print_time( t1, "Consecutive reversed lookup",  s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    auto it = map.begin();
-
-    while( it != map.end() )
-    {
-        if( it->second & 1 )
-        {
-            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
-            {
-                map.erase( it++ );
-            }
-            else
-            {
-                it = map.erase( it );
-            }
-        }
-        else
-        {
-            ++it;
-        }
-    }
-
-    print_time( t1, "Iterate and erase odd elements",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.erase( indices1[ i ] );
-    }
-
-    print_time( t1, "Consecutive erase",  0, map.size() );
-
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.erase( indices2[ i ] );
-    }
-
-    print_time( t1, "Random erase",  0, map.size() );
-
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.erase( indices3[ i ] );
-    }
-
-    print_time( t1, "Consecutive reversed erase",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-// counting allocator
-
-static std::size_t s_alloc_bytes = 0;
-static std::size_t s_alloc_count = 0;
-
-template<class T> struct allocator
-{
-    using value_type = T;
-
-    allocator() = default;
-
-    template<class U> allocator( allocator<U> const & ) noexcept
-    {
-    }
-
-    template<class U> bool operator==( allocator<U> const & ) const noexcept
-    {
-        return true;
-    }
-
-    template<class U> bool operator!=( allocator<U> const& ) const noexcept
-    {
-        return false;
-    }
-
-    T* allocate( std::size_t n ) const
-    {
-        s_alloc_bytes += n * sizeof(T);
-        s_alloc_count++;
-
-        return std::allocator<T>().allocate( n );
-    }
-
-    void deallocate( T* p, std::size_t n ) const noexcept
-    {
-        s_alloc_bytes -= n * sizeof(T);
-        s_alloc_count--;
-
-        std::allocator<T>().deallocate( p, n );
-    }
-};
-
-//
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    std::size_t bytes_;
-    std::size_t count_;
-};
-
-static std::vector<record> times;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    s_alloc_bytes = 0;
-    s_alloc_count = 0;
-
-    Map<uuid, std::uint64_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_insert( map, t1 );
-
-    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
-
-    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
-
-    test_lookup( map, t1 );
-    test_iteration( map, t1 );
-    test_lookup( map, t1 );
-    test_erase( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    times.push_back( rec );
-}
-
-// aliases using the counting allocator
-
-template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
-
-template<class K, class V> using std_unordered_map =
-    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map =
-    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map =
-    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map =
-    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-int main()
-{
-    init_indices();
-
-    test<std_unordered_map>( "std::unordered_map" );
-    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map>( "absl::node_hash_map" );
-    test<absl_flat_hash_map>( "absl::flat_hash_map" );
-
-#endif
-
-    std::cout << "---\n\n";
-
-    for( auto const& x: times )
-    {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
-    }
-}
-
-#ifdef HAVE_ABSEIL
-# include "absl/container/internal/raw_hash_set.cc"
-# include "absl/hash/internal/hash.cc"
-# include "absl/hash/internal/low_level_hash.cc"
-# include "absl/hash/internal/city.cc"
-#endif

benchmark/word_count.cpp

@@ -1,376 +0,0 @@
-// Copyright 2021, 2022 Peter Dimov.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/regex.hpp>
-#ifdef HAVE_ABSEIL
-# include "absl/container/node_hash_map.h"
-# include "absl/container/flat_hash_map.h"
-#endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <fstream>
-#include <string_view>
-#include <string>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-static std::vector<std::string> words;
-
-static void init_words()
-{
-#if SIZE_MAX > UINT32_MAX
-
-    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
-
-#else
-
-    char const* fn = "enwik8"; // ditto
-
-#endif
-
-    auto t1 = std::chrono::steady_clock::now();
-
-    std::ifstream is( fn );
-    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
-
-    boost::regex re( "[a-zA-Z]+");
-    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
-
-    words.assign( it, end );
-
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
-}
-
-template<class Map> BOOST_NOINLINE void test_word_count( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        ++map[ word ];
-        ++s;
-    }
-
-    print_time( t1, "Word count", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_contains( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        std::string_view w2( word );
-        w2.remove_prefix( 1 );
-
-        s += map.contains( w2 );
-    }
-
-    print_time( t1, "Contains", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_count( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        std::string_view w2( word );
-        w2.remove_prefix( 1 );
-
-        s += map.count( w2 );
-    }
-
-    print_time( t1, "Count", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t max = 0;
-    std::string_view word;
-
-    for( auto const& x: map )
-    {
-        if( x.second > max )
-        {
-            word = x.first;
-            max = x.second;
-        }
-    }
-
-    print_time( t1, "Iterate and find max element",  max, map.size() );
-
-    std::cout << std::endl;
-}
-
-// counting allocator
-
-static std::size_t s_alloc_bytes = 0;
-static std::size_t s_alloc_count = 0;
-
-template<class T> struct allocator
-{
-    using value_type = T;
-
-    allocator() = default;
-
-    template<class U> allocator( allocator<U> const & ) noexcept
-    {
-    }
-
-    template<class U> bool operator==( allocator<U> const & ) const noexcept
-    {
-        return true;
-    }
-
-    template<class U> bool operator!=( allocator<U> const& ) const noexcept
-    {
-        return false;
-    }
-
-    T* allocate( std::size_t n ) const
-    {
-        s_alloc_bytes += n * sizeof(T);
-        s_alloc_count++;
-
-        return std::allocator<T>().allocate( n );
-    }
-
-    void deallocate( T* p, std::size_t n ) const noexcept
-    {
-        s_alloc_bytes -= n * sizeof(T);
-        s_alloc_count--;
-
-        std::allocator<T>().deallocate( p, n );
-    }
-};
-
-//
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    std::size_t bytes_;
-    std::size_t count_;
-};
-
-static std::vector<record> times;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    s_alloc_bytes = 0;
-    s_alloc_count = 0;
-
-    Map<std::string_view, std::size_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_word_count( map, t1 );
-
-    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
-
-    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
-
-    test_contains( map, t1 );
-    test_count( map, t1 );
-    test_iteration( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    times.push_back( rec );
-}
-
-// aliases using the counting allocator
-
-template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
-
-template<class K, class V> using std_unordered_map =
-    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map =
-    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map =
-    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map =
-    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-// fnv1a_hash
-
-template<int Bits> struct fnv1a_hash_impl;
-
-template<> struct fnv1a_hash_impl<32>
-{
-    std::size_t operator()( std::string_view const& s ) const
-    {
-        std::size_t h = 0x811C9DC5u;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x01000193ul;
-        }
-
-        return h;
-    }
-};
-
-template<> struct fnv1a_hash_impl<64>
-{
-    std::size_t operator()( std::string_view const& s ) const
-    {
-        std::size_t h = 0xCBF29CE484222325ull;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x00000100000001B3ull;
-        }
-
-        return h;
-    }
-};
-
-struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
-{
-    using is_avalanching = void;
-};
-
-template<class K, class V> using std_unordered_map_fnv1a =
-std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map_fnv1a =
-    boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map_fnv1a =
-    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map_fnv1a =
-    absl::node_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map_fnv1a =
-    absl::flat_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-//
-
-int main()
-{
-    init_words();
-
-    test<std_unordered_map>( "std::unordered_map" );
-    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map>( "absl::node_hash_map" );
-    test<absl_flat_hash_map>( "absl::flat_hash_map" );
-
-#endif
-
-    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
-    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
-    test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
-
-#endif
-
-    std::cout << "---\n\n";
-
-    for( auto const& x: times )
-    {
-        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
-    }
-}
-
-#ifdef HAVE_ABSEIL
-# include "absl/container/internal/raw_hash_set.cc"
-# include "absl/hash/internal/hash.cc"
-# include "absl/hash/internal/low_level_hash.cc"
-# include "absl/hash/internal/city.cc"
-#endif

benchmark/word_size.cpp

@@ -1,238 +0,0 @@
-// Copyright 2021, 2022 Peter Dimov.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/regex.hpp>
-#ifdef HAVE_ABSEIL
-# include "absl/container/node_hash_map.h"
-# include "absl/container/flat_hash_map.h"
-#endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <fstream>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-static std::vector<std::string> words;
-
-static void init_words()
-{
-#if SIZE_MAX > UINT32_MAX
-
-    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
-
-#else
-
-    char const* fn = "enwik8"; // ditto
-
-#endif
-
-    auto t1 = std::chrono::steady_clock::now();
-
-    std::ifstream is( fn );
-    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
-
-    boost::regex re( "[a-zA-Z]+");
-    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
-
-    words.assign( it, end );
-
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
-}
-
-template<class Map> BOOST_NOINLINE void test_word_size( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    for( auto const& word: words )
-    {
-        ++map[ word.size() ];
-    }
-
-    print_time( t1, "Word size count",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& x: map )
-    {
-        s += x.second;
-    }
-
-    print_time( t1, "Iterate and sum counts",  s, map.size() );
-
-    std::cout << std::endl;
-}
-
-// counting allocator
-
-static std::size_t s_alloc_bytes = 0;
-static std::size_t s_alloc_count = 0;
-
-template<class T> struct allocator
-{
-    using value_type = T;
-
-    allocator() = default;
-
-    template<class U> allocator( allocator<U> const & ) noexcept
-    {
-    }
-
-    template<class U> bool operator==( allocator<U> const & ) const noexcept
-    {
-        return true;
-    }
-
-    template<class U> bool operator!=( allocator<U> const& ) const noexcept
-    {
-        return false;
-    }
-
-    T* allocate( std::size_t n ) const
-    {
-        s_alloc_bytes += n * sizeof(T);
-        s_alloc_count++;
-
-        return std::allocator<T>().allocate( n );
-    }
-
-    void deallocate( T* p, std::size_t n ) const noexcept
-    {
-        s_alloc_bytes -= n * sizeof(T);
-        s_alloc_count--;
-
-        std::allocator<T>().deallocate( p, n );
-    }
-};
-
-//
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    std::size_t bytes_;
-    std::size_t count_;
-};
-
-static std::vector<record> times;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    s_alloc_bytes = 0;
-    s_alloc_count = 0;
-
-    Map<std::size_t, std::size_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_word_size( map, t1 );
-
-    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
-
-    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
-
-    test_iteration( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    times.push_back( rec );
-}
-
-// aliases using the counting allocator
-
-template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
-
-template<class K, class V> using std_unordered_map =
-    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map =
-    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map =
-    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map =
-    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-int main()
-{
-    init_words();
-
-    test<std_unordered_map>( "std::unordered_map" );
-    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map>( "absl::node_hash_map" );
-    test<absl_flat_hash_map>( "absl::flat_hash_map" );
-
-#endif
-
-    std::cout << "---\n\n";
-
-    for( auto const& x: times )
-    {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
-    }
-}
-
-#ifdef HAVE_ABSEIL
-# include "absl/container/internal/raw_hash_set.cc"
-# include "absl/hash/internal/hash.cc"
-# include "absl/hash/internal/low_level_hash.cc"
-# include "absl/hash/internal/city.cc"
-#endif