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