[lld][MachO] Sort symbols in parallel in -map

[TH3CHARLie]

Summary

source: https://bugs.llvm.org/show_bug.cgi?id=50689

When writing a map file, sort symbols in parallel using parallel_sort.
Use address name to break ties if two symbols have the same address.

[MaskRay]

Is there a demonstrable speed-up?

[thakis]

Seems fine, but can you change the patch description to say "When writing a map file, sort symbols in parallel" to make clear that this only affects map file writing?

[TH3CHARLie]

In D104346#2820934, @thakis wrote:

Seems fine, but can you change the patch description to say "When writing a map file, sort symbols in parallel" to make clear that this only affects map file writing?

resolved

In D104346#2820932, @MaskRay wrote:

Is there a demonstrable speed-up?

Trying to produce one, please stay tune...

[int3]

Trying to produce one

We often use this Chromium build snapshot as a benchmark: https://drive.google.com/file/d/1j6_f55jX1WYjwrDSmQYbr_X043mLG9L2/view?usp=sharing

Download and unpack it, then you can run the link command like so ld64.lld -map mapoutputfile @response.txt

You'll want to run it a number of times. This is the script that I usually use:

(base) lld/MachO: cat `which bench.sh`
#!/bin/bash
set -x
echo "warming up..." >&2
$@
for i in {1..20}
do
  /usr/bin/time -p $@ 2>&1 | grep "^real " | awk '{print $2}'
done

I typically use that script to generate two sets of measurements, one before and one after this diff is applied. Then I compare the results using https://github.com/codahale/ministat. The commit message in D103979 is an example of the result.

lld/MachO/MapFile.cpp

55–59

I think this can just be llvm::parallel_sort (and with the using namespace llvm above, we don't even need the llvm::). Stuff under detail namespaces shouldn't be used directly -- they're implementation details

[TH3CHARLie]

lld/MachO/MapFile.cpp

55–59

parallel_sort is not available in llvm namespace, parallelSort is. So maybe we should use parallelSort here?

[int3]

lld/MachO/MapFile.cpp

55–59

ah yes. I was thinking of parallelSort

[TH3CHARLie]

Use llvm::parallelSort

[TH3CHARLie]

I reproduce a benchmark number following @int3 's guidance, though the numbers are not as promising as I expected:

cc @MaskRay

#../ministat/ministat -s -w 74 stable.txt parallel.txt
x stable.txt
+ parallel.txt
+--------------------------------------------------------------------------+
|                           +            +     +                           |
|                         + +   x x+     +     +  x x                      |
|+                  + xx ++ ++ xx x* ** ** x   +  x xx x                  x|
|                            |__________MA____________|                    |
|                     |__________A_M________|                              |
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  20          6.53          6.88          6.65         6.661   0.083154897
+  20          6.39           6.7          6.62        6.6055    0.07444355
Difference at 95.0% confidence
        -0.0555 +/- 0.050512
        -0.833208% +/- 0.758325%
        (Student's t, pooled s = 0.0789195)

[thakis]

Do you need someone to commit this for you, or do you have commit permissions.

(FWIW https://github.com/nico/hack/blob/master/bench.py is my "run multiple times" script :) )

[TH3CHARLie]

In D104346#2821598, @thakis wrote:

Do you need someone to commit this for you, or do you have commit permissions.

(FWIW https://github.com/nico/hack/blob/master/bench.py is my "run multiple times" script :) )

Thanks for the review and I have commit access

[TH3CHARLie]

Should I wait for @int3 or I can commit now?

[int3]

lgtm, thanks!

lld/MachO/MapFile.cpp

55–59

since we have using namespace above

[TH3CHARLie]

update

lld/MachO/MapFile.cpp

static SymbolMapTy getSectionSyms(ArrayRef<Defined *> syms) {
   SymbolMapTy ret;
   for (Defined *dr : syms)
     ret[dr->isec].push_back(dr);
 
   // Sort symbols by address. We want to print out symbols in the order they
   // appear in the output file rather than the order they appeared in the input
   // files.
   for (auto &it : ret)
-    llvm::stable_sort(it.second, [](Defined *a, Defined *b) {
-      return a->getVA() < b->getVA();
+    parallelSort(
+        it.second.begin(), it.second.end(), [](Defined *a, Defined *b) {
+          return a->getVA() != b->getVA() ? a->getVA() < b->getVA()
+                                          : a->getName() < b->getName();
         });
   return ret;
 }
 
 // Returns a list of all symbols that we want to print out.
 static std::vector<Defined *> getSymbols() {
   std::vector<Defined *> v;
   for (InputFile *file : inputFiles)
     if (isa<ObjFile>(file))