6 #include "CartesianBenchmarks.h"
7 #include "GenerateInput.h"
8 #include "benchmark/benchmark.h"
9 #include "test_macros.h"
11 constexpr std::size_t MAX_STRING_LEN
= 8 << 14;
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, '*');
18 benchmark::DoNotOptimize(s1
.find(s2
));
20 BENCHMARK(BM_StringFindNoMatch
)->Range(10, MAX_STRING_LEN
);
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), '-');
27 benchmark::DoNotOptimize(s1
.find(s2
));
29 BENCHMARK(BM_StringFindAllMatch
)->Range(1, MAX_STRING_LEN
);
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), '-');
37 benchmark::DoNotOptimize(s1
.find(s2
));
39 BENCHMARK(BM_StringFindMatch1
)->Range(1, MAX_STRING_LEN
/ 4);
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), '-');
48 benchmark::DoNotOptimize(s1
.find(s2
));
50 BENCHMARK(BM_StringFindMatch2
)->Range(1, MAX_STRING_LEN
/ 4);
52 static void BM_StringCtorDefault(benchmark::State
& state
) {
53 for (auto _
: state
) {
55 benchmark::DoNotOptimize(Default
);
58 BENCHMARK(BM_StringCtorDefault
);
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"};
65 enum class Opacity
{ Opaque
, Transparent
};
66 struct AllOpacity
: EnumValuesAsTuple
<AllOpacity
, Opacity
, 2> {
67 static constexpr const char* Names
[] = {"Opaque", "Transparent"};
70 enum class DiffType
{ Control
, ChangeFirst
, ChangeMiddle
, ChangeLast
};
71 struct AllDiffTypes
: EnumValuesAsTuple
<AllDiffTypes
, DiffType
, 4> {
72 static constexpr const char* Names
[] = {"Control", "ChangeFirst", "ChangeMiddle", "ChangeLast"};
75 static constexpr char SmallStringLiteral
[] = "012345678";
77 TEST_ALWAYS_INLINE
const char* getSmallString(DiffType D
) {
79 case DiffType::Control
:
80 return SmallStringLiteral
;
81 case DiffType::ChangeFirst
:
83 case DiffType::ChangeMiddle
:
85 case DiffType::ChangeLast
:
90 static constexpr char LargeStringLiteral
[] = "012345678901234567890123456789012345678901234567890123456789012";
92 TEST_ALWAYS_INLINE
const char* getLargeString(DiffType D
) {
93 #define LARGE_STRING_FIRST "123456789012345678901234567890"
94 #define LARGE_STRING_SECOND "234567890123456789012345678901"
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
"-";
107 TEST_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
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-";
125 TEST_ALWAYS_INLINE
const char* getString(Length L
, DiffType D
= DiffType::Control
) {
130 return getSmallString(D
);
132 return getLargeString(D
);
134 return getHugeString(D
);
138 TEST_ALWAYS_INLINE
std::string
makeString(Length L
, DiffType D
= DiffType::Control
, Opacity O
= Opacity::Transparent
) {
141 return maybeOpaque("", O
== Opacity::Opaque
);
143 return maybeOpaque(getSmallString(D
), O
== Opacity::Opaque
);
145 return maybeOpaque(getLargeString(D
), O
== Opacity::Opaque
);
147 return maybeOpaque(getHugeString(D
), O
== Opacity::Opaque
);
151 template <class Length
, class Opaque
>
152 struct StringConstructDestroyCStr
{
153 static void run(benchmark::State
& state
) {
154 for (auto _
: state
) {
155 benchmark::DoNotOptimize(makeString(Length(), DiffType::Control
, Opaque()));
159 static std::string
name() { return "BM_StringConstructDestroyCStr" + Length::name() + Opaque::name(); }
162 template <class Length
, bool MeasureCopy
, bool MeasureDestroy
>
163 static 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
];
168 while (state
.KeepRunningBatch(NumStrings
)) {
171 for (size_t I
= 0; I
< NumStrings
; ++I
) {
172 ::new (static_cast<void*>(Storage
+ I
)) std::string(Orig
);
175 state
.ResumeTiming();
178 for (size_t I
= 0; I
< NumStrings
; ++I
) {
179 using S
= std::string
;
180 reinterpret_cast<S
*>(Storage
+ I
)->~S();
183 state
.ResumeTiming();
187 template <class Length
>
189 static void run(benchmark::State
& state
) { StringCopyAndDestroy
<Length
, true, false>(state
); }
191 static std::string
name() { return "BM_StringCopy" + Length::name(); }
194 template <class Length
>
195 struct StringDestroy
{
196 static void run(benchmark::State
& state
) { StringCopyAndDestroy
<Length
, false, true>(state
); }
198 static std::string
name() { return "BM_StringDestroy" + Length::name(); }
201 template <class Length
>
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
;
208 S
* newS
= new (static_cast<void*>(Storage
)) std::string(makeString(Length()));
209 for (auto _
: state
) {
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.
222 static std::string
name() { return "BM_StringMove" + Length::name(); }
225 template <class Length
, class Opaque
>
226 struct 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
)) {
234 for (int i
= 0; i
< kNumStrings
; ++i
) {
235 std::string().swap(strings
[i
]);
237 benchmark::DoNotOptimize(strings
);
238 state
.ResumeTiming();
239 for (int i
= 0; i
< kNumStrings
; ++i
) {
240 strings
[i
].__resize_default_init(maybeOpaque(length
, opaque
));
245 static std::string
name() { return "BM_StringResizeDefaultInit" + Length::name() + Opaque::name(); }
248 template <class Length
, class Opaque
>
249 struct 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
)) {
257 for (int i
= 0; i
< kNumStrings
; ++i
) {
258 std::string().swap(strings
[i
]);
260 benchmark::DoNotOptimize(strings
);
261 state
.ResumeTiming();
262 for (int i
= 0; i
< kNumStrings
; ++i
) {
263 strings
[i
] = *maybeOpaque(&src
, opaque
);
268 static std::string
name() { return "BM_StringAssignStr" + Length::name() + Opaque::name(); }
271 template <class Length
, class Opaque
>
272 struct 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
)) {
279 for (int i
= 0; i
< kNumStrings
; ++i
) {
280 std::string().swap(strings
[i
]);
282 benchmark::DoNotOptimize(strings
);
283 state
.ResumeTiming();
284 for (int i
= 0; i
< kNumStrings
; ++i
) {
285 strings
[i
] = maybeOpaque(getString(Length()), opaque
);
290 static std::string
name() { return "BM_StringAssignAsciiz" + Length::name() + Opaque::name(); }
293 template <class Length
, class Opaque
>
294 struct 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
)) {
302 for (int i
= 0; i
< kNumStrings
; ++i
) {
303 strings
[i
] = makeString(Length());
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
));
313 static std::string
name() { return "BM_StringEraseToEnd" + Length::name() + Opaque::name(); }
316 template <class Length
, class Opaque
>
317 struct 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
)) {
326 for (int i
= 0; i
< kNumStrings
; ++i
) {
327 strings
[i
] = makeString(Length());
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
));
337 static std::string
name() { return "BM_StringEraseWithMove" + Length::name() + Opaque::name(); }
340 template <class Opaque
>
341 struct 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
)) {
349 for (int i
= 0; i
< kNumStrings
; ++i
) {
350 std::string().swap(strings
[i
]);
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
);
367 static std::string
name() { return "BM_StringAssignAsciizMix" + Opaque::name(); }
370 enum class Relation
{ Eq
, Less
, Compare
};
371 struct AllRelations
: EnumValuesAsTuple
<AllRelations
, Relation
, 3> {
372 static constexpr const char* Names
[] = {"Eq", "Less", "Compare"};
375 template <class Rel
, class LHLength
, class RHLength
, class DiffType
>
376 struct 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
);
385 benchmark::DoNotOptimize(Lhs
== Rhs
);
388 benchmark::DoNotOptimize(Lhs
< Rhs
);
390 case Relation::Compare
:
391 benchmark::DoNotOptimize(Lhs
.compare(Rhs
));
398 // Eq is commutative, so skip half the matrix.
399 if (Rel() == Relation::Eq
&& LHLength() > RHLength())
401 // We only care about control when the lengths differ.
402 if (LHLength() != RHLength() && DiffType() != ::DiffType::Control
)
404 // For empty, only control matters.
405 if (LHLength() == Length::Empty
&& DiffType() != ::DiffType::Control
)
410 static std::string
name() {
411 return "BM_StringRelational" + Rel::name() + LHLength::name() + RHLength::name() + DiffType::name();
415 template <class Rel
, class LHLength
, class RHLength
, class DiffType
>
416 struct 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
425 : LargeStringLiteral
;
428 benchmark::DoNotOptimize(Lhs
== Literal
);
431 benchmark::DoNotOptimize(Lhs
< Literal
);
433 case Relation::Compare
:
434 benchmark::DoNotOptimize(Lhs
.compare(Literal
));
441 // Doesn't matter how they differ if they have different size.
442 if (LHLength() != RHLength() && DiffType() != ::DiffType::Control
)
444 // We don't need huge. Doensn't give anything different than Large.
445 if (LHLength() == Length::Huge
|| RHLength() == Length::Huge
)
450 static std::string
name() {
451 return "BM_StringRelationalLiteral" + Rel::name() + LHLength::name() + RHLength::name() + DiffType::name();
455 enum class Depth
{ Shallow
, Deep
};
456 struct AllDepths
: EnumValuesAsTuple
<AllDepths
, Depth
, 2> {
457 static constexpr const char* Names
[] = {"Shallow", "Deep"};
460 enum class Temperature
{ Hot
, Cold
};
461 struct AllTemperatures
: EnumValuesAsTuple
<AllTemperatures
, Temperature
, 2> {
462 static constexpr const char* Names
[] = {"Hot", "Cold"};
465 template <class Temperature
, class Depth
, class Length
>
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.");
472 std::vector
<std::string
> Values(NumStrings
, makeString(Length()));
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
];
480 // Read everything first. Escaping data() through DoNotOptimize might
481 // cause the compiler to have to recalculate information about `V` due to
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
490 benchmark::DoNotOptimize(*Data
);
496 // Huge does not give us anything that Large doesn't have. Skip it.
497 if (Length() == ::Length::Huge
) {
503 std::string
name() const { return "BM_StringRead" + Temperature::name() + Depth::name() + Length::name(); }
506 void 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
}) {
512 const auto RhsString
= makeString(Rhs
);
514 // The smaller one must be a prefix of the larger one.
515 if (RhsString
.find(LhsString
) != 0) {
517 stderr
, "Invalid autogenerated strings for sizes (%d,%d).\n", static_cast<int>(Lhs
), static_cast<int>(Rhs
));
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
];
532 fprintf(stderr
, "Invalid autogenerated diff with size %d\n", static_cast<int>(L
));
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);
541 // Some small codegen thunks to easily see generated code.
542 bool StringEqString(const std::string
& a
, const std::string
& b
) { return a
== b
; }
543 bool StringEqCStr(const std::string
& a
, const char* b
) { return a
== b
; }
544 bool CStrEqString(const char* a
, const std::string
& b
) { return a
== b
; }
545 bool StringEqCStrLiteralEmpty(const std::string
& a
) { return a
== ""; }
546 bool StringEqCStrLiteralSmall(const std::string
& a
) { return a
== SmallStringLiteral
; }
547 bool StringEqCStrLiteralLarge(const std::string
& a
) { return a
== LargeStringLiteral
; }
549 int main(int argc
, char** argv
) {
550 benchmark::Initialize(&argc
, argv
);
551 if (benchmark::ReportUnrecognizedArguments(argc
, argv
))
554 sanityCheckGeneratedStrings();
556 makeCartesianProductBenchmark
<StringConstructDestroyCStr
, AllLengths
, AllOpacity
>();
558 makeCartesianProductBenchmark
<StringAssignStr
, AllLengths
, AllOpacity
>();
559 makeCartesianProductBenchmark
<StringAssignAsciiz
, AllLengths
, AllOpacity
>();
560 makeCartesianProductBenchmark
<StringAssignAsciizMix
, AllOpacity
>();
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();
574 // ODR-use the functions to force them being generated in the binary.
575 auto functions
= std::make_tuple(
579 StringEqCStrLiteralEmpty
,
580 StringEqCStrLiteralSmall
,
581 StringEqCStrLiteralLarge
);
582 printf("%p", &functions
);