string.bench.cpp 15 KB

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