libcxx

libcxx mirror with random patches
git clone https://git.neptards.moe/neptards/libcxx.git
Log | Files | Refs

string.bench.cpp (12623B)

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