Index: include/llvm/ADT/TinyAssociativeVector.h
===================================================================
--- /dev/null
+++ include/llvm/ADT/TinyAssociativeVector.h
@@ -0,0 +1,187 @@
+//===- 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
Index: include/llvm/ProfileData/SampleProf.h
===================================================================
--- include/llvm/ProfileData/SampleProf.h
+++ include/llvm/ProfileData/SampleProf.h
@@ -19,6 +19,7 @@
 #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"
@@ -125,7 +126,7 @@
 /// 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;
 
@@ -167,7 +168,7 @@
   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;
   }
@@ -184,9 +185,10 @@
 
 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<std::string, FunctionSamples>;
+using CallsiteSampleMap =
+    TinyAssociativeVector<LineLocation, FunctionSamplesMap>;
 
 /// Representation of the samples collected for a function.
 ///
@@ -278,7 +280,7 @@
       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;
@@ -347,7 +349,7 @@
       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;
   }
@@ -365,10 +367,10 @@
     // 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)
Index: lib/ProfileData/SampleProf.cpp
===================================================================
--- lib/ProfileData/SampleProf.cpp
+++ lib/ProfileData/SampleProf.cpp
@@ -92,7 +92,7 @@
   if (hasCalls()) {
     OS << ", calls:";
     for (const auto &I : getCallTargets())
-      OS << " " << I.first() << ":" << I.second;
+      OS << " " << I.first << ":" << I.second;
   }
   OS << "\n";
 }
@@ -115,10 +115,10 @@
   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";
@@ -129,12 +129,11 @@
   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);
       }
     }
Index: lib/ProfileData/SampleProfWriter.cpp
===================================================================
--- lib/ProfileData/SampleProfWriter.cpp
+++ lib/ProfileData/SampleProfWriter.cpp
@@ -78,10 +78,9 @@
     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 << ": ";
@@ -91,16 +90,14 @@
     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)
@@ -132,7 +129,7 @@
   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.
@@ -213,7 +210,7 @@
     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;
Index: lib/Transforms/IPO/SampleProfile.cpp
===================================================================
--- lib/Transforms/IPO/SampleProfile.cpp
+++ lib/Transforms/IPO/SampleProfile.cpp
@@ -1187,7 +1187,7 @@
     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)
Index: test/tools/llvm-profdata/sample-profile-basic.test
===================================================================
--- test/tools/llvm-profdata/sample-profile-basic.test
+++ test/tools/llvm-profdata/sample-profile-basic.test
@@ -3,7 +3,7 @@
 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
@@ -26,7 +26,7 @@
 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
 
Index: unittests/ADT/CMakeLists.txt
===================================================================
--- unittests/ADT/CMakeLists.txt
+++ unittests/ADT/CMakeLists.txt
@@ -60,6 +60,7 @@
   StringMapTest.cpp
   StringRefTest.cpp
   StringSwitchTest.cpp
+  TinyAssociativeVectorTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
Index: unittests/ADT/TinyAssociativeVectorTest.cpp
===================================================================
--- /dev/null
+++ unittests/ADT/TinyAssociativeVectorTest.cpp
@@ -0,0 +1,211 @@
+//===- 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