3 files changed, 40 insertions, 10 deletions

diff --git a/clang/lib/Serialization/ASTReader.cpp b/clang/lib/Serialization/ASTReader.cpp
index 91a977bb691..7c83641256a 100644
--- a/clang/lib/Serialization/ASTReader.cpp
+++ b/clang/lib/Serialization/ASTReader.cpp
@@ -959,7 +959,7 @@ ASTDeclContextNameLookupTrait::ReadKey(const unsigned char *d, unsigned) {
 void ASTDeclContextNameLookupTrait::ReadDataInto(internal_key_type,
                                                  const unsigned char *d,
                                                  unsigned DataLen,
-                                                 data_type &Val) {
+                                                 data_type_builder &Val) {
   using namespace llvm::support;
   for (unsigned NumDecls = DataLen / 4; NumDecls; --NumDecls) {
     uint32_t LocalID = endian::readNext<uint32_t, little, unaligned>(d);
diff --git a/clang/lib/Serialization/ASTReaderInternals.h b/clang/lib/Serialization/ASTReaderInternals.h
index 5c239e3a021..5e2728522fa 100644
--- a/clang/lib/Serialization/ASTReaderInternals.h
+++ b/clang/lib/Serialization/ASTReaderInternals.h
@@ -47,8 +47,31 @@ public:
   static const int MaxTables = 4;
 
   /// The lookup result is a list of global declaration IDs.
-  // FIXME: LLVM doesn't really have a good data structure for this.
-  typedef llvm::DenseSet<DeclID> data_type;
+  typedef llvm::SmallVector<DeclID, 4> data_type;
+  struct data_type_builder {
+    data_type &Data;
+    llvm::DenseSet<DeclID> Found;
+
+    data_type_builder(data_type &D) : Data(D) {}
+    void insert(DeclID ID) {
+      // Just use a linear scan unless we have more than a few IDs.
+      if (Found.empty() && !Data.empty()) {
+        if (Data.size() <= 4) {
+          for (auto I : Found)
+            if (I == ID)
+              return;
+          Data.push_back(ID);
+          return;
+        }
+
+        // Switch to tracking found IDs in the set.
+        Found.insert(Data.begin(), Data.end());
+      }
+
+      if (Found.insert(ID).second)
+        Data.push_back(ID);
+    }
+  };
   typedef unsigned hash_value_type;
   typedef unsigned offset_type;
   typedef ModuleFile *file_type;
@@ -76,10 +99,12 @@ public:
   internal_key_type ReadKey(const unsigned char *d, unsigned);
 
   void ReadDataInto(internal_key_type, const unsigned char *d,
-                    unsigned DataLen, data_type &Val);
+                    unsigned DataLen, data_type_builder &Val);
 
-  static void MergeDataInto(const data_type &From, data_type &To) {
-    To.insert(From.begin(), From.end());
+  static void MergeDataInto(const data_type &From, data_type_builder &To) {
+    To.Data.reserve(To.Data.size() + From.size());
+    for (DeclID ID : From)
+      To.insert(ID);
   }
 
   file_type ReadFileRef(const unsigned char *&d);
diff --git a/clang/lib/Serialization/MultiOnDiskHashTable.h b/clang/lib/Serialization/MultiOnDiskHashTable.h
index bf06a77912f..704c6343a1c 100644
--- a/clang/lib/Serialization/MultiOnDiskHashTable.h
+++ b/clang/lib/Serialization/MultiOnDiskHashTable.h
@@ -38,6 +38,7 @@ public:
   typedef typename Info::external_key_type external_key_type;
   typedef typename Info::internal_key_type internal_key_type;
   typedef typename Info::data_type data_type;
+  typedef typename Info::data_type_builder data_type_builder;
   typedef unsigned hash_value_type;
 
 private:
@@ -135,8 +136,9 @@ private:
         // FIXME: Don't rely on the OnDiskHashTable format here.
         auto L = InfoObj.ReadKeyDataLength(LocalPtr);
         const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
+        data_type_builder ValueBuilder(Merged->Data[Key]);
         InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second,
-                             Merged->Data[Key]);
+                             ValueBuilder);
       }
 
       Merged->Files.push_back(ODT->File);
@@ -218,12 +220,14 @@ public:
         Result = It->second;
     }
 
+    data_type_builder ResultBuilder(Result);
+
     for (auto *ODT : tables()) {
       auto &HT = ODT->Table;
       auto It = HT.find_hashed(Key, KeyHash);
       if (It != HT.end())
         HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(),
-                                     Result);
+                                     ResultBuilder);
     }
 
     return Result;
@@ -233,13 +237,14 @@ public:
   /// sense if merging values across keys is meaningful.
   data_type findAll() {
     data_type Result;
+    data_type_builder ResultBuilder(Result);
 
     if (!PendingOverrides.empty())
       removeOverriddenTables();
 
     if (MergedTable *M = getMergedTable()) {
       for (auto &KV : M->Data)
-        Info::MergeDataInto(KV.second, Result);
+        Info::MergeDataInto(KV.second, ResultBuilder);
     }
 
     for (auto *ODT : tables()) {
@@ -251,7 +256,7 @@ public:
         // FIXME: Don't rely on the OnDiskHashTable format here.
         auto L = InfoObj.ReadKeyDataLength(LocalPtr);
         const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
-        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, Result);
+        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder);
       }
     }