Gabriel B. has submitted this change. (
https://gem5-review.googlesource.com/c/public/gem5/+/67663?usp=email )
(
11 is the latest approved patch-set.
No files were changed between the latest approved patch-set and the
submitted one.
)Change subject: base: Provide several hash implementations for common
types
......................................................................
base: Provide several hash implementations for common types
These types include std::pair, std::tuple, all iterable types and any
composition of these. Convenience hash factory and computation
functions are also provided.
These functions are in the stl_helpers namespace and must not move to
::std which could cause undefined behaviour. This is because
specialization of std templates for std or native types (or
composition of these) is undefined behaviour. This inconvenience can't
be circumvented for generic code. Users are free to bring these hash
implementations to namespace std after specialization for their own
non-std and non-native types.
Change-Id: Ifd0f0b64e5421d5d44890eb25428cc9c53484eb3
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/67663
Reviewed-by: Daniel Carvalho <oda...@yahoo.com.br>
Maintainer: Daniel Carvalho <oda...@yahoo.com.br>
Tested-by: kokoro <noreply+kok...@google.com>
---
M src/base/stl_helpers.hh
A src/base/stl_helpers/SConscript
A src/base/stl_helpers/hash_helpers.hh
A src/base/stl_helpers/hash_helpers.test.cc
4 files changed, 285 insertions(+), 0 deletions(-)
Approvals:
kokoro: Regressions pass
Daniel Carvalho: Looks good to me, approved; Looks good to me, approved
diff --git a/src/base/stl_helpers.hh b/src/base/stl_helpers.hh
index d12f266..1d19f56 100644
--- a/src/base/stl_helpers.hh
+++ b/src/base/stl_helpers.hh
@@ -31,10 +31,12 @@
#include <algorithm>
#include <iostream>
+#include <numeric>
#include <type_traits>
#include <vector>
#include "base/compiler.hh"
+#include "base/stl_helpers/hash_helpers.hh"
namespace gem5
{
diff --git a/src/base/stl_helpers/SConscript
b/src/base/stl_helpers/SConscript
new file mode 100644
index 0000000..1143dc2
--- /dev/null
+++ b/src/base/stl_helpers/SConscript
@@ -0,0 +1,28 @@
+# Copyright (c) 2023 Arteris, Inc. and its applicable licensors and
affiliates.
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
met:
+# redistributions of source code must retain the above copyright notice,
this
+# list of conditions and the following disclaimer; redistributions in
binary
+# form must reproduce the above copyright notice, this list of conditions
and
+# the following disclaimer in the documentation and/or other materials
provided
+# with the distribution; neither the name of the copyright holders nor the
+# names of its contributors may be used to endorse or promote products
derived
+# from this software without specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE
+# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
THE
+# POSSIBILITY OF SUCH DAMAGE.
+
+Import('*')
+
+GTest('hash_helpers.test', 'hash_helpers.test.cc')
diff --git a/src/base/stl_helpers/hash_helpers.hh
b/src/base/stl_helpers/hash_helpers.hh
new file mode 100644
index 0000000..f638ea9
--- /dev/null
+++ b/src/base/stl_helpers/hash_helpers.hh
@@ -0,0 +1,170 @@
+/*
+ * Copyright (c) 2023 Arteris, Inc. and its applicable licensors and
+ * affiliates.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef BASE_STL_HELPERS_HASH_HELPERS_HH
+#define BASE_STL_HELPERS_HASH_HELPERS_HH
+
+#include <functional>
+#include <numeric>
+#include <tuple>
+#include <type_traits>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+
+#include "base/type_traits.hh"
+
+namespace gem5::stl_helpers
+{
+
+namespace hash_impl
+{
+// The math in hash_combine and hash_refine functions are inspired from Jon
+// Maiga's work hosted at https://github.com/jonmaiga/mx3 under the CC0
+// license. It makes use of two components: a stream mixer for combination
and
+// a scalar mixer for refinement.
+// The stream mixer is a lighter weight function with lower entropy used to
+// combine hash values while the scalar mixer is a high entropy function
that
+// increases the overall hashing quality.
+// The tradeoff of not using hash_refine has not been thoroughtly tested
and is
+// only done based on Maiga's return on exprerience.
+static constexpr uint64_t C = 0xbea225f9eb34556d;
+template<typename... T>
+constexpr size_t hash_combine(T... hashes) {
+ // gcc reports unused variable if T is the empty pack
+ [[maybe_unused]] auto combine = [](uint64_t a, uint64_t b) {
+ b *= C;
+ b ^= b >> 39;
+ a += b * C;
+ a *= C;
+ return a;
+ };
+ // The following couple of expressions is equivalent to a hypothetical
+ // functional "acc = hashes.fold_left(0, combine)". The comma operator
+ // effectively repeats the expression in the second level parenthesis
for
+ // each argument in the parameter pack hashes, in order. Thus, final
value
+ // of acc is the recursive combination of all hashes.
+ uint64_t acc{0};
+ ((acc = combine(acc, static_cast<uint64_t>(hashes))), ...);
+ return static_cast<size_t>(acc);
+}
+
+constexpr size_t hash_refine(size_t x) {
+ x ^= x >> 32;
+ x *= C;
+ x ^= x >> 29;
+ x *= C;
+ x ^= x >> 32;
+ x *= C;
+ x ^= x >> 29;
+ return static_cast<size_t>(x);
+}
+
+// SFINAE-enabled hash functor
+template<typename T, typename = void>
+struct hash;
+
+// Reuse std::hash whenever possible
+template<typename T>
+struct hash<T, std::enable_if_t<is_std_hash_enabled_v<T>>>: std::hash<T>
+{};
+
+// Enable type deduction for hash object construction
+template<typename T>
+constexpr auto make_hash_for(const T&) {
+ return hash<T>();
+}
+
+// Compute a hash without the hassle of constructing a hash functor
+template<typename T>
+constexpr auto hash_value(const T& v) {
+ return make_hash_for(v)(v);
+}
+
+// Hash for tuple
+template<typename... T>
+struct hash<std::tuple<T...>>
+{
+ constexpr size_t operator()(const std::tuple<T...>& t) const {
+ if constexpr (sizeof...(T) == 0) {
+ return 0;
+ } else {
+ return std::apply([](const auto&... e){
+ return hash_refine(hash_combine(hash_value(e)...));
+ }, t);
+ }
+ }
+};
+
+// Hash for pairs (based on hash for 2-uple)
+template<typename T, typename U>
+struct hash<std::pair<T, U>>
+{
+ constexpr size_t operator()(const std::pair<T, U>& p) const {
+ return hash_value(std::tie(p.first, p.second));
+ }
+};
+
+// Hash for any iterable of stl_helpers::hash-enabled types.
+template<typename T>
+struct hash<T, std::enable_if_t<
+ !is_std_hash_enabled_v<T> && is_iterable_v<T>>>
+{
+ constexpr size_t operator()(const T& t) const {
+ auto b = begin(t);
+ auto e = end(t);
+ if (b == e) return 0;
+ // Equivalent to hypothetical functional style
+ // return t.map(hash_value).reduce(hash_combine)
+ auto h = std::accumulate(next(b), e, hash_value(*b),
+ [](const auto& acc, const auto& val) {
+ return hash_combine(acc, hash_value(val));
+ });
+ return hash_refine(h);
+ }
+};
+
+template<typename, typename = void>
+constexpr bool is_hash_enabled = false;
+
+template <typename T>
+constexpr bool is_hash_enabled<T,
+ std::void_t<decltype(hash<T>()(std::declval<T>()))>> = true;
+
+} // namespace hash_impl
+
+// Export useful hash_impl functions
+using hash_impl::hash;
+using hash_impl::make_hash_for;
+using hash_impl::hash_value;
+using hash_impl::is_hash_enabled;
+
+} // namespace gem5::stl_helpers
+
+#endif // BASE_STL_HELPERS_HASH_HELPERS_HH
diff --git a/src/base/stl_helpers/hash_helpers.test.cc
b/src/base/stl_helpers/hash_helpers.test.cc
new file mode 100644
index 0000000..f6f07c5
--- /dev/null
+++ b/src/base/stl_helpers/hash_helpers.test.cc
@@ -0,0 +1,85 @@
+/*
+ * Copyright (c) 2023 Arteris, Inc. and its applicable licensors and
+ * affiliates.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <gtest/gtest.h>
+
+#include <string>
+#include <tuple>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+#include "base/stl_helpers/hash_helpers.hh"
+
+using namespace gem5;
+
+TEST(HashHelpers, isHashEnabled)
+{
+ EXPECT_TRUE(stl_helpers::is_hash_enabled<int>);
+ EXPECT_TRUE(stl_helpers::is_hash_enabled<long>);
+ EXPECT_TRUE(stl_helpers::is_hash_enabled<double>);
+ EXPECT_TRUE(stl_helpers::is_hash_enabled<std::string>);
+ EXPECT_TRUE(stl_helpers::is_hash_enabled<void*>);
+ using vector_t = std::vector<int>;
+ EXPECT_TRUE(stl_helpers::is_hash_enabled<vector_t>);
+ using tuple_t = std::tuple<int, bool, int**, std::string(*)(float)>;
+ EXPECT_TRUE(stl_helpers::is_hash_enabled<tuple_t>);
+ EXPECT_TRUE((stl_helpers::is_hash_enabled<std::pair<vector_t,
tuple_t>>));
+ EXPECT_TRUE((stl_helpers::is_hash_enabled<
+ std::unordered_map<tuple_t, vector_t>>));
+}
+
+// The following tests do not test the hash value as it is considered an
+// implementation detail and there is no contract on the way that value is
+// computed. Testing for hash quality is extremelly computationnaly
intensive
+// and is not suitable for unit tests. Consider these tests to be more of a
+// "does it compile?" check as well as a small set of examples for the
user.
+TEST(HashHelpers, hashPair)
+{
+ auto p = std::make_pair(1, std::string("hello"));
+ auto hashVal = stl_helpers::hash_value(p);
+ auto hashFunc = stl_helpers::hash<std::pair<int, std::string>>{};
+ EXPECT_EQ(hashVal, hashFunc(p));
+}
+
+TEST(HashHelpers, hashTuple)
+{
+ auto t = std::make_tuple(1, "hello", 4.2, std::make_pair(true, 0.f));
+ auto hashVal = stl_helpers::hash_value(t);
+ auto hashFunc = stl_helpers::hash<decltype(t)>{};
+ EXPECT_EQ(hashVal, hashFunc(t));
+}
+
+TEST(HashHelpers, hashVector)
+{
+ auto v = std::vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9};
+ auto hashVal = stl_helpers::hash_value(v);
+ auto hashFunc = stl_helpers::hash<decltype(v)>{};
+ EXPECT_EQ(hashVal, hashFunc(v));
+}
--
To view, visit
https://gem5-review.googlesource.com/c/public/gem5/+/67663?usp=email
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings?usp=email
Gerrit-MessageType: merged
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: Ifd0f0b64e5421d5d44890eb25428cc9c53484eb3
Gerrit-Change-Number: 67663
Gerrit-PatchSet: 13
Gerrit-Owner: Gabriel B. <gabriel.bus...@arteris.com>
Gerrit-Reviewer: Bobby Bruce <bbr...@ucdavis.edu>
Gerrit-Reviewer: Daniel Carvalho <oda...@yahoo.com.br>
Gerrit-Reviewer: Gabriel B. <gabriel.bus...@arteris.com>
Gerrit-Reviewer: Jason Lowe-Power <ja...@lowepower.com>
Gerrit-Reviewer: kokoro <noreply+kok...@google.com>
Gerrit-CC: kokoro <noreply+kok...@google.com>
_______________________________________________
gem5-dev mailing list -- gem5-dev@gem5.org
To unsubscribe send an email to gem5-dev-le...@gem5.org
