folly/experimental/test/StringKeyedBenchmark.cpp

   1 /*
   2  * Copyright 2017 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 // Copyright 2013-present Facebook. All Rights Reserved.
  17
  18 #include <folly/Benchmark.h>
  19 #include <folly/Conv.h>
  20 #include <folly/Range.h>
  21
  22 #include <map>
  23 #include <set>
  24 #include <string>
  25 #include <unordered_map>
  26 #include <unordered_set>
  27
  28 #include <folly/experimental/StringKeyedMap.h>
  29 #include <folly/experimental/StringKeyedSet.h>
  30 #include <folly/experimental/StringKeyedUnorderedMap.h>
  31 #include <folly/experimental/StringKeyedUnorderedSet.h>
  32
  33 using folly::StringKeyedMap;
  34 using folly::StringKeyedSet;
  35 using folly::StringKeyedUnorderedMap;
  36 using folly::StringKeyedUnorderedSet;
  37 using folly::StringPiece;
  38 using std::map;
  39 using folly::to;
  40 using std::set;
  41 using std::string;
  42 using std::unordered_map;
  43 using std::unordered_set;
  44 using namespace std::string_literals;
  45
  46 static map<string, int> m;
  47 static StringKeyedMap<int> skm;
  48 static set<string> s;
  49 static StringKeyedSet sks;
  50 static unordered_map<string, int> um;
  51 static StringKeyedUnorderedMap<int> skum;
  52 static unordered_set<string> us;
  53 static StringKeyedUnorderedSet skus;
  54 static const std::string lookup = "1234567890abcdefghijklmnopqrstuvwxyz"s;
  55 static const folly::StringPiece lookupPiece{
  56     "1234567890abcdefghijklmnopqrstuvwxyz"};
  57
  58 #if !defined(FOLLY_HAVE_COMPARE_EQUIVALENT) && _LIBCPP_VERSION >= 3400
  59 #define FOLLY_HAVE_COMPARE_EQUIVALENT 1
  60 #endif
  61
  62 #if !defined(FOLLY_HAVE_COMPARE_EQUIVALENT) && __GNUC__ >= 5
  63 #define FOLLY_HAVE_COMPARE_EQUIVALENT 1
  64 #endif
  65
  66 #if FOLLY_HAVE_COMPARE_EQUIVALENT
  67 static map<string, int, std::less<void>> m_equiv;
  68 static set<string, std::less<void>> s_equiv;
  69 #endif
  70
  71 static void initBenchmarks() {
  72   for (int i = 0; i < 1000; ++i) {
  73     auto iStr = to<string>(i);
  74     m[iStr] = i;
  75     s.insert(iStr);
  76   }
  77   m.insert(make_pair(lookup, 0));
  78   s.insert(lookup);
  79
  80   skm = decltype(skm){m.begin(), m.end()};
  81   um = decltype(um){m.begin(), m.end()};
  82   skum = decltype(skum){m.begin(), m.end()};
  83
  84   sks = decltype(sks){s.begin(), s.end()};
  85   us = decltype(us){s.begin(), s.end()};
  86   skus = decltype(skus){s.begin(), s.end()};
  87 #if FOLLY_HAVE_COMPARE_EQUIVALENT
  88   m_equiv = decltype(m_equiv){m.begin(), m.end()};
  89   s_equiv = decltype(s_equiv){s.begin(), s.end()};
  90 #endif
  91 }
  92
  93 BENCHMARK(std_map_benchmark_find_native) {
  94   folly::doNotOptimizeAway(m.find(lookup)->second);
  95 }
  96
  97 BENCHMARK_RELATIVE(std_map_benchmark_find_cross) {
  98   folly::doNotOptimizeAway(m.find(lookupPiece.str())->second);
  99 }
 100
 101 #if FOLLY_HAVE_COMPARE_EQUIVALENT
 102 BENCHMARK_RELATIVE(std_map_benchmark_find_equiv) {
 103   folly::doNotOptimizeAway(m_equiv.find(lookupPiece)->second);
 104 }
 105 #endif
 106
 107 BENCHMARK_RELATIVE(sk_map_benchmark_find_native) {
 108   folly::doNotOptimizeAway(skm.find(lookupPiece)->second);
 109 }
 110
 111 BENCHMARK_RELATIVE(sk_map_benchmark_find_cross) {
 112   folly::doNotOptimizeAway(skm.find(lookup)->second);
 113 }
 114
 115 BENCHMARK(std_map_benchmark_erase_emplace_native) {
 116   m.erase(lookup);
 117   m.emplace(lookup, 123);
 118 }
 119
 120 BENCHMARK_RELATIVE(std_map_benchmark_erase_emplace_cross) {
 121   m.erase(lookupPiece.str());
 122   m.emplace(lookupPiece.str(), 123);
 123 }
 124
 125 BENCHMARK_RELATIVE(sk_map_benchmark_erase_emplace_native) {
 126   skm.erase(lookupPiece);
 127   skm.emplace(lookupPiece, 123);
 128 }
 129
 130 BENCHMARK_RELATIVE(sk_map_benchmark_erase_emplace_cross) {
 131   skm.erase(lookup);
 132   skm.emplace(lookup, 123);
 133 }
 134
 135 BENCHMARK(std_unordered_map_benchmark_find_native) {
 136   folly::doNotOptimizeAway(um.find(lookup)->second);
 137 }
 138
 139 BENCHMARK_RELATIVE(std_unordered_map_benchmark_find_cross) {
 140   folly::doNotOptimizeAway(um.find(lookupPiece.str())->second);
 141 }
 142
 143 BENCHMARK_RELATIVE(sk_unordered_map_benchmark_find_native) {
 144   folly::doNotOptimizeAway(skum.find(lookupPiece)->second);
 145 }
 146
 147 BENCHMARK_RELATIVE(sk_unordered_map_benchmark_find_cross) {
 148   folly::doNotOptimizeAway(skum.find(lookup)->second);
 149 }
 150
 151 BENCHMARK(std_unordered_map_benchmark_erase_emplace_native) {
 152   um.erase(lookup);
 153   um.emplace(lookup, 123);
 154 }
 155
 156 BENCHMARK_RELATIVE(std_unordered_map_benchmark_erase_emplace_cross) {
 157   um.erase(lookupPiece.str());
 158   um.emplace(lookupPiece.str(), 123);
 159 }
 160
 161 BENCHMARK_RELATIVE(sk_unordered_map_benchmark_erase_emplace_native) {
 162   skum.erase(lookupPiece);
 163   skum.emplace(lookupPiece, 123);
 164 }
 165
 166 BENCHMARK_RELATIVE(sk_unordered_map_benchmark_erase_emplace_cross) {
 167   skum.erase(lookup);
 168   skum.emplace(lookup, 123);
 169 }
 170
 171 BENCHMARK_DRAW_LINE();
 172
 173 BENCHMARK(std_set_benchmark_find_native) {
 174   folly::doNotOptimizeAway(s.find(lookup));
 175 }
 176
 177 BENCHMARK_RELATIVE(std_set_benchmark_find_cross) {
 178   folly::doNotOptimizeAway(s.find(lookupPiece.str()));
 179 }
 180
 181 #if FOLLY_HAVE_COMPARE_EQUIVALENT
 182 BENCHMARK_RELATIVE(std_set_benchmark_find_equiv) {
 183   folly::doNotOptimizeAway(s_equiv.find(lookupPiece));
 184 }
 185 #endif
 186
 187 BENCHMARK_RELATIVE(sk_set_benchmark_find_native) {
 188   folly::doNotOptimizeAway(sks.find(lookupPiece));
 189 }
 190
 191 BENCHMARK_RELATIVE(sk_set_benchmark_find_cross) {
 192   folly::doNotOptimizeAway(sks.find(lookup));
 193 }
 194
 195 BENCHMARK(std_set_benchmark_erase_emplace_native) {
 196   s.erase(lookup);
 197   s.emplace(lookup);
 198 }
 199
 200 BENCHMARK_RELATIVE(std_set_benchmark_erase_emplace_cross) {
 201   s.erase(lookupPiece.str());
 202   s.emplace(lookupPiece.str());
 203 }
 204
 205 BENCHMARK_RELATIVE(sk_set_benchmark_erase_emplace_native) {
 206   sks.erase(lookupPiece);
 207   sks.emplace(lookupPiece);
 208 }
 209
 210 BENCHMARK_RELATIVE(sk_set_benchmark_erase_emplace_cross) {
 211   sks.erase(lookup);
 212   sks.emplace(lookup);
 213 }
 214
 215 BENCHMARK(std_unordered_set_benchmark_find_native) {
 216   folly::doNotOptimizeAway(us.find(lookup));
 217 }
 218
 219 BENCHMARK(std_unordered_set_benchmark_find_cross) {
 220   folly::doNotOptimizeAway(us.find(lookupPiece.str()));
 221 }
 222
 223 BENCHMARK_RELATIVE(sk_unordered_set_benchmark_find_native) {
 224   folly::doNotOptimizeAway(skus.find(lookupPiece));
 225 }
 226
 227 BENCHMARK_RELATIVE(sk_unordered_set_benchmark_find_cross) {
 228   folly::doNotOptimizeAway(skus.find(lookup));
 229 }
 230
 231 BENCHMARK(std_unordered_set_benchmark_erase_emplace_native) {
 232   us.erase(lookup);
 233   us.emplace(lookup);
 234 }
 235
 236 BENCHMARK_RELATIVE(std_unordered_set_benchmark_erase_emplace_cross) {
 237   us.erase(lookupPiece.str());
 238   us.emplace(lookupPiece.str());
 239 }
 240
 241 BENCHMARK_RELATIVE(sk_unordered_set_benchmark_erase_emplace_native) {
 242   skus.erase(lookupPiece);
 243   skus.emplace(lookupPiece);
 244 }
 245
 246 BENCHMARK_RELATIVE(sk_unordered_set_benchmark_erase_emplace_cross) {
 247   skus.erase(lookup);
 248   skus.emplace(lookup);
 249 }
 250
 251 int main(int argc, char** argv) {
 252   gflags::ParseCommandLineFlags(&argc, &argv, true);
 253   initBenchmarks();
 254   folly::runBenchmarks();
 255 }