hashtable_debug.h
Go to the documentation of this file.
00001 // Copyright 2018 The Abseil Authors.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //      https://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 //
00015 // This library provides APIs to debug the probing behavior of hash tables.
00016 //
00017 // In general, the probing behavior is a black box for users and only the
00018 // side effects can be measured in the form of performance differences.
00019 // These APIs give a glimpse on the actual behavior of the probing algorithms in
00020 // these hashtables given a specified hash function and a set of elements.
00021 //
00022 // The probe count distribution can be used to assess the quality of the hash
00023 // function for that particular hash table. Note that a hash function that
00024 // performs well in one hash table implementation does not necessarily performs
00025 // well in a different one.
00026 //
00027 // This library supports std::unordered_{set,map}, dense_hash_{set,map} and
00028 // absl::{flat,node,string}_hash_{set,map}.
00029 
00030 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_
00031 #define ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_
00032 
00033 #include <cstddef>
00034 #include <algorithm>
00035 #include <type_traits>
00036 #include <vector>
00037 
00038 #include "absl/container/internal/hashtable_debug_hooks.h"
00039 
00040 namespace absl {
00041 namespace container_internal {
00042 
00043 // Returns the number of probes required to lookup `key`.  Returns 0 for a
00044 // search with no collisions.  Higher values mean more hash collisions occurred;
00045 // however, the exact meaning of this number varies according to the container
00046 // type.
00047 template <typename C>
00048 size_t GetHashtableDebugNumProbes(
00049     const C& c, const typename C::key_type& key) {
00050   return absl::container_internal::hashtable_debug_internal::
00051       HashtableDebugAccess<C>::GetNumProbes(c, key);
00052 }
00053 
00054 // Gets a histogram of the number of probes for each elements in the container.
00055 // The sum of all the values in the vector is equal to container.size().
00056 template <typename C>
00057 std::vector<size_t> GetHashtableDebugNumProbesHistogram(const C& container) {
00058   std::vector<size_t> v;
00059   for (auto it = container.begin(); it != container.end(); ++it) {
00060     size_t num_probes = GetHashtableDebugNumProbes(
00061         container,
00062         absl::container_internal::hashtable_debug_internal::GetKey<C>(*it, 0));
00063     v.resize((std::max)(v.size(), num_probes + 1));
00064     v[num_probes]++;
00065   }
00066   return v;
00067 }
00068 
00069 struct HashtableDebugProbeSummary {
00070   size_t total_elements;
00071   size_t total_num_probes;
00072   double mean;
00073 };
00074 
00075 // Gets a summary of the probe count distribution for the elements in the
00076 // container.
00077 template <typename C>
00078 HashtableDebugProbeSummary GetHashtableDebugProbeSummary(const C& container) {
00079   auto probes = GetHashtableDebugNumProbesHistogram(container);
00080   HashtableDebugProbeSummary summary = {};
00081   for (size_t i = 0; i < probes.size(); ++i) {
00082     summary.total_elements += probes[i];
00083     summary.total_num_probes += probes[i] * i;
00084   }
00085   summary.mean = 1.0 * summary.total_num_probes / summary.total_elements;
00086   return summary;
00087 }
00088 
00089 // Returns the number of bytes requested from the allocator by the container
00090 // and not freed.
00091 template <typename C>
00092 size_t AllocatedByteSize(const C& c) {
00093   return absl::container_internal::hashtable_debug_internal::
00094       HashtableDebugAccess<C>::AllocatedByteSize(c);
00095 }
00096 
00097 // Returns a tight lower bound for AllocatedByteSize(c) where `c` is of type `C`
00098 // and `c.size()` is equal to `num_elements`.
00099 template <typename C>
00100 size_t LowerBoundAllocatedByteSize(size_t num_elements) {
00101   return absl::container_internal::hashtable_debug_internal::
00102       HashtableDebugAccess<C>::LowerBoundAllocatedByteSize(num_elements);
00103 }
00104 
00105 }  // namespace container_internal
00106 }  // namespace absl
00107 
00108 #endif  // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_H_


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:14