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 #include <random>
18
19 #include <folly/Benchmark.h>
20 #include <folly/Fingerprint.h>
21 #include <folly/Format.h>
22 #include <folly/detail/SlowFingerprint.h>
23
24 using namespace std;
25 using namespace folly;
26 using folly::detail::SlowFingerprint;
27
28 namespace {
29 constexpr int kMaxIds = 64 << 10; // 64Ki
30 constexpr int kMaxTerms = 64 << 10;
31
32 // Globals are generally bad, but this is a benchmark, so there.
33 uint64_t ids[kMaxIds];
34
35 std::string terms[kMaxTerms];
36
initialize()37 void initialize() {
38 std::mt19937 rng;
39 for (int i = 0; i < kMaxIds; i++) {
40 ids[i] = (((uint64_t)rng()) << 32) | rng();
41 }
42 // Use randomly generated words. These numbers are out of my hat and
43 // probably wrong.
44 // word length = uniformly distributed between 1 and 10
45 // charset = 0x20 - 0x7f
46 std::uniform_int_distribution<size_t> term_len(1, 10);
47 std::uniform_int_distribution<uint16_t> term_char(0x20, 0x7f);
48 for (int i = 0; i < kMaxTerms; i++) {
49 std::string& term = terms[i];
50 int len = term_len(rng);
51 term.reserve(len);
52 for (int j = 0; j < len; j++) {
53 term.append(1, (char)term_char(rng));
54 }
55 }
56 }
57
58 template <class FP>
fingerprintIds(int num_iterations,int num_ids)59 void fingerprintIds(int num_iterations, int num_ids) {
60 for (int iter = 0; iter < num_iterations; iter++) {
61 FP fp;
62 for (int i = 0; i < num_ids; i++) {
63 fp.update64(ids[i]);
64 }
65 // GOTCHA: if we don't actually call write(), compiler optimizes
66 // away the inner loop!
67 uint64_t out;
68 fp.write(&out);
69 VLOG(1) << out;
70 }
71 }
72
73 template <class FP>
fingerprintTerms(int num_iterations,int num_terms)74 void fingerprintTerms(int num_iterations, int num_terms) {
75 for (int iter = 0; iter < num_iterations; iter++) {
76 FP fp;
77 for (int i = 0; i < num_terms; i++) {
78 fp.update(terms[i]);
79 }
80 // GOTCHA: if we don't actually call write(), compiler optimizes
81 // away the inner loop!
82 uint64_t out;
83 fp.write(&out);
84 VLOG(1) << out;
85 }
86 }
87
fastFingerprintIds64(int num_iterations,int num_ids)88 void fastFingerprintIds64(int num_iterations, int num_ids) {
89 fingerprintIds<Fingerprint<64>>(num_iterations, num_ids);
90 }
91
slowFingerprintIds64(int num_iterations,int num_ids)92 void slowFingerprintIds64(int num_iterations, int num_ids) {
93 fingerprintIds<SlowFingerprint<64>>(num_iterations, num_ids);
94 }
95
fastFingerprintIds96(int num_iterations,int num_ids)96 void fastFingerprintIds96(int num_iterations, int num_ids) {
97 fingerprintIds<Fingerprint<96>>(num_iterations, num_ids);
98 }
99
fastFingerprintIds128(int num_iterations,int num_ids)100 void fastFingerprintIds128(int num_iterations, int num_ids) {
101 fingerprintIds<Fingerprint<128>>(num_iterations, num_ids);
102 }
103
fastFingerprintTerms64(int num_iterations,int num_ids)104 void fastFingerprintTerms64(int num_iterations, int num_ids) {
105 fingerprintTerms<Fingerprint<64>>(num_iterations, num_ids);
106 }
107
slowFingerprintTerms64(int num_iterations,int num_ids)108 void slowFingerprintTerms64(int num_iterations, int num_ids) {
109 fingerprintTerms<SlowFingerprint<64>>(num_iterations, num_ids);
110 }
111
fastFingerprintTerms96(int num_iterations,int num_ids)112 void fastFingerprintTerms96(int num_iterations, int num_ids) {
113 fingerprintTerms<Fingerprint<96>>(num_iterations, num_ids);
114 }
115
fastFingerprintTerms128(int num_iterations,int num_ids)116 void fastFingerprintTerms128(int num_iterations, int num_ids) {
117 fingerprintTerms<Fingerprint<128>>(num_iterations, num_ids);
118 }
119
120 } // namespace
121
122 // Only benchmark one size of slowFingerprint; it's significantly slower
123 // than fastFingeprint (as you can see for 64 bits) and it just slows down
124 // the benchmark without providing any useful data.
125
main(int argc,char ** argv)126 int main(int argc, char** argv) {
127 gflags::ParseCommandLineFlags(&argc, &argv, true);
128 #define BM(name, min, max) \
129 for (size_t i = min; i <= max; i *= 2) { \
130 addBenchmark( \
131 __FILE__, sformat("{}_{}", #name, i).c_str(), [=](int iters) { \
132 name(iters, i); \
133 return iters; \
134 }); \
135 }
136 BM(fastFingerprintIds64, 1, kMaxIds)
137 BM(slowFingerprintIds64, 1, kMaxIds)
138 BM(fastFingerprintIds96, 1, kMaxIds)
139 BM(fastFingerprintIds128, 1, kMaxIds)
140 BM(fastFingerprintTerms64, 1, kMaxTerms)
141 BM(slowFingerprintTerms64, 1, kMaxTerms)
142 BM(fastFingerprintTerms96, 1, kMaxTerms)
143 BM(fastFingerprintTerms128, 1, kMaxTerms)
144 #undef BM
145
146 initialize();
147 runBenchmarks();
148 return 0;
149 }
150