tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

memutil_benchmark.cc (4421B)

      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 <algorithm>
     16 #include <cstdlib>
     17 
     18 #include "absl/strings/ascii.h"
     19 #include "absl/strings/internal/memutil.h"
     20 #include "benchmark/benchmark.h"
     21 
     22 // We fill the haystack with aaaaaaaaaaaaaaaaaa...aaaab.
     23 // That gives us:
     24 // - an easy search: 'b'
     25 // - a medium search: 'ab'.  That means every letter is a possible match.
     26 // - a pathological search: 'aaaaaa.......aaaaab' (half as many a's as haytack)
     27 
     28 namespace {
     29 
     30 constexpr int kHaystackSize = 10000;
     31 constexpr int64_t kHaystackSize64 = kHaystackSize;
     32 const char* MakeHaystack() {
     33  char* haystack = new char[kHaystackSize];
     34  for (int i = 0; i < kHaystackSize - 1; ++i) haystack[i] = 'a';
     35  haystack[kHaystackSize - 1] = 'b';
     36  return haystack;
     37 }
     38 const char* const kHaystack = MakeHaystack();
     39 
     40 bool case_eq(const char a, const char b) {
     41  return absl::ascii_tolower(a) == absl::ascii_tolower(b);
     42 }
     43 
     44 void BM_Searchcase(benchmark::State& state) {
     45  for (auto _ : state) {
     46    benchmark::DoNotOptimize(std::search(kHaystack, kHaystack + kHaystackSize,
     47                                         kHaystack + kHaystackSize - 1,
     48                                         kHaystack + kHaystackSize, case_eq));
     49  }
     50  state.SetBytesProcessed(kHaystackSize64 * state.iterations());
     51 }
     52 BENCHMARK(BM_Searchcase);
     53 
     54 void BM_SearchcaseMedium(benchmark::State& state) {
     55  for (auto _ : state) {
     56    benchmark::DoNotOptimize(std::search(kHaystack, kHaystack + kHaystackSize,
     57                                         kHaystack + kHaystackSize - 2,
     58                                         kHaystack + kHaystackSize, case_eq));
     59  }
     60  state.SetBytesProcessed(kHaystackSize64 * state.iterations());
     61 }
     62 BENCHMARK(BM_SearchcaseMedium);
     63 
     64 void BM_SearchcasePathological(benchmark::State& state) {
     65  for (auto _ : state) {
     66    benchmark::DoNotOptimize(std::search(kHaystack, kHaystack + kHaystackSize,
     67                                         kHaystack + kHaystackSize / 2,
     68                                         kHaystack + kHaystackSize, case_eq));
     69  }
     70  state.SetBytesProcessed(kHaystackSize64 * state.iterations());
     71 }
     72 BENCHMARK(BM_SearchcasePathological);
     73 
     74 char* memcasechr(const char* s, int c, size_t slen) {
     75  c = absl::ascii_tolower(c);
     76  for (; slen; ++s, --slen) {
     77    if (absl::ascii_tolower(*s) == c) return const_cast<char*>(s);
     78  }
     79  return nullptr;
     80 }
     81 
     82 const char* memcasematch(const char* phaystack, size_t haylen,
     83                         const char* pneedle, size_t neelen) {
     84  if (0 == neelen) {
     85    return phaystack;  // even if haylen is 0
     86  }
     87  if (haylen < neelen) return nullptr;
     88 
     89  const char* match;
     90  const char* hayend = phaystack + haylen - neelen + 1;
     91  while ((match = static_cast<char*>(
     92              memcasechr(phaystack, pneedle[0], hayend - phaystack)))) {
     93    if (absl::strings_internal::memcasecmp(match, pneedle, neelen) == 0)
     94      return match;
     95    else
     96      phaystack = match + 1;
     97  }
     98  return nullptr;
     99 }
    100 
    101 void BM_Memcasematch(benchmark::State& state) {
    102  for (auto _ : state) {
    103    benchmark::DoNotOptimize(memcasematch(kHaystack, kHaystackSize, "b", 1));
    104  }
    105  state.SetBytesProcessed(kHaystackSize64 * state.iterations());
    106 }
    107 BENCHMARK(BM_Memcasematch);
    108 
    109 void BM_MemcasematchMedium(benchmark::State& state) {
    110  for (auto _ : state) {
    111    benchmark::DoNotOptimize(memcasematch(kHaystack, kHaystackSize, "ab", 2));
    112  }
    113  state.SetBytesProcessed(kHaystackSize64 * state.iterations());
    114 }
    115 BENCHMARK(BM_MemcasematchMedium);
    116 
    117 void BM_MemcasematchPathological(benchmark::State& state) {
    118  for (auto _ : state) {
    119    benchmark::DoNotOptimize(memcasematch(kHaystack, kHaystackSize,
    120                                          kHaystack + kHaystackSize / 2,
    121                                          kHaystackSize - kHaystackSize / 2));
    122  }
    123  state.SetBytesProcessed(kHaystackSize64 * state.iterations());
    124 }
    125 BENCHMARK(BM_MemcasematchPathological);
    126 
    127 }  // namespace