1
2 #include <cstdint>
3 #include <new>
4 #include <vector>
5
6 #include "CartesianBenchmarks.hpp"
7 #include "GenerateInput.hpp"
8 #include "benchmark/benchmark.h"
9 #include "test_macros.h"
10
11 constexpr std::size_t MAX_STRING_LEN = 8 << 14;
12
13 // Benchmark when there is no match.
BM_StringFindNoMatch(benchmark::State & state)14 static void BM_StringFindNoMatch(benchmark::State &state) {
15 std::string s1(state.range(0), '-');
16 std::string s2(8, '*');
17 for (auto _ : state)
18 benchmark::DoNotOptimize(s1.find(s2));
19 }
20 BENCHMARK(BM_StringFindNoMatch)->Range(10, MAX_STRING_LEN);
21
22 // Benchmark when the string matches first time.
BM_StringFindAllMatch(benchmark::State & state)23 static void BM_StringFindAllMatch(benchmark::State &state) {
24 std::string s1(MAX_STRING_LEN, '-');
25 std::string s2(state.range(0), '-');
26 for (auto _ : state)
27 benchmark::DoNotOptimize(s1.find(s2));
28 }
29 BENCHMARK(BM_StringFindAllMatch)->Range(1, MAX_STRING_LEN);
30
31 // Benchmark when the string matches somewhere in the end.
BM_StringFindMatch1(benchmark::State & state)32 static void BM_StringFindMatch1(benchmark::State &state) {
33 std::string s1(MAX_STRING_LEN / 2, '*');
34 s1 += std::string(state.range(0), '-');
35 std::string s2(state.range(0), '-');
36 for (auto _ : state)
37 benchmark::DoNotOptimize(s1.find(s2));
38 }
39 BENCHMARK(BM_StringFindMatch1)->Range(1, MAX_STRING_LEN / 4);
40
41 // Benchmark when the string matches somewhere from middle to the end.
BM_StringFindMatch2(benchmark::State & state)42 static void BM_StringFindMatch2(benchmark::State &state) {
43 std::string s1(MAX_STRING_LEN / 2, '*');
44 s1 += std::string(state.range(0), '-');
45 s1 += std::string(state.range(0), '*');
46 std::string s2(state.range(0), '-');
47 for (auto _ : state)
48 benchmark::DoNotOptimize(s1.find(s2));
49 }
50 BENCHMARK(BM_StringFindMatch2)->Range(1, MAX_STRING_LEN / 4);
51
BM_StringCtorDefault(benchmark::State & state)52 static void BM_StringCtorDefault(benchmark::State &state) {
53 for (auto _ : state) {
54 std::string Default;
55 benchmark::DoNotOptimize(Default);
56 }
57 }
58 BENCHMARK(BM_StringCtorDefault);
59
60 enum class Length { Empty, Small, Large, Huge };
61 struct AllLengths : EnumValuesAsTuple<AllLengths, Length, 4> {
62 static constexpr const char* Names[] = {"Empty", "Small", "Large", "Huge"};
63 };
64
65 enum class Opacity { Opaque, Transparent };
66 struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> {
67 static constexpr const char* Names[] = {"Opaque", "Transparent"};
68 };
69
70 enum class DiffType { Control, ChangeFirst, ChangeMiddle, ChangeLast };
71 struct AllDiffTypes : EnumValuesAsTuple<AllDiffTypes, DiffType, 4> {
72 static constexpr const char* Names[] = {"Control", "ChangeFirst",
73 "ChangeMiddle", "ChangeLast"};
74 };
75
getSmallString(DiffType D)76 TEST_ALWAYS_INLINE const char* getSmallString(DiffType D) {
77 switch (D) {
78 case DiffType::Control:
79 return "0123456";
80 case DiffType::ChangeFirst:
81 return "-123456";
82 case DiffType::ChangeMiddle:
83 return "012-456";
84 case DiffType::ChangeLast:
85 return "012345-";
86 }
87 }
88
getLargeString(DiffType D)89 TEST_ALWAYS_INLINE const char* getLargeString(DiffType D) {
90 #define LARGE_STRING_FIRST "123456789012345678901234567890"
91 #define LARGE_STRING_SECOND "234567890123456789012345678901"
92 switch (D) {
93 case DiffType::Control:
94 return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
95 case DiffType::ChangeFirst:
96 return "-" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
97 case DiffType::ChangeMiddle:
98 return "0" LARGE_STRING_FIRST "-" LARGE_STRING_SECOND "2";
99 case DiffType::ChangeLast:
100 return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "-";
101 }
102 }
103
getHugeString(DiffType D)104 TEST_ALWAYS_INLINE const char* getHugeString(DiffType D) {
105 #define HUGE_STRING0 "0123456789"
106 #define HUGE_STRING1 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0
107 #define HUGE_STRING2 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1
108 #define HUGE_STRING3 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2
109 #define HUGE_STRING4 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3
110 switch (D) {
111 case DiffType::Control:
112 return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
113 case DiffType::ChangeFirst:
114 return "-123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
115 case DiffType::ChangeMiddle:
116 return "0123456789" HUGE_STRING4 "01234-6789" HUGE_STRING4 "0123456789";
117 case DiffType::ChangeLast:
118 return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "012345678-";
119 }
120 }
121
makeString(Length L,DiffType D=DiffType::Control,Opacity O=Opacity::Transparent)122 TEST_ALWAYS_INLINE std::string makeString(Length L,
123 DiffType D = DiffType::Control,
124 Opacity O = Opacity::Transparent) {
125 switch (L) {
126 case Length::Empty:
127 return maybeOpaque("", O == Opacity::Opaque);
128 case Length::Small:
129 return maybeOpaque(getSmallString(D), O == Opacity::Opaque);
130 case Length::Large:
131 return maybeOpaque(getLargeString(D), O == Opacity::Opaque);
132 case Length::Huge:
133 return maybeOpaque(getHugeString(D), O == Opacity::Opaque);
134 }
135 }
136
137 template <class Length, class Opaque>
138 struct StringConstructDestroyCStr {
runStringConstructDestroyCStr139 static void run(benchmark::State& state) {
140 for (auto _ : state) {
141 benchmark::DoNotOptimize(
142 makeString(Length(), DiffType::Control, Opaque()));
143 }
144 }
145
nameStringConstructDestroyCStr146 static std::string name() {
147 return "BM_StringConstructDestroyCStr" + Length::name() + Opaque::name();
148 }
149 };
150
151 template <class Length, bool MeasureCopy, bool MeasureDestroy>
StringCopyAndDestroy(benchmark::State & state)152 static void StringCopyAndDestroy(benchmark::State& state) {
153 static constexpr size_t NumStrings = 1024;
154 auto Orig = makeString(Length());
155 std::aligned_storage<sizeof(std::string)>::type Storage[NumStrings];
156
157 while (state.KeepRunningBatch(NumStrings)) {
158 if (!MeasureCopy)
159 state.PauseTiming();
160 for (size_t I = 0; I < NumStrings; ++I) {
161 ::new (static_cast<void*>(Storage + I)) std::string(Orig);
162 }
163 if (!MeasureCopy)
164 state.ResumeTiming();
165 if (!MeasureDestroy)
166 state.PauseTiming();
167 for (size_t I = 0; I < NumStrings; ++I) {
168 using S = std::string;
169 reinterpret_cast<S*>(Storage + I)->~S();
170 }
171 if (!MeasureDestroy)
172 state.ResumeTiming();
173 }
174 }
175
176 template <class Length>
177 struct StringCopy {
runStringCopy178 static void run(benchmark::State& state) {
179 StringCopyAndDestroy<Length, true, false>(state);
180 }
181
nameStringCopy182 static std::string name() { return "BM_StringCopy" + Length::name(); }
183 };
184
185 template <class Length>
186 struct StringDestroy {
runStringDestroy187 static void run(benchmark::State& state) {
188 StringCopyAndDestroy<Length, false, true>(state);
189 }
190
nameStringDestroy191 static std::string name() { return "BM_StringDestroy" + Length::name(); }
192 };
193
194 template <class Length>
195 struct StringMove {
runStringMove196 static void run(benchmark::State& state) {
197 // Keep two object locations and move construct back and forth.
198 std::aligned_storage<sizeof(std::string), alignof(std::string)>::type Storage[2];
199 using S = std::string;
200 size_t I = 0;
201 S *newS = new (static_cast<void*>(Storage)) std::string(makeString(Length()));
202 for (auto _ : state) {
203 // Switch locations.
204 I ^= 1;
205 benchmark::DoNotOptimize(Storage);
206 // Move construct into the new location,
207 S *tmpS = new (static_cast<void*>(Storage + I)) S(std::move(*newS));
208 // then destroy the old one.
209 newS->~S();
210 newS = tmpS;
211 }
212 newS->~S();
213 }
214
nameStringMove215 static std::string name() { return "BM_StringMove" + Length::name(); }
216 };
217
218 enum class Relation { Eq, Less, Compare };
219 struct AllRelations : EnumValuesAsTuple<AllRelations, Relation, 3> {
220 static constexpr const char* Names[] = {"Eq", "Less", "Compare"};
221 };
222
223 template <class Rel, class LHLength, class RHLength, class DiffType>
224 struct StringRelational {
runStringRelational225 static void run(benchmark::State& state) {
226 auto Lhs = makeString(RHLength());
227 auto Rhs = makeString(LHLength(), DiffType());
228 for (auto _ : state) {
229 benchmark::DoNotOptimize(Lhs);
230 benchmark::DoNotOptimize(Rhs);
231 switch (Rel()) {
232 case Relation::Eq:
233 benchmark::DoNotOptimize(Lhs == Rhs);
234 break;
235 case Relation::Less:
236 benchmark::DoNotOptimize(Lhs < Rhs);
237 break;
238 case Relation::Compare:
239 benchmark::DoNotOptimize(Lhs.compare(Rhs));
240 break;
241 }
242 }
243 }
244
skipStringRelational245 static bool skip() {
246 // Eq is commutative, so skip half the matrix.
247 if (Rel() == Relation::Eq && LHLength() > RHLength())
248 return true;
249 // We only care about control when the lengths differ.
250 if (LHLength() != RHLength() && DiffType() != ::DiffType::Control)
251 return true;
252 // For empty, only control matters.
253 if (LHLength() == Length::Empty && DiffType() != ::DiffType::Control)
254 return true;
255 return false;
256 }
257
nameStringRelational258 static std::string name() {
259 return "BM_StringRelational" + Rel::name() + LHLength::name() +
260 RHLength::name() + DiffType::name();
261 }
262 };
263
264 enum class Depth { Shallow, Deep };
265 struct AllDepths : EnumValuesAsTuple<AllDepths, Depth, 2> {
266 static constexpr const char* Names[] = {"Shallow", "Deep"};
267 };
268
269 enum class Temperature { Hot, Cold };
270 struct AllTemperatures : EnumValuesAsTuple<AllTemperatures, Temperature, 2> {
271 static constexpr const char* Names[] = {"Hot", "Cold"};
272 };
273
274 template <class Temperature, class Depth, class Length>
275 struct StringRead {
runStringRead276 void run(benchmark::State& state) const {
277 static constexpr size_t NumStrings =
278 Temperature() == ::Temperature::Hot
279 ? 1 << 10
280 : /* Enough strings to overflow the cache */ 1 << 20;
281 static_assert((NumStrings & (NumStrings - 1)) == 0,
282 "NumStrings should be a power of two to reduce overhead.");
283
284 std::vector<std::string> Values(NumStrings, makeString(Length()));
285 size_t I = 0;
286 for (auto _ : state) {
287 // Jump long enough to defeat cache locality, and use a value that is
288 // coprime with NumStrings to ensure we visit every element.
289 I = (I + 17) % NumStrings;
290 const auto& V = Values[I];
291
292 // Read everything first. Escaping data() through DoNotOptimize might
293 // cause the compiler to have to recalculate information about `V` due to
294 // aliasing.
295 const char* const Data = V.data();
296 const size_t Size = V.size();
297 benchmark::DoNotOptimize(Data);
298 benchmark::DoNotOptimize(Size);
299 if (Depth() == ::Depth::Deep) {
300 // Read into the payload. This mainly shows the benefit of SSO when the
301 // data is cold.
302 benchmark::DoNotOptimize(*Data);
303 }
304 }
305 }
306
skipStringRead307 static bool skip() {
308 // Huge does not give us anything that Large doesn't have. Skip it.
309 if (Length() == ::Length::Huge) {
310 return true;
311 }
312 return false;
313 }
314
nameStringRead315 std::string name() const {
316 return "BM_StringRead" + Temperature::name() + Depth::name() +
317 Length::name();
318 }
319 };
320
sanityCheckGeneratedStrings()321 void sanityCheckGeneratedStrings() {
322 for (auto Lhs : {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
323 const auto LhsString = makeString(Lhs);
324 for (auto Rhs :
325 {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
326 if (Lhs > Rhs)
327 continue;
328 const auto RhsString = makeString(Rhs);
329
330 // The smaller one must be a prefix of the larger one.
331 if (RhsString.find(LhsString) != 0) {
332 fprintf(stderr, "Invalid autogenerated strings for sizes (%d,%d).\n",
333 static_cast<int>(Lhs), static_cast<int>(Rhs));
334 std::abort();
335 }
336 }
337 }
338 // Verify the autogenerated diffs
339 for (auto L : {Length::Small, Length::Large, Length::Huge}) {
340 const auto Control = makeString(L);
341 const auto Verify = [&](std::string Exp, size_t Pos) {
342 // Only change on the Pos char.
343 if (Control[Pos] != Exp[Pos]) {
344 Exp[Pos] = Control[Pos];
345 if (Control == Exp)
346 return;
347 }
348 fprintf(stderr, "Invalid autogenerated diff with size %d\n",
349 static_cast<int>(L));
350 std::abort();
351 };
352 Verify(makeString(L, DiffType::ChangeFirst), 0);
353 Verify(makeString(L, DiffType::ChangeMiddle), Control.size() / 2);
354 Verify(makeString(L, DiffType::ChangeLast), Control.size() - 1);
355 }
356 }
357
main(int argc,char ** argv)358 int main(int argc, char** argv) {
359 benchmark::Initialize(&argc, argv);
360 if (benchmark::ReportUnrecognizedArguments(argc, argv))
361 return 1;
362
363 sanityCheckGeneratedStrings();
364
365 makeCartesianProductBenchmark<StringConstructDestroyCStr, AllLengths,
366 AllOpacity>();
367 makeCartesianProductBenchmark<StringCopy, AllLengths>();
368 makeCartesianProductBenchmark<StringMove, AllLengths>();
369 makeCartesianProductBenchmark<StringDestroy, AllLengths>();
370 makeCartesianProductBenchmark<StringRelational, AllRelations, AllLengths,
371 AllLengths, AllDiffTypes>();
372 makeCartesianProductBenchmark<StringRead, AllTemperatures, AllDepths,
373 AllLengths>();
374 benchmark::RunSpecifiedBenchmarks();
375 }
376