[libc] automemcpy - result analyzer

[gchatelet]

Summary

"automemcpy: A framework for automatic generation of fundamental memory operations"
https://research.google/pubs/pub50338/

This patch implements the concepts presented in the paper, the overall approach is the following:

• Makes use of constraint programming to model the implementation of a memory function (memcpy, memset, memcmp, bzero, bcmp).
• Generate the code for all valid implementations
• Compile the implementations and benchmark them on a set of machines. The benchmark makes use of representative distributions for the function's arguments.
• Analyze the result and pick "the best" performing function according to the specific environement.

This patch in particular implements the code that reads the result of the benchmark and produce an analysis of the performance of each autogenerated function.

[gchatelet]

• Move analyzer to subdirectory

[courbet]

This could really use some doc.

libc/benchmarks/automemcpy/lib/ResultAnalyzer.cpp

161–163

any reason not to group {Throughput,Score,GradeAttribution} to avoid the 3 parallel maps ?

[gchatelet]

Will update the patch with more comments shortly.

libc/benchmarks/automemcpy/lib/ResultAnalyzer.cpp

161–163

Yes, Throughputs is currently move constructed (see line 185).
I can extract the distribution data into its own data structure with 3 fields, but then I'll have to iterate the map to construct Throughputs instead of moving it.
I'll update the patch with the new version so you can judge.

[gchatelet]

• Add documentation, unify three maps as a single one.

[courbet]

As discussed, this is complex enough to warrant unit tests.

libc/benchmarks/automemcpy/lib/ResultAnalyzer.cpp

12

You have not defined distribution in this file yet. Give a pointer ?

161–163

I think it's better grouped.

196

std::nth_element, given that you're not using the values for anything else ?

212

Normalize ?

[gchatelet]

• Add tests for result analyzer

[gchatelet]

• Address comments

[courbet]

libc/benchmarks/automemcpy/lib/ResultAnalyzerMain.cpp

2

Missing header

[gchatelet]

• Fix file headers

[gchatelet]

Submitted within D111801.

libc/benchmarks/automemcpy/include/automemcpy/ResultAnalyzer.h

+//===-- Analyze benchmark JSON files ----------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LIBC_BENCHMARKS_AUTOMEMCPY_RESULTANALYZER_H
+#define LIBC_BENCHMARKS_AUTOMEMCPY_RESULTANALYZER_H
+
+#include "automemcpy/FunctionDescriptor.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringMap.h"
+#include <array>
+#include <vector>
+
+namespace llvm {
+namespace automemcpy {
+
+// A Grade as in the Majority Judgment voting system.
+struct Grade {
+  enum GradeEnum {
+    EXCELLENT,
+    VERY_GOOD,
+    GOOD,
+    PASSABLE,
+    INADEQUATE,
+    MEDIOCRE,
+    BAD,
+    ARRAY_SIZE,
+  };
+
+  // Returns a human readable string of the enum.
+  static StringRef getString(const GradeEnum &GE);
+
+  // Turns 'Score' into a GradeEnum.
+  static GradeEnum judge(double Score);
+};
+
+// A 'GradeEnum' indexed array with counts for each grade.
+using GradeHistogram = std::array<size_t, Grade::ARRAY_SIZE>;
+
+// Identifies a Function by its name and type. Used as a key in a map.
+struct FunctionId {
+  StringRef Name;
+  FunctionType Type;
+  COMPARABLE_AND_HASHABLE(FunctionId, Type, Name)
+};
+
+struct PerDistributionData {
+  double MedianBytesPerSecond; // Median of samples for this distribution.
+  double Score;                // Normalized score for this distribution.
+  Grade::GradeEnum Grade;      // Grade for this distribution.
+};
+
+struct FunctionData {
+  FunctionId Id;
+  StringMap<PerDistributionData> PerDistributionData;
+  GradeHistogram GradeHisto = {};           // GradeEnum indexed array
+  Grade::GradeEnum FinalGrade = Grade::BAD; // Overall grade for this function
+};
+
+// Identifies a Distribution by its name. Used as a key in a map.
+struct DistributionId {
+  StringRef Name;
+  COMPARABLE_AND_HASHABLE(DistributionId, Name)
+};
+
+// Identifies a Sample by its distribution and function. Used as a key in a map.
+struct SampleId {
+  FunctionId Function;
+  DistributionId Distribution;
+  COMPARABLE_AND_HASHABLE(SampleId, Function.Type, Function.Name,
+                          Distribution.Name)
+};
+
+// A SampleId with an associated measured throughput.
+struct Sample {
+  SampleId Id;
+  double BytesPerSecond = 0;
+};
+
+// This function collects Samples that belong to the same distribution and
+// function and retains the median one. It then stores each of them into a
+// 'FunctionData' and returns them as a vector.
+std::vector<FunctionData> getThroughputs(ArrayRef<Sample> Samples);
+
+// Normalize the function's throughput per distribution.
+void fillScores(MutableArrayRef<FunctionData> Functions);
+
+// Convert scores into Grades, stores an histogram of Grade for each functions
+// and cast a median grade for the function.
+void castVotes(MutableArrayRef<FunctionData> Functions);
+
+} // namespace automemcpy
+} // namespace llvm
+
+#endif // LIBC_BENCHMARKS_AUTOMEMCPY_RESULTANALYZER_H

libc/benchmarks/automemcpy/lib/ResultAnalyzer.cpp

+//===-- Analyze benchmark JSON files --------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+// This code analyzes the json file produced by the `automemcpy` binary.
+//
+// As a remainder, `automemcpy` will benchmark each autogenerated memory
+// functions against one of the predefined distributions available in the
+// `libc/benchmarks/distributions` folder.
+//
+// It works as follows:
+// - Reads one or more json files.
+// - If there are several runs for the same function and distribution, picks the
+//   median throughput (aka `BytesPerSecond`).
+// - Aggregates the throughput per distributions and scores them from worst (0)
+//   to best (1).
+// - Each distribution categorizes each function into one of the following
+//   categories: EXCELLENT, VERY_GOOD, GOOD, PASSABLE, INADEQUATE, MEDIOCRE,
+//   BAD.
+// - A process similar to the Majority Judgment voting system is used to `elect`
+//   the best function. The histogram of grades is returned so we can
+//   distinguish between functions with the same final grade. In the following
+//   example both functions grade EXCELLENT but we may prefer the second one.
+//
+//   |            | EXCELLENT | VERY_GOOD | GOOD | PASSABLE | ...
+//   |------------|-----------|-----------|------|----------| ...
+//   | Function_1 |     7     |     1     |   2  |          | ...
+//   | Function_2 |     6     |     4     |      |          | ...
+
+#include "automemcpy/ResultAnalyzer.h"
+#include "llvm/ADT/StringRef.h"
+#include <numeric>
+#include <unordered_map>
+
+namespace llvm {
+
+namespace automemcpy {
+
+StringRef Grade::getString(const GradeEnum &GE) {
+  switch (GE) {
+  case EXCELLENT:
+    return "EXCELLENT";
+  case VERY_GOOD:
+    return "VERY_GOOD";
+  case GOOD:
+    return "GOOD";
+  case PASSABLE:
+    return "PASSABLE";
+  case INADEQUATE:
+    return "INADEQUATE";
+  case MEDIOCRE:
+    return "MEDIOCRE";
+  case BAD:
+    return "BAD";
+  case ARRAY_SIZE:
+    report_fatal_error("logic error");
+  }
+}
+
+Grade::GradeEnum Grade::judge(double Score) {
+  if (Score >= 6. / 7)
+    return EXCELLENT;
+  if (Score >= 5. / 7)
+    return VERY_GOOD;
+  if (Score >= 4. / 7)
+    return GOOD;
+  if (Score >= 3. / 7)
+    return PASSABLE;
+  if (Score >= 2. / 7)
+    return INADEQUATE;
+  if (Score >= 1. / 7)
+    return MEDIOCRE;
+  return BAD;
+}
+
+std::vector<FunctionData> getThroughputs(ArrayRef<Sample> Samples) {
+  std::unordered_map<SampleId, std::vector<double>, SampleId::Hasher>
+      BucketedSamples;
+  for (const auto &S : Samples)
+    BucketedSamples[S.Id].push_back(S.BytesPerSecond);
+  std::unordered_map<FunctionId, StringMap<double>, FunctionId::Hasher>
+      Throughputs;
+  for (auto &Pair : BucketedSamples) {
+    const auto &Id = Pair.first;
+    auto &Values = Pair.second;
+    const size_t HalfSize = Values.size() / 2;
+    std::nth_element(Values.begin(), Values.begin() + HalfSize, Values.end());
+    const double MedianValue = Values[HalfSize];
+    Throughputs[Id.Function][Id.Distribution.Name] = MedianValue;
+  }
+  std::vector<FunctionData> Output;
+  for (auto &Pair : Throughputs) {
+    FunctionData Data;
+    Data.Id = Pair.first;
+    for (const auto &Pair : Pair.second)
+      Data.PerDistributionData[Pair.getKey()].MedianBytesPerSecond =
+          Pair.getValue();
+    Output.push_back(std::move(Data));
+  }
+  return Output;
+}
+
+void fillScores(MutableArrayRef<FunctionData> Functions) {
+  // A key to bucket throughput per function type and distribution.
+  struct Key {
+    FunctionType Type;
+    StringRef Distribution;
+
+    COMPARABLE_AND_HASHABLE(Key, Type, Distribution)
+  };
+
+  // Tracks minimum and maximum values.
+  struct MinMax {
+    double Min = std::numeric_limits<double>::max();
+    double Max = std::numeric_limits<double>::min();
+    void update(double Value) {
+      if (Value < Min)
+        Min = Value;
+      if (Value > Max)
+        Max = Value;
+    }
+    double normalize(double Value) const { return (Value - Min) / (Max - Min); }
+  };
+
+  std::unordered_map<Key, MinMax, Key::Hasher> ThroughputMinMax;
+  for (const auto &Function : Functions) {
+    const FunctionType Type = Function.Id.Type;
+    for (const auto &Pair : Function.PerDistributionData) {
+      const auto &Distribution = Pair.getKey();
+      const double Throughput = Pair.getValue().MedianBytesPerSecond;
+      const Key K{Type, Distribution};
+      ThroughputMinMax[K].update(Throughput);
+    }
+  }
+
+  for (auto &Function : Functions) {
+    const FunctionType Type = Function.Id.Type;
+    for (const auto &Pair : Function.PerDistributionData) {
+      const auto &Distribution = Pair.getKey();
+      const double Throughput = Pair.getValue().MedianBytesPerSecond;
+      const Key K{Type, Distribution};
+      Function.PerDistributionData[Distribution].Score =
+          ThroughputMinMax[K].normalize(Throughput);
+    }
+  }
+}
+
+void castVotes(MutableArrayRef<FunctionData> Functions) {
+  for (FunctionData &Function : Functions)
+    for (const auto &Pair : Function.PerDistributionData) {
+      const StringRef Distribution = Pair.getKey();
+      const double Score = Pair.getValue().Score;
+      const auto G = Grade::judge(Score);
+      ++(Function.GradeHisto[G]);
+      Function.PerDistributionData[Distribution].Grade = G;
+    }
+
+  for (FunctionData &Function : Functions) {
+    const auto &GradeHisto = Function.GradeHisto;
+    const size_t Votes =
+        std::accumulate(GradeHisto.begin(), GradeHisto.end(), 0U);
+    const size_t MedianVote = Votes / 2;
+    size_t CountedVotes = 0;
+    Grade::GradeEnum MedianGrade = Grade::BAD;
+    for (size_t I = 0; I < GradeHisto.size(); ++I) {
+      CountedVotes += GradeHisto[I];
+      if (CountedVotes > MedianVote) {
+        MedianGrade = Grade::GradeEnum(I);
+        break;
+      }
+    }
+    Function.FinalGrade = MedianGrade;
+  }
+}
+
+} // namespace automemcpy
+} // namespace llvm

libc/benchmarks/automemcpy/lib/ResultAnalyzerMain.cpp

+//===-- Application to analyze benchmark JSON files -----------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "automemcpy/ResultAnalyzer.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/JSON.h"
+#include "llvm/Support/MemoryBuffer.h"
+
+namespace llvm {
+
+// User can specify one or more json filenames to process on the command line.
+static cl::list<std::string> InputFilenames(cl::Positional, cl::OneOrMore,
+                                            cl::desc("<input json files>"));
+
+namespace automemcpy {
+
+// This is defined in the autogenerated 'Implementations.cpp' file.
+extern ArrayRef<NamedFunctionDescriptor> getFunctionDescriptors();
+
+// Iterates over all functions and fills a map of function name to function
+// descriptor pointers.
+static StringMap<const FunctionDescriptor *> createFunctionDescriptorMap() {
+  StringMap<const FunctionDescriptor *> Descriptors;
+  for (const NamedFunctionDescriptor &FD : getFunctionDescriptors())
+    Descriptors.insert_or_assign(FD.Name, &FD.Desc);
+  return Descriptors;
+}
+
+// Retrieves the function descriptor for a particular function name.
+static const FunctionDescriptor &getFunctionDescriptor(StringRef FunctionName) {
+  static StringMap<const FunctionDescriptor *> Descriptors =
+      createFunctionDescriptorMap();
+  const auto *FD = Descriptors.lookup(FunctionName);
+  if (!FD)
+    report_fatal_error(
+        Twine("No FunctionDescriptor for ").concat(FunctionName));
+  return *FD;
+}
+
+// Functions and distributions names are stored quite a few times so it's more
+// efficient to internalize these strings and refer to them through 'StringRef'.
+static StringRef getInternalizedString(StringRef VolatileStr) {
+  static llvm::StringSet<> StringCache;
+  return StringCache.insert(VolatileStr).first->getKey();
+}
+
+// Helper function for the LLVM JSON API.
+bool fromJSON(const json::Value &V, Sample &Out, json::Path P) {
+  std::string Label;
+  json::ObjectMapper O(V, P);
+  if (O && O.map("bytes_per_second", Out.BytesPerSecond) &&
+      O.map("label", Label)) {
+    const auto LabelPair = StringRef(Label).split(',');
+    Out.Id.Function.Name = getInternalizedString(LabelPair.first);
+    Out.Id.Function.Type = getFunctionDescriptor(LabelPair.first).Type;
+    Out.Id.Distribution.Name = getInternalizedString(LabelPair.second);
+    return true;
+  }
+  return false;
+}
+
+// An object to represent the content of the JSON file.
+// This is easier to parse/serialize JSON when the structures of the json file
+// maps the structure of the object.
+struct JsonFile {
+  std::vector<Sample> Samples;
+};
+
+// Helper function for the LLVM JSON API.
+bool fromJSON(const json::Value &V, JsonFile &JF, json::Path P) {
+  json::ObjectMapper O(V, P);
+  return O && O.map("benchmarks", JF.Samples);
+}
+
+// Global object to ease error reporting, it consumes errors and crash the
+// application with a meaningful message.
+static ExitOnError ExitOnErr;
+
+// Main JSON parsing method. Reads the content of the file pointed to by
+// 'Filename' and returns a JsonFile object.
+JsonFile parseJsonResultFile(StringRef Filename) {
+  auto Buf = ExitOnErr(errorOrToExpected(
+      MemoryBuffer::getFile(Filename, /*bool IsText=*/true,
+                            /*RequiresNullTerminator=*/false)));
+  auto JsonValue = ExitOnErr(json::parse(Buf->getBuffer()));
+  json::Path::Root Root;
+  JsonFile JF;
+  if (!fromJSON(JsonValue, JF, Root))
+    ExitOnErr(Root.getError());
+  return JF;
+}
+
+// Serializes the 'GradeHisto' to the provided 'Stream'.
+static void Serialize(raw_ostream &Stream, const GradeHistogram &GH) {
+  static constexpr std::array<StringRef, 9> kCharacters = {
+      " ", "▁", "▂", "▃", "▄", "▅", "▆", "▇", "█"};
+
+  const size_t Max = *std::max_element(GH.begin(), GH.end());
+  for (size_t I = 0; I < GH.size(); ++I) {
+    size_t Index = (float(GH[I]) / Max) * (kCharacters.size() - 1);
+    Stream << kCharacters.at(Index);
+  }
+}
+
+int Main(int argc, char **argv) {
+  ExitOnErr.setBanner("Automemcpy Json Results Analyzer stopped with error: ");
+  cl::ParseCommandLineOptions(argc, argv, "Automemcpy Json Results Analyzer\n");
+
+  // Reads all samples stored in the input JSON files.
+  std::vector<Sample> Samples;
+  for (const auto &Filename : InputFilenames) {
+    auto Result = parseJsonResultFile(Filename);
+    llvm::append_range(Samples, Result.Samples);
+  }
+
+  // Extracts median of throughputs.
+  std::vector<FunctionData> Functions = getThroughputs(Samples);
+  fillScores(Functions);
+  castVotes(Functions);
+
+  // TODO: Implement tie breaking algorithm.
+  std::sort(Functions.begin(), Functions.end(),
+            [](const FunctionData &A, const FunctionData &B) {
+              return A.FinalGrade < B.FinalGrade;
+            });
+
+  // Present data by function type.
+  std::stable_sort(Functions.begin(), Functions.end(),
+                   [](const FunctionData &A, const FunctionData &B) {
+                     return A.Id.Type < B.Id.Type;
+                   });
+
+  // Print result.
+  for (const FunctionData &Function : Functions) {
+    outs() << formatv("{0,-10}", Grade::getString(Function.FinalGrade));
+    outs() << " |";
+    Serialize(outs(), Function.GradeHisto);
+    outs() << "| ";
+    outs().resetColor();
+    outs() << formatv("{0,+25}", Function.Id.Name);
+    outs() << "\n";
+  }
+
+  return EXIT_SUCCESS;
+}
+
+} // namespace automemcpy
+} // namespace llvm
+
+int main(int argc, char **argv) { return llvm::automemcpy::Main(argc, argv); }

libc/benchmarks/automemcpy/unittests/ResultAnalyzerTest.cpp

+//===--  Automemcpy Json Results Analyzer Test ----------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "automemcpy/ResultAnalyzer.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using testing::ElementsAre;
+using testing::Pair;
+using testing::SizeIs;
+
+namespace llvm {
+namespace automemcpy {
+namespace {
+
+TEST(AutomemcpyJsonResultsAnalyzer, getThroughputsOneSample) {
+  static constexpr FunctionId Foo1 = {"memcpy1", FunctionType::MEMCPY};
+  static constexpr DistributionId DistA = {{"A"}};
+  static constexpr SampleId Id = {Foo1, DistA};
+  static constexpr Sample kSamples[] = {
+      Sample{Id, 4},
+  };
+
+  const std::vector<FunctionData> Data = getThroughputs(kSamples);
+  EXPECT_THAT(Data, SizeIs(1));
+  EXPECT_THAT(Data[0].Id, Foo1);
+  EXPECT_THAT(Data[0].PerDistributionData, SizeIs(1));
+  // A single value is provided.
+  EXPECT_THAT(
+      Data[0].PerDistributionData.lookup(DistA.Name).MedianBytesPerSecond, 4);
+}
+
+TEST(AutomemcpyJsonResultsAnalyzer, getThroughputsManySamplesSameBucket) {
+  static constexpr FunctionId Foo1 = {"memcpy1", FunctionType::MEMCPY};
+  static constexpr DistributionId DistA = {{"A"}};
+  static constexpr SampleId Id = {Foo1, DistA};
+  static constexpr Sample kSamples[] = {Sample{Id, 4}, Sample{Id, 5},
+                                        Sample{Id, 5}};
+
+  const std::vector<FunctionData> Data = getThroughputs(kSamples);
+  EXPECT_THAT(Data, SizeIs(1));
+  EXPECT_THAT(Data[0].Id, Foo1);
+  EXPECT_THAT(Data[0].PerDistributionData, SizeIs(1));
+  // When multiple values are provided we pick the median one (here median of 4,
+  // 5, 5).
+  EXPECT_THAT(
+      Data[0].PerDistributionData.lookup(DistA.Name).MedianBytesPerSecond, 5);
+}
+
+TEST(AutomemcpyJsonResultsAnalyzer, getThroughputsServeralFunctionAndDist) {
+  static constexpr FunctionId Foo1 = {"memcpy1", FunctionType::MEMCPY};
+  static constexpr DistributionId DistA = {{"A"}};
+  static constexpr FunctionId Foo2 = {"memcpy2", FunctionType::MEMCPY};
+  static constexpr DistributionId DistB = {{"B"}};
+  static constexpr Sample kSamples[] = {
+      Sample{{Foo1, DistA}, 1}, Sample{{Foo1, DistB}, 2},
+      Sample{{Foo2, DistA}, 3}, Sample{{Foo2, DistB}, 4}};
+  // Data is aggregated per function.
+  const std::vector<FunctionData> Data = getThroughputs(kSamples);
+  EXPECT_THAT(Data, SizeIs(2)); // 2 functions Foo1 and Foo2.
+  // Each function has data for both distributions DistA and DistB.
+  EXPECT_THAT(Data[0].PerDistributionData, SizeIs(2));
+  EXPECT_THAT(Data[1].PerDistributionData, SizeIs(2));
+}
+
+TEST(AutomemcpyJsonResultsAnalyzer, getScore) {
+  static constexpr FunctionId Foo1 = {"memcpy1", FunctionType::MEMCPY};
+  static constexpr FunctionId Foo2 = {"memcpy2", FunctionType::MEMCPY};
+  static constexpr FunctionId Foo3 = {"memcpy3", FunctionType::MEMCPY};
+  static constexpr DistributionId Dist = {{"A"}};
+  static constexpr Sample kSamples[] = {Sample{{Foo1, Dist}, 1},
+                                        Sample{{Foo2, Dist}, 2},
+                                        Sample{{Foo3, Dist}, 3}};
+
+  // Data is aggregated per function.
+  std::vector<FunctionData> Data = getThroughputs(kSamples);
+
+  // Sort Data by function name so we can test them.
+  std::sort(
+      Data.begin(), Data.end(),
+      [](const FunctionData &A, const FunctionData &B) { return A.Id < B.Id; });
+
+  EXPECT_THAT(Data[0].Id, Foo1);
+  EXPECT_THAT(Data[0].PerDistributionData.lookup("A").MedianBytesPerSecond, 1);
+  EXPECT_THAT(Data[1].Id, Foo2);
+  EXPECT_THAT(Data[1].PerDistributionData.lookup("A").MedianBytesPerSecond, 2);
+  EXPECT_THAT(Data[2].Id, Foo3);
+  EXPECT_THAT(Data[2].PerDistributionData.lookup("A").MedianBytesPerSecond, 3);
+
+  // Normalizes throughput per distribution.
+  fillScores(Data);
+  EXPECT_THAT(Data[0].PerDistributionData.lookup("A").Score, 0);
+  EXPECT_THAT(Data[1].PerDistributionData.lookup("A").Score, 0.5);
+  EXPECT_THAT(Data[2].PerDistributionData.lookup("A").Score, 1);
+}
+
+TEST(AutomemcpyJsonResultsAnalyzer, castVotes) {
+  static constexpr double kAbsErr = 0.01;
+
+  static constexpr FunctionId Foo1 = {"memcpy1", FunctionType::MEMCPY};
+  static constexpr FunctionId Foo2 = {"memcpy2", FunctionType::MEMCPY};
+  static constexpr FunctionId Foo3 = {"memcpy3", FunctionType::MEMCPY};
+  static constexpr DistributionId DistA = {{"A"}};
+  static constexpr DistributionId DistB = {{"B"}};
+  static constexpr Sample kSamples[] = {
+      Sample{{Foo1, DistA}, 0}, Sample{{Foo1, DistB}, 30},
+      Sample{{Foo2, DistA}, 1}, Sample{{Foo2, DistB}, 100},
+      Sample{{Foo3, DistA}, 7}, Sample{{Foo3, DistB}, 100},
+  };
+
+  // DistA Thoughput ranges from 0 to 7.
+  // DistB Thoughput ranges from 30 to 100.
+
+  // Data is aggregated per function.
+  std::vector<FunctionData> Data = getThroughputs(kSamples);
+
+  // Sort Data by function name so we can test them.
+  std::sort(
+      Data.begin(), Data.end(),
+      [](const FunctionData &A, const FunctionData &B) { return A.Id < B.Id; });
+
+  // Normalizes throughput per distribution.
+  fillScores(Data);
+
+  // Cast votes
+  castVotes(Data);
+
+  EXPECT_THAT(Data[0].Id, Foo1);
+  EXPECT_THAT(Data[1].Id, Foo2);
+  EXPECT_THAT(Data[2].Id, Foo3);
+
+  // Distribution A
+  // Throughput is 0, 1 and 7, so normalized scores are 0, 1/7 and 1.
+  EXPECT_NEAR(Data[0].PerDistributionData.lookup("A").Score, 0, kAbsErr);
+  EXPECT_NEAR(Data[1].PerDistributionData.lookup("A").Score, 1. / 7, kAbsErr);
+  EXPECT_NEAR(Data[2].PerDistributionData.lookup("A").Score, 1, kAbsErr);
+  // which are turned into grades BAD,  MEDIOCRE and EXCELLENT.
+  EXPECT_THAT(Data[0].PerDistributionData.lookup("A").Grade, Grade::BAD);
+  EXPECT_THAT(Data[1].PerDistributionData.lookup("A").Grade, Grade::MEDIOCRE);
+  EXPECT_THAT(Data[2].PerDistributionData.lookup("A").Grade, Grade::EXCELLENT);
+
+  // Distribution B
+  // Throughput is 30, 100 and 100, so normalized scores are 0, 1 and 1.
+  EXPECT_NEAR(Data[0].PerDistributionData.lookup("B").Score, 0, kAbsErr);
+  EXPECT_NEAR(Data[1].PerDistributionData.lookup("B").Score, 1, kAbsErr);
+  EXPECT_NEAR(Data[2].PerDistributionData.lookup("B").Score, 1, kAbsErr);
+  // which are turned into grades BAD, EXCELLENT and EXCELLENT.
+  EXPECT_THAT(Data[0].PerDistributionData.lookup("B").Grade, Grade::BAD);
+  EXPECT_THAT(Data[1].PerDistributionData.lookup("B").Grade, Grade::EXCELLENT);
+  EXPECT_THAT(Data[2].PerDistributionData.lookup("B").Grade, Grade::EXCELLENT);
+
+  // Now looking from the functions point of view.
+  // Note the array is indexed by GradeEnum values (EXCELLENT=0 / BAD = 6)
+  EXPECT_THAT(Data[0].GradeHisto, ElementsAre(0, 0, 0, 0, 0, 0, 2));
+  EXPECT_THAT(Data[1].GradeHisto, ElementsAre(1, 0, 0, 0, 0, 1, 0));
+  EXPECT_THAT(Data[2].GradeHisto, ElementsAre(2, 0, 0, 0, 0, 0, 0));
+
+  EXPECT_THAT(Data[0].FinalGrade, Grade::BAD);
+  EXPECT_THAT(Data[1].FinalGrade, Grade::MEDIOCRE);
+  EXPECT_THAT(Data[2].FinalGrade, Grade::EXCELLENT);
+}
+
+} // namespace
+} // namespace automemcpy
+} // namespace llvm