updated boost::unordered_[multi]set and boost::unordered_(flat|node)_map benchmarks

README.md

@@ -1,49 +1,73 @@
 # Boost.Unordered
 
-Part of collection of the [Boost C++ Libraries](http://github.com/boostorg).
+[![Branch](https://img.shields.io/badge/branch-master-brightgreen.svg)](https://github.com/boostorg/unordered/tree/master) [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=master)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=master&svg=true)](https://ci.appveyor.com/project/cppalliance/unordered/branch/master)  [![codecov](https://codecov.io/gh/boostorg/unordered/branch/master/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/master)  [![Deps](https://img.shields.io/badge/deps-master-brightgreen.svg)](https://pdimov.github.io/boostdep-report/master/unordered.html)  [![Documentation](https://img.shields.io/badge/docs-master-brightgreen.svg)](https://www.boost.org/doc/libs/master/libs/unordered/doc/html/unordered.html)  [![Enter the Matrix](https://img.shields.io/badge/matrix-master-brightgreen.svg)](http://www.boost.org/development/tests/master/developer/unordered.html)<br/>
+[![Branch](https://img.shields.io/badge/branch-develop-brightgreen.svg)](https://github.com/boostorg/unordered/tree/develop) [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=develop)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=develop&svg=true)](https://ci.appveyor.com/project/cppalliance/unordered/branch/develop) [![codecov](https://codecov.io/gh/boostorg/unordered/branch/develop/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/develop) [![Deps](https://img.shields.io/badge/deps-develop-brightgreen.svg)](https://pdimov.github.io/boostdep-report/develop/unordered.html) [![Documentation](https://img.shields.io/badge/docs-develop-brightgreen.svg)](https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html) [![Enter the Matrix](https://img.shields.io/badge/matrix-develop-brightgreen.svg)](http://www.boost.org/development/tests/develop/developer/unordered.html)<br/>
+[![BSL 1.0](https://img.shields.io/badge/license-BSL_1.0-blue.svg)](https://www.boost.org/users/license.html) <img alt="C++11 required" src="https://img.shields.io/badge/standard-C%2b%2b11-blue.svg"> <img alt="Header-only library" src="https://img.shields.io/badge/build-header--only-blue.svg">
 
-For accessing data based on key lookup, the C++ standard library offers `std::set`, `std::map`, `std::multiset` and `std::multimap`.
-These are generally implemented using balanced binary trees so that lookup time has logarithmic complexity.
-That is generally okay, but in many cases a hash table can perform better, as accessing data has constant complexity, on average.
-The worst case complexity is linear, but that occurs rarely and with some care, can be avoided.
+Boost.Unordered offers a catalog of hash containers with different standards compliance levels, performances and intented usage scenarios:
 
-Also, the existing containers require a 'less than' comparison object to order their elements.
-For some data types this is impossible to implement or isn’t practical.
-In contrast, a hash table only needs an equality function and a hash function for the key.
+**`boost::unordered_set` `boost::unordered_map` `boost::unordered_multiset` `boost::unordered_multimap`**
 
-With this in mind, unordered associative containers were added to the C++ standard.
-This is an implementation of the containers described in C++11, with some deviations from the standard in order to work with non-C++11 compilers and libraries.
+<ul>Fully conformant implementations of <code>std::unordered_[multi](set|map)</code>,
+but faster and up to the latest revisions of the standard even if you're working in an older version of C++ (heterogeneous lookup,
+<code>try_emplace</code>, <code>contains</code>, etc.)</ul>
 
+**`boost::unordered_flat_set` `boost::unordered_flat_map`**
 
-### License
+<ul>The fastest of the lot. Based on open addressing, these containers slightly
+deviate from the standard in exchange for top performance.</ul>
 
-Distributed under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).
+**`boost::unordered_node_set` `boost::unordered_node_map`**
 
-### Properties
+<ul>Variations of <code>boost::unordered_flat_(set|map)</code> providing pointer stability.</ul>
 
-* C++03
-* Header-Only
+**`boost::concurrent_flat_set` `boost::concurrent_flat_map`**
 
-### Build Status
+<ul>High performance for multithreaded scenarios. Introducing a new non-standard, iterator-free API.</ul>
 
-Branch          | GH Actions | Appveyor | codecov.io | Deps | Docs | Tests |
-:-------------: | ---------- | -------- | ---------- | ---- | ---- | ----- |
-[`master`](https://github.com/boostorg/unordered/tree/master)   | [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=master)](https://github.com/boostorg/unordered/actions/workflows/ci.yml)  | [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=master&svg=true)](https://ci.appveyor.com/project/danieljames/unordered-qtwe6/branch/master)   | [![codecov](https://codecov.io/gh/boostorg/unordered/branch/master/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/master)   | [![Deps](https://img.shields.io/badge/deps-master-brightgreen.svg)](https://pdimov.github.io/boostdep-report/master/unordered.html)   | [![Documentation](https://img.shields.io/badge/docs-master-brightgreen.svg)](https://www.boost.org/doc/libs/master/libs/unordered/doc/html/unordered.html)   | [![Enter the Matrix](https://img.shields.io/badge/matrix-master-brightgreen.svg)](http://www.boost.org/development/tests/master/developer/unordered.html)
-[`develop`](https://github.com/boostorg/unordered/tree/develop) | [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=develop)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) | [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=develop&svg=true)](https://ci.appveyor.com/project/danieljames/unordered-qtwe6/branch/develop) | [![codecov](https://codecov.io/gh/boostorg/unordered/branch/develop/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/develop) | [![Deps](https://img.shields.io/badge/deps-develop-brightgreen.svg)](https://pdimov.github.io/boostdep-report/develop/unordered.html) | [![Documentation](https://img.shields.io/badge/docs-develop-brightgreen.svg)](https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html) | [![Enter the Matrix](https://img.shields.io/badge/matrix-develop-brightgreen.svg)](http://www.boost.org/development/tests/develop/developer/unordered.html)
+## Learn about Boost.Unordered
 
-### Directories
+* [Online documentation](https://boost.org/libs/unordered)
+* [Some benchmarks](https://github.com/boostorg/boost_unordered_benchmarks)
+* Technical articles on Boost.Unordered internal design:
+  * [Advancing the state of the art for `std::unordered_map` implementations](https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html)
+  * [Inside `boost::unordered_flat_map`](https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html)
+  * [Inside `boost::concurrent_flat_map`](https://bannalia.blogspot.com/2023/07/inside-boostconcurrentflatmap.html)
+  * [Bulk visitation in `boost::concurrent_flat_map`](https://bannalia.blogspot.com/2023/10/bulk-visitation-in-boostconcurrentflatm.html)
 
-| Name        | Purpose                        |
-| ----------- | ------------------------------ |
-| `doc`       | documentation                  |
-| `example`   | examples                       |
-| `include`   | headers                        |
-| `test`      | unit tests                     |
+## Get the library
 
-### More information
+Boost.Unordered can be installed in a number of ways:
 
-* [Ask questions](http://stackoverflow.com/questions/ask?tags=c%2B%2B,boost,boost-unordered)
-* [Report bugs](https://github.com/boostorg/unordered/issues): Be sure to mention Boost version, platform and compiler you're using. A small compilable code sample to reproduce the problem is always good as well.
-* Submit your patches as pull requests against **develop** branch. Note that by submitting patches you agree to license your modifications under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).
-* Discussions about the library are held on the [Boost developers mailing list](http://www.boost.org/community/groups.html#main). Be sure to read the [discussion policy](http://www.boost.org/community/policy.html) before posting and add the `[unordered]` tag at the beginning of the subject line.
+* [Download Boost](https://www.boost.org/users/download/) and you're ready to go (this is a header-only library requiring no building).
+* Using Conan 2: In case you don't have it yet, add an entry for Boost in your `conanfile.txt` (the example requires at least Boost 1.83):
+```
+[requires]
+boost/[>=1.83.0]
+```
+<ul>If you're not using any compiled Boost library, the following will skip building altogether:</ul>
 
+```
+[options]
+boost:header_only=True
+```
+* Using vcpkg: Execute the command
+```
+vcpkg install boost-unordered
+```
+* Using CMake: [Boost CMake support infrastructure](https://github.com/boostorg/cmake)
+allows you to use CMake directly to download, build and consume all of Boost or
+some specific libraries.
+
+## Support
+
+* Join the **#boost-unordered** discussion group at [cpplang.slack.com](https://cpplang.slack.com/)
+([ask for an invite](https://cppalliance.org/slack/) if you’re not a member of this workspace yet)
+* Ask in the [Boost Users mailing list](https://lists.boost.org/mailman/listinfo.cgi/boost-users)
+(add the `[unordered]` tag at the beginning of the subject line)
+* [File an issue](https://github.com/boostorg/unordered/issues)
+
+## Contribute
+
+* [Pull requests](https://github.com/boostorg/unordered/pulls) against **develop** branch are most welcome.
+Note that by submitting patches you agree to license your modifications under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).

doc/unordered/benchmarks.adoc

@@ -10,7 +10,7 @@ All benchmarks were created using `unordered_set<unsigned int>` (non-duplicate)
 
 The insertion benchmarks insert `n` random values, where `n` is between 10,000 and 3 million. For the duplicated benchmarks, the same random values are repeated an average of 5 times.
 
-The erasure benchmarks erase all `n` elements randomly until the container is empty.
+The erasure benchmarks erase all `n` elements randomly until the container is empty. Erasure by key uses `erase(const key_type&)` to remove entire groups of equivalent elements in each operation.
 
 The successful lookup benchmarks are done by looking up all `n` values, in their original insertion order.
 
@@ -30,7 +30,7 @@ The unsuccessful lookup benchmarks use `n` randomly generated integers but using
 
 h|non-duplicate elements 
 h|duplicate elements 
-h|duplicate elements +
+h|duplicate elements, +
 max load factor 5
 |===
 
@@ -64,8 +64,18 @@ prior `reserve`
 
 h|non-duplicate elements 
 h|duplicate elements 
-h|duplicate elements +
+h|duplicate elements, +
 max load factor 5
+
+|
+|image::benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===
 
 ==== Successful Lookup
@@ -154,6 +164,15 @@ h|duplicate elements
 h|duplicate elements, +
 max load factor 5
 
+|
+|image::benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===
 
 ==== Successful lookup
@@ -242,6 +261,15 @@ h|duplicate elements
 h|duplicate elements, +
 max load factor 5
 
+|
+|image::benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===
 
 ==== Successful lookup

doc/unordered/unordered_node_map.adoc

@@ -1216,6 +1216,12 @@ template<class H2, class P2>
 
 Transfers all the element nodes from `source` whose key is not already present in `*this`.
 
+[horizontal]
+Requires:;; `this\->get_allocator() == source.get_allocator()`.
+Notes:;; Invalidates iterators to the elements transferred.
+If the resulting size of `*this` is greater than its original maximum load,
+invalidates all iterators associated to `*this`.
+
 ---
 
 === Observers

doc/unordered/unordered_node_set.adoc

@@ -1030,6 +1030,12 @@ template<class H2, class P2>
 
 Transfers all the element nodes from `source` whose key is not already present in `*this`.
 
+[horizontal]
+Requires:;; `this\->get_allocator() == source.get_allocator()`.
+Notes:;; Invalidates iterators to the elements transferred.
+If the resulting size of `*this` is greater than its original maximum load,
+invalidates all iterators associated to `*this`.
+
 ---
 
 === Observers

include/boost/unordered/concurrent_flat_map.hpp

@@ -855,8 +855,6 @@ namespace boost {
 #endif
 
   } // namespace unordered
-
-  using unordered::concurrent_flat_map;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP

include/boost/unordered/concurrent_flat_map_fwd.hpp

@@ -46,9 +46,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::concurrent_flat_map;
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP

include/boost/unordered/concurrent_flat_set.hpp

@@ -711,8 +711,6 @@ namespace boost {
 #endif
 
   } // namespace unordered
-
-  using unordered::concurrent_flat_set;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_SET_HPP

include/boost/unordered/concurrent_flat_set_fwd.hpp

@@ -47,9 +47,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::concurrent_flat_set;
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_SET_FWD_HPP

include/boost/unordered/detail/foa/concurrent_table.hpp

@@ -1216,8 +1216,8 @@ private:
       auto mask=masks[i]=(this->arrays.groups()+pos)->match(hash);
       if(mask){
         BOOST_UNORDERED_PREFETCH(this->arrays.group_accesses()+pos);
-        //BOOST_UNORDERED_PREFETCH_ELEMENTS(this->arrays.elements()+pos*N,N);
-        BOOST_UNORDERED_PREFETCH(this->arrays.elements()+pos*N+unchecked_countr_zero(mask));
+        BOOST_UNORDERED_PREFETCH(
+          this->arrays.elements()+pos*N+unchecked_countr_zero(mask));
       }
     }
 

include/boost/unordered/unordered_flat_map_fwd.hpp

@@ -39,10 +39,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::unordered_flat_map;
-
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif

include/boost/unordered/unordered_flat_set_fwd.hpp

@@ -39,10 +39,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::unordered_flat_set;
-
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif

include/boost/unordered/unordered_map_fwd.hpp

@@ -60,11 +60,8 @@ namespace boost {
     template <class Iter, class NodeType> struct insert_return_type_map;
   } // namespace unordered
 
-  using boost::unordered::swap;
   using boost::unordered::unordered_map;
   using boost::unordered::unordered_multimap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif

include/boost/unordered/unordered_node_map.hpp

@@ -529,6 +529,7 @@ namespace boost {
         unordered_node_map<key_type, mapped_type, H2, P2, allocator_type>&
           source)
       {
+        BOOST_ASSERT(get_allocator() == source.get_allocator());
         table_.merge(source.table_);
       }
 
@@ -537,6 +538,7 @@ namespace boost {
         unordered_node_map<key_type, mapped_type, H2, P2, allocator_type>&&
           source)
       {
+        BOOST_ASSERT(get_allocator() == source.get_allocator());
         table_.merge(std::move(source.table_));
       }
 

include/boost/unordered/unordered_node_map_fwd.hpp

@@ -39,10 +39,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::unordered_node_map;
-
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif

include/boost/unordered/unordered_node_set.hpp

@@ -415,12 +415,14 @@ namespace boost {
       template <class H2, class P2>
       void merge(unordered_node_set<key_type, H2, P2, allocator_type>& source)
       {
+        BOOST_ASSERT(get_allocator() == source.get_allocator());
         table_.merge(source.table_);
       }
 
       template <class H2, class P2>
       void merge(unordered_node_set<key_type, H2, P2, allocator_type>&& source)
       {
+        BOOST_ASSERT(get_allocator() == source.get_allocator());
         table_.merge(std::move(source.table_));
       }
 

include/boost/unordered/unordered_node_set_fwd.hpp

@@ -39,10 +39,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::unordered_node_set;
-
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif

include/boost/unordered/unordered_set_fwd.hpp

@@ -58,11 +58,8 @@ namespace boost {
     template <class Iter, class NodeType> struct insert_return_type_set;
   } // namespace unordered
 
-  using boost::unordered::swap;
   using boost::unordered::unordered_multiset;
   using boost::unordered::unordered_set;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif

test/unordered/compile_tests.hpp

@@ -1,6 +1,6 @@
 
 // Copyright 2005-2009 Daniel James.
-// Copyright 2022 Christian Mazakas.
+// Copyright 2022-2023 Christian Mazakas.
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 
@@ -496,8 +496,6 @@ template <class X> void equality_test(X& r)
 
   test::check_return_type<bool>::equals(a == b);
   test::check_return_type<bool>::equals(a != b);
-  test::check_return_type<bool>::equals(boost::operator==(a, b));
-  test::check_return_type<bool>::equals(boost::operator!=(a, b));
 }
 
 template <class X, class T> void unordered_unique_test(X& r, T const& t)