folly/test/FingerprintBenchmark.cpp

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