container/internal/hashtable_debug.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // This library provides APIs to debug the probing behavior of hash tables.
0016 //
0017 // In general, the probing behavior is a black box for users and only the
0018 // side effects can be measured in the form of performance differences.
0019 // These APIs give a glimpse on the actual behavior of the probing algorithms in
0020 // these hashtables given a specified hash function and a set of elements.
0021 //
0022 // The probe count distribution can be used to assess the quality of the hash
0023 // function for that particular hash table. Note that a hash function that
0024 // performs well in one hash table implementation does not necessarily performs
0025 // well in a different one.
0026 //
0027 // This library supports std::unordered_{set,map}, dense_hash_{set,map} and
0028 // absl::{flat,node,string}_hash_{set,map}.
0029
0030 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_
0031 #define ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_
0032
0033 #include <cstddef>
0034 #include <algorithm>
0035 #include <type_traits>
0036 #include <vector>
0037
0038 #include "absl/container/internal/hashtable_debug_hooks.h"
0039
0040 namespace absl {
0041 ABSL_NAMESPACE_BEGIN
0042 namespace container_internal {
0043
0044 // Returns the number of probes required to lookup `key`.  Returns 0 for a
0045 // search with no collisions.  Higher values mean more hash collisions occurred;
0046 // however, the exact meaning of this number varies according to the container
0047 // type.
0048 template <typename C>
0049 size_t GetHashtableDebugNumProbes(
0050     const C& c, const typename C::key_type& key) {
0051   return absl::container_internal::hashtable_debug_internal::
0052       HashtableDebugAccess<C>::GetNumProbes(c, key);
0053 }
0054
0055 // Gets a histogram of the number of probes for each elements in the container.
0056 // The sum of all the values in the vector is equal to container.size().
0057 template <typename C>
0058 std::vector<size_t> GetHashtableDebugNumProbesHistogram(const C& container) {
0059   std::vector<size_t> v;
0060   for (auto it = container.begin(); it != container.end(); ++it) {
0061     size_t num_probes = GetHashtableDebugNumProbes(
0062         container,
0063         absl::container_internal::hashtable_debug_internal::GetKey<C>(*it, 0));
0064     v.resize((std::max)(v.size(), num_probes + 1));
0065     v[num_probes]++;
0066   }
0067   return v;
0068 }
0069
0070 struct HashtableDebugProbeSummary {
0071   size_t total_elements;
0072   size_t total_num_probes;
0073   double mean;
0074 };
0075
0076 // Gets a summary of the probe count distribution for the elements in the
0077 // container.
0078 template <typename C>
0079 HashtableDebugProbeSummary GetHashtableDebugProbeSummary(const C& container) {
0080   auto probes = GetHashtableDebugNumProbesHistogram(container);
0081   HashtableDebugProbeSummary summary = {};
0082   for (size_t i = 0; i < probes.size(); ++i) {
0083     summary.total_elements += probes[i];
0084     summary.total_num_probes += probes[i] * i;
0085   }
0086   summary.mean = 1.0 * summary.total_num_probes / summary.total_elements;
0087   return summary;
0088 }
0089
0090 // Returns the number of bytes requested from the allocator by the container
0091 // and not freed.
0092 template <typename C>
0093 size_t AllocatedByteSize(const C& c) {
0094   return absl::container_internal::hashtable_debug_internal::
0095       HashtableDebugAccess<C>::AllocatedByteSize(c);
0096 }
0097
0098 }  // namespace container_internal
0099 ABSL_NAMESPACE_END
0100 }  // namespace absl
0101
0102 #endif  // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_