1
2#include <cstdint>
3#include <new>
4#include <vector>
5
6#include "CartesianBenchmarks.h"
7#include "GenerateInput.h"
8#include "benchmark/benchmark.h"
9#include "test_macros.h"
10
11constexpr std::size_t MAX_STRING_LEN = 8 << 14;
12
13// Benchmark when there is no match.
14static 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}
20BENCHMARK(BM_StringFindNoMatch)->Range(10, MAX_STRING_LEN);
21
22// Benchmark when the string matches first time.
23static 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}
29BENCHMARK(BM_StringFindAllMatch)->Range(1, MAX_STRING_LEN);
30
31// Benchmark when the string matches somewhere in the end.
32static 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}
39BENCHMARK(BM_StringFindMatch1)->Range(1, MAX_STRING_LEN / 4);
40
41// Benchmark when the string matches somewhere from middle to the end.
42static 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}
50BENCHMARK(BM_StringFindMatch2)->Range(1, MAX_STRING_LEN / 4);
51
52static void BM_StringCtorDefault(benchmark::State& state) {
53 for (auto _ : state) {
54 std::string Default;
55 benchmark::DoNotOptimize(Default);
56 }
57}
58BENCHMARK(BM_StringCtorDefault);
59
60enum class Length { Empty, Small, Large, Huge };
61struct AllLengths : EnumValuesAsTuple<AllLengths, Length, 4> {
62 static constexpr const char* Names[] = {"Empty", "Small", "Large", "Huge"};
63};
64
65enum class Opacity { Opaque, Transparent };
66struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> {
67 static constexpr const char* Names[] = {"Opaque", "Transparent"};
68};
69
70enum class DiffType { Control, ChangeFirst, ChangeMiddle, ChangeLast };
71struct AllDiffTypes : EnumValuesAsTuple<AllDiffTypes, DiffType, 4> {
72 static constexpr const char* Names[] = {"Control", "ChangeFirst", "ChangeMiddle", "ChangeLast"};
73};
74
75static constexpr char SmallStringLiteral[] = "012345678";
76
77TEST_ALWAYS_INLINE const char* getSmallString(DiffType D) {
78 switch (D) {
79 case DiffType::Control:
80 return SmallStringLiteral;
81 case DiffType::ChangeFirst:
82 return "-12345678";
83 case DiffType::ChangeMiddle:
84 return "0123-5678";
85 case DiffType::ChangeLast:
86 return "01234567-";
87 }
88}
89
90static constexpr char LargeStringLiteral[] = "012345678901234567890123456789012345678901234567890123456789012";
91
92TEST_ALWAYS_INLINE const char* getLargeString(DiffType D) {
93#define LARGE_STRING_FIRST "123456789012345678901234567890"
94#define LARGE_STRING_SECOND "234567890123456789012345678901"
95 switch (D) {
96 case DiffType::Control:
97 return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
98 case DiffType::ChangeFirst:
99 return "-" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
100 case DiffType::ChangeMiddle:
101 return "0" LARGE_STRING_FIRST "-" LARGE_STRING_SECOND "2";
102 case DiffType::ChangeLast:
103 return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "-";
104 }
105}
106
107TEST_ALWAYS_INLINE const char* getHugeString(DiffType D) {
108#define HUGE_STRING0 "0123456789"
109#define HUGE_STRING1 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0
110#define HUGE_STRING2 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1
111#define HUGE_STRING3 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2
112#define HUGE_STRING4 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3
113 switch (D) {
114 case DiffType::Control:
115 return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
116 case DiffType::ChangeFirst:
117 return "-123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
118 case DiffType::ChangeMiddle:
119 return "0123456789" HUGE_STRING4 "01234-6789" HUGE_STRING4 "0123456789";
120 case DiffType::ChangeLast:
121 return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "012345678-";
122 }
123}
124
125TEST_ALWAYS_INLINE const char* getString(Length L, DiffType D = DiffType::Control) {
126 switch (L) {
127 case Length::Empty:
128 return "";
129 case Length::Small:
130 return getSmallString(D);
131 case Length::Large:
132 return getLargeString(D);
133 case Length::Huge:
134 return getHugeString(D);
135 }
136}
137
138TEST_ALWAYS_INLINE std::string makeString(Length L, DiffType D = DiffType::Control, Opacity O = Opacity::Transparent) {
139 switch (L) {
140 case Length::Empty:
141 return maybeOpaque("", O == Opacity::Opaque);
142 case Length::Small:
143 return maybeOpaque(getSmallString(D), O == Opacity::Opaque);
144 case Length::Large:
145 return maybeOpaque(getLargeString(D), O == Opacity::Opaque);
146 case Length::Huge:
147 return maybeOpaque(getHugeString(D), O == Opacity::Opaque);
148 }
149}
150
151template <class Length, class Opaque>
152struct StringConstructDestroyCStr {
153 static void run(benchmark::State& state) {
154 for (auto _ : state) {
155 benchmark::DoNotOptimize(makeString(Length(), DiffType::Control, Opaque()));
156 }
157 }
158
159 static std::string name() { return "BM_StringConstructDestroyCStr" + Length::name() + Opaque::name(); }
160};
161
162template <class Length, bool MeasureCopy, bool MeasureDestroy>
163static void StringCopyAndDestroy(benchmark::State& state) {
164 static constexpr size_t NumStrings = 1024;
165 auto Orig = makeString(Length());
166 std::aligned_storage<sizeof(std::string)>::type Storage[NumStrings];
167
168 while (state.KeepRunningBatch(NumStrings)) {
169 if (!MeasureCopy)
170 state.PauseTiming();
171 for (size_t I = 0; I < NumStrings; ++I) {
172 ::new (static_cast<void*>(Storage + I)) std::string(Orig);
173 }
174 if (!MeasureCopy)
175 state.ResumeTiming();
176 if (!MeasureDestroy)
177 state.PauseTiming();
178 for (size_t I = 0; I < NumStrings; ++I) {
179 using S = std::string;
180 reinterpret_cast<S*>(Storage + I)->~S();
181 }
182 if (!MeasureDestroy)
183 state.ResumeTiming();
184 }
185}
186
187template <class Length>
188struct StringCopy {
189 static void run(benchmark::State& state) { StringCopyAndDestroy<Length, true, false>(state); }
190
191 static std::string name() { return "BM_StringCopy" + Length::name(); }
192};
193
194template <class Length>
195struct StringDestroy {
196 static void run(benchmark::State& state) { StringCopyAndDestroy<Length, false, true>(state); }
197
198 static std::string name() { return "BM_StringDestroy" + Length::name(); }
199};
200
201template <class Length>
202struct StringMove {
203 static void run(benchmark::State& state) {
204 // Keep two object locations and move construct back and forth.
205 std::aligned_storage<sizeof(std::string), alignof(std::string)>::type Storage[2];
206 using S = std::string;
207 size_t I = 0;
208 S* newS = new (static_cast<void*>(Storage)) std::string(makeString(Length()));
209 for (auto _ : state) {
210 // Switch locations.
211 I ^= 1;
212 benchmark::DoNotOptimize(Storage);
213 // Move construct into the new location,
214 S* tmpS = new (static_cast<void*>(Storage + I)) S(std::move(*newS));
215 // then destroy the old one.
216 newS->~S();
217 newS = tmpS;
218 }
219 newS->~S();
220 }
221
222 static std::string name() { return "BM_StringMove" + Length::name(); }
223};
224
225template <class Length, class Opaque>
226struct StringResizeDefaultInit {
227 static void run(benchmark::State& state) {
228 constexpr bool opaque = Opaque{} == Opacity::Opaque;
229 constexpr int kNumStrings = 4 << 10;
230 size_t length = makeString(Length()).size();
231 std::string strings[kNumStrings];
232 while (state.KeepRunningBatch(kNumStrings)) {
233 state.PauseTiming();
234 for (int i = 0; i < kNumStrings; ++i) {
235 std::string().swap(strings[i]);
236 }
237 benchmark::DoNotOptimize(strings);
238 state.ResumeTiming();
239 for (int i = 0; i < kNumStrings; ++i) {
240 strings[i].__resize_default_init(maybeOpaque(length, opaque));
241 }
242 }
243 }
244
245 static std::string name() { return "BM_StringResizeDefaultInit" + Length::name() + Opaque::name(); }
246};
247
248template <class Length, class Opaque>
249struct StringAssignStr {
250 static void run(benchmark::State& state) {
251 constexpr bool opaque = Opaque{} == Opacity::Opaque;
252 constexpr int kNumStrings = 4 << 10;
253 std::string src = makeString(Length());
254 std::string strings[kNumStrings];
255 while (state.KeepRunningBatch(kNumStrings)) {
256 state.PauseTiming();
257 for (int i = 0; i < kNumStrings; ++i) {
258 std::string().swap(strings[i]);
259 }
260 benchmark::DoNotOptimize(strings);
261 state.ResumeTiming();
262 for (int i = 0; i < kNumStrings; ++i) {
263 strings[i] = *maybeOpaque(&src, opaque);
264 }
265 }
266 }
267
268 static std::string name() { return "BM_StringAssignStr" + Length::name() + Opaque::name(); }
269};
270
271template <class Length, class Opaque>
272struct StringAssignAsciiz {
273 static void run(benchmark::State& state) {
274 constexpr bool opaque = Opaque{} == Opacity::Opaque;
275 constexpr int kNumStrings = 4 << 10;
276 std::string strings[kNumStrings];
277 while (state.KeepRunningBatch(kNumStrings)) {
278 state.PauseTiming();
279 for (int i = 0; i < kNumStrings; ++i) {
280 std::string().swap(strings[i]);
281 }
282 benchmark::DoNotOptimize(strings);
283 state.ResumeTiming();
284 for (int i = 0; i < kNumStrings; ++i) {
285 strings[i] = maybeOpaque(getString(Length()), opaque);
286 }
287 }
288 }
289
290 static std::string name() { return "BM_StringAssignAsciiz" + Length::name() + Opaque::name(); }
291};
292
293template <class Length, class Opaque>
294struct StringEraseToEnd {
295 static void run(benchmark::State& state) {
296 constexpr bool opaque = Opaque{} == Opacity::Opaque;
297 constexpr int kNumStrings = 4 << 10;
298 std::string strings[kNumStrings];
299 const int mid = makeString(Length()).size() / 2;
300 while (state.KeepRunningBatch(kNumStrings)) {
301 state.PauseTiming();
302 for (int i = 0; i < kNumStrings; ++i) {
303 strings[i] = makeString(Length());
304 }
305 benchmark::DoNotOptimize(strings);
306 state.ResumeTiming();
307 for (int i = 0; i < kNumStrings; ++i) {
308 strings[i].erase(maybeOpaque(mid, opaque), maybeOpaque(std::string::npos, opaque));
309 }
310 }
311 }
312
313 static std::string name() { return "BM_StringEraseToEnd" + Length::name() + Opaque::name(); }
314};
315
316template <class Length, class Opaque>
317struct StringEraseWithMove {
318 static void run(benchmark::State& state) {
319 constexpr bool opaque = Opaque{} == Opacity::Opaque;
320 constexpr int kNumStrings = 4 << 10;
321 std::string strings[kNumStrings];
322 const int n = makeString(Length()).size() / 2;
323 const int pos = n / 2;
324 while (state.KeepRunningBatch(kNumStrings)) {
325 state.PauseTiming();
326 for (int i = 0; i < kNumStrings; ++i) {
327 strings[i] = makeString(Length());
328 }
329 benchmark::DoNotOptimize(strings);
330 state.ResumeTiming();
331 for (int i = 0; i < kNumStrings; ++i) {
332 strings[i].erase(maybeOpaque(pos, opaque), maybeOpaque(n, opaque));
333 }
334 }
335 }
336
337 static std::string name() { return "BM_StringEraseWithMove" + Length::name() + Opaque::name(); }
338};
339
340template <class Opaque>
341struct StringAssignAsciizMix {
342 static void run(benchmark::State& state) {
343 constexpr auto O = Opaque{};
344 constexpr auto D = DiffType::Control;
345 constexpr int kNumStrings = 4 << 10;
346 std::string strings[kNumStrings];
347 while (state.KeepRunningBatch(kNumStrings)) {
348 state.PauseTiming();
349 for (int i = 0; i < kNumStrings; ++i) {
350 std::string().swap(strings[i]);
351 }
352 benchmark::DoNotOptimize(strings);
353 state.ResumeTiming();
354 for (int i = 0; i < kNumStrings - 7; i += 8) {
355 strings[i + 0] = maybeOpaque(getSmallString(D), O == Opacity::Opaque);
356 strings[i + 1] = maybeOpaque(getSmallString(D), O == Opacity::Opaque);
357 strings[i + 2] = maybeOpaque(getLargeString(D), O == Opacity::Opaque);
358 strings[i + 3] = maybeOpaque(getSmallString(D), O == Opacity::Opaque);
359 strings[i + 4] = maybeOpaque(getSmallString(D), O == Opacity::Opaque);
360 strings[i + 5] = maybeOpaque(getSmallString(D), O == Opacity::Opaque);
361 strings[i + 6] = maybeOpaque(getLargeString(D), O == Opacity::Opaque);
362 strings[i + 7] = maybeOpaque(getSmallString(D), O == Opacity::Opaque);
363 }
364 }
365 }
366
367 static std::string name() { return "BM_StringAssignAsciizMix" + Opaque::name(); }
368};
369
370enum class Relation { Eq, Less, Compare };
371struct AllRelations : EnumValuesAsTuple<AllRelations, Relation, 3> {
372 static constexpr const char* Names[] = {"Eq", "Less", "Compare"};
373};
374
375template <class Rel, class LHLength, class RHLength, class DiffType>
376struct StringRelational {
377 static void run(benchmark::State& state) {
378 auto Lhs = makeString(RHLength());
379 auto Rhs = makeString(LHLength(), DiffType());
380 for (auto _ : state) {
381 benchmark::DoNotOptimize(Lhs);
382 benchmark::DoNotOptimize(Rhs);
383 switch (Rel()) {
384 case Relation::Eq:
385 benchmark::DoNotOptimize(Lhs == Rhs);
386 break;
387 case Relation::Less:
388 benchmark::DoNotOptimize(Lhs < Rhs);
389 break;
390 case Relation::Compare:
391 benchmark::DoNotOptimize(Lhs.compare(Rhs));
392 break;
393 }
394 }
395 }
396
397 static bool skip() {
398 // Eq is commutative, so skip half the matrix.
399 if (Rel() == Relation::Eq && LHLength() > RHLength())
400 return true;
401 // We only care about control when the lengths differ.
402 if (LHLength() != RHLength() && DiffType() != ::DiffType::Control)
403 return true;
404 // For empty, only control matters.
405 if (LHLength() == Length::Empty && DiffType() != ::DiffType::Control)
406 return true;
407 return false;
408 }
409
410 static std::string name() {
411 return "BM_StringRelational" + Rel::name() + LHLength::name() + RHLength::name() + DiffType::name();
412 }
413};
414
415template <class Rel, class LHLength, class RHLength, class DiffType>
416struct StringRelationalLiteral {
417 static void run(benchmark::State& state) {
418 auto Lhs = makeString(LHLength(), DiffType());
419 for (auto _ : state) {
420 benchmark::DoNotOptimize(Lhs);
421 constexpr const char* Literal =
422 RHLength::value == Length::Empty ? ""
423 : RHLength::value == Length::Small
424 ? SmallStringLiteral
425 : LargeStringLiteral;
426 switch (Rel()) {
427 case Relation::Eq:
428 benchmark::DoNotOptimize(Lhs == Literal);
429 break;
430 case Relation::Less:
431 benchmark::DoNotOptimize(Lhs < Literal);
432 break;
433 case Relation::Compare:
434 benchmark::DoNotOptimize(Lhs.compare(Literal));
435 break;
436 }
437 }
438 }
439
440 static bool skip() {
441 // Doesn't matter how they differ if they have different size.
442 if (LHLength() != RHLength() && DiffType() != ::DiffType::Control)
443 return true;
444 // We don't need huge. Doensn't give anything different than Large.
445 if (LHLength() == Length::Huge || RHLength() == Length::Huge)
446 return true;
447 return false;
448 }
449
450 static std::string name() {
451 return "BM_StringRelationalLiteral" + Rel::name() + LHLength::name() + RHLength::name() + DiffType::name();
452 }
453};
454
455enum class Depth { Shallow, Deep };
456struct AllDepths : EnumValuesAsTuple<AllDepths, Depth, 2> {
457 static constexpr const char* Names[] = {"Shallow", "Deep"};
458};
459
460enum class Temperature { Hot, Cold };
461struct AllTemperatures : EnumValuesAsTuple<AllTemperatures, Temperature, 2> {
462 static constexpr const char* Names[] = {"Hot", "Cold"};
463};
464
465template <class Temperature, class Depth, class Length>
466struct StringRead {
467 void run(benchmark::State& state) const {
468 static constexpr size_t NumStrings =
469 Temperature() == ::Temperature::Hot ? 1 << 10 : /* Enough strings to overflow the cache */ 1 << 20;
470 static_assert((NumStrings & (NumStrings - 1)) == 0, "NumStrings should be a power of two to reduce overhead.");
471
472 std::vector<std::string> Values(NumStrings, makeString(Length()));
473 size_t I = 0;
474 for (auto _ : state) {
475 // Jump long enough to defeat cache locality, and use a value that is
476 // coprime with NumStrings to ensure we visit every element.
477 I = (I + 17) % NumStrings;
478 const auto& V = Values[I];
479
480 // Read everything first. Escaping data() through DoNotOptimize might
481 // cause the compiler to have to recalculate information about `V` due to
482 // aliasing.
483 const char* const Data = V.data();
484 const size_t Size = V.size();
485 benchmark::DoNotOptimize(Data);
486 benchmark::DoNotOptimize(Size);
487 if (Depth() == ::Depth::Deep) {
488 // Read into the payload. This mainly shows the benefit of SSO when the
489 // data is cold.
490 benchmark::DoNotOptimize(*Data);
491 }
492 }
493 }
494
495 static bool skip() {
496 // Huge does not give us anything that Large doesn't have. Skip it.
497 if (Length() == ::Length::Huge) {
498 return true;
499 }
500 return false;
501 }
502
503 std::string name() const { return "BM_StringRead" + Temperature::name() + Depth::name() + Length::name(); }
504};
505
506void sanityCheckGeneratedStrings() {
507 for (auto Lhs : {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
508 const auto LhsString = makeString(Lhs);
509 for (auto Rhs : {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
510 if (Lhs > Rhs)
511 continue;
512 const auto RhsString = makeString(Rhs);
513
514 // The smaller one must be a prefix of the larger one.
515 if (RhsString.find(LhsString) != 0) {
516 fprintf(
517 stderr, "Invalid autogenerated strings for sizes (%d,%d).\n", static_cast<int>(Lhs), static_cast<int>(Rhs));
518 std::abort();
519 }
520 }
521 }
522 // Verify the autogenerated diffs
523 for (auto L : {Length::Small, Length::Large, Length::Huge}) {
524 const auto Control = makeString(L);
525 const auto Verify = [&](std::string Exp, size_t Pos) {
526 // Only change on the Pos char.
527 if (Control[Pos] != Exp[Pos]) {
528 Exp[Pos] = Control[Pos];
529 if (Control == Exp)
530 return;
531 }
532 fprintf(stderr, "Invalid autogenerated diff with size %d\n", static_cast<int>(L));
533 std::abort();
534 };
535 Verify(makeString(L, DiffType::ChangeFirst), 0);
536 Verify(makeString(L, DiffType::ChangeMiddle), Control.size() / 2);
537 Verify(makeString(L, DiffType::ChangeLast), Control.size() - 1);
538 }
539}
540
541// Some small codegen thunks to easily see generated code.
542bool StringEqString(const std::string& a, const std::string& b) { return a == b; }
543bool StringEqCStr(const std::string& a, const char* b) { return a == b; }
544bool CStrEqString(const char* a, const std::string& b) { return a == b; }
545bool StringEqCStrLiteralEmpty(const std::string& a) { return a == ""; }
546bool StringEqCStrLiteralSmall(const std::string& a) { return a == SmallStringLiteral; }
547bool StringEqCStrLiteralLarge(const std::string& a) { return a == LargeStringLiteral; }
548
549int main(int argc, char** argv) {
550 benchmark::Initialize(&argc, argv);
551 if (benchmark::ReportUnrecognizedArguments(argc, argv))
552 return 1;
553
554 sanityCheckGeneratedStrings();
555
556 makeCartesianProductBenchmark<StringConstructDestroyCStr, AllLengths, AllOpacity>();
557
558 makeCartesianProductBenchmark<StringAssignStr, AllLengths, AllOpacity>();
559 makeCartesianProductBenchmark<StringAssignAsciiz, AllLengths, AllOpacity>();
560 makeCartesianProductBenchmark<StringAssignAsciizMix, AllOpacity>();
561
562 makeCartesianProductBenchmark<StringCopy, AllLengths>();
563 makeCartesianProductBenchmark<StringMove, AllLengths>();
564 makeCartesianProductBenchmark<StringDestroy, AllLengths>();
565 makeCartesianProductBenchmark<StringResizeDefaultInit, AllLengths, AllOpacity>();
566 makeCartesianProductBenchmark<StringEraseToEnd, AllLengths, AllOpacity>();
567 makeCartesianProductBenchmark<StringEraseWithMove, AllLengths, AllOpacity>();
568 makeCartesianProductBenchmark<StringRelational, AllRelations, AllLengths, AllLengths, AllDiffTypes>();
569 makeCartesianProductBenchmark<StringRelationalLiteral, AllRelations, AllLengths, AllLengths, AllDiffTypes>();
570 makeCartesianProductBenchmark<StringRead, AllTemperatures, AllDepths, AllLengths>();
571 benchmark::RunSpecifiedBenchmarks();
572
573 if (argc < 0) {
574 // ODR-use the functions to force them being generated in the binary.
575 auto functions = std::make_tuple(
576 StringEqString,
577 StringEqCStr,
578 CStrEqString,
579 StringEqCStrLiteralEmpty,
580 StringEqCStrLiteralSmall,
581 StringEqCStrLiteralLarge);
582 printf("%p", &functions);
583 }
584}
585