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