Adding caching to libc++ std::function formatter for lookups that require scanning symbols

[shafik]

Summary

Performance issues lead to the libc++ std::function formatter to be disabled, see D65666

This change is the first of two changes that should address the performance issues and allow us to enable the formatter again.

In some cases we end up scanning the symbol table for the callable wrapped by std::function for those cases we will now cache the results and used the cache in subsequent look-ups. This still leaves a large cost for the initial lookup which will be addressed in the next change.

We are also expanding the tests but they will remain disabled.

[friss]

packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-stl/libcxx/function/TestLibCxxFunction.py

55–57

Can we find a better way to test the cache lookups?

Ideally, we'd test that the result actually come from the cache. Maybe we can add some logging to FindSymbolsMatchingRegExAndType and check that it doesn't appear on the second search? Also, to make this look like less of a copy-pasto, I would put the test in a helper function and run that function twice, the second time in a mode that checks that the lookups use the caching.

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.h

88–90

llvm::StringMap?

[shafik]

Addressing comments

• Using log timers to verify whether we are using the cache or not
• Switched to llvm::StringMap

[friss]

packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-stl/libcxx/function/TestLibCxxFunction.py

60–70

Can you wrap all of the above in a helper function? You repeat this same pattern for every variable, the test would be much more readable. It also gives you a good spot to expand a little bit on way the testing involves "timers".

[shafik]

• Refactored test to use a function to do repetitive task

[aprantl]

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.cpp

250

This is performing the lookup twice.

auto it = CallableLookupCache.find(func_to_match);
if (it != CallableLookupCache.end)
  return *it;

275

Factor these conditions out into a helper function with a descriptive name since it's also used above?

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.h

91

Since this is used in only one place, I would skip the using statement, but that's more a personal style preference.

[friss]

packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-stl/libcxx/function/TestLibCxxFunction.py

31

Does this negative lookahead regex actually fail if FindSymbolsMatchingRegExAndType is in the output? I would expect the .* afterwards to match basically anything, including what you have in your negative lookahead or another line of the output.

[shafik]

• Fixing test based on comments

packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-stl/libcxx/function/TestLibCxxFunction.py

31

Good catch, I was trying to be too clever and forgot how it worked.

This is more easily done using matching=False

[shafik]

Changes based on comments:

• Removed extra lookup
• Refactored redundant code

[friss]

This LGTM, in principle, but it's weird to add the testing in a skipped test. I trust that it works on your machine, but we won't know if it works on all the tested configurations. Can committing this wait for the perf issue to be fixed? Do you know how much work this is going to be?

[aprantl]

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.cpp

196

StringRefs are meant to be value types. A StringRef is only a ptr+offset so we are not being much more efficient by passing a pointer to a StringRef to a function. This should just be a StringRef value argument.

275

Not your code, but since you're there: symbol &&

Actually, this would really benefit from another descriptive helper methid since this is used in several places and not obvious to me what is being checked here. Lambda invokes, block invokes, both?

[aprantl]

Otherwise this LGTM now.

packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-stl/libcxx/function/TestLibCxxFunction.py

 from lldbsuite.test.lldbtest import *
 from lldbsuite.test import lldbutil
 
 
 class LibCxxFunctionTestCase(TestBase):
 
     mydir = TestBase.compute_mydir(__file__)
 
-    def get_variable(self, name):
-        var = self.frame().FindVariable(name)
-        var.SetPreferDynamicValue(lldb.eDynamicCanRunTarget)
-        var.SetPreferSyntheticValue(True)
-        return var
+    # Run frame var for a variable twice. Verify we do not hit the cache
+    # the first time but do the second time.
+    def run_frame_var_check_cache_use(self, variable, result_to_match):
+        self.runCmd("log timers reset")
+        self.expect("frame variable " + variable,
+                    substrs=[variable + " =  " + result_to_match])
+        self.expect("log timers dump",
+                   substrs=["lldb_private::Module::FindSymbolsMatchingRegExAndType"])
+
+        self.runCmd("log timers reset")
+        self.expect("frame variable " + variable,
+                    substrs=[variable + " =  " + result_to_match])
+        self.expect("log timers dump",
+                   matching=False,
+                   substrs=["lldb_private::Module::FindSymbolsMatchingRegExAndType"])
+
 
     # Temporarily skipping for everywhere b/c we are disabling the std::function formatter
     # due to performance issues but plan on turning it back on once they are addressed.
     @skipIf
     @add_test_categories(["libc++"])
     def test(self):
         """Test that std::function as defined by libc++ is correctly printed by LLDB"""
         self.build()
         self.runCmd("file " + self.getBuildArtifact("a.out"), CURRENT_EXECUTABLE_SET)
 
         bkpt = self.target().FindBreakpointByID(
             lldbutil.run_break_set_by_source_regexp(
                 self, "Set break point at this line."))
 
         self.runCmd("run", RUN_SUCCEEDED)
 
         # The stop reason of the thread should be breakpoint.
         self.expect("thread list", STOPPED_DUE_TO_BREAKPOINT,
                     substrs=['stopped',
                              'stop reason = breakpoint'])
 
-        self.expect("frame variable f1",
-                    substrs=['f1 =  Function = foo(int, int)'])
+        self.run_frame_var_check_cache_use("foo2_f", "Lambda in File main.cpp at Line 30")
+
+        lldbutil.continue_to_breakpoint(self.process(), bkpt)
 
-        self.expect("frame variable f2",
-                    substrs=['f2 =  Lambda in File main.cpp at Line 26'])
+        self.run_frame_var_check_cache_use("add_num2_f", "Lambda in File main.cpp at Line 21")
 
-        self.expect("frame variable f3",
-                    substrs=['f3 =  Lambda in File main.cpp at Line 30'])
+        lldbutil.continue_to_breakpoint(self.process(), bkpt)
 
-        self.expect("frame variable f4",
-                    substrs=['f4 =  Function in File main.cpp at Line 16'])
+        self.run_frame_var_check_cache_use("f2", "Lambda in File main.cpp at Line 43")
+        self.run_frame_var_check_cache_use("f3", "Lambda in File main.cpp at Line 47")
+        self.run_frame_var_check_cache_use("f4", "Function in File main.cpp at Line 16")
+
+        # These cases won't hit the cache at all but also don't require
+        # an expensive lookup.
+        self.expect("frame variable f1",
+                    substrs=['f1 =  Function = foo(int, int)'])
 
         self.expect("frame variable f5",
                     substrs=['f5 =  Function = Bar::add_num(int) const'])

packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-stl/libcxx/function/main.cpp

int foo(int x, int y) {
   return x + y - 1;
 }
 
 struct Bar {
    int operator()() {
        return 66 ;
    }
    int add_num(int i) const { return i + 3 ; }
-} ;
+   int add_num2(int i) {
+     std::function<int (int)> add_num2_f = [](int x) {
+         return x+1;
+      };
 
+      return add_num2_f(i); // Set break point at this line.
+   }
+} ;
+
+int foo2() {
+   auto f = [](int x) {
+       return x+1;
+   };
+
+   std::function<int (int)> foo2_f = f;
+
+   return foo2_f(10); // Set break point at this line.
+}
+
 int main (int argc, char *argv[])
 {
   int acc = 42;
   std::function<int (int,int)> f1 = foo;
   std::function<int (int)> f2 = [acc,f1] (int x) -> int {
     return x+f1(acc,x);
   };
 
   auto f = [](int x, int y) { return x + y; };
   auto g = [](int x, int y) { return x * y; } ;
   std::function<int (int,int)> f3 =  argc %2 ? f : g ;
 
   Bar bar1 ;
   std::function<int ()> f4( bar1 ) ;
   std::function<int (const Bar&, int)> f5 = &Bar::add_num;
 
+  int foo2_result = foo2();
+  int bar_add_num2_result = bar1.add_num2(10);
+
   return f1(acc,acc) + f2(acc) + f3(acc+1,acc+2) + f4() + f5(bar1, 10); // Set break point at this line.
 }

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.h

 //===-- CPPLanguageRuntime.h
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef liblldb_CPPLanguageRuntime_h_
 #define liblldb_CPPLanguageRuntime_h_
 
 #include <vector>
+
+#include "llvm/ADT/StringMap.h"
+
 #include "lldb/Core/PluginInterface.h"
 #include "lldb/Target/LanguageRuntime.h"
 #include "lldb/lldb-private.h"
 
 namespace lldb_private {
 
 class CPPLanguageRuntime : public LanguageRuntime {
 public:
lldb::ThreadPlanSP GetStepThroughTrampolinePlan(Thread &thread,
                                                   bool stop_others) override;
 
   bool IsWhitelistedRuntimeValue(ConstString name) override;
 protected:
   // Classes that inherit from CPPLanguageRuntime can see and modify these
   CPPLanguageRuntime(Process *process);
 
 private:
+  using OperatorStringToCallableInfoMap =
+    llvm::StringMap<CPPLanguageRuntime::LibCppStdFunctionCallableInfo>;
+
+  OperatorStringToCallableInfoMap CallableLookupCache;
+
   DISALLOW_COPY_AND_ASSIGN(CPPLanguageRuntime);
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_CPPLanguageRuntime_h_

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.cpp

CPPLanguageRuntime::FindLibCppStdFunctionCallableInfo(
   // vtable. We will use a process of elimination to drop through each case
   // and obtain the data we need.
   if (target.GetSectionLoadList().ResolveLoadAddress(
           possible_function_address, function_address_resolved)) {
     target.GetImages().ResolveSymbolContextForAddress(
         function_address_resolved, eSymbolContextEverything, sc);
     symbol = sc.symbol;
   }
     
-  auto get_name = [&first_template_parameter, &symbol]() {
+    auto contains_lambda_identifier = []( llvm::StringRef & str_ref ) {
+        return str_ref.contains("$_") || str_ref.contains("'lambda'");
+    };
+
+  // Case 4 or 5
+  // We eliminate these cases early because they don't need the potentially
+  // expensive lookup through the symbol table.
+  if (symbol && !symbol->GetName().GetStringRef().startswith("vtable for") &&
+      !contains_lambda_identifier(first_template_parameter) &&
+      !symbol->GetName().GetStringRef().contains("__invoke")) {
+    optional_info.callable_case =
+        LibCppStdFunctionCallableCase::FreeOrMemberFunction;
+    optional_info.callable_address = function_address_resolved;
+    optional_info.callable_symbol = *symbol;
+
+    return optional_info;
+  }
+
+  auto get_name = [&first_template_parameter, &symbol, contains_lambda_identifier]() {
     // Given case 1:
     //
     //    main::$_0
+    //    Bar::add_num2(int)::'lambda'(int)
     //
     // we want to append ::operator()()
-    if (first_template_parameter.contains("$_"))
+    if (contains_lambda_identifier(first_template_parameter))
       return llvm::Regex::escape(first_template_parameter.str()) +
              R"(::operator\(\)\(.*\))";
 
     if (symbol != nullptr &&
         symbol->GetName().GetStringRef().contains("__invoke")) {
 
       llvm::StringRef symbol_name = symbol->GetName().GetStringRef();
       size_t pos2 = symbol_name.find_last_of(':');
auto get_name = [&first_template_parameter, &symbol, contains_lambda_identifier]() {
 
     // Case 3
     return first_template_parameter.str() + R"(::operator\(\)\(.*\))";
     ;
   };
 
   std::string func_to_match = get_name();
 
+  auto it = CallableLookupCache.find(func_to_match);
+  if (it != CallableLookupCache.end())
+    return it->second;
+
   SymbolContextList scl;
 
   target.GetImages().FindSymbolsMatchingRegExAndType(
       RegularExpression{R"(^)" + func_to_match}, eSymbolTypeAny, scl, true);
 
   // Case 1,2 or 3
   if (scl.GetSize() >= 1) {
     SymbolContext sc2 = scl[0];
 
     AddressRange range;
     sc2.GetAddressRange(eSymbolContextEverything, 0, false, range);
 
     Address address = range.GetBaseAddress();
 
     Address addr;
     if (target.ResolveLoadAddress(address.GetCallableLoadAddress(&target),
                                   addr)) {
       LineEntry line_entry;
       addr.CalculateSymbolContextLineEntry(line_entry);
 
-      if (first_template_parameter.contains("$_") ||
+      if (contains_lambda_identifier(first_template_parameter) ||
           (symbol != nullptr &&
            symbol->GetName().GetStringRef().contains("__invoke"))) {
         // Case 1 and 2
         optional_info.callable_case = LibCppStdFunctionCallableCase::Lambda;
       } else {
         // Case 3
         optional_info.callable_case =
             LibCppStdFunctionCallableCase::CallableObject;
       }
 
       optional_info.callable_symbol = *symbol;
       optional_info.callable_line_entry = line_entry;
       optional_info.callable_address = addr;
-      return optional_info;
     }
   }
 
-  // Case 4 or 5
-  if (symbol && !symbol->GetName().GetStringRef().startswith("vtable for")) {
-    optional_info.callable_case =
-        LibCppStdFunctionCallableCase::FreeOrMemberFunction;
-    optional_info.callable_address = function_address_resolved;
-    optional_info.callable_symbol = *symbol;
-
-    return optional_info;
-  }
+  CallableLookupCache[func_to_match] = optional_info;
 
   return optional_info;
 }
 
 lldb::ThreadPlanSP
 CPPLanguageRuntime::GetStepThroughTrampolinePlan(Thread &thread,
                                                  bool stop_others) {
   ThreadPlanSP ret_plan_sp;