libc/benchmarks/LibcMemoryBenchmark.h

   1 //===-- Benchmark memory specific tools -------------------------*- C++ -*-===//
   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 // This file complements the `benchmark` header with memory specific tools and
  10 // benchmarking facilities.
  11
  12 #ifndef LLVM_LIBC_UTILS_BENCHMARK_MEMORY_BENCHMARK_H
  13 #define LLVM_LIBC_UTILS_BENCHMARK_MEMORY_BENCHMARK_H
  14
  15 #include "LibcBenchmark.h"
  16 #include "LibcFunctionPrototypes.h"
  17 #include "MemorySizeDistributions.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/Support/Alignment.h"
  20 #include <cstdint>
  21 #include <optional>
  22 #include <random>
  23
  24 namespace llvm {
  25 namespace libc_benchmarks {
  26
  27 //--------------
  28 // Configuration
  29 //--------------
  30
  31 struct StudyConfiguration {
  32   // One of 'memcpy', 'memset', 'memcmp'.
  33   // The underlying implementation is always the llvm libc one.
  34   // e.g. 'memcpy' will test '__llvm_libc::memcpy'
  35   std::string Function;
  36
  37   // The number of trials to run for this benchmark.
  38   // If in SweepMode, each individual sizes are measured 'NumTrials' time.
  39   // i.e 'NumTrials' measurements for 0, 'NumTrials' measurements for 1 ...
  40   uint32_t NumTrials = 1;
  41
  42   // Toggles between Sweep Mode and Distribution Mode (default).
  43   // See 'SweepModeMaxSize' and 'SizeDistributionName' below.
  44   bool IsSweepMode = false;
  45
  46   // Maximum size to use when measuring a ramp of size values (SweepMode).
  47   // The benchmark measures all sizes from 0 to SweepModeMaxSize.
  48   // Note: in sweep mode the same size is sampled several times in a row this
  49   // will allow the processor to learn it and optimize the branching pattern.
  50   // The resulting measurement is likely to be idealized.
  51   uint32_t SweepModeMaxSize = 0; // inclusive
  52
  53   // The name of the distribution to be used to randomize the size parameter.
  54   // This is used when SweepMode is false (default).
  55   std::string SizeDistributionName;
  56
  57   // This parameter allows to control how the buffers are accessed during
  58   // benchmark:
  59   // None : Use a fixed address that is at least cache line aligned,
  60   //    1 : Use random address,
  61   //   >1 : Use random address aligned to value.
  62   MaybeAlign AccessAlignment = std::nullopt;
  63
  64   // When Function == 'memcmp', this is the buffers mismatch position.
  65   //  0 : Buffers always compare equal,
  66   // >0 : Buffers compare different at byte N-1.
  67   uint32_t MemcmpMismatchAt = 0;
  68 };
  69
  70 struct Runtime {
  71   // Details about the Host (cpu name, cpu frequency, cache hierarchy).
  72   HostState Host;
  73
  74   // The framework will populate this value so all data accessed during the
  75   // benchmark will stay in L1 data cache. This includes bookkeeping data.
  76   uint32_t BufferSize = 0;
  77
  78   // This is the number of distinct parameters used in a single batch.
  79   // The framework always tests a batch of randomized parameter to prevent the
  80   // cpu from learning branching patterns.
  81   uint32_t BatchParameterCount = 0;
  82
  83   // The benchmark options that were used to perform the measurement.
  84   // This is decided by the framework.
  85   BenchmarkOptions BenchmarkOptions;
  86 };
  87
  88 //--------
  89 // Results
  90 //--------
  91
  92 // The root object containing all the data (configuration and measurements).
  93 struct Study {
  94   std::string StudyName;
  95   Runtime Runtime;
  96   StudyConfiguration Configuration;
  97   std::vector<Duration> Measurements;
  98 };
  99
 100 //------
 101 // Utils
 102 //------
 103
 104 // Provides an aligned, dynamically allocated buffer.
 105 class AlignedBuffer {
 106   char *const Buffer = nullptr;
 107   size_t Size = 0;
 108
 109 public:
 110   // Note: msan / asan can't handle Alignment > 512.
 111   static constexpr size_t Alignment = 512;
 112
 113   explicit AlignedBuffer(size_t Size)
 114       : Buffer(static_cast<char *>(aligned_alloc(Alignment, Size))),
 115         Size(Size) {}
 116   ~AlignedBuffer() { free(Buffer); }
 117
 118   inline char *operator+(size_t Index) { return Buffer + Index; }
 119   inline const char *operator+(size_t Index) const { return Buffer + Index; }
 120   inline char &operator[](size_t Index) { return Buffer[Index]; }
 121   inline const char &operator[](size_t Index) const { return Buffer[Index]; }
 122   inline char *begin() { return Buffer; }
 123   inline char *end() { return Buffer + Size; }
 124 };
 125
 126 // Helper to generate random buffer offsets that satisfy the configuration
 127 // constraints.
 128 class OffsetDistribution {
 129   std::uniform_int_distribution<uint32_t> Distribution;
 130   uint32_t Factor;
 131
 132 public:
 133   explicit OffsetDistribution(size_t BufferSize, size_t MaxSizeValue,
 134                               MaybeAlign AccessAlignment);
 135
 136   template <class Generator> uint32_t operator()(Generator &G) {
 137     return Distribution(G) * Factor;
 138   }
 139 };
 140
 141 // Helper to generate random buffer offsets that satisfy the configuration
 142 // constraints. It is specifically designed to benchmark `memcmp` functions
 143 // where we may want the Nth byte to differ.
 144 class MismatchOffsetDistribution {
 145   std::uniform_int_distribution<size_t> MismatchIndexSelector;
 146   llvm::SmallVector<uint32_t, 16> MismatchIndices;
 147   const uint32_t MismatchAt;
 148
 149 public:
 150   explicit MismatchOffsetDistribution(size_t BufferSize, size_t MaxSizeValue,
 151                                       size_t MismatchAt);
 152
 153   explicit operator bool() const { return !MismatchIndices.empty(); }
 154
 155   const llvm::SmallVectorImpl<uint32_t> &getMismatchIndices() const {
 156     return MismatchIndices;
 157   }
 158
 159   template <class Generator> uint32_t operator()(Generator &G, uint32_t Size) {
 160     const uint32_t MismatchIndex = MismatchIndices[MismatchIndexSelector(G)];
 161     // We need to position the offset so that a mismatch occurs at MismatchAt.
 162     if (Size >= MismatchAt)
 163       return MismatchIndex - MismatchAt;
 164     // Size is too small to trigger the mismatch.
 165     return MismatchIndex - Size - 1;
 166   }
 167 };
 168
 169 /// This structure holds a vector of ParameterType.
 170 /// It makes sure that BufferCount x BufferSize Bytes and the vector of
 171 /// ParameterType can all fit in the L1 cache.
 172 struct ParameterBatch {
 173   struct ParameterType {
 174     unsigned OffsetBytes : 16; // max : 16 KiB - 1
 175     unsigned SizeBytes : 16;   // max : 16 KiB - 1
 176   };
 177
 178   ParameterBatch(size_t BufferCount);
 179
 180   /// Verifies that memory accessed through this parameter is valid.
 181   void checkValid(const ParameterType &) const;
 182
 183   /// Computes the number of bytes processed during within this batch.
 184   size_t getBatchBytes() const;
 185
 186   const size_t BufferSize;
 187   const size_t BatchSize;
 188   std::vector<ParameterType> Parameters;
 189 };
 190
 191 /// Provides source and destination buffers for the Copy operation as well as
 192 /// the associated size distributions.
 193 struct CopySetup : public ParameterBatch {
 194   CopySetup();
 195
 196   inline static const ArrayRef<MemorySizeDistribution> getDistributions() {
 197     return getMemcpySizeDistributions();
 198   }
 199
 200   inline void *Call(ParameterType Parameter, MemcpyFunction Memcpy) {
 201     return Memcpy(DstBuffer + Parameter.OffsetBytes,
 202                   SrcBuffer + Parameter.OffsetBytes, Parameter.SizeBytes);
 203   }
 204
 205 private:
 206   AlignedBuffer SrcBuffer;
 207   AlignedBuffer DstBuffer;
 208 };
 209
 210 /// Provides source and destination buffers for the Move operation as well as
 211 /// the associated size distributions.
 212 struct MoveSetup : public ParameterBatch {
 213   MoveSetup();
 214
 215   inline static const ArrayRef<MemorySizeDistribution> getDistributions() {
 216     return getMemmoveSizeDistributions();
 217   }
 218
 219   inline void *Call(ParameterType Parameter, MemmoveFunction Memmove) {
 220     return Memmove(Buffer + ParameterBatch::BufferSize / 3,
 221                    Buffer + Parameter.OffsetBytes, Parameter.SizeBytes);
 222   }
 223
 224 private:
 225   AlignedBuffer Buffer;
 226 };
 227
 228 /// Provides destination buffer for the Set operation as well as the associated
 229 /// size distributions.
 230 struct SetSetup : public ParameterBatch {
 231   SetSetup();
 232
 233   inline static const ArrayRef<MemorySizeDistribution> getDistributions() {
 234     return getMemsetSizeDistributions();
 235   }
 236
 237   inline void *Call(ParameterType Parameter, MemsetFunction Memset) {
 238     return Memset(DstBuffer + Parameter.OffsetBytes,
 239                   Parameter.OffsetBytes % 0xFF, Parameter.SizeBytes);
 240   }
 241
 242   inline void *Call(ParameterType Parameter, BzeroFunction Bzero) {
 243     Bzero(DstBuffer + Parameter.OffsetBytes, Parameter.SizeBytes);
 244     return DstBuffer.begin();
 245   }
 246
 247 private:
 248   AlignedBuffer DstBuffer;
 249 };
 250
 251 /// Provides left and right buffers for the Comparison operation as well as the
 252 /// associated size distributions.
 253 struct ComparisonSetup : public ParameterBatch {
 254   ComparisonSetup();
 255
 256   inline static const ArrayRef<MemorySizeDistribution> getDistributions() {
 257     return getMemcmpSizeDistributions();
 258   }
 259
 260   inline int Call(ParameterType Parameter, MemcmpOrBcmpFunction MemcmpOrBcmp) {
 261     return MemcmpOrBcmp(LhsBuffer + Parameter.OffsetBytes,
 262                         RhsBuffer + Parameter.OffsetBytes, Parameter.SizeBytes);
 263   }
 264
 265 private:
 266   AlignedBuffer LhsBuffer;
 267   AlignedBuffer RhsBuffer;
 268 };
 269
 270 } // namespace libc_benchmarks
 271 } // namespace llvm
 272
 273 #endif // LLVM_LIBC_UTILS_BENCHMARK_MEMORY_BENCHMARK_H