str_replace_benchmark.cc (4509B)
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 <cstring> 16 #include <string> 17 18 #include "absl/base/internal/raw_logging.h" 19 #include "absl/strings/str_replace.h" 20 #include "benchmark/benchmark.h" 21 22 namespace { 23 24 std::string* big_string; 25 std::string* after_replacing_the; 26 std::string* after_replacing_many; 27 28 struct Replacement { 29 const char* needle; 30 const char* replacement; 31 } replacements[] = { 32 {"the", "box"}, // 33 {"brown", "quick"}, // 34 {"jumped", "liquored"}, // 35 {"dozen", "brown"}, // 36 {"lazy", "pack"}, // 37 {"liquor", "shakes"}, // 38 }; 39 40 // Here, we set up a string for use in global-replace benchmarks. 41 // We started with a million blanks, and then deterministically insert 42 // 10,000 copies each of two pangrams. The result is a string that is 43 // 40% blank space and 60% these words. 'the' occurs 18,247 times and 44 // all the substitutions together occur 49,004 times. 45 // 46 // We then create "after_replacing_the" to be a string that is a result of 47 // replacing "the" with "box" in big_string. 48 // 49 // And then we create "after_replacing_many" to be a string that is result 50 // of preferring several substitutions. 51 void SetUpStrings() { 52 if (big_string == nullptr) { 53 size_t r = 0; 54 big_string = new std::string(1000 * 1000, ' '); 55 for (std::string phrase : {"the quick brown fox jumped over the lazy dogs", 56 "pack my box with the five dozen liquor jugs"}) { 57 for (int i = 0; i < 10 * 1000; ++i) { 58 r = r * 237 + 41; // not very random. 59 memcpy(&(*big_string)[r % (big_string->size() - phrase.size())], 60 phrase.data(), phrase.size()); 61 } 62 } 63 // big_string->resize(50); 64 // OK, we've set up the string, now let's set up expectations - first by 65 // just replacing "the" with "box" 66 after_replacing_the = new std::string(*big_string); 67 for (size_t pos = 0; 68 (pos = after_replacing_the->find("the", pos)) != std::string::npos;) { 69 memcpy(&(*after_replacing_the)[pos], "box", 3); 70 } 71 // And then with all the replacements. 72 after_replacing_many = new std::string(*big_string); 73 for (size_t pos = 0;;) { 74 size_t next_pos = static_cast<size_t>(-1); 75 const char* needle_string = nullptr; 76 const char* replacement_string = nullptr; 77 for (const auto& r : replacements) { 78 auto needlepos = after_replacing_many->find(r.needle, pos); 79 if (needlepos != std::string::npos && needlepos < next_pos) { 80 next_pos = needlepos; 81 needle_string = r.needle; 82 replacement_string = r.replacement; 83 } 84 } 85 if (next_pos > after_replacing_many->size()) break; 86 after_replacing_many->replace(next_pos, strlen(needle_string), 87 replacement_string); 88 next_pos += strlen(replacement_string); 89 pos = next_pos; 90 } 91 } 92 } 93 94 void BM_StrReplaceAllOneReplacement(benchmark::State& state) { 95 SetUpStrings(); 96 std::string src = *big_string; 97 for (auto _ : state) { 98 std::string dest = absl::StrReplaceAll(src, {{"the", "box"}}); 99 ABSL_RAW_CHECK(dest == *after_replacing_the, 100 "not benchmarking intended behavior"); 101 } 102 } 103 BENCHMARK(BM_StrReplaceAllOneReplacement); 104 105 void BM_StrReplaceAll(benchmark::State& state) { 106 SetUpStrings(); 107 std::string src = *big_string; 108 for (auto _ : state) { 109 std::string dest = absl::StrReplaceAll(src, {{"the", "box"}, 110 {"brown", "quick"}, 111 {"jumped", "liquored"}, 112 {"dozen", "brown"}, 113 {"lazy", "pack"}, 114 {"liquor", "shakes"}}); 115 ABSL_RAW_CHECK(dest == *after_replacing_many, 116 "not benchmarking intended behavior"); 117 } 118 } 119 BENCHMARK(BM_StrReplaceAll); 120 121 } // namespace