Speed up accelerator table lookups

[aprantl]

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.

[aprantl]

Now with testcase!

[JDevlieghere]

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?

[clayborg]

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]

Address feedback from Jonas.

[aprantl]

In D68678#1702418, @clayborg wrote:

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.

[aprantl]

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

[aprantl]

Added a if (!has_qualified_name_hash).

[aprantl]

I think this addresses all outstanding questions?

[clayborg]

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]

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]

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

112–114

Missing " before ).

[aprantl]

Address feedback from Greg.

[aprantl]

and feedback from Jonas.

[clayborg]

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

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/Makefile

+# There is no guaranteed order in which the linker will order these
+# files, so we just have a lot of them to make it unlikely that we hit
+# the right one first by pure luck.
+
+CXX_SOURCES := main.cpp a.cpp b.cpp c.cpp d.cpp e.cpp f.cpp g.cpp
+
+include Makefile.rules

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/TestCPPAccelerator.py

+import lldb
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+
+class CPPAcceleratorTableTestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    @skipUnlessDarwin
+    @skipIf(debug_info=no_match(["dwarf"]))
+    def test(self):
+        """Test that type lookups fail early (performance)"""
+        self.build()
+        logfile = self.getBuildArtifact('dwarf.log')
+        self.expect('log enable dwarf lookups -f' + logfile)
+        target, process, thread, bkpt = lldbutil.run_to_source_breakpoint(
+            self, 'break here', lldb.SBFileSpec('main.cpp'))
+        # Pick one from the middle of the list to have a high chance
+        # of it not being in the first file looked at.
+        self.expect('frame variable inner_d')
+
+        log = open(logfile, 'r')
+        n = 0
+        for line in log:
+            if re.findall(r'[abcdefg]\.o: FindByNameAndTag\(\)', line):
+                self.assertTrue("d.o" in line)
+                n += 1
+
+        self.assertEqual(n, 1, log)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/a.cpp

+#include "source.h"
+CLASS(A)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/b.cpp

+#include "source.h"
+CLASS(B)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/c.cpp

+#include "source.h"
+CLASS(C)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/d.cpp

+#include "source.h"
+CLASS(D)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/e.cpp

+#include "source.h"
+CLASS(E)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/f.cpp

+#include "source.h"
+CLASS(F)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/g.cpp

+#include "source.h"
+CLASS(G)

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/main.cpp

+#define CLASS(NAME)                             \
+  class NAME {                                  \
+  public:                                       \
+    struct Inner;                               \
+    Inner *i = nullptr;                         \
+  };                                            \
+NAME::Inner &getInner##NAME();
+
+CLASS(A)
+CLASS(B)
+CLASS(C)
+CLASS(D)
+CLASS(E)
+CLASS(F)
+CLASS(G)
+
+int main()
+{
+  A::Inner &inner_a = getInnerA();
+  B::Inner &inner_b = getInnerB();
+  C::Inner &inner_c = getInnerC();
+  D::Inner &inner_d = getInnerD();
+  E::Inner &inner_e = getInnerE();
+  F::Inner &inner_f = getInnerF();
+  G::Inner &inner_g = getInnerG();
+
+  return 0; // break here
+}

lldb/packages/Python/lldbsuite/test/lang/cpp/accelerator-table/source.h

+#define CLASS(NAME)                             \
+  class NAME {                                  \
+    public:                                     \
+    class Inner {                               \
+      int j = #NAME[0];                         \
+    };                                          \
+    Inner *i = nullptr;                         \
+  };                                            \
+                                                \
+  static NAME::Inner inner;                     \
+  static NAME obj;                              \
+  NAME::Inner &getInner##NAME() { return inner; }

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

if (!m_apple_types_up)
     return;
 
   Log *log = LogChannelDWARF::GetLogIfAny(DWARF_LOG_TYPE_COMPLETION |
                                           DWARF_LOG_LOOKUPS);
   const bool has_tag = m_apple_types_up->GetHeader().header_data.ContainsAtom(
       DWARFMappedHash::eAtomTypeTag);
   const bool has_qualified_name_hash =
       m_apple_types_up->GetHeader().header_data.ContainsAtom(
           DWARFMappedHash::eAtomTypeQualNameHash);
+
   const ConstString type_name(context[0].name);
   const dw_tag_t tag = context[0].tag;
   if (has_tag && has_qualified_name_hash) {
     const char *qualified_name = context.GetQualifiedName();
     const uint32_t qualified_name_hash = llvm::djbHash(qualified_name);
     if (log)
       m_module.LogMessage(log, "FindByNameAndTagAndQualifiedNameHash()");
     m_apple_types_up->FindByNameAndTagAndQualifiedNameHash(
         type_name.GetStringRef(), tag, qualified_name_hash, offsets);
-  } else if (has_tag) {
+    return;
+  }
+
+  if (has_tag) {
+    // When searching for a scoped type (for example,
+    // "std::vector<int>::const_iterator") searching for the innermost
+    // name alone ("const_iterator") could yield many false
+    // positives. By searching for the parent type ("vector<int>")
+    // first we can avoid extracting type DIEs from object files that
+    // would fail the filter anyway.
+    if (!has_qualified_name_hash && (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 (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);
+    return;
+  }
+
 }
 
 void AppleDWARFIndex::GetNamespaces(ConstString name, DIEArray &offsets) {
   if (m_apple_namespaces_up)
     m_apple_namespaces_up->FindByName(name.GetStringRef(), offsets);
 }
 
 void AppleDWARFIndex::GetFunctions(ConstString name, SymbolFileDWARF &dwarf,