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