1 /* 2 * Copyright (c) Facebook, Inc. and its affiliates. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <cstddef> 20 #include <ostream> 21 #include <type_traits> 22 #include <vector> 23 24 #include <folly/container/detail/F14Policy.h> 25 #include <folly/container/detail/F14Table.h> 26 27 namespace folly { 28 namespace f14 { 29 30 struct Histo { 31 std::vector<std::size_t> const& data; 32 }; 33 34 inline std::ostream& operator<<(std::ostream& xo, Histo const& histo) { 35 xo << "["; 36 size_t sum = 0; 37 for (auto v : histo.data) { 38 sum += v; 39 } 40 size_t partial = 0; 41 for (size_t i = 0; i < histo.data.size(); ++i) { 42 if (i > 0) { 43 xo << ", "; 44 } 45 partial += histo.data[i]; 46 if (histo.data[i] > 0) { 47 xo << i << ": " << histo.data[i] << " (" 48 << (static_cast<double>(partial) * 100.0 / sum) << "%)"; 49 } 50 } 51 xo << "]"; 52 return xo; 53 } 54 expectedProbe(std::vector<std::size_t> const & probeLengths)55inline double expectedProbe(std::vector<std::size_t> const& probeLengths) { 56 std::size_t sum = 0; 57 std::size_t count = 0; 58 for (std::size_t i = 1; i < probeLengths.size(); ++i) { 59 sum += i * probeLengths[i]; 60 count += probeLengths[i]; 61 } 62 return static_cast<double>(sum) / static_cast<double>(count); 63 } 64 65 // Returns i such that probeLengths elements 0 to i (inclusive) account 66 // for at least 99% of the samples. p99Probe(std::vector<std::size_t> const & probeLengths)67inline std::size_t p99Probe(std::vector<std::size_t> const& probeLengths) { 68 std::size_t count = 0; 69 for (std::size_t i = 1; i < probeLengths.size(); ++i) { 70 count += probeLengths[i]; 71 } 72 std::size_t rv = probeLengths.size(); 73 std::size_t suffix = 0; 74 while ((suffix + probeLengths[rv - 1]) * 100 <= count) { 75 --rv; 76 } 77 return rv; 78 } 79 80 inline std::ostream& operator<<(std::ostream& xo, F14TableStats const& stats) { 81 xo << "{ " << std::endl; 82 xo << " policy: " << stats.policy << std::endl; 83 xo << " size: " << stats.size << std::endl; 84 xo << " valueSize: " << stats.valueSize << std::endl; 85 xo << " bucketCount: " << stats.bucketCount << std::endl; 86 xo << " chunkCount: " << stats.chunkCount << std::endl; 87 xo << " chunkOccupancyHisto" << Histo{stats.chunkOccupancyHisto} 88 << std::endl; 89 xo << " chunkOutboundOverflowHisto" 90 << Histo{stats.chunkOutboundOverflowHisto} << std::endl; 91 xo << " chunkHostedOverflowHisto" << Histo{stats.chunkHostedOverflowHisto} 92 << std::endl; 93 xo << " keyProbeLengthHisto" << Histo{stats.keyProbeLengthHisto} 94 << std::endl; 95 xo << " missProbeLengthHisto" << Histo{stats.missProbeLengthHisto} 96 << std::endl; 97 xo << " totalBytes: " << stats.totalBytes << std::endl; 98 xo << " valueBytes: " << (stats.size * stats.valueSize) << std::endl; 99 xo << " overheadBytes: " << stats.overheadBytes << std::endl; 100 if (stats.size > 0) { 101 xo << " overheadBytesPerKey: " 102 << (static_cast<double>(stats.overheadBytes) / 103 static_cast<double>(stats.size)) 104 << std::endl; 105 } 106 xo << "}"; 107 return xo; 108 } 109 110 template <typename Container> asVector(const Container & c)111std::vector<typename std::decay_t<Container>::value_type> asVector( 112 const Container& c) { 113 return {c.begin(), c.end()}; 114 } 115 116 } // namespace f14 117 } // namespace folly 118