This is an archive of the discontinued LLVM Phabricator instance.

Speed up accelerator table lookups
ClosedPublic

Authored by aprantl on Oct 8 2019, 6:13 PM.

Details

Summary

When debugging a large program like clang and doing "frame variable *this", the ValueObject pretty printer is doing hundreds of scoped FindTypes lookups. The ones that take longest are the ones where the DWARFDeclContext ends in something like ::Iterator which produces many false positives that need to be filtered out *after* extracting the DIEs. This patch demonstrates a way to filter out false positives at the accerator table lookup step.

With this patch lldb clang-10 -o "b EmitFunctionStart" -o r -o "f 2" -o "fr v *this" -b -- ... goes from 5.6s -> 4.83s or wall clock 6.979s -> 5.99s.
There are probably other good heuristics, too, and I should also implement this for DWARF 5 debug_names.

Diff Detail

Event Timeline

aprantl created this revision.Oct 8 2019, 6:13 PM
aprantl updated this revision to Diff 224140.Oct 9 2019, 1:26 PM

Now with testcase!

aprantl updated this revision to Diff 224145.Oct 9 2019, 1:40 PM
aprantl retitled this revision from WIP: Speed up accelerator table lookups to Speed up accelerator table lookups.
JDevlieghere added inline comments.Oct 9 2019, 1:59 PM
lldb/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp
114

This comment gives the impression that this heuristic only applies to std::vector, maybe reword it to make it clear that this is just an example?

aprantl updated this revision to Diff 224161.Oct 9 2019, 2:13 PM

That qualified name hash the Apple tables used to avoid pulling in DWARF for stuff that didn't match. Did this functionality stop working when accelerator tables got refactored? The .apple_types has a qualified name hash which is the hash of the complete type named (demangled).

lldb/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp
114

The "qualified_name_hash" used to avoid pulling in all DWARF for anything that didn't match. Is this not working anymore?

aprantl updated this revision to Diff 224193.Oct 9 2019, 3:44 PM

Address feedback from Jonas.

That qualified name hash the Apple tables used to avoid pulling in DWARF for stuff that didn't match. Did this functionality stop working when accelerator tables got refactored? The .apple_types has a qualified name hash which is the hash of the complete type named (demangled).

Interesting point! I checked all the way back to clang-500 and it turns out that clang never emitted the qualified name hash, this is something that only dsymutil knows how to do.

(and my patch is meant primarily for the non-dsym case)

aprantl updated this revision to Diff 224197.Oct 9 2019, 4:16 PM

Added a if (!has_qualified_name_hash).

I think this addresses all outstanding questions?

So now we are doing two lookups each time we are doing a lookup? One idea to improve upon this would be to do this search a bit later on after we lookup "iterator" and only do this extra context matching if we find at last a certain number of results? So the flow would go:

  • do normal lookup on "iterator" and find N matches
  • if N is large enough then do your search above?

See inline code for an example of a possible improvement

lldb/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp
112–114

s/exampe/example/

112–114

This should probably be moved down into line 139 and 143 instead of checking "if (! has_qualified_name_hash..."? See inline comments below.

123–148

We can probably move your code above to here:

} else {
  if (context.GetSize() > 1) && (context[1].tag == DW_TAG_class_type ||
                                 context[1].tag == DW_TAG_structure_type)) {
    DIEArray class_matches;
    m_apple_types_up->FindByName(context[1].name, class_matches);
    if (class_matches.empty())
      return;
  }
  if (has_tag) {
    if (log)
      m_module.LogMessage(log, "FindByNameAndTag()");
    m_apple_types_up->FindByNameAndTag(type_name.GetStringRef(), tag, offsets);
  } else
    m_apple_types_up->FindByName(type_name.GetStringRef(), offsets);
}

Or better yet:

} else {
   if (has_tag) {
     if (log)
       m_module.LogMessage(log, "FindByNameAndTag()");
     m_apple_types_up->FindByNameAndTag(type_name.GetStringRef(), tag, offsets);
   } else
     m_apple_types_up->FindByName(type_name.GetStringRef(), offsets);
   // If we have too many matches, we might want to ensure that the context
   // that this type is contained in actually exists so we don't end up pulling 
   // in too much DWARF for common type like "iterator".
   if (offsets.size() > THRESHOLD) {
     if (context.GetSize() > 1) && (context[1].tag == DW_TAG_class_type ||
                                    context[1].tag == DW_TAG_structure_type)) {
       DIEArray class_matches;
       m_apple_types_up->FindByName(context[1].name, class_matches);
       if (class_matches.empty()) {
         offsets.clear();
         return;
       }
     }
   }
 }

We might also be able to remove some offsets from "offsets" by iterating through "offsets" and removing any values that come before an entry in "class_matches". For example if offsets contains:

offsets = [0x1100, 0x2100, 0x3100, 0x4100]

and

class_offsets = [0x4000]

could we remove "[0x1100, 0x2100, 0x3100]" from offsets? Maybe not with DW_AT_specification and DW_AT_abstract_origin?

aprantl marked an inline comment as done.Oct 10 2019, 10:39 AM
aprantl added inline comments.
lldb/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp
123–148

Moving the code into the else (first suggestion) is equivalent, but may be more obvious to read. Thanks.

The second suggestions is not a clear win to me. The point of this patch is to eliminate entire .o files quickly that don't have the parent class type in it, in order to avoid extracting type DIEs for matches. The assumption here is that an accelerator table lookup is much cheaper than extracting a DIE. I believe the threshold is 1.

I also learned to never make assumptions about performance, so here are some numbers for my clang benchmark:

original: 8.7s
this patch: 5.9s
threshold 100: 6.5s
threshold  50: 6.5s
threshold  25: 6.5s
threshold  12: 6.4s
threshold   6: 6.4s
threshold   3: 6.4s
threshold   1: 6.5s
JDevlieghere added inline comments.Oct 10 2019, 10:39 AM
lldb/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp
112–114

Missing " before ).

aprantl updated this revision to Diff 224407.Oct 10 2019, 10:40 AM

Address feedback from Greg.

aprantl updated this revision to Diff 224409.Oct 10 2019, 10:41 AM

and feedback from Jonas.

clayborg accepted this revision.Oct 10 2019, 10:45 AM

Sounds good, thanks for entertaining the extra fix and proving it didn't work!

This revision is now accepted and ready to land.Oct 10 2019, 10:45 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptOct 10 2019, 11:03 AM