[llvm-exegesis] Let Counter returns up to 16 entries.

[oontvoo]

Summary

LBR contains (up to) 16 entries for last x branches and the X86LBRCounter (from D77422) should be able to return all those.
Currently, it just returns the latest entry, which could lead to mis-leading measurements.
This patch aslo changes the LatencyBenchmarkRunner to accommodate multi-value readings.

[courbet]

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp

60

Please get rif of the magic number. Why 16 ? what about Counter->numValues() ?

87

Please split this off to void accumulateCounterValues(ValueOrError.get(), CounterValues)

88

[style]

if (!ValueOrError)
  return ValueOrError.takeError();
...

94

Why not += ?

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

27

ComputeVariance ?

37

This is missing a square.

42

So computing the min and stddev across values in runAndMeasureMulti() requires them to be measuring the same thing. From the documentation it's not clear to me what the values represent. Are they always homogeneous ? Can you give an example of what they are in the LBR case.

48

why not std::numeric_limits<double> ?

56

Technically you're computing a variance.

57

Because of short-circuiting, if WithMinStdev.empty(), then CurStdev will not be evaluated, and CurStdev will be zero. Then Stdev will be set to 0, preventing any further updates.

58

Was this supposed to be the other way around ? Here we are selecting the largest stddev.

llvm/tools/llvm-exegesis/lib/PerfHelper.cpp

136

This returns a vector with Count elements set to zero. If this passes all tests then we are clearly missing tests :(

[ondrasej]

This looks good in general, but we should be careful about aggregating the values from the measurements (and aggregation when the counter returns multiple values). In particular for the LBR, we'd be losing interesting and potentially useful information by aggregating all the values into a single number.

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h

71

This should be llvm::SmallVector<int64_t, N> with some small N (e.g. 4) to avoid memory allocations when there is just one return value. This is the case for virtually all counters except the LBR.

72

Consider calling this runAndSample().

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

32

You could do
const double Sum = std::accumulate(Values.begin(), Values.end(), 0.0);
instead.

68

I'd prefer to have more flexibility about the numbers that are returned and reported by the tool. The original code collapsed the measurements to a single value (the minimum). This is useful when looking for lower bounds/optimistic numbers, but other processing would also make sense:

• the mean of the measurements - this might give a better idea of the actual performance when running in the loop.
• the list of all measured values - so that the user can analyze the distribution of the measurements by themselves (and go beyond the mean/variance).

In particular for the LBR measurements: being able to see the raw timings of individual loop iterations is what makes that measurement method so appealing, and we'd lose all that information if we just took an aggregate value, be it a min or a mean. The min and mean from the LBR do have their value and I'd expect them to be more precise than the measurements over an unrolled loop, so ideally we'd have a way to see both.

I think a good solution would be to add an argument to this method that determines how the values are aggregated over the measurements:

• min,
• mean,
• min variance,
• keep all.
  
  and over the contents of the returned vector:
• min,
• mean,
• keep all.

This will mean more changes up the call stack, but it would give us a lot more flexibility in using the tool. What do you think?

llvm/tools/llvm-exegesis/lib/PerfHelper.cpp

123

You might want to check that there is at least one element.

129

This should be llvm::SmallVector<int64_t, some small N> - most counters return just a single value.

[oontvoo]

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

68

Yes, that's a good idea. I've thought about this a bit more and realised even keeping min-variance (of each read) could still be completely wrong.

Imagine your benchmarked code has a number of distinct branches; then there is no reason to expect the cycles from these branches to correlate. The min-variance approach is only meaningful if it's the same code-path.

[oontvoo]

Updated diff

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

42

Yes, they're supposed to be homogenous, representing the measurements of the same block sampled at fixed rate.

For the LBR specifically:

• Each value in the vector is the number of elapsed cycles since last branch-retire
• When we take a sample, we have 16 of such values, representing the last 16 branches.
• If we have a loop whose body is a basic-block, then effectively these are the measurements for the last 16 iterations[0]. if the loop body has some branches then we'd need a different aggregation strategy.

[0] I think this is where it's a bit "wrong" right now. We always only read the last 16 branches. What we probably want is to be able to have the BenchmarkRunner pause at fixed period and take a sample.

• (Just made a note so we could talk about this tomorrow @courbet @ondrasej )

56

¯\_(ツ)_/¯ indeed!

[oontvoo]

Fix clang-tidy issues

[ondrasej]

I've added a couple of style comment + one bigger comment on the aggregation of results from multiple runs/counter buffer.

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp

56

NewValues should be a const reference, no?

60

s/reserved/Reserved/

65

This is probably not a big deal, but consider:

const size_t NumValues = std::max(NewValues.size(), Result->size());
if (NumValues > Result->size()) Result->resize(NumValues, 0);
for (size_t i = 0, End = NewValues.size(); i < End; ++i) {
  (*Result)[i] += NewValues[i];
}

for unrolled + vectorized code.

74

I'd prefer not using assignment in function arguments - this might be easily overlooked or mistaken for a bug (assignment in place of equality comparison).

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

35

std::pow is somewhat heavy-weight as it is not optimized for integer exponents,
const double Delta = V - Mean;
Ret += Delta * Delta;
will likely be significantly faster.

47

A shorter way to write this:

return std::accumulate(
  Values.begin(), Values.end(), std::numeric_limits<int64_t>::max(),
  [](int64_t A, int64_t B) { return A < B ? A : B; });

And similar for FindMax below.

60

Nit: Since we have WithMinVariance, consider renaming Variance to MinVariance, and CurVariance to just Variance.

61

Ideally, this should use move semantics (if they are supported by SmallVector).

62

This would update Variance (MinVariance with the rename proposed above) even if the variance increased. What you probably want is

if (Variance < MinVariance) {
  WithMinVariance = *ExpectedCounterValues;
  MinVariancec = Variance;
}

82

I'd still split this into two arguments:
One that decides what happens with the return values of runAndSample() with {Concatenate, MinVariance}.

And another one that decides what to do with the results of the previous step (Min, Max, Mean, return as is}.

With the current MinVariance filtering in all cases, we're changing the behavior for scalar counters, where we might drop some values (and we might drop some values also in the LBR case).

llvm/tools/llvm-exegesis/lib/PerfHelper.cpp

151

This should also be llvm::SmallVector (please test with HAVE_LIBPFM undefined/false).

[oontvoo]

Fixed another clang-tidy issue

[oontvoo]

Updated diff

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

82

Ah, I think we can infer how to accumulate the values returnt by runAndSample().

• If the return vector has more than 1 element, then keep the set with min variance (because it wouldn't make sense to concat all the values from different runs together)
• If the vector only has 1 element, then concat them together to find Min/Max/Mean

[ondrasej]

One last comment, but otherwise this looks good. I'll leave the approval to Clement.

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

48

Very nit: if we're working with doubles, std::numeric_limits<double>::infinity() might be even better.

[oontvoo]

std::numeric_limits<double>::infinity()

[courbet]

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp

62

[style] no braces

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

47

Why not std::min_element ?

llvm/tools/llvm-exegesis/lib/Target.cpp

74 ↗

(On Diff #271816)

Let's do this now to avoid being in an inconsistent state.

[oontvoo]

update diff

[courbet]

llvm/tools/llvm-exegesis/lib/Target.cpp

118 ↗

(On Diff #273211)

I the default Target implementation does not use it, let's just do:

std::unique_ptr<BenchmarkRunner> ExegesisTarget::createUopsBenchmarkRunner(
    const LLVMState &State,
    InstructionBenchmark::ResultAggregationModeE /*unused*/) const {
  return std::make_unique<UopsBenchmarkRunner>(State);
}

[oontvoo]

llvm/tools/llvm-exegesis/lib/Target.cpp

118 ↗

(On Diff #273211)

Should we change the impl to use it?

[oontvoo]

Removed unused ResultAggMode

[oontvoo]

update diff

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h

private:
     char *const AlignedPtr;
   };
 
   // A helper to measure counters while executing a function in a sandboxed
   // context.
   class FunctionExecutor {
   public:
     virtual ~FunctionExecutor();
+    // FIXME deprecate this.
     virtual Expected<int64_t> runAndMeasure(const char *Counters) const = 0;
+
+    virtual Expected<std::vector<int64_t>>
+    runAndMeasureMulti(const char *Counters) const = 0;
   };
 
 protected:
   const LLVMState &State;
   const InstructionBenchmark::ModeE Mode;
 
 private:
   virtual Expected<std::vector<BenchmarkMeasure>>

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp

public:
   FunctionExecutorImpl(const LLVMState &State,
                        object::OwningBinary<object::ObjectFile> Obj,
                        BenchmarkRunner::ScratchSpace *Scratch)
       : State(State), Function(State.createTargetMachine(), std::move(Obj)),
         Scratch(Scratch) {}
 
 private:
   Expected<int64_t> runAndMeasure(const char *Counters) const override {
+    auto resultOrError = runAndMeasureMulti(Counters);
+    if (resultOrError)
+      return resultOrError.get()[0];
+    return resultOrError.takeError();
+  }
+
+  Expected<std::vector<int64_t>>
+  runAndMeasureMulti(const char *Counters) const override {
     // We sum counts when there are several counters for a single ProcRes
     // (e.g. P23 on SandyBridge).
-    int64_t CounterValue = 0;
+    std::vector<int64_t> CounterValues;
+    CounterValues.reserve(16); // Counter returns at most 16 entries.
     SmallVector<StringRef, 2> CounterNames;
     StringRef(Counters).split(CounterNames, '+');
     char *const ScratchPtr = Scratch->ptr();
     for (auto &CounterName : CounterNames) {
       CounterName = CounterName.trim();
       auto CounterOrError =
           State.getExegesisTarget().createCounter(CounterName, State);
 
       if (!CounterOrError)
         return CounterOrError.takeError();
 
       pfm::Counter *Counter = CounterOrError.get().get();
       Scratch->clear();
       {
         CrashRecoveryContext CRC;
         CrashRecoveryContext::Enable();
         const bool Crashed = !CRC.RunSafely([this, Counter, ScratchPtr]() {
           Counter->start();
           this->Function(ScratchPtr);
           Counter->stop();
         });
         CrashRecoveryContext::Disable();
         // FIXME: Better diagnosis.
         if (Crashed)
           return make_error<SnippetCrash>("snippet crashed while running");
       }
-      CounterValue += Counter->read();
+      auto ValueOrError = Counter->readOrError();
+      if (ValueOrError) {
+        int i = 0;
+        for (const int64_t &result : ValueOrError.get()) {
+          if (i >= CounterValues.size())
+            CounterValues.push_back(result);
+          else
+            CounterValues[i] = CounterValues[i] + result;
+          ++i;
+        }
+      } else
+        return ValueOrError.takeError();
     }
-    return CounterValue;
+    return CounterValues;
   }
 
   const LLVMState &State;
   const ExecutableFunction Function;
   BenchmarkRunner::ScratchSpace *const Scratch;
 };
 } // namespace
 

llvm/tools/llvm-exegesis/lib/LatencyBenchmarkRunner.cpp

LatencyBenchmarkRunner::LatencyBenchmarkRunner(const LLVMState &State,
     : BenchmarkRunner(State, Mode) {
   assert((Mode == InstructionBenchmark::Latency ||
           Mode == InstructionBenchmark::InverseThroughput) &&
          "invalid mode");
 }
 
 LatencyBenchmarkRunner::~LatencyBenchmarkRunner() = default;
 
+static double squareStdev(const std::vector<int64_t> Values) {
+  if (Values.empty())
+    return 0.0;
+  double Sum = 0;
+  for (const auto &V : Values)
+    Sum += V;
+
+  const double Mean = Sum / Values.size();
+  double Ret = 0;
+  for (const auto &V : Values) {
+    Ret += V - Mean;
+  }
+  return Ret / Values.size();
+}
+
 Expected<std::vector<BenchmarkMeasure>> LatencyBenchmarkRunner::runMeasurements(
     const FunctionExecutor &Executor) const {
   // Cycle measurements include some overhead from the kernel. Repeat the
   // measure several times and take the minimum value.
   constexpr const int NumMeasurements = 30;
-  int64_t MinValue = std::numeric_limits<int64_t>::max();
+  std::vector<int64_t> WithMinStdev;
+  double Stdev = std::numeric_limits<int64_t>::max();
   const char *CounterName = State.getPfmCounters().CycleCounter;
   for (size_t I = 0; I < NumMeasurements; ++I) {
-    auto ExpectedCounterValue = Executor.runAndMeasure(CounterName);
+    auto ExpectedCounterValue = Executor.runAndMeasureMulti(CounterName);
     if (!ExpectedCounterValue)
       return ExpectedCounterValue.takeError();
-    if (*ExpectedCounterValue < MinValue)
-      MinValue = *ExpectedCounterValue;
+
+    // We'll keep the reading with lowest stdev (ie., most stable)
+    double CurStdev = 0;
+    if (WithMinStdev.empty() ||
+        Stdev < (CurStdev = squareStdev(*ExpectedCounterValue))) {
+      WithMinStdev = *ExpectedCounterValue;
+      Stdev = CurStdev;
     }
+  }
+
+  int64_t MinValue = std::numeric_limits<int64_t>::max();
+  for (const auto &V : WithMinStdev) {
+    if (V < MinValue)
+      MinValue = V;
+  }
+
   std::vector<BenchmarkMeasure> Result;
   switch (Mode) {
   case InstructionBenchmark::Latency:
     Result = {BenchmarkMeasure::Create("latency", MinValue)};
     break;
   case InstructionBenchmark::InverseThroughput:
     Result = {BenchmarkMeasure::Create("inverse_throughput", MinValue)};
     break;
   default:
     break;
   }
   return std::move(Result);
 }
 
 } // namespace exegesis
 } // namespace llvm

llvm/tools/llvm-exegesis/lib/PerfHelper.h

 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Config/config.h"
 #include "llvm/Support/Error.h"
 #include <cstdint>
 #include <functional>
 #include <memory>
+#include <vector>
 
 struct perf_event_attr;
 
 namespace llvm {
 namespace exegesis {
 namespace pfm {
 
 // Returns true on error.
public:
 
   /// Stops the measurement of the event.
   void stop();
 
   /// Returns the current value of the counter or -1 if it cannot be read.
   int64_t read() const;
 
   /// Returns the current value of the counter or error if it cannot be read.
-  virtual llvm::Expected<int64_t> readOrError() const;
+  virtual llvm::Expected<std::vector<int64_t>> readOrError() const;
 
 private:
   PerfEvent Event;
 #ifdef HAVE_LIBPFM
   int FileDescriptor = -1;
 #endif
 };
 
 } // namespace pfm
 } // namespace exegesis
 } // namespace llvm
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_PERFHELPER_H

llvm/tools/llvm-exegesis/lib/PerfHelper.cpp

 
 void Counter::start() { ioctl(FileDescriptor, PERF_EVENT_IOC_RESET, 0); }
 
 void Counter::stop() { ioctl(FileDescriptor, PERF_EVENT_IOC_DISABLE, 0); }
 
 int64_t Counter::read() const {
   auto ValueOrError = readOrError();
   if (ValueOrError)
-    return ValueOrError.get();
+    return ValueOrError.get()[0];
 
   errs() << ValueOrError.takeError() << "\n";
   return -1;
 }
 
-llvm::Expected<int64_t> Counter::readOrError() const {
+llvm::Expected<std::vector<int64_t>> Counter::readOrError() const {
   int64_t Count = 0;
   ssize_t ReadSize = ::read(FileDescriptor, &Count, sizeof(Count));
   if (ReadSize != sizeof(Count))
     return llvm::make_error<llvm::StringError>("Failed to read event counter",
                                                llvm::errc::io_error);
 
-  return Count;
+  return std::vector<int64_t>{Count};
 }
 
 #else
 
 Counter::Counter(PerfEvent &&Event) : Event(std::move(Event)) {}
 
 Counter::~Counter() = default;
 
 void Counter::start() {}
 
 void Counter::stop() {}
 
 int64_t Counter::read() const { return 42; }
 
-llvm::Expected<int64_t> Counter::readOrError() const {
+llvm::Expected<std::vector<int64_t>> Counter::readOrError() const {
   return llvm::make_error<llvm::StringError>("Not implemented",
                                              llvm::errc::io_error);
 }
 
 #endif
 
 } // namespace pfm
 } // namespace exegesis
 } // namespace llvm