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 <hs...@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()
