Use a custom container to reduce AFDO's memory usage by ~60%

[george.burgess.iv]

Summary

This patch introduces a new associative container that's optimized for either being empty or having one element, and makes our sampling profile data structures use it.

As it turns out, AFDO profiles build lots of empty (or almost-empty) maps. :)

The results of three tests I ran with/without the patch:

• Merging 3.1GB of profile data (split across 226 profiles) consumed 10.2GB of RAM and took 42 seconds to terminate with this patch. Without, it took 26.3GB of RAM and took 70 seconds.
• Given a 32MB profile in $foo, running echo | clang -O0 -x c - -fprofile-sample-use=$foo took 250MB of RAM with this patch, and 650MB without. Clang itself ate 40MB without -fprofile-sample-use being passed.
• Given a 50MB profile collected by someone else, I observed a drop from 1.6GB of RAM consumption to 569MB with this patch.

Aside: I'm unsure of what the requirements are to land a new data structure in ADT. If this seems too tailored to AFDO's uses or too incomplete (e.g. it lacks insert, remove, and emplace; it doesn't support a custom less-than op, ...) on its own, I'm happy to move it elsewhere or add whatever's missing.

[george.burgess.iv]

include/llvm/ADT/TinyAssociativeVector.h

38

Visibility boost for this bit ^

[davidxl]

Is it enough to simply replace StringMap with std::map<std::string, ..> for small maps? Do you have memory data with that?

include/llvm/ProfileData/SampleProf.h

188

I wonder how much is saved by replacing just std::map with TinyAssociativeVector.

426

Can you split out this clean up change into a separate patch?

[george.burgess.iv]

Addressed feedback; thanks!

Also, I made FunctionSamplesMap's key a std::string, so this is as close to NFC as possible. Doing so is a bit pricey, but we're still left with a 50-55% memory reduction. If we want, we can swap to StringRef in its own CL.

[george.burgess.iv]

Is it enough to simply replace StringMap with std::map<std::string, ..> for small maps? Do you have memory data with that?

Please see the response to your inline comment. The short answer is "that is a good win, but more on the order of 12%." I don't know if that's enough, but can check if you'd like.

include/llvm/ProfileData/SampleProf.h

188

For the 1.5GB profile case:

• Only changing BodySampleMap and CallsiteSampleMap to TinyAssociativeVectors saved us 20% (1.603GB -> 1.288GB)
• Only changing FunctionSamplesMap and CallTargetMap to TinyAssociativeVectors (FunctionSamplesMap using StringRefs) saved us 45% (1.603GB -> 884MB)
• Only changing FunctionSamplesMap and CallTargetMap to std::maps (FunctionSamplesMap using StringRefs) saved us 22% (1.603GB -> 1.219GB)

Changing an individual StringMap -> std::map or StringMap/std::map to TinyAssociativeVector is always a win in memory usage, in my tests.

The majority of the benefit is from FunctionSamplesMap: changing that alone to a TinyAssociativeVector drops memory usage by 34% (1.603GB -> 1.025GB). Of that, a reasonable portion of the benefit is from not copying strings around: using a TinySortedMapVector<std::string, FunctionSamples> for FunctionSamplesMap lands us at 1.159GB of memory use, which is a 26% reduction over a StringMap.

If there are any other combinations you'd like to see, please let me know. I have an earlier version of this that makes toggling these (and any required usage-related changes) really easy. :)

426

Done. Will submit as a follow-up to this one

[davidxl]

I suggest making this a multiple stage change.

patch-1: change expensive map type to std::map to materialize memory savings quickly -- with the data you collected, it is quite safe to check it in
patch-2: TinyMap implementation patch
patch-3: Use TinyMap in samplePGO -- with incremental savings data collected.

Patch-2 needs more closer look by someone like Chandler. Data from patch-3 or perhaps some other potential users can help justify patch-2.

[george.burgess.iv]

I like that idea. :)

Also, it looks like I was mistaken: CallTargetMap is better off a StringMap than a std::map<std::string, uint64_t>. The difference was around 5%, which makes step one save us 17% of memory. Checked it in as r320764, as requested.

I'll do step 2 and step 3 in fresh, more targeted reviews.

Thanks again!

include/llvm/ADT/TinyAssociativeVector.h

+//===- llvm/ADT/TinyAssociativeVector.h - Size-optimized map ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a sorted, associative container optimized for containing 0
+// or 1 elements.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_TINYASSOCIATIVEVECTOR_H
+#define LLVM_ADT_TINYASSOCIATIVEVECTOR_H
+
+#include "llvm/ADT/TinyPtrVector.h"
+#include <algorithm>
+#include <assert.h>
+#include <type_traits>
+#include <utility>
+
+namespace llvm {
+// A sorted, associative container optimized for when the container is often
+// very small (e.g. 0 or 1 elements). Ordering is determined using `operator<`
+// on the keys.
+//
+// This container currently provides the address stability of containers like
+// std::map, but has iterator invalidation characteristics similar to
+// std::vector.
+//
+// Please note that -- unlike maps -- this container has linear-time insertions
+// in the average case, since we need to preserve a sorted order. There exists a
+// special case that makes inserting keys in strictly increasing order
+// constant-time per insertion.
+//
+// (Code review FIXME): Naming recommendations welcome. MapVector already means
+// something that's very much different than this. :)
+template <typename Key, typename Value> struct TinyAssociativeVector {
+  using key_type = Key;
+  using mapped_type = Value;
+  using value_type = std::pair<const key_type, mapped_type>;
+
+private:
+  // This is effectively a TinyPtrVector of std::unique_ptrs, but TinyPtrVector
+  // doesn't support std::unique_ptrs. Probably for good reason.
+  using ImplTy = TinyPtrVector<std::pair<const Key, Value> *>;
+  ImplTy Impl;
+
+  template <typename T>
+  using RemoveTwoPointers =
+      typename std::remove_pointer<typename std::remove_pointer<T>::type>::type;
+
+  // Iterator that transparently dereferences values twice (or once, for
+  // operator->)
+  template <typename InnerTy>
+  class DerefIter : public iterator_facade_base<DerefIter<InnerTy>,
+                                                std::random_access_iterator_tag,
+                                                RemoveTwoPointers<InnerTy>> {
+    // For converting const_iterator -> iterator
+    template <typename T> friend class DerefIter;
+
+    using Super = iterator_facade_base<DerefIter<InnerTy>,
+                                       std::random_access_iterator_tag,
+                                       RemoveTwoPointers<InnerTy>>;
+
+    InnerTy Cur;
+
+  public:
+    DerefIter(InnerTy C) : Cur(C) {}
+
+    template <typename OtherInner>
+    DerefIter(const DerefIter<OtherInner> &O) : Cur(O.Cur) {}
+
+    typename Super::value_type &operator*() const { return **Cur; }
+
+    bool operator==(const DerefIter &Other) const { return Cur == Other.Cur; }
+    bool operator<(const DerefIter &Other) const { return Cur < Other.Cur; }
+
+    typename Super::difference_type operator-(const DerefIter &Other) const {
+      return Cur - Other.Cur;
+    }
+
+    DerefIter &operator+=(typename Super::difference_type N) {
+      Cur += N;
+      return *this;
+    }
+
+    DerefIter &operator-=(typename Super::difference_type N) {
+      Cur -= N;
+      return *this;
+    }
+  };
+
+public:
+  using iterator = DerefIter<typename ImplTy::iterator>;
+  using const_iterator = DerefIter<typename ImplTy::const_iterator>;
+
+  TinyAssociativeVector() = default;
+  TinyAssociativeVector(const TinyAssociativeVector &O) { clone(O); }
+  TinyAssociativeVector(TinyAssociativeVector &&) = default;
+
+  ~TinyAssociativeVector() { clear(); }
+
+  TinyAssociativeVector &operator=(const TinyAssociativeVector &O) {
+    clear();
+    clone(O);
+    return *this;
+  }
+
+  TinyAssociativeVector &operator=(TinyAssociativeVector &&O) {
+    clear();
+    Impl = std::move(O.Impl);
+    return *this;
+  }
+
+  iterator begin() { return Impl.begin(); }
+  iterator end() { return Impl.end(); }
+  const_iterator begin() const { return Impl.begin(); }
+  const_iterator end() const { return Impl.end(); }
+
+  size_t size() const { return Impl.size(); }
+  bool empty() const { return Impl.empty(); }
+
+  void clear() {
+    for (auto *P : Impl)
+      delete P;
+    Impl.clear();
+  }
+
+  // One of the intended uses of this is with StringRef args and std::string
+  // keys. We ideally don't want to allocate on each lookup, hence the extra
+  // templating.
+  template <typename ConvKey>
+  mapped_type &operator[](const ConvKey &K) {
+    typename ImplTy::iterator InsertPt;
+    // Our users generally insert already-sorted data. Optimize for that.
+    if (Impl.empty() || Impl.back()->first < K) {
+      InsertPt = Impl.end();
+    } else {
+      InsertPt = findInsertPoint(K);
+      assert(InsertPt != Impl.end() &&
+             "back()->first < K, but K sorts after back()?");
+      if (keysEqual((*InsertPt)->first, K))
+        return (*InsertPt)->second;
+    }
+
+    auto *Elem = new value_type(K, mapped_type{});
+    Impl.insert(InsertPt, Elem);
+    return Elem->second;
+  }
+
+  template <typename CompKey>
+  iterator find(const CompKey &K) {
+    auto I = findInsertPoint(K);
+    if (I != Impl.end() && keysEqual((*I)->first, K))
+      return I;
+    return end();
+  }
+
+  template <typename CompKey>
+  const_iterator find(const CompKey &K) const {
+    return const_cast<TinyAssociativeVector *>(this)->find(K);
+  }
+
+private:
+  template <typename CompKey>
+  static bool keysEqual(const key_type &A, const CompKey &B) {
+    return !(A < B) && !(B < A);
+  }
+
+  void clone(const TinyAssociativeVector &O) {
+    for (const value_type &P : O)
+      Impl.push_back(new value_type(P));
+  }
+
+  template <typename CompKey>
+  typename ImplTy::iterator findInsertPoint(const CompKey &K) {
+    return std::lower_bound(
+        Impl.begin(), Impl.end(), K,
+        [](const value_type *A, const CompKey &B) { return A->first < B; });
+  }
+};
+} // namespace llvm
+
+#endif // LLVM_ADT_TINYASSOCIATIVEVECTOR_H

include/llvm/ProfileData/SampleProf.h

 
 #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
 #define LLVM_PROFILEDATA_SAMPLEPROF_H
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/TinyAssociativeVector.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cstdint>

 ///
 /// Additionally, if the associated location contains a function call,
 /// the record will hold a list of all the possible called targets. For
 /// direct calls, this will be the exact function being invoked. For
 /// indirect calls (function pointers, virtual table dispatch), this
 /// will be a list of one or more functions.
 class SampleRecord {
 public:
-  using CallTargetMap = StringMap<uint64_t>;
+  using CallTargetMap = TinyAssociativeVector<std::string, uint64_t>;
 
   SampleRecord() = default;
 
   /// Increment the number of samples for this record by \p S.
   /// Optionally scale sample count \p S by \p Weight.
   ///
   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
   /// around unsigned integers.
public:
   uint64_t getSamples() const { return NumSamples; }
   const CallTargetMap &getCallTargets() const { return CallTargets; }
 
   /// Merge the samples in \p Other into this record.
   /// Optionally scale sample counts by \p Weight.
   sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
     sampleprof_error Result = addSamples(Other.getSamples(), Weight);
     for (const auto &I : Other.getCallTargets()) {
-      MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
+      MergeResult(Result, addCalledTarget(I.first, I.second, Weight));
     }
     return Result;
   }
 
   void print(raw_ostream &OS, unsigned Indent) const;
   void dump() const;
 
 private:
   uint64_t NumSamples = 0;
   CallTargetMap CallTargets;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
 
 class FunctionSamples;
 
-using BodySampleMap = std::map<LineLocation, SampleRecord>;
-using FunctionSamplesMap = StringMap<FunctionSamples>;
-using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
+using BodySampleMap = TinyAssociativeVector<LineLocation, SampleRecord>;
+using FunctionSamplesMap = TinyAssociativeVector<StringRef, FunctionSamples>;
+using CallsiteSampleMap =
+    TinyAssociativeVector<LineLocation, FunctionSamplesMap>;
 
 /// Representation of the samples collected for a function.
 ///
 /// This data structure contains all the collected samples for the body
 /// of a function. Each sample corresponds to a LineLocation instance
 /// within the body of the function.
 class FunctionSamples {
 public:
public:
   /// with the maximum total sample count.
   const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
                                                StringRef CalleeName) const {
     auto iter = CallsiteSamples.find(Loc);
     if (iter == CallsiteSamples.end())
       return nullptr;
     auto FS = iter->second.find(CalleeName);
     if (FS != iter->second.end())
-      return &FS->getValue();
+      return &FS->second;
     // If we cannot find exact match of the callee name, return the FS with
     // the max total count.
     uint64_t MaxTotalSamples = 0;
     const FunctionSamples *R = nullptr;
     for (const auto &NameFS : iter->second)
       if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
         MaxTotalSamples = NameFS.second.getTotalSamples();
         R = &NameFS.second;
for (const auto &I : Other.getBodySamples()) {
       const LineLocation &Loc = I.first;
       const SampleRecord &Rec = I.second;
       MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
     }
     for (const auto &I : Other.getCallsiteSamples()) {
       const LineLocation &Loc = I.first;
       FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
       for (const auto &Rec : I.second)
-        MergeResult(Result, FSMap[Rec.first()].merge(Rec.second, Weight));
+        MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight));
     }
     return Result;
   }
 
   /// Recursively traverses all children, if the total sample count of the
   /// corresponding function is no less than \p Threshold, add its corresponding
   /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
   /// to \p S.
   void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
                             uint64_t Threshold) const {
     if (TotalSamples <= Threshold)
       return;
     S.insert(Function::getGUID(Name));
     // Import hot CallTargets, which may not be available in IR because full
     // profile annotation cannot be done until backend compilation in ThinLTO.
     for (const auto &BS : BodySamples)
       for (const auto &TS : BS.second.getCallTargets())
-        if (TS.getValue() > Threshold) {
-          Function *Callee = M->getFunction(TS.getKey());
+        if (TS.second > Threshold) {
+          Function *Callee = M->getFunction(TS.first);
           if (!Callee || !Callee->getSubprogram())
-            S.insert(Function::getGUID(TS.getKey()));
+            S.insert(Function::getGUID(TS.first));
         }
     for (const auto &CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
         NameFS.second.findInlinedFunctions(S, M, Threshold);
   }
 
   /// Set the name of the function.
   void setName(StringRef FunctionName) { Name = FunctionName; }
private:
   /// If the bar() and baz() calls were inlined inside foo(), this
   /// map will contain two entries.  One for all the samples collected
   /// in the call to bar() at line offset 1, the other for all the samples
   /// collected in the call to baz() at line offset 8.
   CallsiteSampleMap CallsiteSamples;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
-
-/// Sort a LocationT->SampleT map by LocationT.
-///
-/// It produces a sorted list of <LocationT, SampleT> records by ascending
-/// order of LocationT.
-template <class LocationT, class SampleT> class SampleSorter {
-public:
-  using SamplesWithLoc = std::pair<const LocationT, SampleT>;
-  using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
-
-  SampleSorter(const std::map<LocationT, SampleT> &Samples) {
-    for (const auto &I : Samples)
-      V.push_back(&I);
-    std::stable_sort(V.begin(), V.end(),
-                     [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
-                       return A->first < B->first;
-                     });
-  }
-
-  const SamplesWithLocList &get() const { return V; }
-
-private:
-  SamplesWithLocList V;
-};
-
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H

lib/ProfileData/SampleProf.cpp

 #endif
 
 /// \brief Print the sample record to the stream \p OS indented by \p Indent.
 void SampleRecord::print(raw_ostream &OS, unsigned Indent) const {
   OS << NumSamples;
   if (hasCalls()) {
     OS << ", calls:";
     for (const auto &I : getCallTargets())
-      OS << " " << I.first() << ":" << I.second;
+      OS << " " << I.first << ":" << I.second;
   }
   OS << "\n";
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void SampleRecord::dump() const { print(dbgs(), 0); }
 #endif
 
 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
                                           const SampleRecord &Sample) {
   Sample.print(OS, 0);
   return OS;
 }
 
 /// \brief Print the samples collected for a function on stream \p OS.
 void FunctionSamples::print(raw_ostream &OS, unsigned Indent) const {
   OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
      << " sampled lines\n";
 
   OS.indent(Indent);
   if (!BodySamples.empty()) {
     OS << "Samples collected in the function's body {\n";
-    SampleSorter<LineLocation, SampleRecord> SortedBodySamples(BodySamples);
-    for (const auto &SI : SortedBodySamples.get()) {
+
+    for (const auto &SI : BodySamples) {
       OS.indent(Indent + 2);
-      OS << SI->first << ": " << SI->second;
+      OS << SI.first << ": " << SI.second;
     }
     OS.indent(Indent);
     OS << "}\n";
   } else {
     OS << "No samples collected in the function's body\n";
   }
 
   OS.indent(Indent);
   if (!CallsiteSamples.empty()) {
     OS << "Samples collected in inlined callsites {\n";
-    SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(
-        CallsiteSamples);
-    for (const auto &CS : SortedCallsiteSamples.get()) {
-      for (const auto &FS : CS->second) {
+
+    for (const auto &CS : CallsiteSamples) {
+      for (const auto &FS : CS.second) {
         OS.indent(Indent + 2);
-        OS << CS->first << ": inlined callee: " << FS.second.getName() << ": ";
+        OS << CS.first << ": inlined callee: " << FS.second.getName() << ": ";
         FS.second.print(OS, Indent + 4);
       }
     }
     OS << "}\n";
   } else {
     OS << "No inlined callsites in this function\n";
   }
 }

lib/ProfileData/SampleProfWriter.cpp

 /// it needs to be parsed by the SampleProfileReaderText class.
 std::error_code SampleProfileWriterText::write(const FunctionSamples &S) {
   auto &OS = *OutputStream;
   OS << S.getName() << ":" << S.getTotalSamples();
   if (Indent == 0)
     OS << ":" << S.getHeadSamples();
   OS << "\n";
 
-  SampleSorter<LineLocation, SampleRecord> SortedSamples(S.getBodySamples());
-  for (const auto &I : SortedSamples.get()) {
-    LineLocation Loc = I->first;
-    const SampleRecord &Sample = I->second;
+  for (const auto &I : S.getBodySamples()) {
+    LineLocation Loc = I.first;
+    const SampleRecord &Sample = I.second;
     OS.indent(Indent + 1);
     if (Loc.Discriminator == 0)
       OS << Loc.LineOffset << ": ";
     else
       OS << Loc.LineOffset << "." << Loc.Discriminator << ": ";
 
     OS << Sample.getSamples();
 
     for (const auto &J : Sample.getCallTargets())
-      OS << " " << J.first() << ":" << J.second;
+      OS << " " << J.first << ":" << J.second;
     OS << "\n";
   }
 
-  SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(
-      S.getCallsiteSamples());
   Indent += 1;
-  for (const auto &I : SortedCallsiteSamples.get())
-    for (const auto &FS : I->second) {
-      LineLocation Loc = I->first;
+  for (const auto &I : S.getCallsiteSamples())
+    for (const auto &FS : I.second) {
+      LineLocation Loc = I.first;
       const FunctionSamples &CalleeSamples = FS.second;
       OS.indent(Indent);
       if (Loc.Discriminator == 0)
         OS << Loc.LineOffset << ": ";
       else
         OS << Loc.LineOffset << "." << Loc.Discriminator << ": ";
       if (std::error_code EC = write(CalleeSamples))
         return EC;
void SampleProfileWriterBinary::addName(StringRef FName) {
   NameTable.insert(std::make_pair(FName, 0));
 }
 
 void SampleProfileWriterBinary::addNames(const FunctionSamples &S) {
   // Add all the names in indirect call targets.
   for (const auto &I : S.getBodySamples()) {
     const SampleRecord &Sample = I.second;
     for (const auto &J : Sample.getCallTargets())
-      addName(J.first());
+      addName(J.first);
   }
 
   // Recursively add all the names for inlined callsites.
   for (const auto &J : S.getCallsiteSamples())
     for (const auto &FS : J.second) {
       const FunctionSamples &CalleeSamples = FS.second;
       addName(CalleeSamples.getName());
       addNames(CalleeSamples);
std::error_code SampleProfileWriterBinary::writeBody(const FunctionSamples &S) {
   for (const auto &I : S.getBodySamples()) {
     LineLocation Loc = I.first;
     const SampleRecord &Sample = I.second;
     encodeULEB128(Loc.LineOffset, OS);
     encodeULEB128(Loc.Discriminator, OS);
     encodeULEB128(Sample.getSamples(), OS);
     encodeULEB128(Sample.getCallTargets().size(), OS);
     for (const auto &J : Sample.getCallTargets()) {
-      StringRef Callee = J.first();
+      StringRef Callee = J.first;
       uint64_t CalleeSamples = J.second;
       if (std::error_code EC = writeNameIdx(Callee))
         return EC;
       encodeULEB128(CalleeSamples, OS);
     }
   }
 
   // Recursively emit all the callsite samples.

lib/Transforms/IPO/SampleProfile.cpp

void SampleProfileLoader::buildEdges(Function &F) {
   }
 }
 
 /// Returns the sorted CallTargetMap \p M by count in descending order.
 static SmallVector<InstrProfValueData, 2> SortCallTargets(
     const SampleRecord::CallTargetMap &M) {
   SmallVector<InstrProfValueData, 2> R;
   for (auto I = M.begin(); I != M.end(); ++I)
-    R.push_back({Function::getGUID(I->getKey()), I->getValue()});
+    R.push_back({Function::getGUID(I->first), I->second});
   std::sort(R.begin(), R.end(),
             [](const InstrProfValueData &L, const InstrProfValueData &R) {
               if (L.Count == R.Count)
                 return L.Value > R.Value;
               else
                 return L.Count > R.Count;
             });
   return R;

test/tools/llvm-profdata/sample-profile-basic.test

 Basic tests for sample profiles.
 
 1- Show all functions
 RUN: llvm-profdata show --sample %p/Inputs/sample-profile.proftext | FileCheck %s --check-prefix=SHOW1
 SHOW1-DAG: Function: main: 184019, 0, 7 sampled lines
-SHOW1-DAG: 9: 2064, calls: _Z3fooi:631 _Z3bari:1471
+SHOW1-DAG: 9: 2064, calls: _Z3bari:1471 _Z3fooi:631
 SHOW1-DAG: Function: _Z3fooi: 7711, 610, 1 sampled lines
 SHOW1-DAG: Function: _Z3bari: 20301, 1437, 1 sampled lines
 SHOW1-DAG: 1: 1437
 
 2- Show only bar
 RUN: llvm-profdata show --sample --function=_Z3bari %p/Inputs/sample-profile.proftext | FileCheck %s --check-prefix=SHOW2
 SHOW2: Function: _Z3bari: 20301, 1437, 1 sampled lines
 SHOW2: 1: 1437
 SHOW2-NOT: Function: main: 184019, 0, 7 sampled lines
 SHOW2-NOT: Function: _Z3fooi: 7711, 610, 1 sampled lines
 
 3- Convert the profile to binary encoding and check that they are both
    identical.
 RUN: llvm-profdata merge --sample %p/Inputs/sample-profile.proftext --binary -o - | llvm-profdata show --sample - -o %t-binary
 RUN: llvm-profdata show --sample %p/Inputs/sample-profile.proftext -o %t-text
 RUN: diff %t-binary %t-text
 
 4- Merge the binary and text encodings of the profile and check that the
    counters have doubled.
 RUN: llvm-profdata merge --sample %p/Inputs/sample-profile.proftext -o %t-binprof
 RUN: llvm-profdata merge --sample --text %p/Inputs/sample-profile.proftext %t-binprof -o - | FileCheck %s --check-prefix=MERGE1
 MERGE1: main:368038:0
-MERGE1: 9: 4128 _Z3fooi:1262 _Z3bari:2942
+MERGE1: 9: 4128 _Z3bari:2942 _Z3fooi:1262
 MERGE1: _Z3bari:40602:2874
 MERGE1: _Z3fooi:15422:1220
 
 5- Detect invalid text encoding (e.g. instrumentation profile text format).
 RUN: not llvm-profdata show --sample %p/Inputs/foo3bar3-1.proftext 2>&1 | FileCheck %s --check-prefix=BADTEXT
 BADTEXT: error: {{.+}}: Unrecognized sample profile encoding format

unittests/ADT/CMakeLists.txt

set(ADTSources
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp
   SparseSetTest.cpp
   StringExtrasTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp
   StringSwitchTest.cpp
+  TinyAssociativeVectorTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
   VariadicFunctionTest.cpp
  )
 
 add_llvm_unittest(ADTTests
   ${ADTSources}
   )
 
 add_dependencies(ADTTests intrinsics_gen)

unittests/ADT/TinyAssociativeVectorTest.cpp

+//===- llvm/unittest/ADT/TinyAssociativeVectorTest.cpp --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// TinyAssociativeVector unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/TinyAssociativeVector.h"
+#include "gtest/gtest.h"
+#include <algorithm>
+#include <initializer_list>
+#include <memory>
+
+using namespace llvm;
+
+namespace {
+struct Nothing {};
+
+TEST(TinyAssociativeVectorTest, IsSorted) {
+  TinyAssociativeVector<int, Nothing> TAV;
+  TAV[5] = {};
+  TAV[1] = {};
+  TAV[2] = {};
+
+  using Value = decltype(TAV)::value_type;
+  EXPECT_TRUE(std::is_sorted(
+      TAV.begin(), TAV.end(),
+      [](const Value &A, const Value &B) { return A.first < B.first; }));
+}
+
+TEST(TinyAssociativeVectorTest, InsertsInSortedOrderWork) {
+  TinyAssociativeVector<int, int> TAV;
+  TAV[0] = 1;
+  TAV[1] = 2;
+  EXPECT_EQ(TAV[1], 2);
+  TAV[2] = 3;
+
+  int I = 0;
+  for (const auto &Pair : TAV) {
+    EXPECT_EQ(Pair.first, I);
+    EXPECT_EQ(Pair.second, I + 1);
+    ++I;
+  }
+
+  EXPECT_EQ(I, 3);
+}
+
+TEST(TinyAssociativeVectorTest, IteratorsFunction) {
+  TinyAssociativeVector<int, int> TAV;
+  TAV[5] = 0;
+  TAV[1] = 1;
+  TAV[2] = 2;
+
+  std::initializer_list<decltype(TAV)::value_type> ExpectedItems = {
+      {1, 1},
+      {2, 2},
+      {5, 0},
+  };
+  ASSERT_EQ(TAV.end() - TAV.begin(), int(ExpectedItems.size()));
+  EXPECT_TRUE(std::equal(TAV.begin(), TAV.end(), ExpectedItems.begin()));
+}
+
+TEST(TinyAssociativeVectorTest, PointersAreStable) {
+  TinyAssociativeVector<int, Nothing> TAV;
+  auto *NothingPtr = &TAV[5];
+
+  // Make it resize
+  TAV[1] = {};
+
+  EXPECT_EQ(NothingPtr, &TAV[5]);
+}
+
+TEST(TinyAssociativeVectorTest, OnlyRequiresOperatorLessThan) {
+  struct OnlyLT {
+    int I;
+    bool operator<(const OnlyLT &O) const { return I < O.I; }
+  };
+
+  TinyAssociativeVector<OnlyLT, Nothing> TAV;
+  TAV[OnlyLT{5}] = {};
+  TAV[OnlyLT{1}] = {};
+  TAV[OnlyLT{2}] = {};
+
+  using Value = decltype(TAV)::value_type;
+  std::initializer_list<Value> ExpectedItems = {
+      {{1}, {}},
+      {{2}, {}},
+      {{5}, {}},
+  };
+
+  ASSERT_EQ(TAV.end() - TAV.begin(), int(ExpectedItems.size()));
+  EXPECT_TRUE(std::equal(
+      TAV.begin(), TAV.end(), ExpectedItems.begin(),
+      [](const Value &A, const Value &B) { return A.first.I == B.first.I; }));
+}
+
+struct OnlyLTInts {
+  int N;
+};
+
+bool operator<(int A, const OnlyLTInts &B) { return A < B.N; }
+bool operator<(const OnlyLTInts &A, int B) { return B < A.N; }
+
+TEST(TinyAssociativeVectorTest, ComparableKeysAreGoodEnoughForFind) {
+  TinyAssociativeVector<int, Nothing> TAV;
+  TAV[0] = {};
+  EXPECT_NE(TAV.find(OnlyLTInts{0}), TAV.end());
+}
+
+TEST(TinyAssociativeVectorTest, CopyAndMoveCtors) {
+  {
+    TinyAssociativeVector<int, Nothing> TAV;
+    auto TAV2 = TAV;
+    EXPECT_TRUE(TAV2.empty());
+
+    auto TAV3 = std::move(TAV);
+    EXPECT_TRUE(TAV3.empty());
+
+    TAV = TAV2;
+    EXPECT_TRUE(TAV.empty());
+
+    TAV = std::move(TAV2);
+    EXPECT_TRUE(TAV.empty());
+  }
+
+  {
+    TinyAssociativeVector<int, Nothing> TAV;
+    auto *Ptr = &TAV[0];
+
+    auto TAV2 = TAV;
+    EXPECT_NE(TAV2.find(0), TAV2.end());
+    EXPECT_NE(Ptr, &TAV2[0]);
+    EXPECT_NE(TAV.find(0), TAV.end());
+    EXPECT_EQ(Ptr, &TAV[0]);
+  }
+
+  {
+    TinyAssociativeVector<int, Nothing> TAV;
+    auto *Ptr = &TAV[0];
+
+    auto TAV2 = std::move(TAV);
+    EXPECT_NE(TAV2.find(0), TAV2.end());
+    EXPECT_EQ(Ptr, &TAV2[0]);
+    EXPECT_EQ(TAV.find(0), TAV.end());
+  }
+
+  {
+    TinyAssociativeVector<int, std::shared_ptr<int>> TAV, TAV2;
+    TAV[0] = std::make_shared<int>(1);
+    std::weak_ptr<int> Elem(TAV[0]);
+
+    TAV2[1] = std::make_shared<int>(2);
+    TAV = TAV2;
+    EXPECT_TRUE(Elem.expired());
+    EXPECT_EQ(&*TAV[0], &*TAV2[0]);
+  }
+
+  {
+    TinyAssociativeVector<int, std::shared_ptr<int>> TAV, TAV2;
+    TAV[0] = std::make_shared<int>(1);
+    std::weak_ptr<int> Elem(TAV[0]);
+
+    TAV2[1] = std::make_shared<int>(2);
+    TAV = std::move(TAV2);
+    EXPECT_TRUE(Elem.expired());
+    EXPECT_EQ(TAV[0], nullptr);
+    EXPECT_EQ(*TAV[1], 2);
+  }
+
+  {
+    TinyAssociativeVector<int, Nothing> TAV;
+    auto *Initial = &TAV[1];
+
+    // Some compilers complain about obvious self-moves.
+    auto *volatile TAVShadow = &TAV;
+    TAV = std::move(*TAVShadow);
+
+    EXPECT_EQ(Initial, &TAV[1]);
+  }
+}
+
+TEST(TinyAssociativeVectorTest, Find) {
+  TinyAssociativeVector<int, Nothing> TAV;
+  auto *Zero = &TAV[0];
+  auto *Two = &TAV[2];
+
+  EXPECT_EQ(TAV.find(-1), TAV.end());
+  EXPECT_EQ(&TAV.find(0)->second, Zero);
+  EXPECT_EQ(TAV.find(1), TAV.end());
+  EXPECT_EQ(&TAV.find(2)->second, Two);
+  EXPECT_EQ(TAV.find(3), TAV.end());
+}
+
+TEST(TinyAssociativeVectorTest, Clear) {
+  TinyAssociativeVector<int, std::shared_ptr<int>> TAV;
+  TAV[0] = std::make_shared<int>(1);
+
+  std::weak_ptr<int> Ptr(TAV[0]);
+  EXPECT_FALSE(Ptr.expired());
+
+  TAV.clear();
+  EXPECT_TRUE(Ptr.expired());
+  EXPECT_TRUE(TAV.empty());
+}
+} // end namespace