[XRay] cache symbolized function names for a repeatedly queried function ID

[pelikan]

Summary

Processing 2 GB XRay traces with "llvm-xray convert -symbolize" needs to
go over each trace record and symbolize the function name refered to by
its ID. Currently this happens by asking the LLVM symbolizer code every
single time. A simple cache can save around 30 minutes of processing of
my testing trace which took ~100 minutes at HEAD and ~40 minutes with
D43892 also in, making the combined speedup around 10×.

llvm-xray's resident memory usage increased negligibly with this cache.

[dberris]

Just one suggested change, but should be good to land after.

Thanks, @pelikan!

tools/llvm-xray/func-id-helper.h

32

Can you use an llvm::DenseMap instead of the standard (poorly performing) one instead?

[pelikan]

std::unordered_map -> llvm::DenseMap (as requested)

[pelikan]

tools/llvm-xray/func-id-helper.h

32

I actually tested the speed difference with std::map only, and used unordered_map just like FunctionAddressMap does above. I'm happy to change it though.

tools/llvm-xray/func-id-helper.h

 //===- func-id-helper.h - XRay Function ID Conversion Helpers -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Defines helper tools dealing with XRay-generated function ids.
 //
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_TOOLS_LLVM_XRAY_FUNC_ID_HELPER_H
 #define LLVM_TOOLS_LLVM_XRAY_FUNC_ID_HELPER_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/DebugInfo/Symbolize/Symbolize.h"
 #include <unordered_map>
 
 namespace llvm {
 namespace xray {
 
 // This class consolidates common operations related to Function IDs.
 class FuncIdConversionHelper {
 public:
   using FunctionAddressMap = std::unordered_map<int32_t, uint64_t>;
 
 private:
   std::string BinaryInstrMap;
   symbolize::LLVMSymbolizer &Symbolizer;
   const FunctionAddressMap &FunctionAddresses;
+  mutable llvm::DenseMap<int32_t, std::string> CachedNames;
 
 public:
   FuncIdConversionHelper(std::string BinaryInstrMap,
                          symbolize::LLVMSymbolizer &Symbolizer,
                          const FunctionAddressMap &FunctionAddresses)
       : BinaryInstrMap(std::move(BinaryInstrMap)), Symbolizer(Symbolizer),
         FunctionAddresses(FunctionAddresses) {}
 

tools/llvm-xray/func-id-helper.cc

 #include "func-id-helper.h"
 #include "llvm/Support/Path.h"
 #include <sstream>
 
 using namespace llvm;
 using namespace xray;
 
 std::string FuncIdConversionHelper::SymbolOrNumber(int32_t FuncId) const {
+  auto CacheIt = CachedNames.find(FuncId);
+  if (CacheIt != CachedNames.end())
+    return CacheIt->second;
+
   std::ostringstream F;
   auto It = FunctionAddresses.find(FuncId);
   if (It == FunctionAddresses.end()) {
     F << "#" << FuncId;
     return F.str();
   }
 
   if (auto ResOrErr = Symbolizer.symbolizeCode(BinaryInstrMap, It->second)) {
     auto &DI = *ResOrErr;
     if (DI.FunctionName == "<invalid>")
       F << "@(" << std::hex << It->second << ")";
     else
       F << DI.FunctionName;
   } else
     handleAllErrors(ResOrErr.takeError(), [&](const ErrorInfoBase &) {
       F << "@(" << std::hex << It->second << ")";
     });
 
-  return F.str();
+  auto S = F.str();
+  CachedNames[FuncId] = S;
+  return S;
 }
 
 std::string FuncIdConversionHelper::FileLineAndColumn(int32_t FuncId) const {
   auto It = FunctionAddresses.find(FuncId);
   if (It == FunctionAddresses.end())
     return "(unknown)";
 
   std::ostringstream F;