1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // This library provides APIs to debug the probing behavior of hash tables.
16 //
17 // In general, the probing behavior is a black box for users and only the
18 // side effects can be measured in the form of performance differences.
19 // These APIs give a glimpse on the actual behavior of the probing algorithms in
20 // these hashtables given a specified hash function and a set of elements.
21 //
22 // The probe count distribution can be used to assess the quality of the hash
23 // function for that particular hash table. Note that a hash function that
24 // performs well in one hash table implementation does not necessarily performs
25 // well in a different one.
26 //
27 // This library supports std::unordered_{set,map}, dense_hash_{set,map} and
28 // absl::{flat,node,string}_hash_{set,map}.
29
30 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_
31 #define ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_
32
33 #include <cstddef>
34 #include <algorithm>
35 #include <type_traits>
36 #include <vector>
37
38 #include "absl/container/internal/hashtable_debug_hooks.h"
39
40 namespace absl {
41 ABSL_NAMESPACE_BEGIN
42 namespace container_internal {
43
44 // Returns the number of probes required to lookup `key`. Returns 0 for a
45 // search with no collisions. Higher values mean more hash collisions occurred;
46 // however, the exact meaning of this number varies according to the container
47 // type.
48 template <typename C>
GetHashtableDebugNumProbes(const C & c,const typename C::key_type & key)49 size_t GetHashtableDebugNumProbes(
50 const C& c, const typename C::key_type& key) {
51 return absl::container_internal::hashtable_debug_internal::
52 HashtableDebugAccess<C>::GetNumProbes(c, key);
53 }
54
55 // Gets a histogram of the number of probes for each elements in the container.
56 // The sum of all the values in the vector is equal to container.size().
57 template <typename C>
GetHashtableDebugNumProbesHistogram(const C & container)58 std::vector<size_t> GetHashtableDebugNumProbesHistogram(const C& container) {
59 std::vector<size_t> v;
60 for (auto it = container.begin(); it != container.end(); ++it) {
61 size_t num_probes = GetHashtableDebugNumProbes(
62 container,
63 absl::container_internal::hashtable_debug_internal::GetKey<C>(*it, 0));
64 v.resize((std::max)(v.size(), num_probes + 1));
65 v[num_probes]++;
66 }
67 return v;
68 }
69
70 struct HashtableDebugProbeSummary {
71 size_t total_elements;
72 size_t total_num_probes;
73 double mean;
74 };
75
76 // Gets a summary of the probe count distribution for the elements in the
77 // container.
78 template <typename C>
GetHashtableDebugProbeSummary(const C & container)79 HashtableDebugProbeSummary GetHashtableDebugProbeSummary(const C& container) {
80 auto probes = GetHashtableDebugNumProbesHistogram(container);
81 HashtableDebugProbeSummary summary = {};
82 for (size_t i = 0; i < probes.size(); ++i) {
83 summary.total_elements += probes[i];
84 summary.total_num_probes += probes[i] * i;
85 }
86 summary.mean = 1.0 * summary.total_num_probes / summary.total_elements;
87 return summary;
88 }
89
90 // Returns the number of bytes requested from the allocator by the container
91 // and not freed.
92 template <typename C>
AllocatedByteSize(const C & c)93 size_t AllocatedByteSize(const C& c) {
94 return absl::container_internal::hashtable_debug_internal::
95 HashtableDebugAccess<C>::AllocatedByteSize(c);
96 }
97
98 // Returns a tight lower bound for AllocatedByteSize(c) where `c` is of type `C`
99 // and `c.size()` is equal to `num_elements`.
100 template <typename C>
LowerBoundAllocatedByteSize(size_t num_elements)101 size_t LowerBoundAllocatedByteSize(size_t num_elements) {
102 return absl::container_internal::hashtable_debug_internal::
103 HashtableDebugAccess<C>::LowerBoundAllocatedByteSize(num_elements);
104 }
105
106 } // namespace container_internal
107 ABSL_NAMESPACE_END
108 } // namespace absl
109
110 #endif // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_
111