Austin Schuh | 36244a1 | 2019-09-21 17:52:38 -0700 | [diff] [blame^] | 1 | // Copyright 2018 The Abseil Authors. |
| 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | // you may not use this file except in compliance with the License. |
| 5 | // You may obtain a copy of the License at |
| 6 | // |
| 7 | // https://www.apache.org/licenses/LICENSE-2.0 |
| 8 | // |
| 9 | // Unless required by applicable law or agreed to in writing, software |
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | // See the License for the specific language governing permissions and |
| 13 | // limitations under the License. |
| 14 | |
| 15 | #include "absl/strings/string_view.h" |
| 16 | |
| 17 | #include <algorithm> |
| 18 | #include <cstdint> |
| 19 | #include <map> |
| 20 | #include <random> |
| 21 | #include <string> |
| 22 | #include <unordered_set> |
| 23 | #include <vector> |
| 24 | |
| 25 | #include "benchmark/benchmark.h" |
| 26 | #include "absl/base/attributes.h" |
| 27 | #include "absl/base/internal/raw_logging.h" |
| 28 | #include "absl/base/macros.h" |
| 29 | #include "absl/strings/str_cat.h" |
| 30 | |
| 31 | namespace { |
| 32 | |
| 33 | // Provide a forcibly out-of-line wrapper for operator== that can be used in |
| 34 | // benchmarks to measure the impact of inlining. |
| 35 | ABSL_ATTRIBUTE_NOINLINE |
| 36 | bool NonInlinedEq(absl::string_view a, absl::string_view b) { return a == b; } |
| 37 | |
| 38 | // We use functions that cannot be inlined to perform the comparison loops so |
| 39 | // that inlining of the operator== can't optimize away *everything*. |
| 40 | ABSL_ATTRIBUTE_NOINLINE |
| 41 | void DoEqualityComparisons(benchmark::State& state, absl::string_view a, |
| 42 | absl::string_view b) { |
| 43 | for (auto _ : state) { |
| 44 | benchmark::DoNotOptimize(a == b); |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | void BM_EqualIdentical(benchmark::State& state) { |
| 49 | std::string x(state.range(0), 'a'); |
| 50 | DoEqualityComparisons(state, x, x); |
| 51 | } |
| 52 | BENCHMARK(BM_EqualIdentical)->DenseRange(0, 3)->Range(4, 1 << 10); |
| 53 | |
| 54 | void BM_EqualSame(benchmark::State& state) { |
| 55 | std::string x(state.range(0), 'a'); |
| 56 | std::string y = x; |
| 57 | DoEqualityComparisons(state, x, y); |
| 58 | } |
| 59 | BENCHMARK(BM_EqualSame) |
| 60 | ->DenseRange(0, 10) |
| 61 | ->Arg(20) |
| 62 | ->Arg(40) |
| 63 | ->Arg(70) |
| 64 | ->Arg(110) |
| 65 | ->Range(160, 4096); |
| 66 | |
| 67 | void BM_EqualDifferent(benchmark::State& state) { |
| 68 | const int len = state.range(0); |
| 69 | std::string x(len, 'a'); |
| 70 | std::string y = x; |
| 71 | if (len > 0) { |
| 72 | y[len - 1] = 'b'; |
| 73 | } |
| 74 | DoEqualityComparisons(state, x, y); |
| 75 | } |
| 76 | BENCHMARK(BM_EqualDifferent)->DenseRange(0, 3)->Range(4, 1 << 10); |
| 77 | |
| 78 | // This benchmark is intended to check that important simplifications can be |
| 79 | // made with absl::string_view comparisons against constant strings. The idea is |
| 80 | // that if constant strings cause redundant components of the comparison, the |
| 81 | // compiler should detect and eliminate them. Here we use 8 different strings, |
| 82 | // each with the same size. Provided our comparison makes the implementation |
| 83 | // inline-able by the compiler, it should fold all of these away into a single |
| 84 | // size check once per loop iteration. |
| 85 | ABSL_ATTRIBUTE_NOINLINE |
| 86 | void DoConstantSizeInlinedEqualityComparisons(benchmark::State& state, |
| 87 | absl::string_view a) { |
| 88 | for (auto _ : state) { |
| 89 | benchmark::DoNotOptimize(a == "aaa"); |
| 90 | benchmark::DoNotOptimize(a == "bbb"); |
| 91 | benchmark::DoNotOptimize(a == "ccc"); |
| 92 | benchmark::DoNotOptimize(a == "ddd"); |
| 93 | benchmark::DoNotOptimize(a == "eee"); |
| 94 | benchmark::DoNotOptimize(a == "fff"); |
| 95 | benchmark::DoNotOptimize(a == "ggg"); |
| 96 | benchmark::DoNotOptimize(a == "hhh"); |
| 97 | } |
| 98 | } |
| 99 | void BM_EqualConstantSizeInlined(benchmark::State& state) { |
| 100 | std::string x(state.range(0), 'a'); |
| 101 | DoConstantSizeInlinedEqualityComparisons(state, x); |
| 102 | } |
| 103 | // We only need to check for size of 3, and <> 3 as this benchmark only has to |
| 104 | // do with size differences. |
| 105 | BENCHMARK(BM_EqualConstantSizeInlined)->DenseRange(2, 4); |
| 106 | |
| 107 | // This benchmark exists purely to give context to the above timings: this is |
| 108 | // what they would look like if the compiler is completely unable to simplify |
| 109 | // between two comparisons when they are comparing against constant strings. |
| 110 | ABSL_ATTRIBUTE_NOINLINE |
| 111 | void DoConstantSizeNonInlinedEqualityComparisons(benchmark::State& state, |
| 112 | absl::string_view a) { |
| 113 | for (auto _ : state) { |
| 114 | // Force these out-of-line to compare with the above function. |
| 115 | benchmark::DoNotOptimize(NonInlinedEq(a, "aaa")); |
| 116 | benchmark::DoNotOptimize(NonInlinedEq(a, "bbb")); |
| 117 | benchmark::DoNotOptimize(NonInlinedEq(a, "ccc")); |
| 118 | benchmark::DoNotOptimize(NonInlinedEq(a, "ddd")); |
| 119 | benchmark::DoNotOptimize(NonInlinedEq(a, "eee")); |
| 120 | benchmark::DoNotOptimize(NonInlinedEq(a, "fff")); |
| 121 | benchmark::DoNotOptimize(NonInlinedEq(a, "ggg")); |
| 122 | benchmark::DoNotOptimize(NonInlinedEq(a, "hhh")); |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | void BM_EqualConstantSizeNonInlined(benchmark::State& state) { |
| 127 | std::string x(state.range(0), 'a'); |
| 128 | DoConstantSizeNonInlinedEqualityComparisons(state, x); |
| 129 | } |
| 130 | // We only need to check for size of 3, and <> 3 as this benchmark only has to |
| 131 | // do with size differences. |
| 132 | BENCHMARK(BM_EqualConstantSizeNonInlined)->DenseRange(2, 4); |
| 133 | |
| 134 | void BM_CompareSame(benchmark::State& state) { |
| 135 | const int len = state.range(0); |
| 136 | std::string x; |
| 137 | for (int i = 0; i < len; i++) { |
| 138 | x += 'a'; |
| 139 | } |
| 140 | std::string y = x; |
| 141 | absl::string_view a = x; |
| 142 | absl::string_view b = y; |
| 143 | |
| 144 | for (auto _ : state) { |
| 145 | benchmark::DoNotOptimize(a.compare(b)); |
| 146 | } |
| 147 | } |
| 148 | BENCHMARK(BM_CompareSame)->DenseRange(0, 3)->Range(4, 1 << 10); |
| 149 | |
| 150 | void BM_find_string_view_len_one(benchmark::State& state) { |
| 151 | std::string haystack(state.range(0), '0'); |
| 152 | absl::string_view s(haystack); |
| 153 | for (auto _ : state) { |
| 154 | benchmark::DoNotOptimize(s.find("x")); // not present; length 1 |
| 155 | } |
| 156 | } |
| 157 | BENCHMARK(BM_find_string_view_len_one)->Range(1, 1 << 20); |
| 158 | |
| 159 | void BM_find_string_view_len_two(benchmark::State& state) { |
| 160 | std::string haystack(state.range(0), '0'); |
| 161 | absl::string_view s(haystack); |
| 162 | for (auto _ : state) { |
| 163 | benchmark::DoNotOptimize(s.find("xx")); // not present; length 2 |
| 164 | } |
| 165 | } |
| 166 | BENCHMARK(BM_find_string_view_len_two)->Range(1, 1 << 20); |
| 167 | |
| 168 | void BM_find_one_char(benchmark::State& state) { |
| 169 | std::string haystack(state.range(0), '0'); |
| 170 | absl::string_view s(haystack); |
| 171 | for (auto _ : state) { |
| 172 | benchmark::DoNotOptimize(s.find('x')); // not present |
| 173 | } |
| 174 | } |
| 175 | BENCHMARK(BM_find_one_char)->Range(1, 1 << 20); |
| 176 | |
| 177 | void BM_rfind_one_char(benchmark::State& state) { |
| 178 | std::string haystack(state.range(0), '0'); |
| 179 | absl::string_view s(haystack); |
| 180 | for (auto _ : state) { |
| 181 | benchmark::DoNotOptimize(s.rfind('x')); // not present |
| 182 | } |
| 183 | } |
| 184 | BENCHMARK(BM_rfind_one_char)->Range(1, 1 << 20); |
| 185 | |
| 186 | void BM_worst_case_find_first_of(benchmark::State& state, int haystack_len) { |
| 187 | const int needle_len = state.range(0); |
| 188 | std::string needle; |
| 189 | for (int i = 0; i < needle_len; ++i) { |
| 190 | needle += 'a' + i; |
| 191 | } |
| 192 | std::string haystack(haystack_len, '0'); // 1000 zeros. |
| 193 | |
| 194 | absl::string_view s(haystack); |
| 195 | for (auto _ : state) { |
| 196 | benchmark::DoNotOptimize(s.find_first_of(needle)); |
| 197 | } |
| 198 | } |
| 199 | |
| 200 | void BM_find_first_of_short(benchmark::State& state) { |
| 201 | BM_worst_case_find_first_of(state, 10); |
| 202 | } |
| 203 | |
| 204 | void BM_find_first_of_medium(benchmark::State& state) { |
| 205 | BM_worst_case_find_first_of(state, 100); |
| 206 | } |
| 207 | |
| 208 | void BM_find_first_of_long(benchmark::State& state) { |
| 209 | BM_worst_case_find_first_of(state, 1000); |
| 210 | } |
| 211 | |
| 212 | BENCHMARK(BM_find_first_of_short)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); |
| 213 | BENCHMARK(BM_find_first_of_medium)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); |
| 214 | BENCHMARK(BM_find_first_of_long)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); |
| 215 | |
| 216 | struct EasyMap : public std::map<absl::string_view, uint64_t> { |
| 217 | explicit EasyMap(size_t) {} |
| 218 | }; |
| 219 | |
| 220 | // This templated benchmark helper function is intended to stress operator== or |
| 221 | // operator< in a realistic test. It surely isn't entirely realistic, but it's |
| 222 | // a start. The test creates a map of type Map, a template arg, and populates |
| 223 | // it with table_size key/value pairs. Each key has WordsPerKey words. After |
| 224 | // creating the map, a number of lookups are done in random order. Some keys |
| 225 | // are used much more frequently than others in this phase of the test. |
| 226 | template <typename Map, int WordsPerKey> |
| 227 | void StringViewMapBenchmark(benchmark::State& state) { |
| 228 | const int table_size = state.range(0); |
| 229 | const double kFractionOfKeysThatAreHot = 0.2; |
| 230 | const int kNumLookupsOfHotKeys = 20; |
| 231 | const int kNumLookupsOfColdKeys = 1; |
| 232 | const char* words[] = {"the", "quick", "brown", "fox", "jumped", |
| 233 | "over", "the", "lazy", "dog", "and", |
| 234 | "found", "a", "large", "mushroom", "and", |
| 235 | "a", "couple", "crickets", "eating", "pie"}; |
| 236 | // Create some keys that consist of words in random order. |
| 237 | std::random_device r; |
| 238 | std::seed_seq seed({r(), r(), r(), r(), r(), r(), r(), r()}); |
| 239 | std::mt19937 rng(seed); |
| 240 | std::vector<std::string> keys(table_size); |
| 241 | std::vector<int> all_indices; |
| 242 | const int kBlockSize = 1 << 12; |
| 243 | std::unordered_set<std::string> t(kBlockSize); |
| 244 | std::uniform_int_distribution<int> uniform(0, ABSL_ARRAYSIZE(words) - 1); |
| 245 | for (int i = 0; i < table_size; i++) { |
| 246 | all_indices.push_back(i); |
| 247 | do { |
| 248 | keys[i].clear(); |
| 249 | for (int j = 0; j < WordsPerKey; j++) { |
| 250 | absl::StrAppend(&keys[i], j > 0 ? " " : "", words[uniform(rng)]); |
| 251 | } |
| 252 | } while (!t.insert(keys[i]).second); |
| 253 | } |
| 254 | |
| 255 | // Create a list of strings to lookup: a permutation of the array of |
| 256 | // keys we just created, with repeats. "Hot" keys get repeated more. |
| 257 | std::shuffle(all_indices.begin(), all_indices.end(), rng); |
| 258 | const int num_hot = table_size * kFractionOfKeysThatAreHot; |
| 259 | const int num_cold = table_size - num_hot; |
| 260 | std::vector<int> hot_indices(all_indices.begin(), |
| 261 | all_indices.begin() + num_hot); |
| 262 | std::vector<int> indices; |
| 263 | for (int i = 0; i < kNumLookupsOfColdKeys; i++) { |
| 264 | indices.insert(indices.end(), all_indices.begin(), all_indices.end()); |
| 265 | } |
| 266 | for (int i = 0; i < kNumLookupsOfHotKeys - kNumLookupsOfColdKeys; i++) { |
| 267 | indices.insert(indices.end(), hot_indices.begin(), hot_indices.end()); |
| 268 | } |
| 269 | std::shuffle(indices.begin(), indices.end(), rng); |
| 270 | ABSL_RAW_CHECK( |
| 271 | num_cold * kNumLookupsOfColdKeys + num_hot * kNumLookupsOfHotKeys == |
| 272 | indices.size(), |
| 273 | ""); |
| 274 | // After constructing the array we probe it with absl::string_views built from |
| 275 | // test_strings. This means operator== won't see equal pointers, so |
| 276 | // it'll have to check for equal lengths and equal characters. |
| 277 | std::vector<std::string> test_strings(indices.size()); |
| 278 | for (int i = 0; i < indices.size(); i++) { |
| 279 | test_strings[i] = keys[indices[i]]; |
| 280 | } |
| 281 | |
| 282 | // Run the benchmark. It includes map construction but is mostly |
| 283 | // map lookups. |
| 284 | for (auto _ : state) { |
| 285 | Map h(table_size); |
| 286 | for (int i = 0; i < table_size; i++) { |
| 287 | h[keys[i]] = i * 2; |
| 288 | } |
| 289 | ABSL_RAW_CHECK(h.size() == table_size, ""); |
| 290 | uint64_t sum = 0; |
| 291 | for (int i = 0; i < indices.size(); i++) { |
| 292 | sum += h[test_strings[i]]; |
| 293 | } |
| 294 | benchmark::DoNotOptimize(sum); |
| 295 | } |
| 296 | } |
| 297 | |
| 298 | void BM_StdMap_4(benchmark::State& state) { |
| 299 | StringViewMapBenchmark<EasyMap, 4>(state); |
| 300 | } |
| 301 | BENCHMARK(BM_StdMap_4)->Range(1 << 10, 1 << 16); |
| 302 | |
| 303 | void BM_StdMap_8(benchmark::State& state) { |
| 304 | StringViewMapBenchmark<EasyMap, 8>(state); |
| 305 | } |
| 306 | BENCHMARK(BM_StdMap_8)->Range(1 << 10, 1 << 16); |
| 307 | |
| 308 | void BM_CopyToStringNative(benchmark::State& state) { |
| 309 | std::string src(state.range(0), 'x'); |
| 310 | absl::string_view sv(src); |
| 311 | std::string dst; |
| 312 | for (auto _ : state) { |
| 313 | dst.assign(sv.begin(), sv.end()); |
| 314 | } |
| 315 | } |
| 316 | BENCHMARK(BM_CopyToStringNative)->Range(1 << 3, 1 << 12); |
| 317 | |
| 318 | void BM_AppendToStringNative(benchmark::State& state) { |
| 319 | std::string src(state.range(0), 'x'); |
| 320 | absl::string_view sv(src); |
| 321 | std::string dst; |
| 322 | for (auto _ : state) { |
| 323 | dst.clear(); |
| 324 | dst.insert(dst.end(), sv.begin(), sv.end()); |
| 325 | } |
| 326 | } |
| 327 | BENCHMARK(BM_AppendToStringNative)->Range(1 << 3, 1 << 12); |
| 328 | |
| 329 | } // namespace |