[lldb] Speed up DebugAbbrev parsing

[bulbazord]

Summary

While measuring some performance in LLDB I noticed that we were
spending a decent amount of time parsing the debug abbrev section.

There are 2 very easy ways to improve speed here:

• Move DWARFAbbreviationDeclarationSets into the the DWARFDebugAbbrev map
• Use an llvm::SmallVector instead of a std::vector for DWARFAbbreviationDeclaration's m_attributes field. These things hardly ever have more than 10-11 attributes, so SmallVector seems like a better fit.

To measure performance impact, I took a project with 10,000 c++ source
files, built objects out of them all, and linked them into one binary.
Then I loaded it into lldb, placed a breakpoint on main, and then
exited.

Without this patch, it took about 5.2 seconds on my machine. With this
patch, it took about 4.9 seconds, so this shaves off about 300ms of
time.

[aprantl]

Did you also measure the extra memory consumption? I would be surprised if this mattered, but we do parse a lot of DWARF DIEs...

Generally this seems fine.

[bulbazord]

In D149214#4300491, @aprantl wrote:

Did you also measure the extra memory consumption? I would be surprised if this mattered, but we do parse a lot of DWARF DIEs...

Generally this seems fine.

I compared the memory profile before/after this change. The summary is that we consume about 50% more memory on average (283mb vs 425mb) but our total number of allocations is down by over half. This makes sense because the size of DWARFAbbreviationDeclaration now includes the size of 8 DWARFAttributes, so when we create the DWARFAbbreviationDeclaration and copy it into the DWARFAbbreviationDeclarationSet's vector, we're going to allocate more memory to hold each one. However, most DWARFAbbreviationDeclarations probably don't use all 8 slots of the SmallVector on average, so maybe we could tune this number further to reduce overall memory consumptions?

For what it's worth, llvm's version of DWARFAbbreviationDeclaration also stores attributes in a SmallVector<$attribute_type, 8> as well, so we're not doing any worse than LLVM in this regard.

[JDevlieghere]

In D149214#4300547, @bulbazord wrote:

In D149214#4300491, @aprantl wrote:

Did you also measure the extra memory consumption? I would be surprised if this mattered, but we do parse a lot of DWARF DIEs...

Generally this seems fine.

I compared the memory profile before/after this change. The summary is that we consume about 50% more memory on average (283mb vs 425mb) but our total number of allocations is down by over half. This makes sense because the size of DWARFAbbreviationDeclaration now includes the size of 8 DWARFAttributes, so when we create the DWARFAbbreviationDeclaration and copy it into the DWARFAbbreviationDeclarationSet's vector, we're going to allocate more memory to hold each one. However, most DWARFAbbreviationDeclarations probably don't use all 8 slots of the SmallVector on average, so maybe we could tune this number further to reduce overall memory consumptions?

I think it would be worthwhile to take something like clang and see how many abbreviations there are on average. I assume that should be relatively easy to track as a running average with a static variable. I also wonder what the performance hit would be if we went down to say 4 and have to allocate on the heap more frequently. I don't think it makes sense to use a non-power-of-2 value.

[labath]

I guess the most efficient (performance- and memory-wise) approach would be to have a global (well, scoped to a DWARFUnit or something) array of DWARFAttribute objects, and have the individual abbreviations just store pointers/indexes to that.

[kastiglione]

lldb/source/Plugins/SymbolFile/DWARF/DWARFAbbreviationDeclaration.h

61

With this change, can the following be removed from` DWARFAttribute.h`?

typedef std::vector<DWARFAttribute> collection;
typedef collection::iterator iterator;
typedef collection::const_iterator const_iterator;

[bulbazord]

lldb/source/Plugins/SymbolFile/DWARF/DWARFAbbreviationDeclaration.h

61

Possibly? I sort of put this patch on the back burner... but it would be nice to get rid of those as well!

[bulbazord]

Thanks for the reviews and suggestions. I took a step back and looked at DWARFAbbreviationDeclaration and DWARFAttribute in more detail and I've decided I'm going to take this in a slightly different direction. I don't want to repurpose this diff because I'm making a different design decision, but I don't want people here to lose context so I'm going to link this review in the other one. I've added everyone here as reviewers (and more).

New patch: https://reviews.llvm.org/D150418

lldb/source/Plugins/SymbolFile/DWARF/DWARFAbbreviationDeclaration.h

public:
   extract(const lldb_private::DWARFDataExtractor &data,
           lldb::offset_t *offset_ptr);
   bool IsValid();
 
 protected:
   dw_uleb128_t m_code = InvalidCode;
   dw_tag_t m_tag = llvm::dwarf::DW_TAG_null;
   uint8_t m_has_children = 0;
-  DWARFAttribute::collection m_attributes;
+  llvm::SmallVector<DWARFAttribute, 8> m_attributes;
 };
 
 #endif // LLDB_SOURCE_PLUGINS_SYMBOLFILE_DWARF_DWARFABBREVIATIONDECLARATION_H

lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAbbrev.cpp

llvm::Error DWARFDebugAbbrev::parse(const DWARFDataExtractor &data) {
   while (data.ValidOffset(offset)) {
     uint32_t initial_cu_offset = offset;
     DWARFAbbreviationDeclarationSet abbrevDeclSet;
 
     llvm::Error error = abbrevDeclSet.extract(data, &offset);
     if (error)
       return error;
 
-    m_abbrevCollMap[initial_cu_offset] = abbrevDeclSet;
+    m_abbrevCollMap[initial_cu_offset] = std::move(abbrevDeclSet);
   }
   m_prev_abbr_offset_pos = m_abbrevCollMap.end();
   return llvm::ErrorSuccess();
 }
 
 // DWARFDebugAbbrev::GetAbbreviationDeclarationSet()
 const DWARFAbbreviationDeclarationSet *
 DWARFDebugAbbrev::GetAbbreviationDeclarationSet(