[lldb] Don't keep demangled names in memory after indexing

[JDevlieghere]

Summary

The symbol table needs to demangle all symbol names when building its index. However, this doesn't require the full mangled name: we only need the base name and the function declaration context. Currently, we always construct the demangled string during indexing and cache it in the string pool as a way to speed up future lookups. Constructing the demangled string is by far the most expensive step of the demangling process, because the output string can be exponentially larger than the input and unless you're dumping the symbol table, many of those demangled names will not be needed again.

This patch avoids constructing the full demangled string when we can partially demangle. This speeds up indexing and reduces memory usage.

[kastiglione]

the amount of memory we save here is well worth the small performance hit

any numbers to share?

[JDevlieghere]

In D118814#3291174, @kastiglione wrote:

the amount of memory we save here is well worth the small performance hit

any numbers to share?

We have one scenario where this bring memory usage after attach down from 7gb to 1.8gb. (rdar://86413848) This is definitely an extreme example though.

[jingham]

This patch does have one side-effect that I know of, which is that if we don't keep demangled names in the symbol table, then breaking on an overload by demangled name won't work. OTOH, that only worked if you exactly matched the demangler's output - no extra spaces, etc. We don't have a smart matcher for overloads, so I'm not sure that requiring you to supply the mangled name instead in this case is much of a burden.

And if we want to actually have a nice way to break on overloads, it would involve parsing the incoming specification, extracting the method name and arguments, finding the method name matches and then doing some kind of fuzzy match against the arguments. So we wouldn't need to keep all the demangled strings for that purpose either.

IMO the UE for breaking on overloads is not currently good enough that it outweighs the savings we get from not storing all the demangled names. And if this is important to somebody's workflow, they can always get the old behavior back by reversing the setting value.

[JDevlieghere]

The symbol table index is the only caller to DemangleWithRichManglingInfo, so I removed the optional argument. Based on Pavel's observations in D118812 I also removed the setting because the current behavior defeats the purpose of partial demangling.

[JDevlieghere]

Before
Memory usage: 280MB

Benchmark 1: ./bin/lldb -n Slack -o quit
  Time (mean ± σ):      4.829 s ±  0.518 s    [User: 4.012 s, System: 0.208 s]
  Range (min … max):    4.624 s …  6.294 s    10 runs

After
Memory usage: 189MB

Benchmark 1: ./bin/lldb -n Slack -o quit
  Time (mean ± σ):      4.182 s ±  0.025 s    [User: 3.536 s, System: 0.192 s]
  Range (min … max):    4.152 s …  4.233 s    10 runs

[clayborg]

LGTM if the RichManglingContext isn't actually demangling the string anyway, no need to force it to do so and cache the results.

lldb/source/Symbol/Symtab.cpp

387–388

I was checking this function out as the only user of RichManglingContext. Seems that we could modify RichManglingContext::ParseFunctionBaseName() to just return the base name? Seems weird to call parse and then fetch. Could also just rename to "StringRef RichManglingContext::GetFunctionBaseName().

In fact the RichManglingContext class has the notion of an internal buffer where people call some parse routine and then call RichManglingContext::GetBufferRef()? Seems like we should just get rid of the internal buffer and just return it each time from all of the RichManglingContext::ParseXXX routines. Not needed, but just something I found interesting about the RichManglingContext class implementation.

[JDevlieghere]

lldb/source/Symbol/Symtab.cpp

387–388

Agreed. I created a separate patch for that: https://reviews.llvm.org/D118953

[labath]

This seems fine, though it's not clear to me what is the effect of this patch in terms of functionality. Does the "side-effect" mentioned by Jim still apply here, or is this NFC now? Either is probably fine, but I'd like to understand what is going on. It seems like it should be NFC, but does that mean that the demangling (and the cpu/memory cost) is delayed until the first operation which requests it (such as matching a breakpoint by the full demangled name) ?

lldb/source/Core/Mangled.cpp

198

I guess it would be more correct to call this GetRichManglingInfo now

[jingham]

In D118814#3296008, @labath wrote:

This seems fine, though it's not clear to me what is the effect of this patch in terms of functionality. Does the "side-effect" mentioned by Jim still apply here, or is this NFC now? Either is probably fine, but I'd like to understand what is going on. It seems like it should be NFC, but does that mean that the demangling (and the cpu/memory cost) is delayed until the first operation which requests it (such as matching a breakpoint by the full demangled name) ?

I haven't gone back to read our lookups in detail, but I certainly hope that the first time we see a breakpoint on a symbol name we don't recognize, we wouldn't go demangling every symbol name in the system. We really try to keep mistypings from cascading into "unpack the entire world" events.

[JDevlieghere]

In D118814#3297075, @jingham wrote:

In D118814#3296008, @labath wrote:

This seems fine, though it's not clear to me what is the effect of this patch in terms of functionality. Does the "side-effect" mentioned by Jim still apply here, or is this NFC now? Either is probably fine, but I'd like to understand what is going on. It seems like it should be NFC, but does that mean that the demangling (and the cpu/memory cost) is delayed until the first operation which requests it (such as matching a breakpoint by the full demangled name) ?

I haven't gone back to read our lookups in detail, but I certainly hope that the first time we see a breakpoint on a symbol name we don't recognize, we wouldn't go demangling every symbol name in the system. We really try to keep mistypings from cascading into "unpack the entire world" events.

Yes, this does break the ability to set breakpoints on full demangled names. Based on the code and the comments, it really looks like it was always the intention to avoid demangling the whole name, but then (accidentally?) made it work by storing it in the ConstString. The continue on line 333 is what prevents us from indexing the full name. Before this patch, GetDemangledName would return the cached full demanged name, which now isn't cached and would have to be computed on demand (effectively defeating the purpose of this patch and making things slower).

[jingham]

In D118814#3297198, @JDevlieghere wrote:

In D118814#3297075, @jingham wrote:

In D118814#3296008, @labath wrote:

This seems fine, though it's not clear to me what is the effect of this patch in terms of functionality. Does the "side-effect" mentioned by Jim still apply here, or is this NFC now? Either is probably fine, but I'd like to understand what is going on. It seems like it should be NFC, but does that mean that the demangling (and the cpu/memory cost) is delayed until the first operation which requests it (such as matching a breakpoint by the full demangled name) ?

I haven't gone back to read our lookups in detail, but I certainly hope that the first time we see a breakpoint on a symbol name we don't recognize, we wouldn't go demangling every symbol name in the system. We really try to keep mistypings from cascading into "unpack the entire world" events.

Yes, this does break the ability to set breakpoints on full demangled names. Based on the code and the comments, it really looks like it was always the intention to avoid demangling the whole name, but then (accidentally?) made it work by storing it in the ConstString. The continue on line 333 is what prevents us from indexing the full name. Before this patch, GetDemangledName would return the cached full demanged name, which now isn't cached and would have to be computed on demand (effectively defeating the purpose of this patch and making things slower).

We really should come up with a good story for symbol lookup on function names that include arguments, but "match the exact output of the demangler" was never a good story. And I don't think we need pre-demangled names to do it right, rather we should pull the method name out of the user specification, find the matches to that - which goes quickly 'cause it uses the name chopper indices - then winnow down the matches. Since this is just for function name matches, we could even do smart stuff like (this is spitballing, not a proposed design):

(lldb) break set -n foo::bar::bar(int, *)

meaning, the first parameter has to be an int, I don't care about the others, etc.

[labath]

In D118814#3297198, @JDevlieghere wrote:

In D118814#3297075, @jingham wrote:

In D118814#3296008, @labath wrote:

This seems fine, though it's not clear to me what is the effect of this patch in terms of functionality. Does the "side-effect" mentioned by Jim still apply here, or is this NFC now? Either is probably fine, but I'd like to understand what is going on. It seems like it should be NFC, but does that mean that the demangling (and the cpu/memory cost) is delayed until the first operation which requests it (such as matching a breakpoint by the full demangled name) ?

I haven't gone back to read our lookups in detail, but I certainly hope that the first time we see a breakpoint on a symbol name we don't recognize, we wouldn't go demangling every symbol name in the system. We really try to keep mistypings from cascading into "unpack the entire world" events.

Yes, this does break the ability to set breakpoints on full demangled names. Based on the code and the comments, it really looks like it was always the intention to avoid demangling the whole name, but then (accidentally?) made it work by storing it in the ConstString. The continue on line 333 is what prevents us from indexing the full name.

That's what I was missing. Thanks.

lldb/test/API/macosx/dyld-trie-symbols/TestDyldTrieSymbols.py

41

I guess this is no longer true

lldb/source/Core/Mangled.cpp

else
       LLDB_LOG(log, "demangled dlang: {0} -> error: failed to demangle", M);
   }
 
   return demangled_cstr;
 }
 
 // Explicit demangling for scheduled requests during batch processing. This
 // makes use of ItaniumPartialDemangler's rich demangle info
 bool Mangled::DemangleWithRichManglingInfo(
     RichManglingContext &context, SkipMangledNameFn *skip_mangled_name) {
   // Others are not meant to arrive here. ObjC names or C's main() for example
   // have their names stored in m_demangled, while m_mangled is empty.
   assert(m_mangled);
 
   // Check whether or not we are interested in this name at all.
   ManglingScheme scheme = GetManglingScheme(m_mangled.GetStringRef());
   if (skip_mangled_name && skip_mangled_name(m_mangled.GetStringRef(), scheme))
     return false;
 
   switch (scheme) {
   case eManglingSchemeNone:
     // The current mangled_name_filter would allow llvm_unreachable here.
     return false;
 
   case eManglingSchemeItanium:
     // We want the rich mangling info here, so we don't care whether or not
     // there is a demangled string in the pool already.
-    if (context.FromItaniumName(m_mangled)) {
-      // If we got an info, we have a name. Copy to string pool and connect the
-      // counterparts to accelerate later access in GetDemangledName().
-      m_demangled.SetStringWithMangledCounterpart(context.ParseFullName(),
-                                                  m_mangled);
-      return true;
-    } else {
-      m_demangled.SetCString("");
-      return false;
-    }
+    return context.FromItaniumName(m_mangled);
 
   case eManglingSchemeMSVC: {
     // We have no rich mangling for MSVC-mangled names yet, so first try to
     // demangle it if necessary.
     if (!m_demangled && !m_mangled.GetMangledCounterpart(m_demangled)) {
       if (char *d = GetMSVCDemangledStr(m_mangled.GetCString())) {
-        // If we got an info, we have a name. Copy to string pool and connect
-        // the counterparts to accelerate later access in GetDemangledName().
+        // Without the rich mangling info we have to demangle the full name.
+        // Copy it to string pool and connect the counterparts to accelerate
+        // later access in GetDemangledName().
         m_demangled.SetStringWithMangledCounterpart(llvm::StringRef(d),
                                                     m_mangled);
         ::free(d);
       } else {
         m_demangled.SetCString("");
       }
     }
 

lldb/source/Symbol/Symtab.cpp

for (uint32_t value = 0; value < num_symbols; ++value) {
           // the annotations.
           ConstString stripped = ConstString(
               m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
           name_to_index.Append(stripped, value);
         }
 
         const SymbolType type = symbol->GetType();
         if (type == eSymbolTypeCode || type == eSymbolTypeResolver) {
-          if (mangled.DemangleWithRichManglingInfo(rmc, lldb_skip_name))
+          if (mangled.DemangleWithRichManglingInfo(rmc, lldb_skip_name)) {
             RegisterMangledNameEntry(value, class_contexts, backlog, rmc);
+            continue;
+          }
         }
       }
 
       // Symbol name strings that didn't match a Mangled::ManglingScheme, are
       // stored in the demangled field.
       if (ConstString name = mangled.GetDemangledName()) {
         name_to_index.Append(name, value);
 
if (!m_name_indexes_computed) {
     method_to_index.SizeToFit();
   }
 }
 
 void Symtab::RegisterMangledNameEntry(
     uint32_t value, std::set<const char *> &class_contexts,
     std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog,
     RichManglingContext &rmc) {
   // Only register functions that have a base name.
   llvm::StringRef base_name = rmc.ParseFunctionBaseName();
   if (base_name.empty())
     return;
 
   // The base name will be our entry's name.
   NameToIndexMap::Entry entry(ConstString(base_name), value);
   llvm::StringRef decl_context = rmc.ParseFunctionDeclContextName();
 
   // Register functions with no context.

lldb/test/API/macosx/dyld-trie-symbols/TestDyldTrieSymbols.py

def test_dyld_trie_symbols(self):
         unstripped_patval_symbols = unstripped_target.FindSymbols("patval")
         self.assertEqual(unstripped_patval_symbols.GetSize(), 1)
         unstripped_Z3foo_symbols = unstripped_target.FindSymbols("_Z3foov")
         self.assertEqual(unstripped_Z3foo_symbols.GetSize(), 1)
         unstripped_foo_symbols = unstripped_target.FindSymbols("foo")
         self.assertEqual(unstripped_foo_symbols.GetSize(), 1)
 
         # make sure we can look up the mangled name, demangled base name,
         # demangled name with argument.
         unstripped_Z3pat_symbols = unstripped_target.FindSymbols("_Z3pati")
         self.assertEqual(unstripped_Z3pat_symbols.GetSize(), 1)
         unstripped_pat_symbols = unstripped_target.FindSymbols("pat")
         self.assertEqual(unstripped_pat_symbols.GetSize(), 1)
-        unstripped_patint_symbols = unstripped_target.FindSymbols("pat(int)")
-        self.assertEqual(unstripped_patint_symbols.GetSize(), 1)
 
         unstripped_bar_symbols = unstripped_target.FindSymbols("bar")
         self.assertEqual(unstripped_bar_symbols.GetSize(), 1)
 
 
 
         # Verify that we can retrieve all the symbols with external
         # linkage after the binary has been stripped; they should not
def test_dyld_trie_symbols(self):
         self.assertEqual(stripped_foo_symbols.GetSize(), 1)
 
         # make sure we can look up the mangled name, demangled base name,
         # demangled name with argument.
         stripped_Z3pat_symbols = stripped_target.FindSymbols("_Z3pati")
         self.assertEqual(stripped_Z3pat_symbols.GetSize(), 1)
         stripped_pat_symbols = stripped_target.FindSymbols("pat")
         self.assertEqual(stripped_pat_symbols.GetSize(), 1)
-        stripped_patint_symbols = stripped_target.FindSymbols("pat(int)")
-        self.assertEqual(stripped_patint_symbols.GetSize(), 1)
 
         # bar should have been strippped.  We should not find it, or the
         # stripping went wrong.
         stripped_bar_symbols = stripped_target.FindSymbols("bar")
         self.assertEqual(stripped_bar_symbols.GetSize(), 0)
 
         # confirm that we classified objc runtime symbols correctly and
         # stripped off the objc prefix from the symbol names.