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

source code of libcxx/test/benchmarks/containers/string.bench.cpp