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.
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.
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.
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.
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 
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 
76 static constexpr char SmallStringLiteral[] = "012345678";
77 
78 TEST_ALWAYS_INLINE const char* getSmallString(DiffType D) {
79   switch (D) {
80     case DiffType::Control:
81       return SmallStringLiteral;
82     case DiffType::ChangeFirst:
83       return "-12345678";
84     case DiffType::ChangeMiddle:
85       return "0123-5678";
86     case DiffType::ChangeLast:
87       return "01234567-";
88   }
89 }
90 
91 static constexpr char LargeStringLiteral[] =
92     "012345678901234567890123456789012345678901234567890123456789012";
93 
94 TEST_ALWAYS_INLINE const char* getLargeString(DiffType D) {
95 #define LARGE_STRING_FIRST "123456789012345678901234567890"
96 #define LARGE_STRING_SECOND "234567890123456789012345678901"
97   switch (D) {
98     case DiffType::Control:
99       return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
100     case DiffType::ChangeFirst:
101       return "-" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
102     case DiffType::ChangeMiddle:
103       return "0" LARGE_STRING_FIRST "-" LARGE_STRING_SECOND "2";
104     case DiffType::ChangeLast:
105       return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "-";
106   }
107 }
108 
109 TEST_ALWAYS_INLINE const char* getHugeString(DiffType D) {
110 #define HUGE_STRING0 "0123456789"
111 #define HUGE_STRING1 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0
112 #define HUGE_STRING2 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1
113 #define HUGE_STRING3 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2
114 #define HUGE_STRING4 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3
115   switch (D) {
116     case DiffType::Control:
117       return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
118     case DiffType::ChangeFirst:
119       return "-123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
120     case DiffType::ChangeMiddle:
121       return "0123456789" HUGE_STRING4 "01234-6789" HUGE_STRING4 "0123456789";
122     case DiffType::ChangeLast:
123       return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "012345678-";
124   }
125 }
126 
127 TEST_ALWAYS_INLINE std::string makeString(Length L,
128                                           DiffType D = DiffType::Control,
129                                           Opacity O = Opacity::Transparent) {
130   switch (L) {
131   case Length::Empty:
132     return maybeOpaque("", O == Opacity::Opaque);
133   case Length::Small:
134     return maybeOpaque(getSmallString(D), O == Opacity::Opaque);
135   case Length::Large:
136     return maybeOpaque(getLargeString(D), O == Opacity::Opaque);
137   case Length::Huge:
138     return maybeOpaque(getHugeString(D), O == Opacity::Opaque);
139   }
140 }
141 
142 template <class Length, class Opaque>
143 struct StringConstructDestroyCStr {
144   static void run(benchmark::State& state) {
145     for (auto _ : state) {
146       benchmark::DoNotOptimize(
147           makeString(Length(), DiffType::Control, Opaque()));
148     }
149   }
150 
151   static std::string name() {
152     return "BM_StringConstructDestroyCStr" + Length::name() + Opaque::name();
153   }
154 };
155 
156 template <class Length, bool MeasureCopy, bool MeasureDestroy>
157 static void StringCopyAndDestroy(benchmark::State& state) {
158   static constexpr size_t NumStrings = 1024;
159   auto Orig = makeString(Length());
160   std::aligned_storage<sizeof(std::string)>::type Storage[NumStrings];
161 
162   while (state.KeepRunningBatch(NumStrings)) {
163     if (!MeasureCopy)
164       state.PauseTiming();
165     for (size_t I = 0; I < NumStrings; ++I) {
166       ::new (static_cast<void*>(Storage + I)) std::string(Orig);
167     }
168     if (!MeasureCopy)
169       state.ResumeTiming();
170     if (!MeasureDestroy)
171       state.PauseTiming();
172     for (size_t I = 0; I < NumStrings; ++I) {
173       using S = std::string;
174       reinterpret_cast<S*>(Storage + I)->~S();
175     }
176     if (!MeasureDestroy)
177       state.ResumeTiming();
178   }
179 }
180 
181 template <class Length>
182 struct StringCopy {
183   static void run(benchmark::State& state) {
184     StringCopyAndDestroy<Length, true, false>(state);
185   }
186 
187   static std::string name() { return "BM_StringCopy" + Length::name(); }
188 };
189 
190 template <class Length>
191 struct StringDestroy {
192   static void run(benchmark::State& state) {
193     StringCopyAndDestroy<Length, false, true>(state);
194   }
195 
196   static std::string name() { return "BM_StringDestroy" + Length::name(); }
197 };
198 
199 template <class Length>
200 struct StringMove {
201   static void run(benchmark::State& state) {
202     // Keep two object locations and move construct back and forth.
203     std::aligned_storage<sizeof(std::string), alignof(std::string)>::type Storage[2];
204     using S = std::string;
205     size_t I = 0;
206     S *newS = new (static_cast<void*>(Storage)) std::string(makeString(Length()));
207     for (auto _ : state) {
208       // Switch locations.
209       I ^= 1;
210       benchmark::DoNotOptimize(Storage);
211       // Move construct into the new location,
212       S *tmpS = new (static_cast<void*>(Storage + I)) S(std::move(*newS));
213       // then destroy the old one.
214       newS->~S();
215       newS = tmpS;
216     }
217     newS->~S();
218   }
219 
220   static std::string name() { return "BM_StringMove" + Length::name(); }
221 };
222 
223 enum class Relation { Eq, Less, Compare };
224 struct AllRelations : EnumValuesAsTuple<AllRelations, Relation, 3> {
225   static constexpr const char* Names[] = {"Eq", "Less", "Compare"};
226 };
227 
228 template <class Rel, class LHLength, class RHLength, class DiffType>
229 struct StringRelational {
230   static void run(benchmark::State& state) {
231     auto Lhs = makeString(RHLength());
232     auto Rhs = makeString(LHLength(), DiffType());
233     for (auto _ : state) {
234       benchmark::DoNotOptimize(Lhs);
235       benchmark::DoNotOptimize(Rhs);
236       switch (Rel()) {
237       case Relation::Eq:
238         benchmark::DoNotOptimize(Lhs == Rhs);
239         break;
240       case Relation::Less:
241         benchmark::DoNotOptimize(Lhs < Rhs);
242         break;
243       case Relation::Compare:
244         benchmark::DoNotOptimize(Lhs.compare(Rhs));
245         break;
246       }
247     }
248   }
249 
250   static bool skip() {
251     // Eq is commutative, so skip half the matrix.
252     if (Rel() == Relation::Eq && LHLength() > RHLength())
253       return true;
254     // We only care about control when the lengths differ.
255     if (LHLength() != RHLength() && DiffType() != ::DiffType::Control)
256       return true;
257     // For empty, only control matters.
258     if (LHLength() == Length::Empty && DiffType() != ::DiffType::Control)
259       return true;
260     return false;
261   }
262 
263   static std::string name() {
264     return "BM_StringRelational" + Rel::name() + LHLength::name() +
265            RHLength::name() + DiffType::name();
266   }
267 };
268 
269 template <class Rel, class LHLength, class RHLength, class DiffType>
270 struct StringRelationalLiteral {
271   static void run(benchmark::State& state) {
272     auto Lhs = makeString(LHLength(), DiffType());
273     for (auto _ : state) {
274       benchmark::DoNotOptimize(Lhs);
275       constexpr const char* Literal = RHLength::value == Length::Empty
276                                           ? ""
277                                           : RHLength::value == Length::Small
278                                                 ? SmallStringLiteral
279                                                 : LargeStringLiteral;
280       switch (Rel()) {
281       case Relation::Eq:
282         benchmark::DoNotOptimize(Lhs == Literal);
283         break;
284       case Relation::Less:
285         benchmark::DoNotOptimize(Lhs < Literal);
286         break;
287       case Relation::Compare:
288         benchmark::DoNotOptimize(Lhs.compare(Literal));
289         break;
290       }
291     }
292   }
293 
294   static bool skip() {
295     // Doesn't matter how they differ if they have different size.
296     if (LHLength() != RHLength() && DiffType() != ::DiffType::Control)
297       return true;
298     // We don't need huge. Doensn't give anything different than Large.
299     if (LHLength() == Length::Huge || RHLength() == Length::Huge)
300       return true;
301     return false;
302   }
303 
304   static std::string name() {
305     return "BM_StringRelationalLiteral" + Rel::name() + LHLength::name() +
306            RHLength::name() + DiffType::name();
307   }
308 };
309 
310 enum class Depth { Shallow, Deep };
311 struct AllDepths : EnumValuesAsTuple<AllDepths, Depth, 2> {
312   static constexpr const char* Names[] = {"Shallow", "Deep"};
313 };
314 
315 enum class Temperature { Hot, Cold };
316 struct AllTemperatures : EnumValuesAsTuple<AllTemperatures, Temperature, 2> {
317   static constexpr const char* Names[] = {"Hot", "Cold"};
318 };
319 
320 template <class Temperature, class Depth, class Length>
321 struct StringRead {
322   void run(benchmark::State& state) const {
323     static constexpr size_t NumStrings =
324         Temperature() == ::Temperature::Hot
325             ? 1 << 10
326             : /* Enough strings to overflow the cache */ 1 << 20;
327     static_assert((NumStrings & (NumStrings - 1)) == 0,
328                   "NumStrings should be a power of two to reduce overhead.");
329 
330     std::vector<std::string> Values(NumStrings, makeString(Length()));
331     size_t I = 0;
332     for (auto _ : state) {
333       // Jump long enough to defeat cache locality, and use a value that is
334       // coprime with NumStrings to ensure we visit every element.
335       I = (I + 17) % NumStrings;
336       const auto& V = Values[I];
337 
338       // Read everything first. Escaping data() through DoNotOptimize might
339       // cause the compiler to have to recalculate information about `V` due to
340       // aliasing.
341       const char* const Data = V.data();
342       const size_t Size = V.size();
343       benchmark::DoNotOptimize(Data);
344       benchmark::DoNotOptimize(Size);
345       if (Depth() == ::Depth::Deep) {
346         // Read into the payload. This mainly shows the benefit of SSO when the
347         // data is cold.
348         benchmark::DoNotOptimize(*Data);
349       }
350     }
351   }
352 
353   static bool skip() {
354     // Huge does not give us anything that Large doesn't have. Skip it.
355     if (Length() == ::Length::Huge) {
356       return true;
357     }
358     return false;
359   }
360 
361   std::string name() const {
362     return "BM_StringRead" + Temperature::name() + Depth::name() +
363            Length::name();
364   }
365 };
366 
367 void sanityCheckGeneratedStrings() {
368   for (auto Lhs : {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
369     const auto LhsString = makeString(Lhs);
370     for (auto Rhs :
371          {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
372       if (Lhs > Rhs)
373         continue;
374       const auto RhsString = makeString(Rhs);
375 
376       // The smaller one must be a prefix of the larger one.
377       if (RhsString.find(LhsString) != 0) {
378         fprintf(stderr, "Invalid autogenerated strings for sizes (%d,%d).\n",
379                 static_cast<int>(Lhs), static_cast<int>(Rhs));
380         std::abort();
381       }
382     }
383   }
384   // Verify the autogenerated diffs
385   for (auto L : {Length::Small, Length::Large, Length::Huge}) {
386     const auto Control = makeString(L);
387     const auto Verify = [&](std::string Exp, size_t Pos) {
388       // Only change on the Pos char.
389       if (Control[Pos] != Exp[Pos]) {
390         Exp[Pos] = Control[Pos];
391         if (Control == Exp)
392           return;
393       }
394       fprintf(stderr, "Invalid autogenerated diff with size %d\n",
395               static_cast<int>(L));
396       std::abort();
397     };
398     Verify(makeString(L, DiffType::ChangeFirst), 0);
399     Verify(makeString(L, DiffType::ChangeMiddle), Control.size() / 2);
400     Verify(makeString(L, DiffType::ChangeLast), Control.size() - 1);
401   }
402 }
403 
404 // Some small codegen thunks to easily see generated code.
405 bool StringEqString(const std::string& a, const std::string& b) {
406   return a == b;
407 }
408 bool StringEqCStr(const std::string& a, const char* b) { return a == b; }
409 bool CStrEqString(const char* a, const std::string& b) { return a == b; }
410 bool StringEqCStrLiteralEmpty(const std::string& a) {
411   return a == "";
412 }
413 bool StringEqCStrLiteralSmall(const std::string& a) {
414   return a == SmallStringLiteral;
415 }
416 bool StringEqCStrLiteralLarge(const std::string& a) {
417   return a == LargeStringLiteral;
418 }
419 
420 int main(int argc, char** argv) {
421   benchmark::Initialize(&argc, argv);
422   if (benchmark::ReportUnrecognizedArguments(argc, argv))
423     return 1;
424 
425   sanityCheckGeneratedStrings();
426 
427   makeCartesianProductBenchmark<StringConstructDestroyCStr, AllLengths,
428                                 AllOpacity>();
429   makeCartesianProductBenchmark<StringCopy, AllLengths>();
430   makeCartesianProductBenchmark<StringMove, AllLengths>();
431   makeCartesianProductBenchmark<StringDestroy, AllLengths>();
432   makeCartesianProductBenchmark<StringRelational, AllRelations, AllLengths,
433                                 AllLengths, AllDiffTypes>();
434   makeCartesianProductBenchmark<StringRelationalLiteral, AllRelations,
435                                 AllLengths, AllLengths, AllDiffTypes>();
436   makeCartesianProductBenchmark<StringRead, AllTemperatures, AllDepths,
437                                 AllLengths>();
438   benchmark::RunSpecifiedBenchmarks();
439 
440   if (argc < 0) {
441     // ODR-use the functions to force them being generated in the binary.
442     auto functions = std::make_tuple(
443         StringEqString, StringEqCStr, CStrEqString, StringEqCStrLiteralEmpty,
444         StringEqCStrLiteralSmall, StringEqCStrLiteralLarge);
445     printf("%p", &functions);
446   }
447 }
448