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)55 inline 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)67 inline 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)111 std::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