Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package robin-map for openSUSE:Factory checked in at 2024-06-24 20:53:02 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/robin-map (Old) and /work/SRC/openSUSE:Factory/.robin-map.new.18349 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Package is "robin-map" Mon Jun 24 20:53:02 2024 rev:5 rq:1182635 version:1.3.0 Changes: -------- --- /work/SRC/openSUSE:Factory/robin-map/robin-map.changes 2023-06-04 00:13:05.961712217 +0200 +++ /work/SRC/openSUSE:Factory/.robin-map.new.18349/robin-map.changes 2024-06-24 20:54:13.046338069 +0200 @@ -1,0 +2,14 @@ +Fri Jun 21 17:00:23 UTC 2024 - Friedrich Haubensak <hsk17@mail.de> + +- Update to version 1.3.0: + * Add erase_fast(iterator pos) method which in contrast to + erase(iterator pos) doesn't return an iterator, avoiding the + cost of looking for the next element after erasure of the + element at iterator pos. +- Changes of version 1.2.2: + * Specify library version & versioning rules in headers + * Mark error_message in numeric_cast as unused to avoid compiler + warning in some cases + * Remove support for CMake < 3.3 + +------------------------------------------------------------------- Old: ---- robin-map-1.2.1.tar.gz New: ---- robin-map-1.3.0.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ robin-map.spec ++++++ --- /var/tmp/diff_new_pack.N9MlSc/_old 2024-06-24 20:54:13.558356803 +0200 +++ /var/tmp/diff_new_pack.N9MlSc/_new 2024-06-24 20:54:13.558356803 +0200 @@ -17,7 +17,7 @@ Name: robin-map -Version: 1.2.1 +Version: 1.3.0 Release: 0 Summary: C++ implementation of a fast hash map and hash set using robin hood hashing License: MIT ++++++ robin-map-1.2.1.tar.gz -> robin-map-1.3.0.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/.clang-format new/robin-map-1.3.0/.clang-format --- old/robin-map-1.2.1/.clang-format 1970-01-01 01:00:00.000000000 +0100 +++ new/robin-map-1.3.0/.clang-format 2024-04-19 21:21:18.000000000 +0200 @@ -0,0 +1 @@ +BasedOnStyle: Google diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/.github/workflows/ci.yml new/robin-map-1.3.0/.github/workflows/ci.yml --- old/robin-map-1.2.1/.github/workflows/ci.yml 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/.github/workflows/ci.yml 2024-04-19 21:21:18.000000000 +0200 @@ -9,49 +9,49 @@ matrix: config: - { - name: linux-x64-gcc-7, - os: ubuntu-18.04, - cxx: g++-7, + name: linux-x64-gcc, + os: ubuntu-latest, + cxx: g++, cmake-build-type: Release } - { - name: linux-x64-gcc-7-no-exceptions, - os: ubuntu-18.04, - cxx: g++-7, + name: linux-x64-gcc-no-exceptions, + os: ubuntu-latest, + cxx: g++, cxx-flags: -fno-exceptions, cmake-build-type: Release } - { - name: linux-x64-clang-9, - os: ubuntu-18.04, - cxx: clang++-9, + name: linux-x64-clang, + os: ubuntu-latest, + cxx: clang++, cmake-build-type: Release } - { name: macos-x64-gcc, - os: macos-10.15, + os: macos-latest, cxx: g++, cmake-build-type: Release } - { name: macos-x64-clang, - os: macos-10.15, + os: macos-latest, cxx: clang++, cmake-build-type: Release } - { - name: linux-x64-clang-12-sanitize, - os: ubuntu-20.04, - cxx: clang++-12, + name: linux-x64-clang-sanitize, + os: ubuntu-latest, + cxx: clang++, cxx-flags: "-fsanitize=address,undefined", cmake-build-type: Release } - { - name: linux-x64-gcc-10-coverage, - os: ubuntu-20.04, - cxx: g++-10, + name: linux-x64-gcc-coverage, + os: ubuntu-latest, + cxx: g++, cxx-flags: --coverage, - gcov-tool: gcov-10, + gcov-tool: gcov, cmake-build-type: Debug } - { @@ -133,4 +133,4 @@ sudo apt-get install -y lcov lcov -c -b ${{github.workspace}}/include -d ${{github.workspace}}/build -o ${{github.workspace}}/coverage.info --no-external --gcov-tool ${{matrix.config.gcov-tool}} bash <(curl -s https://codecov.io/bash) -f ${{github.workspace}}/coverage.info - if: ${{matrix.config.name == 'linux-x64-gcc-10-coverage'}} + if: ${{matrix.config.name == 'linux-x64-gcc-coverage'}} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/CMakeLists.txt new/robin-map-1.3.0/CMakeLists.txt --- old/robin-map-1.2.1/CMakeLists.txt 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/CMakeLists.txt 2024-04-19 21:21:18.000000000 +0200 @@ -1,6 +1,6 @@ -cmake_minimum_required(VERSION 3.1) +cmake_minimum_required(VERSION 3.3) -project(tsl-robin-map VERSION 1.2.1 LANGUAGES CXX) +project(tsl-robin-map VERSION 1.3.0 LANGUAGES CXX) include(GNUInstallDirs) @@ -33,8 +33,8 @@ set(IS_SUBPROJECT FALSE) endif() -# Installation (only compatible with CMake version >= 3.3) -if(NOT IS_SUBPROJECT AND ${CMAKE_VERSION} VERSION_GREATER "3.2") +# Installation +if(NOT IS_SUBPROJECT) include(CMakePackageConfigHelpers) ## Install include directory and potential natvis file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/README.md new/robin-map-1.3.0/README.md --- old/robin-map-1.2.1/README.md 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/README.md 2024-04-19 21:21:18.000000000 +0200 @@ -275,7 +275,6 @@ } ``` - #### Serialization The library provides an efficient way to serialize and deserialize a map or a set so that it can be saved to a file or send through the network. @@ -478,6 +477,45 @@ } ``` +#### Performance pitfalls + +Two potential performance pitfalls involving `tsl::robin_map` and +`tsl::robin_set` are noteworthy: + +1. *Bad hashes*. Hash functions that produce many collisions can lead to the + following surprising behavior: when the number of collisions exceeds a + certain threshold, the hash table will automatically expand to fix the + problem. However, in degenerate cases, this expansion might have _no effect_ + on the collision count, causing a failure mode where a linear sequence of + insertion leads to exponential storage growth. + + This case has mainly been observed when using the default power-of-two + growth strategy with the default STL `std::hash<T>` for arithmetic types + `T`, which is often an identity! See issue + [#39](https://github.com/Tessil/robin-map/issues/39) for an example. The + solution is simple: use a better hash function and/or `tsl::robin_pg_set` / + `tsl::robin_pg_map`. + +2. *Element erasure and low load factors*. `tsl::robin_map` and + `tsl::robin_set` mirror the STL map/set API, which exposes an `iterator + erase(iterator)` method that removes an element at a certain position, + returning a valid iterator that points to the next element. + + Constructing this new iterator object requires walking to the next nonempty + bucket in the table, which can be a expensive operation when the hash table + has a low *load factor* (i.e., when `capacity()` is much larger then + `size()`). + + The `erase()` method furthermore never shrinks & re-hashes the table as + this is not permitted by the specification of this function. A linear + sequence of random removals without intermediate insertions can then lead to + a degenerate case with quadratic runtime cost. + + In such cases, an iterator return value is often not even needed, so the + cost is entirely unnecessary. Both `tsl::robin_set` and `tsl::robin_map` + therefore provide an alternative erasure method `void erase_fast(iterator)` + that does not return an iterator to avoid having to find the next element. + ### License The code is licensed under the MIT license, see the [LICENSE file](LICENSE) for details. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/include/tsl/robin_growth_policy.h new/robin-map-1.3.0/include/tsl/robin_growth_policy.h --- old/robin-map-1.2.1/include/tsl/robin_growth_policy.h 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/include/tsl/robin_growth_policy.h 2024-04-19 21:21:18.000000000 +0200 @@ -35,6 +35,16 @@ #include <ratio> #include <stdexcept> +// A change of the major version indicates an API and/or ABI break (change of +// in-memory layout of the data structure) +#define TSL_RH_VERSION_MAJOR 1 +// A change of the minor version indicates the addition of a feature without +// impact on the API/ABI +#define TSL_RH_VERSION_MINOR 3 +// A change of the patch version indicates a bugfix without additional +// functionality +#define TSL_RH_VERSION_PATCH 0 + #ifdef TSL_DEBUG #define tsl_rh_assert(expr) assert(expr) #else diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/include/tsl/robin_hash.h new/robin-map-1.3.0/include/tsl/robin_hash.h --- old/robin-map-1.2.1/include/tsl/robin_hash.h 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/include/tsl/robin_hash.h 2024-04-19 21:21:18.000000000 +0200 @@ -87,6 +87,8 @@ TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message); } + TSL_RH_UNUSED(error_message); + return ret; } @@ -818,6 +820,10 @@ return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first; } + void erase_fast(iterator pos) { + erase_from_bucket(pos); + } + /** * Here to avoid `template<class K> size_type erase(const K& key)` being used * when we use an `iterator` instead of a `const_iterator`. @@ -834,8 +840,6 @@ ++pos; } - m_try_shrink_on_next_insert = true; - return pos; } @@ -914,8 +918,6 @@ auto it = find(key, hash); if (it != end()) { erase_from_bucket(it); - m_try_shrink_on_next_insert = true; - return 1; } else { return 0; @@ -1209,6 +1211,7 @@ previous_ibucket = ibucket; ibucket = next_bucket(ibucket); } + m_try_shrink_on_next_insert = true; } template <class K, class... Args> diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/include/tsl/robin_map.h new/robin-map-1.3.0/include/tsl/robin_map.h --- old/robin-map-1.2.1/include/tsl/robin_map.h 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/include/tsl/robin_map.h 2024-04-19 21:21:18.000000000 +0200 @@ -340,6 +340,14 @@ size_type erase(const key_type& key) { return m_ht.erase(key); } /** + * Erase the element at position 'pos'. In contrast to the regular erase() + * function, erase_fast() does not return an iterator. This allows it to be + * faster especially in hash tables with a low load factor, where finding the + * next nonempty bucket would be costly. + */ + void erase_fast(iterator pos) { return m_ht.erase_fast(pos); } + + /** * Use the hash value 'precalculated_hash' instead of hashing the key. The * hash value should be the same as hash_function()(key). Useful to speed-up * the lookup to the value if you already have the hash. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/include/tsl/robin_set.h new/robin-map-1.3.0/include/tsl/robin_set.h --- old/robin-map-1.2.1/include/tsl/robin_set.h 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/include/tsl/robin_set.h 2024-04-19 21:21:18.000000000 +0200 @@ -264,6 +264,14 @@ size_type erase(const key_type& key) { return m_ht.erase(key); } /** + * Erase the element at position 'pos'. In contrast to the regular erase() + * function, erase_fast() does not return an iterator. This allows it to be + * faster especially in hash sets with a low load factor, where finding the + * next nonempty bucket would be costly. + */ + void erase_fast(iterator pos) { return m_ht.erase_fast(pos); } + + /** * Use the hash value 'precalculated_hash' instead of hashing the key. The * hash value should be the same as hash_function()(key). Useful to speed-up * the lookup to the value if you already have the hash. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/tests/robin_map_tests.cpp new/robin-map-1.3.0/tests/robin_map_tests.cpp --- old/robin-map-1.2.1/tests/robin_map_tests.cpp 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/tests/robin_map_tests.cpp 2024-04-19 21:21:18.000000000 +0200 @@ -1448,4 +1448,15 @@ BOOST_CHECK_EQUAL(map.erase(4, map.hash_function()(2)), 0); } +BOOST_AUTO_TEST_CASE(test_erase_fast) { + using Map = tsl::robin_map<int, int>; + Map map; + map.emplace(4, 5); + auto it = map.find(4); + BOOST_CHECK(it != map.end()); + map.erase_fast(it); + BOOST_CHECK(map.size() == 0); +} + + BOOST_AUTO_TEST_SUITE_END() diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-1.2.1/tests/robin_set_tests.cpp new/robin-map-1.3.0/tests/robin_set_tests.cpp --- old/robin-map-1.2.1/tests/robin_set_tests.cpp 2023-01-06 00:07:42.000000000 +0100 +++ new/robin-map-1.3.0/tests/robin_set_tests.cpp 2024-04-19 21:21:18.000000000 +0200 @@ -161,4 +161,14 @@ BOOST_CHECK(set_deserialized == set); } +BOOST_AUTO_TEST_CASE(test_erase_fast) { + using Set = tsl::robin_set<int>; + Set set; + set.emplace(4); + auto it = set.find(4); + BOOST_CHECK(it != set.end()); + set.erase_fast(it); + BOOST_CHECK(set.size() == 0); +} + BOOST_AUTO_TEST_SUITE_END()