[MemFunctions] Add microbenchmarks for memory functions.

[courbet]

Summary

Memory functions (memcmp, memcpy, ...) are typically recognized by the
compiler and expanded to specific asm patterns when the size is known at
compile time.

This will help catch any regressions in expansions.

Right now we're only testing memcmp (see context in D60318).

[spatel]

Thanks for working on this! I'm not familiar with how the benchmarking framework works, so someone else should definitely have a look.

Does the framework automatically account for and filter out noisy results? I'm guessing that tiny memcmp() will have a lot of run-to-run variation.

[lebedev.ri]

In D64082#1566955, @spatel wrote:

Thanks for working on this! I'm not familiar with how the benchmarking framework works, so someone else should definitely have a look.

That could be me, i suppose.
Does not look too wrong to me.

Does the framework automatically account for and filter out noisy results? I'm guessing that tiny memcmp() will have a lot of run-to-run variation.

The for (auto _ : state) loop will run for up to 0.5 sec, so the results should be good;
Plus at the test-suite/lnt level the test suite can be run several times so it's possible ensure that timing changes are meaningful (U Test, e.g.)

MicroBenchmarks/MemFunctions/main.cpp

35–39

So what about q? It's intentionally left all-zeros? That warrants a comment.

83–95

I'd do one or two macro levels here

112–119

BENCHMARK_MAIN();

[courbet]

Address review comments.

[courbet]

Thanks Roman.

MicroBenchmarks/MemFunctions/main.cpp

112–119

Thanks for the pointer.

[courbet]

In D64082#1566955, @spatel wrote:

Thanks for working on this! I'm not familiar with how the benchmarking framework works, so someone else should definitely have a look.

Does the framework automatically account for and filter out noisy results? I'm guessing that tiny memcmp() will have a lot of run-to-run variation.

The framework will grow number of iterations until measurements stabilize. This is usually sufficient. However it will not do statistical significance testing for you (which is what I've done in the attached PDF just to be sure).

[lebedev.ri]

MicroBenchmarks/MemFunctions/main.cpp

44

This may be paranoia, but i'm not sure this is sufficient to guarantee that compiler *can't* just look into p/q.
I'd suggest adding this here:

benchmark::DoNotOptimize(p);
benchmark::DoNotOptimize(q);

benchmark::ClobberMemory(p);
benchmark::ClobberMemory(q);

(i see that you do that for std::vector<char>'s already, but you have already acquired _storage.data()..)

[courbet]

MicroBenchmarks/MemFunctions/main.cpp

44

Sounds reasonable. I've even moved the ClobberMemory inside the call (and verified that benchmark numbers do not change).

[courbet]

Be evel less permissive as to what we allow the compiler to see.

[lebedev.ri]

MicroBenchmarks/MemFunctions/main.cpp

30

Magical constant
I'm guessing that by 4096 you limit the maximal size of p and q buffers,
implying that they should fit into L1 cache?
Do you want to use the actual L1 size instead?
Otherwise,

static constexpr size_t kMaxBufSizeBytes = 4096;
constexpr size_t kNumElements = kMaxBufSizeBytes / kSize;

[courbet]

Name magical constant.

[courbet]

Add comment for buffer size.

[courbet]

MicroBenchmarks/MemFunctions/main.cpp

30

It's combination of things, among which caching. But you're right that this warrants a comment. Done.

[lebedev.ri]

Looks ok to me from benchmark perspective, but some more thoughts about the benchmark itself..

MicroBenchmarks/MemFunctions/main.cpp

44

Nice.

50

I think i'm forgetting about some magic.
All the predicates (EqZero, ...) take a single argument, how does this work if it passes two args?

58–66

To be noted, none of these is the actual memcmp, i think?

59

Does it matter that these take int while you always pass char?

[courbet]

Clarify top comment.

MicroBenchmarks/MemFunctions/main.cpp

50

I think you missed that the result of calling memcmp is passed to pred. Pred just defines which of ==, < or > we're benching. I updated the bench comment to make that clearer.

58–66

See my comment above.

59

See my comment above.

[lebedev.ri]

MicroBenchmarks/MemFunctions/main.cpp

50

Oh i see, that explains it, thanks!

[xbolva00]

lg too

[courbet]

Thanks!

MicroBenchmarks/CMakeLists.txt

 file(COPY lit.local.cfg DESTINATION ${CMAKE_CURRENT_BINARY_DIR})
 
 add_subdirectory(libs)
 add_subdirectory(XRay)
 add_subdirectory(LCALS)
 add_subdirectory(harris)
 add_subdirectory(ImageProcessing)
 add_subdirectory(LoopInterchange)
+add_subdirectory(MemFunctions)

MicroBenchmarks/MemFunctions/CMakeLists.txt

+llvm_test_run(WORKDIR ${CMAKE_CURRENT_BINARY_DIR})
+
+llvm_test_executable(MemFunctions main.cpp)
+
+target_link_libraries(MemFunctions benchmark)

MicroBenchmarks/MemFunctions/main.cpp

+//===- main.cc - Memory Functions Benchmarks ------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Memory functions (memcmp, memcpy, ...) are typically recognized by the
+// compiler and expanded to specific asm patterns when the size is known at
+// compile time. THese microbenchmarks help catch potential CodeGen regressions.
+//
+// Note that these microbenchmarks do not represent a typical real-life
+// situation. They are designed to test the LLVM CodeGen. In particular,
+// real-life applications will typically be memory- rather than compute-bound
+// when manipulating memory.
+//
+//===----------------------------------------------------------------------===//
+
+#include <cstring>
+#include <vector>
+
+#include "benchmark/benchmark.h"
+
+// Benchmarks memcmp(p, q, size) where n is known at compile time.
+// The compiler typically inlines this to loads and compares.
+template <int kSize, typename Pred, typename Mod>
+void BM_MemCmp(benchmark::State& state) {
+  static constexpr size_t kMaxBufSizeBytes = 4096;
+  constexpr const size_t kNumElements = kMaxBufSizeBytes / kSize;
+
+  std::vector<char> p_storage(kNumElements * kSize);
+  std::vector<char> q_storage(kNumElements * kSize);
+  char* p = p_storage.data();
+  const char* q = q_storage.data();
+
+  // We're comparing an all-zeros buffer (q) vs an all-zeros-but-one-element
+  // buffer (p). The non-zero element is detemined by `Mod`.
+  for (int i = 0; i < kNumElements; ++i)
+    Mod().template Change<kSize>(p + i * kSize);
+
+  benchmark::DoNotOptimize(p);
+  benchmark::DoNotOptimize(q);
+
+  for (auto _ : state) {
+    benchmark::ClobberMemory();
+    benchmark::ClobberMemory();
+
+    for (int i = 0; i < kNumElements; ++i) {
+      int res = Pred()(memcmp(p + i * kSize, q + i * kSize, kSize));
+      benchmark::DoNotOptimize(res);
+    }
+  }
+  state.SetBytesProcessed(p_storage.size() * state.iterations());
+}
+
+// Predicates.
+struct EqZero {
+  bool operator()(int v) const { return v == 0; }
+};
+struct LessThanZero {
+  bool operator()(int v) const { return v < 0; }
+};
+struct GreaterThanZero {
+  bool operator()(int v) const { return v > 0; }
+};
+
+// Functors to change the first/mid/last or no value.
+struct None {
+  template <int kSize>
+  void Change(char* const p) const {}
+};
+struct First {
+  template <int kSize>
+  void Change(char* const p) const {
+    p[0] = 128;
+  }
+};
+struct Mid {
+  template <int kSize>
+  void Change(char* const p) const {
+    p[kSize / 2] = 128;
+  }
+};
+struct Last {
+  template <int kSize>
+  void Change(char* const p) const {
+    p[kSize - 1] = 128;
+  }
+};
+
+#define MEMCMP_BENCHMARK_PRED_CHANGE(size, pred, change) \
+  BENCHMARK_TEMPLATE(BM_MemCmp, size, pred, change)      \
+      ->Unit(benchmark::kNanosecond);
+
+#define MEMCMP_BENCHMARK_PRED(size, pred)          \
+  MEMCMP_BENCHMARK_PRED_CHANGE(size, pred, None);  \
+  MEMCMP_BENCHMARK_PRED_CHANGE(size, pred, First); \
+  MEMCMP_BENCHMARK_PRED_CHANGE(size, pred, Mid);   \
+  MEMCMP_BENCHMARK_PRED_CHANGE(size, pred, Last);
+
+#define MEMCMP_BENCHMARK(size)              \
+  MEMCMP_BENCHMARK_PRED(size, EqZero)       \
+  MEMCMP_BENCHMARK_PRED(size, LessThanZero) \
+  MEMCMP_BENCHMARK_PRED(size, GreaterThanZero)
+
+MEMCMP_BENCHMARK(1)
+MEMCMP_BENCHMARK(2)
+MEMCMP_BENCHMARK(3)
+MEMCMP_BENCHMARK(4)
+MEMCMP_BENCHMARK(5)
+MEMCMP_BENCHMARK(6)
+MEMCMP_BENCHMARK(7)
+MEMCMP_BENCHMARK(8)
+MEMCMP_BENCHMARK(15)
+MEMCMP_BENCHMARK(16)
+MEMCMP_BENCHMARK(31)
+MEMCMP_BENCHMARK(32)
+MEMCMP_BENCHMARK(63)
+MEMCMP_BENCHMARK(64)
+
+BENCHMARK_MAIN();