hashtable_debug.h (3784B)
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> 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> 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> 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> 93 size_t AllocatedByteSize(const C& c) { 94 return absl::container_internal::hashtable_debug_internal:: 95 HashtableDebugAccess<C>::AllocatedByteSize(c); 96 } 97 98 } // namespace container_internal 99 ABSL_NAMESPACE_END 100 } // namespace absl 101 102 #endif // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_