Save memory in ASTReader by using DenseMap instead of vector

[yamaguchi]

Summary

ReadASTBlock was allocating extra memory by resizing vector for all
record decls, and half of them stayed nullptr without being loaded. For
us this part was crucial and this patch had large amount of memory
improvement.

About clang performance regression, I run whole clang test 5 times
with and without this patch and took average:
Without patch: 239.43400000000003
With patch : 238.862
So I think this doesn't cause cpu time regression.

[yamaguchi]

FYI, raw benchmarking data:
https://gist.github.com/yamaguchi1024/4f28406f51b413129cc762365fdd76c8
https://gist.github.com/yamaguchi1024/318b30db03adb10b7b230b706012a14c

[v.g.vassilev]

Ping...

clang/include/clang/Serialization/ASTReader.h

private:
   /// A map of reversed (SourceManager::MaxLoadedOffset - SLocOffset)
   /// SourceLocation offsets to the modules containing them.
   GlobalSLocOffsetMapType GlobalSLocOffsetMap;
 
   /// Types that have already been loaded from the chain.
   ///
   /// When the pointer at index I is non-NULL, the type with
   /// ID = (I + 1) << FastQual::Width has already been loaded
-  std::vector<QualType> TypesLoaded;
+  llvm::DenseMap<unsigned, QualType> TypesLoaded;
+
+  /// A sum of the number of record types of TYPE_OFFSET.
+  unsigned NumTypes = 0;
 
   using GlobalTypeMapType =
       ContinuousRangeMap<serialization::TypeID, ModuleFile *, 4>;
 
   /// Mapping from global type IDs to the module in which the
   /// type resides along with the offset that should be added to the
   /// global type ID to produce a local ID.
   GlobalTypeMapType GlobalTypeMap;
 
   /// Declarations that have already been loaded from the chain.
   ///
   /// When the pointer at index I is non-NULL, the declaration with ID
   /// = I + 1 has already been loaded.
-  std::vector<Decl *> DeclsLoaded;
+  llvm::DenseMap<unsigned, Decl *> DeclsLoaded;
+
+  /// A sum of the number of record types of DECL_OFFSET.
+  unsigned NumDecls = 0;
 
   using GlobalDeclMapType =
       ContinuousRangeMap<serialization::DeclID, ModuleFile *, 4>;
 
   /// Mapping from global declaration IDs to the module in which the
   /// declaration resides.
   GlobalDeclMapType GlobalDeclMap;
 
private:
   GlobalIdentifierMapType GlobalIdentifierMap;
 
   /// A vector containing macros that have already been
   /// loaded.
   ///
   /// If the pointer at index I is non-NULL, then it refers to the
   /// MacroInfo for the identifier with ID=I+1 that has already
   /// been loaded.
-  std::vector<MacroInfo *> MacrosLoaded;
+  llvm::DenseMap<unsigned, MacroInfo *> MacrosLoaded;
+
+  /// A sum of the number of record types of MACRO_OFFSET.
+  unsigned NumMacros = 0;
 
   using LoadedMacroInfo =
       std::pair<IdentifierInfo *, serialization::SubmoduleID>;
 
   /// A set of #undef directives that we have loaded; used to
   /// deduplicate the same #undef information coming from multiple module
   /// files.
   llvm::DenseSet<LoadedMacroInfo> LoadedUndefs;
public:
   }
 
   /// Returns the number of identifiers found in the chain.
   unsigned getTotalNumIdentifiers() const {
     return static_cast<unsigned>(IdentifiersLoaded.size());
   }
 
   /// Returns the number of macros found in the chain.
-  unsigned getTotalNumMacros() const {
-    return static_cast<unsigned>(MacrosLoaded.size());
-  }
+  unsigned getTotalNumMacros() const { return NumMacros; }
 
   /// Returns the number of types found in the chain.
-  unsigned getTotalNumTypes() const {
-    return static_cast<unsigned>(TypesLoaded.size());
-  }
+  unsigned getTotalNumTypes() const { return NumTypes; }
 
   /// Returns the number of declarations found in the chain.
-  unsigned getTotalNumDecls() const {
-    return static_cast<unsigned>(DeclsLoaded.size());
-  }
+  unsigned getTotalNumDecls() const { return NumDecls; }
 
   /// Returns the number of submodules known.
   unsigned getTotalNumSubmodules() const {
     return static_cast<unsigned>(SubmodulesLoaded.size());
   }
 
   /// Returns the number of selectors found in the chain.
   unsigned getTotalNumSelectors() const {

clang/lib/Serialization/ASTReader.cpp

case TYPE_OFFSET: {
         // Introduce the global -> local mapping for types within this module.
         GlobalTypeMap.insert(std::make_pair(getTotalNumTypes(), &F));
 
         // Introduce the local -> global mapping for types within this module.
         F.TypeRemap.insertOrReplace(
           std::make_pair(LocalBaseTypeIndex,
                          F.BaseTypeIndex - LocalBaseTypeIndex));
 
-        TypesLoaded.resize(TypesLoaded.size() + F.LocalNumTypes);
+        NumTypes += F.LocalNumTypes;
       }
       break;
     }
 
     case DECL_OFFSET: {
       if (F.LocalNumDecls != 0) {
         Error("duplicate DECL_OFFSET record in AST file");
         return Failure;
case DECL_OFFSET: {
         // module.
         F.DeclRemap.insertOrReplace(
           std::make_pair(LocalBaseDeclID, F.BaseDeclID - LocalBaseDeclID));
 
         // Introduce the global -> local mapping for declarations within this
         // module.
         F.GlobalToLocalDeclIDs[&F] = LocalBaseDeclID;
 
-        DeclsLoaded.resize(DeclsLoaded.size() + F.LocalNumDecls);
+        NumDecls += F.LocalNumDecls;
       }
       break;
     }
 
     case TU_UPDATE_LEXICAL: {
       DeclContext *TU = ContextObj->getTranslationUnitDecl();
       LexicalContents Contents(
           reinterpret_cast<const llvm::support::unaligned_uint32_t *>(
case MACRO_OFFSET: {
         // Introduce the global -> local mapping for macros within this module.
         GlobalMacroMap.insert(std::make_pair(getTotalNumMacros() + 1, &F));
 
         // Introduce the local -> global mapping for macros within this module.
         F.MacroRemap.insertOrReplace(
           std::make_pair(LocalBaseMacroID,
                          F.BaseMacroID - LocalBaseMacroID));
 
-        MacrosLoaded.resize(MacrosLoaded.size() + F.LocalNumMacros);
+        NumMacros += F.LocalNumMacros;
       }
       break;
     }
 
     case LATE_PARSED_TEMPLATE:
       LateParsedTemplates.append(Record.begin(), Record.end());
       break;
 
case PREDEF_TYPE_OMP_ARRAY_SECTION:
       break;
     }
 
     assert(!T.isNull() && "Unknown predefined type");
     return T.withFastQualifiers(FastQuals);
   }
 
   Index -= NUM_PREDEF_TYPE_IDS;
-  assert(Index < TypesLoaded.size() && "Type index out-of-range");
-  if (TypesLoaded[Index].isNull()) {
-    TypesLoaded[Index] = readTypeRecord(Index);
-    if (TypesLoaded[Index].isNull())
+  assert(Index < NumTypes && "Type index out-of-range");
+  if (TypesLoaded.find(Index) == TypesLoaded.end()) {
+    QualType QualTy = readTypeRecord(Index);
+    TypesLoaded.insert({Index, QualTy});
+    if (TypesLoaded.find(Index) == TypesLoaded.end())
       return QualType();
 
-    TypesLoaded[Index]->setFromAST();
+    QualTy->setFromAST();
     if (DeserializationListener)
-      DeserializationListener->TypeRead(TypeIdx::fromTypeID(ID),
-                                        TypesLoaded[Index]);
+      DeserializationListener->TypeRead(TypeIdx::fromTypeID(ID), QualTy);
   }
 
-  return TypesLoaded[Index].withFastQualifiers(FastQuals);
+  return TypesLoaded.find(Index)->second.withFastQualifiers(FastQuals);
 }
 
 QualType ASTReader::getLocalType(ModuleFile &F, unsigned LocalID) {
   return GetType(getGlobalTypeID(F, LocalID));
 }
 
 serialization::TypeID
 ASTReader::getGlobalTypeID(ModuleFile &F, unsigned LocalID) const {

 }
 
 SourceLocation ASTReader::getSourceLocationForDeclID(GlobalDeclID ID) {
   if (ID < NUM_PREDEF_DECL_IDS)
     return SourceLocation();
 
   unsigned Index = ID - NUM_PREDEF_DECL_IDS;
 
-  if (Index > DeclsLoaded.size()) {
+  if (Index > NumDecls) {
     Error("declaration ID out-of-range for AST file");
     return SourceLocation();
   }
 
-  if (Decl *D = DeclsLoaded[Index])
-    return D->getLocation();
+  auto FindRes = DeclsLoaded.find(Index);
+  if (FindRes != DeclsLoaded.end())
+    return FindRes->second->getLocation();
 
   SourceLocation Loc;
   DeclCursorForID(ID, Loc);
   return Loc;
 }
 
 static Decl *getPredefinedDecl(ASTContext &Context, PredefinedDeclIDs ID) {
   switch (ID) {
if (D) {
       if (Merged.empty())
         Merged.push_back(ID);
     }
     return D;
   }
 
   unsigned Index = ID - NUM_PREDEF_DECL_IDS;
 
-  if (Index >= DeclsLoaded.size()) {
+  if (Index >= NumDecls) {
     assert(0 && "declaration ID out-of-range for AST file");
     Error("declaration ID out-of-range for AST file");
     return nullptr;
   }
 
-  return DeclsLoaded[Index];
+  auto FindRes = DeclsLoaded.find(Index);
+  if (FindRes == DeclsLoaded.end())
+    return nullptr;
+
+  return FindRes->second;
 }
 
 Decl *ASTReader::GetDecl(DeclID ID) {
   if (ID < NUM_PREDEF_DECL_IDS)
     return GetExistingDecl(ID);
 
   unsigned Index = ID - NUM_PREDEF_DECL_IDS;
 
-  if (Index >= DeclsLoaded.size()) {
+  if (Index >= NumDecls) {
     assert(0 && "declaration ID out-of-range for AST file");
     Error("declaration ID out-of-range for AST file");
     return nullptr;
   }
 
-  if (!DeclsLoaded[Index]) {
+  if (DeclsLoaded.find(Index) == DeclsLoaded.end()) {
     ReadDeclRecord(ID);
     if (DeserializationListener)
-      DeserializationListener->DeclRead(ID, DeclsLoaded[Index]);
+      DeserializationListener->DeclRead(ID, DeclsLoaded.find(Index)->second);
   }
 
-  return DeclsLoaded[Index];
+  return DeclsLoaded.find(Index)->second;
 }
 
 DeclID ASTReader::mapGlobalIDToModuleFileGlobalID(ModuleFile &M,
                                                   DeclID GlobalID) {
   if (GlobalID < NUM_PREDEF_DECL_IDS)
     return GlobalID;
 
   GlobalDeclMapType::const_iterator I = GlobalDeclMap.find(GlobalID);
void ASTReader::StartTranslationUnit(ASTConsumer *Consumer) {
 
   if (DeserializationListener)
     DeserializationListener->ReaderInitialized(this);
 }
 
 void ASTReader::PrintStats() {
   std::fprintf(stderr, "*** AST File Statistics:\n");
 
-  unsigned NumTypesLoaded
-    = TypesLoaded.size() - std::count(TypesLoaded.begin(), TypesLoaded.end(),
-                                      QualType());
-  unsigned NumDeclsLoaded
-    = DeclsLoaded.size() - std::count(DeclsLoaded.begin(), DeclsLoaded.end(),
-                                      (Decl *)nullptr);
   unsigned NumIdentifiersLoaded
     = IdentifiersLoaded.size() - std::count(IdentifiersLoaded.begin(),
                                             IdentifiersLoaded.end(),
                                             (IdentifierInfo *)nullptr);
-  unsigned NumMacrosLoaded
-    = MacrosLoaded.size() - std::count(MacrosLoaded.begin(),
-                                       MacrosLoaded.end(),
-                                       (MacroInfo *)nullptr);
   unsigned NumSelectorsLoaded
     = SelectorsLoaded.size() - std::count(SelectorsLoaded.begin(),
                                           SelectorsLoaded.end(),
                                           Selector());
 
   if (unsigned TotalNumSLocEntries = getTotalNumSLocs())
     std::fprintf(stderr, "  %u/%u source location entries read (%f%%)\n",
                  NumSLocEntriesRead, TotalNumSLocEntries,
                  ((float)NumSLocEntriesRead/TotalNumSLocEntries * 100));
-  if (!TypesLoaded.empty())
-    std::fprintf(stderr, "  %u/%u types read (%f%%)\n",
-                 NumTypesLoaded, (unsigned)TypesLoaded.size(),
-                 ((float)NumTypesLoaded/TypesLoaded.size() * 100));
-  if (!DeclsLoaded.empty())
+  if (!NumTypes)
+    std::fprintf(stderr, "  %u/%u types read (%f%%)\n", TypesLoaded.size(),
+                 (unsigned)NumTypes,
+                 ((float)TypesLoaded.size() / NumTypes * 100));
+  if (!NumDecls)
     std::fprintf(stderr, "  %u/%u declarations read (%f%%)\n",
-                 NumDeclsLoaded, (unsigned)DeclsLoaded.size(),
-                 ((float)NumDeclsLoaded/DeclsLoaded.size() * 100));
+                 DeclsLoaded.size(), (unsigned)NumDecls,
+                 ((float)DeclsLoaded.size() / NumDecls * 100));
   if (!IdentifiersLoaded.empty())
     std::fprintf(stderr, "  %u/%u identifiers read (%f%%)\n",
                  NumIdentifiersLoaded, (unsigned)IdentifiersLoaded.size(),
                  ((float)NumIdentifiersLoaded/IdentifiersLoaded.size() * 100));
-  if (!MacrosLoaded.empty())
-    std::fprintf(stderr, "  %u/%u macros read (%f%%)\n",
-                 NumMacrosLoaded, (unsigned)MacrosLoaded.size(),
-                 ((float)NumMacrosLoaded/MacrosLoaded.size() * 100));
+  if (!NumMacros)
+    std::fprintf(stderr, "  %u/%u macros read (%f%%)\n", MacrosLoaded.size(),
+                 (unsigned)NumMacros,
+                 ((float)MacrosLoaded.size() / NumMacros * 100));
   if (!SelectorsLoaded.empty())
     std::fprintf(stderr, "  %u/%u selectors read (%f%%)\n",
                  NumSelectorsLoaded, (unsigned)SelectorsLoaded.size(),
                  ((float)NumSelectorsLoaded/SelectorsLoaded.size() * 100));
   if (TotalNumStatements)
     std::fprintf(stderr, "  %u/%u statements read (%f%%)\n",
                  NumStatementsRead, TotalNumStatements,
                  ((float)NumStatementsRead/TotalNumStatements * 100));
IdentifierID ASTReader::getGlobalIdentifierID(ModuleFile &M, unsigned LocalID) {
 
   return LocalID + I->second;
 }
 
 MacroInfo *ASTReader::getMacro(MacroID ID) {
   if (ID == 0)
     return nullptr;
 
-  if (MacrosLoaded.empty()) {
+  if (!NumMacros) {
     Error("no macro table in AST file");
     return nullptr;
   }
 
   ID -= NUM_PREDEF_MACRO_IDS;
-  if (!MacrosLoaded[ID]) {
+  auto FindRes = MacrosLoaded.find(ID);
+  if (FindRes == MacrosLoaded.end()) {
     GlobalMacroMapType::iterator I
       = GlobalMacroMap.find(ID + NUM_PREDEF_MACRO_IDS);
     assert(I != GlobalMacroMap.end() && "Corrupted global macro map");
     ModuleFile *M = I->second;
     unsigned Index = ID - M->BaseMacroID;
-    MacrosLoaded[ID] = ReadMacroRecord(*M, M->MacroOffsets[Index]);
+    MacroInfo *MI = ReadMacroRecord(*M, M->MacroOffsets[Index]);
+    MacrosLoaded.insert({ID, MI});
 
     if (DeserializationListener)
-      DeserializationListener->MacroRead(ID + NUM_PREDEF_MACRO_IDS,
-                                         MacrosLoaded[ID]);
+      DeserializationListener->MacroRead(ID + NUM_PREDEF_MACRO_IDS, MI);
   }
 
-  return MacrosLoaded[ID];
+  FindRes = MacrosLoaded.find(ID);
+  if (FindRes == MacrosLoaded.end())
+    return nullptr;
+  return FindRes->second;
 }
 
 MacroID ASTReader::getGlobalMacroID(ModuleFile &M, unsigned LocalID) {
   if (LocalID < NUM_PREDEF_MACRO_IDS)
     return LocalID;
 
   if (!M.ModuleOffsetMap.empty())
     ReadModuleOffsetMap(M);

clang/lib/Serialization/ASTReaderDecl.cpp

 
 /// Note that we have loaded the declaration with the given
 /// Index.
 ///
 /// This routine notes that this declaration has already been loaded,
 /// so that future GetDecl calls will return this declaration rather
 /// than trying to load a new declaration.
 inline void ASTReader::LoadedDecl(unsigned Index, Decl *D) {
-  assert(!DeclsLoaded[Index] && "Decl loaded twice?");
-  DeclsLoaded[Index] = D;
+  assert((DeclsLoaded.find(Index) == DeclsLoaded.end()) &&
+         "Decl loaded twice?");
+  DeclsLoaded.insert({Index, D});
 }
 
 /// Determine whether the consumer will be interested in seeing
 /// this declaration (via HandleTopLevelDecl).
 ///
 /// This routine should return true for anything that might affect
 /// code generation, e.g., inline function definitions, Objective-C
 /// declarations with metadata, etc.