[SymbolSize] Improve the performance of SymbolSize computation

[steven_wu]

Summary

The current algorithm to compute the symbol size is quadratic if there
are lots of symbols sharing the same addresses. This happens in a debug
build when lots of debug symbols get emitted in the symtab.

This patch improves the performance like llvm-symbolizer that relies
on the symbol size computation. Symbolizing a release+assert clang with
DebugInfo sees significant improvements from 3:40min to less than 1s.

[steven_wu]

Update commit message

[mehdi_amini]

Nice!

[MaskRay]

Nice! This is for non-ELF object file formats (https://discourse.llvm.org/t/llvm-symbolizer-has-gotten-extremely-slow/67262/29). It may be different from others' reports (primarily about ELF).

[steven_wu]

Nice! This is for non-ELF object file formats (https://discourse.llvm.org/t/llvm-symbolizer-has-gotten-extremely-slow/67262/29). It may be different from others' reports (primarily about ELF).

I guess I missed most of the context on discord thread. I saw this issue on Darwin CI and did some investigation while try to find any bug references. Thanks for review.

[arsenm]

In D156603#4545106, @steven_wu wrote:

Nice! This is for non-ELF object file formats (https://discourse.llvm.org/t/llvm-symbolizer-has-gotten-extremely-slow/67262/29). It may be different from others' reports (primarily about ELF).

I guess I missed most of the context on discord thread. I saw this issue on Darwin CI and did some investigation while try to find any bug references. Thanks for review.

It was really bad on linux and mac. There was a previous fix that helped a little for linux, but it's still much slower than it used to be

[jhenderson]

llvm/lib/Object/SymbolSize.cpp

89

Post commit nit "using" -> "use"

[steven_wu]

llvm/lib/Object/SymbolSize.cpp

89

Fixed. Thanks!

[steakhal]

Aha, I was wondering if this patch is going to be back ported to clang-17.
It was in https://github.com/llvm/llvm-project/commit/e96c444fd725661e6273d1708dfd10f2b6c3de6b

llvm/lib/Object/SymbolSize.cpp

Addresses.push_back(
         {O.symbol_end(), Address + Size, 0, getSectionID(O, Sec)});
   }
 
   if (Addresses.empty())
     return Ret;
 
   array_pod_sort(Addresses.begin(), Addresses.end(), compareAddress);
 
-  // Compute the size as the gap to the next symbol
-  for (unsigned I = 0, N = Addresses.size() - 1; I < N; ++I) {
+  // Compute the size as the gap to the next symbol. If multiple symbols have
+  // the same address, give both the same size. Because Addresses is sorted,
+  // using two pointers to keep track of the current symbol vs. the next symbol
+  // that doesn't have the same address for size computation.
+  for (unsigned I = 0, NextI = 0, N = Addresses.size() - 1; I < N; ++I) {
     auto &P = Addresses[I];
     if (P.I == O.symbol_end())
       continue;
 
-    // If multiple symbol have the same address, give both the same size.
-    unsigned NextI = I + 1;
+    // If the next pointer is behind, update it to the next symbol.
+    if (NextI <= I) {
+      NextI = I + 1;
       while (NextI < N && Addresses[NextI].Address == P.Address)
         ++NextI;
+    }
 
     uint64_t Size = Addresses[NextI].Address - P.Address;
     P.Address = Size;
   }
 
   // Assign the sorted symbols in the original order.
   Ret.resize(SymNum);
   for (SymEntry &P : Addresses) {
     if (P.I == O.symbol_end())
       continue;
     Ret[P.Number] = {*P.I, P.Address};
   }
   return Ret;
 }