Skip to content
Snippets Groups Projects
  • Abseil Team's avatar
    59ae4d5a
    - a4e14440b870dbf7b36975eaebf783a70a7fcee4 Release string_view... · 59ae4d5a
    Abseil Team authored
      - a4e14440b870dbf7b36975eaebf783a70a7fcee4 Release string_view microbenchmarks. by Alex Strelnikov <strel@google.com>
      - 7cec68e37e16fb4e266368236ae1de6419f6946a Increase Abseil's minimum supported cmake version to 3.1.... by Jon Cohen <cohenjon@google.com>
      - b977456175c8db380676bd56c44b32efbfc6f606 Fix a typo in the mutex.h comments. by Abseil Team <absl-team@google.com>
      - 3d30cec131d08b066bc1cf877e4f661e8ee0584c Release StrSplit microbenchmarks. by Alex Strelnikov <strel@google.com>
      - dddece6031feac1cca4689e623462f895f28d019 Release StrReplace microbenchmarks. by Alex Strelnikov <strel@google.com>
      - ac3b40e1694f74bdcf31b8d1152481e92edfd441 Internal Change by Abseil Team <absl-team@google.com>
      - d0e69ad6ddf0e59596a02ccab0253967f2909cdb Release StrCat microbenchmarks. by Alex Strelnikov <strel@google.com>
      - db4d471030fa320d2b9d2ce241610333f0eb7a50 Release StrJoin microbenchmarks. by Alex Strelnikov <strel@google.com>
    
    GitOrigin-RevId: a4e14440b870dbf7b36975eaebf783a70a7fcee4
    Change-Id: I3f12700aafce677049f4d1a6e09ea821963a8c9e
    59ae4d5a
    History
    - a4e14440b870dbf7b36975eaebf783a70a7fcee4 Release string_view...
    Abseil Team authored
      - a4e14440b870dbf7b36975eaebf783a70a7fcee4 Release string_view microbenchmarks. by Alex Strelnikov <strel@google.com>
      - 7cec68e37e16fb4e266368236ae1de6419f6946a Increase Abseil's minimum supported cmake version to 3.1.... by Jon Cohen <cohenjon@google.com>
      - b977456175c8db380676bd56c44b32efbfc6f606 Fix a typo in the mutex.h comments. by Abseil Team <absl-team@google.com>
      - 3d30cec131d08b066bc1cf877e4f661e8ee0584c Release StrSplit microbenchmarks. by Alex Strelnikov <strel@google.com>
      - dddece6031feac1cca4689e623462f895f28d019 Release StrReplace microbenchmarks. by Alex Strelnikov <strel@google.com>
      - ac3b40e1694f74bdcf31b8d1152481e92edfd441 Internal Change by Abseil Team <absl-team@google.com>
      - d0e69ad6ddf0e59596a02ccab0253967f2909cdb Release StrCat microbenchmarks. by Alex Strelnikov <strel@google.com>
      - db4d471030fa320d2b9d2ce241610333f0eb7a50 Release StrJoin microbenchmarks. by Alex Strelnikov <strel@google.com>
    
    GitOrigin-RevId: a4e14440b870dbf7b36975eaebf783a70a7fcee4
    Change-Id: I3f12700aafce677049f4d1a6e09ea821963a8c9e
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
str_replace_benchmark.cc 4.42 KiB
// Copyright 2018 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "absl/strings/str_replace.h"

#include <cstring>
#include <string>

#include "benchmark/benchmark.h"
#include "absl/base/internal/raw_logging.h"

namespace {

std::string* big_string;
std::string* after_replacing_the;
std::string* after_replacing_many;

struct Replacement {
  const char* needle;
  const char* replacement;
} replacements[] = {
    {"the", "box"},          //
    {"brown", "quick"},      //
    {"jumped", "liquored"},  //
    {"dozen", "brown"},      //
    {"lazy", "pack"},        //
    {"liquor", "shakes"},    //
};

// Here, we set up a std::string for use in global-replace benchmarks.
// We started with a million blanks, and then deterministically insert
// 10,000 copies each of two pangrams.  The result is a std::string that is
// 40% blank space and 60% these words.  'the' occurs 18,247 times and
// all the substitutions together occur 49,004 times.
//
// We then create "after_replacing_the" to be a std::string that is a result of
// replacing "the" with "box" in big_string.
//
// And then we create "after_replacing_many" to be a std::string that is result
// of preferring several substitutions.
void SetUpStrings() {
  if (big_string == nullptr) {
    size_t r = 0;
    big_string = new std::string(1000 * 1000, ' ');
    for (std::string phrase : {"the quick brown fox jumped over the lazy dogs",
                          "pack my box with the five dozen liquor jugs"}) {
      for (int i = 0; i < 10 * 1000; ++i) {
        r = r * 237 + 41;  // not very random.
        memcpy(&(*big_string)[r % (big_string->size() - phrase.size())],
               phrase.data(), phrase.size());
      }
    }
    // big_string->resize(50);
    // OK, we've set up the std::string, now let's set up expectations - first by
    // just replacing "the" with "box"
    after_replacing_the = new std::string(*big_string);
    for (size_t pos = 0;
         (pos = after_replacing_the->find("the", pos)) != std::string::npos;) {
      memcpy(&(*after_replacing_the)[pos], "box", 3);
    }
    // And then with all the replacements.
    after_replacing_many = new std::string(*big_string);
    for (size_t pos = 0;;) {
      size_t next_pos = static_cast<size_t>(-1);
      const char* needle_string = nullptr;
      const char* replacement_string = nullptr;
      for (const auto& r : replacements) {
        auto needlepos = after_replacing_many->find(r.needle, pos);
        if (needlepos != std::string::npos && needlepos < next_pos) {
          next_pos = needlepos;
          needle_string = r.needle;
          replacement_string = r.replacement;
        }
      }
      if (next_pos > after_replacing_many->size()) break;
      after_replacing_many->replace(next_pos, strlen(needle_string),
                                    replacement_string);
      next_pos += strlen(replacement_string);
      pos = next_pos;
    }
  }
}

void BM_StrReplaceAllOneReplacement(benchmark::State& state) {
  SetUpStrings();
  std::string src = *big_string;
  for (auto _ : state) {
    std::string dest = absl::StrReplaceAll(src, {{"the", "box"}});
    ABSL_RAW_CHECK(dest == *after_replacing_the,
                   "not benchmarking intended behavior");
  }
}
BENCHMARK(BM_StrReplaceAllOneReplacement);

void BM_StrReplaceAll(benchmark::State& state) {
  SetUpStrings();
  std::string src = *big_string;
  for (auto _ : state) {
    std::string dest = absl::StrReplaceAll(src, {{"the", "box"},
                                            {"brown", "quick"},
                                            {"jumped", "liquored"},
                                            {"dozen", "brown"},
                                            {"lazy", "pack"},
                                            {"liquor", "shakes"}});
    ABSL_RAW_CHECK(dest == *after_replacing_many,
                   "not benchmarking intended behavior");
  }
}
BENCHMARK(BM_StrReplaceAll);

}  // namespace

BENCHMARK_MAIN();