[PDB] Improve performance of the PDB DIA plugin

[aleksandr.urakov]

Summary

This patch improves performance of SymbolFilePDB on huge executables in two ways:

• cache names of public symbols by address. When creating variables we are trying to get a mangled name for each one, and in GetMangledForPDBData we are enumerating all public symbols, which takes O(n) for each variable. With the cache we can retrieve a mangled name in O(log(n));

• cache section contributions. When parsing variables for context we are enumerating all variables and check if the current one is belonging to the current compiland. So we are retrieving a compiland ID for the variable. But in PDBSymbolData::getCompilandId for almost every variable we are enumerating all section contributions to check if the variable is belonging to it, and get a compiland ID from the section contribution if so. It takes O(n) for each variable, but with caching it takes about O(log(n)). I've placed the cache in SymbolFilePDB and have created GetCompilandId there. It actually duplicates PDBSymbolData::getCompilandId except for the cache part. Another option is to support caching in PDBSymbolData::getCompilandId and to place cache in DIASession, but it seems that the last one doesn't imply such functionality, because it's a lightweight wrapper over DIA and whole its state is only a COM pointer to the DIA session. Moreover, PDBSymbolData::getCompilandId is used only inside of SymbolFilePDB, so I think that it's not a bad place to do such things. With this patch PDBSymbolData::getCompilandId is not used at all.

This bottlenecks were found with profiling. I've discovered these on a simple demo project of Unreal Engine (x86 executable ~72M, PDB ~82M).

This patch doesn't change external behavior of the plugin, so I think that there's no need for additional testing (already existing tests should warn us about regress, if any).

[asmith]

Thanks for adding the cache. We noticed the slowdown also and were discussing the same thing. This LGTM if the other reviewers done have any comments.

[aleksandr.urakov]

Thank you!

[Hui]

In D53375#1269504, @asmith wrote:

Thanks for adding the cache. We noticed the slowdown also and were discussing the same thing. This LGTM if the other reviewers done have any comments.

I think parsing types e.g. SymbolFilePDB::ParseTypes also has speed bumps. Will be good to have them cached too.

[aleksandr.urakov]

In D53375#1271336, @Hui wrote:

I think parsing types e.g. SymbolFilePDB::ParseTypes also has speed bumps. Will be good to have them cached too.

We are already caching them, see m_types field.

source/Plugins/SymbolFile/PDB/SymbolFilePDB.h

public:
 
   uint32_t GetPluginVersion() override;
 
   llvm::pdb::IPDBSession &GetPDBSession();
 
   const llvm::pdb::IPDBSession &GetPDBSession() const;
 
 private:
+  struct SecContribInfo {
+    uint32_t Offset;
+    uint32_t Size;
+    uint32_t CompilandId;
+  };
+  using SecContribsMap = std::map<uint32_t, std::vector<SecContribInfo>>;
+
   lldb::CompUnitSP ParseCompileUnitForUID(uint32_t id,
                                           uint32_t index = UINT32_MAX);
 
   bool ParseCompileUnitLineTable(const lldb_private::SymbolContext &sc,
                                  uint32_t match_line);
 
   void BuildSupportFileIdToSupportFileIndexMap(
       const llvm::pdb::PDBSymbolCompiland &pdb_compiland,
private:
   bool ResolveFunction(uint32_t uid, bool include_inlines,
                        lldb_private::SymbolContextList &sc_list);
 
   void CacheFunctionNames();
 
   bool DeclContextMatchesThisSymbolFile(
       const lldb_private::CompilerDeclContext *decl_ctx);
 
+  uint32_t GetCompilandId(const llvm::pdb::PDBSymbolData &data);
+
   llvm::DenseMap<uint32_t, lldb::CompUnitSP> m_comp_units;
   llvm::DenseMap<uint32_t, lldb::TypeSP> m_types;
   llvm::DenseMap<uint32_t, lldb::VariableSP> m_variables;
+  llvm::DenseMap<uint64_t, std::string> m_public_names;
+
+  SecContribsMap m_sec_contribs;
 
   std::vector<lldb::TypeSP> m_builtin_types;
   std::unique_ptr<llvm::pdb::IPDBSession> m_session_up;
   std::unique_ptr<llvm::pdb::PDBSymbolExe> m_global_scope_up;
   uint32_t m_cached_compile_unit_count;
   std::unique_ptr<lldb_private::CompilerDeclContext> m_tu_decl_ctx_up;
 
   lldb_private::UniqueCStringMap<uint32_t> m_func_full_names;
   lldb_private::UniqueCStringMap<uint32_t> m_func_base_names;
   lldb_private::UniqueCStringMap<uint32_t> m_func_method_names;
 };
 
 #endif // lldb_Plugins_SymbolFile_PDB_SymbolFilePDB_h_

source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp

if (!compiland)
       return 0;
 
     if (sc.comp_unit->GetVariableList(false))
       return 0;
 
     auto results = m_global_scope_up->findAllChildren<PDBSymbolData>();
     if (results && results->getChildCount()) {
       while (auto result = results->getNext()) {
-        auto cu_id = result->getCompilandId();
+        auto cu_id = GetCompilandId(*result);
         // FIXME: We are not able to determine variable's compile unit.
         if (cu_id == 0)
           continue;
 
         if (cu_id == sc.comp_unit->GetID())
           num_added += ParseVariables(sc, *result);
       }
     }
while (auto compiland = compilands->getNext()) {
         sc_list.Append(sc);
       }
     }
   }
   return sc_list.GetSize() - old_size;
 }
 
 std::string SymbolFilePDB::GetMangledForPDBData(const PDBSymbolData &pdb_data) {
-  std::string decorated_name;
-  auto vm_addr = pdb_data.getVirtualAddress();
-  if (vm_addr != LLDB_INVALID_ADDRESS && vm_addr) {
-    auto result_up =
-        m_global_scope_up->findAllChildren(PDB_SymType::PublicSymbol);
-    if (result_up) {
-      while (auto symbol_up = result_up->getNext()) {
-        if (symbol_up->getRawSymbol().getVirtualAddress() == vm_addr) {
-          decorated_name = symbol_up->getRawSymbol().getName();
-          break;
-        }
-      }
-    }
-  }
-  if (!decorated_name.empty())
-    return decorated_name;
+  // Cache public names at first
+  if (m_public_names.empty())
+    if (auto result_up =
+            m_global_scope_up->findAllChildren(PDB_SymType::PublicSymbol))
+      while (auto symbol_up = result_up->getNext())
+        if (auto addr = symbol_up->getRawSymbol().getVirtualAddress())
+          m_public_names[addr] = symbol_up->getRawSymbol().getName();
 
-  return std::string();
+  // Look up the name in the cache
+  return m_public_names.lookup(pdb_data.getVirtualAddress());
 }
 
 VariableSP SymbolFilePDB::ParseVariableForPDBData(
     const lldb_private::SymbolContext &sc,
     const llvm::pdb::PDBSymbolData &pdb_data) {
   VariableSP var_sp;
   uint32_t var_uid = pdb_data.getSymIndexId();
   auto result = m_variables.find(var_uid);
while (auto result = results->getNext()) {
     auto pdb_data = llvm::dyn_cast<PDBSymbolData>(result.get());
     if (max_matches > 0 && matches >= max_matches)
       break;
 
     SymbolContext sc;
     sc.module_sp = m_obj_file->GetModule();
     lldbassert(sc.module_sp.get());
 
-    sc.comp_unit = ParseCompileUnitForUID(pdb_data->getCompilandId()).get();
-    // FIXME: We are not able to determine the compile unit.
-    if (sc.comp_unit == nullptr)
-      continue;
-
     if (!name.GetStringRef().equals(
             PDBASTParser::PDBNameDropScope(pdb_data->getName())))
       continue;
 
+    sc.comp_unit = ParseCompileUnitForUID(GetCompilandId(*pdb_data)).get();
+    // FIXME: We are not able to determine the compile unit.
+    if (sc.comp_unit == nullptr)
+      continue;
+
     auto actual_parent_decl_ctx =
         GetDeclContextContainingUID(result->getSymIndexId());
     if (actual_parent_decl_ctx != *parent_decl_ctx)
       continue;
 
     ParseVariables(sc, *pdb_data, &variables);
     matches = variables.GetSize() - old_size;
   }
while (auto pdb_data = results->getNext()) {
     if (var_name.empty())
       continue;
     if (!regex.Execute(var_name))
       continue;
     SymbolContext sc;
     sc.module_sp = m_obj_file->GetModule();
     lldbassert(sc.module_sp.get());
 
-    sc.comp_unit = ParseCompileUnitForUID(pdb_data->getCompilandId()).get();
+    sc.comp_unit = ParseCompileUnitForUID(GetCompilandId(*pdb_data)).get();
     // FIXME: We are not able to determine the compile unit.
     if (sc.comp_unit == nullptr)
       continue;
 
     ParseVariables(sc, *pdb_data, &variables);
     matches = variables.GetSize() - old_size;
   }
 
if (!decl_ctx_type_system)
     return false;
   TypeSystem *type_system = GetTypeSystemForLanguage(
       decl_ctx_type_system->GetMinimumLanguage(nullptr));
   if (decl_ctx_type_system == type_system)
     return true; // The type systems match, return true
 
   return false;
 }
+
+uint32_t SymbolFilePDB::GetCompilandId(const llvm::pdb::PDBSymbolData &data) {
+  static const auto pred_upper = [](uint32_t lhs, SecContribInfo rhs) {
+    return lhs < rhs.Offset;
+  };
+
+  // Cache section contributions
+  if (m_sec_contribs.empty()) {
+    if (auto SecContribs = m_session_up->getSectionContribs()) {
+      while (auto SectionContrib = SecContribs->getNext()) {
+        auto comp_id = SectionContrib->getCompilandId();
+        if (!comp_id)
+          continue;
+
+        auto sec = SectionContrib->getAddressSection();
+        auto &sec_cs = m_sec_contribs[sec];
+
+        auto offset = SectionContrib->getAddressOffset();
+        auto it =
+            std::upper_bound(sec_cs.begin(), sec_cs.end(), offset, pred_upper);
+
+        auto size = SectionContrib->getLength();
+        sec_cs.insert(it, {offset, size, comp_id});
+      }
+    }
+  }
+
+  // Check by line number
+  if (auto Lines = data.getLineNumbers()) {
+    if (auto FirstLine = Lines->getNext())
+      return FirstLine->getCompilandId();
+  }
+
+  // Retrieve section + offset
+  uint32_t DataSection = data.getAddressSection();
+  uint32_t DataOffset = data.getAddressOffset();
+  if (DataSection == 0) {
+    if (auto RVA = data.getRelativeVirtualAddress())
+      m_session_up->addressForRVA(RVA, DataSection, DataOffset);
+  }
+
+  if (DataSection) {
+    // Search by section contributions
+    auto &sec_cs = m_sec_contribs[DataSection];
+    auto it =
+        std::upper_bound(sec_cs.begin(), sec_cs.end(), DataOffset, pred_upper);
+    if (it != sec_cs.begin()) {
+      --it;
+      if (DataOffset < it->Offset + it->Size)
+        return it->CompilandId;
+    }
+  } else {
+    // Search in lexical tree
+    auto LexParentId = data.getLexicalParentId();
+    while (auto LexParent = m_session_up->getSymbolById(LexParentId)) {
+      if (LexParent->getSymTag() == PDB_SymType::Exe)
+        break;
+      if (LexParent->getSymTag() == PDB_SymType::Compiland)
+        return LexParentId;
+      LexParentId = LexParent->getRawSymbol().getLexicalParentId();
+    }
+  }
+
+  return 0;
+}