[lld-macho] Parallelize UUID hash computation

[int3]

Summary

This reuses the approach (and some code) from LLD-ELF.

It's a decent win when linking chromium_framework on a Mac Pro (3.2 GHz 16-Core Intel Xeon W):

    N           Min           Max        Median           Avg        Stddev
x  20          4.58          4.83          4.66        4.6685   0.066591844
+  20          4.42          4.61           4.5         4.505    0.04751731
Difference at 95.0% confidence
        -0.1635 +/- 0.0370242
        -3.5022% +/- 0.793064%
        (Student's t, pooled s = 0.0578462)

The output binary is 381MB.

[oontvoo]

lld/MachO/Writer.cpp

932–936

Looking at the implementation of xxHash64, I think the reinterpret_cast<uint8_t *> is UB.
Specifically, it tried to iterate the array by +8.

How about this?

[tschuett]

ELF uses the same chunk size. I am wondering, why the chunk size is independent of the file size and the number of cores? E.g. why bother with chunks if you have 1 core? Or if if you link a 1GB file with 10 cores, you probably have too many chunks?

[tschuett]

Would you mind adding the file size and the number of cores to the summary?

[int3]

Would you mind adding the file size and the number of cores to the summary?

Ah yeah I'd forgotten to do that, good catch

lld/MachO/Writer.cpp

932–936

Looking at the implementation of xxHash64, I think the reinterpret_cast<uint8_t *> is UB.
Specifically, it tried to iterate the array by +8.

Can you elaborate? I'm not sure I follow.

As for using write64le to write the intermediate values, I know LLD-ELF does it, but seems pretty superfluous to me. I guess it means that we'll get the same hash values if we run LLD on a big-endian host machine, but ... when will that ever happen? And if someone tried that, I'm pretty sure lots of things would break anyway, since we don't have any contbuilds covering this.

[int3]

Let me see what I can do about the chunks.

[oontvoo]

lld/MachO/Writer.cpp

932–936

Can you elaborate? I'm not sure I follow.
As for using write64le <..... >

I guess write64le is not strictly required :)

I was getting more at the reinterpret_cast. There is no *guarantee* that casting uint64_t* to a uint8_t* won't cause aliasing violations. In practice, it's probably fine. If possible, though, it'd be nice to avoid it. (And it *is* possible in this case)

[int3]

lld/MachO/Writer.cpp

932–936

Hmm interesting. I did some reading up on aliasing rules, and if I understand things correctly, casting to a char type is fine.

From https://github.com/cplusplus/draft/raw/master/papers/n4659.pdf, section 6.10 [basic.lval] point 8:

If a program attempts to access the stored value of an object through a glvalue of other than one of the following types the behavior is undefined
...
a char, unsigned char, or std::byte type.

[int3]

size chunks based on number of cores

[int3]

The initial numbers were noisy, I've updated the commit message with better data

[int3]

bump. Can I get a stamp?

[oontvoo]

LGTM

lld/MachO/Writer.cpp

931

It seems strategy is only initted to hardware_concurrency (in Driver.cpp) if --threads is set.
Do we care to set set it unconditionally?

932–936

Not the hill to die on but I'll add that uint8_t isn't *guaranteed* to be unsigned char. Yes, in practice code in LLVM seems to make this kind of assumption. so .... ¯\_(ツ)_/¯

[int3]

lld/MachO/Writer.cpp

931

The default-constructed strategy will return the right value for compute_thread_count() too, so we don't need to

[MaskRay]

lld/MachO/Writer.cpp

931

Is this approach faster than fixed-size 1MiB chunks used by lld/ELF?

lld/ELF/Writer.cpp

 #include "LinkerScript.h"
 #include "MapFile.h"
 #include "OutputSections.h"
 #include "Relocations.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
+#include "lld/Common/Arrays.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
for (OutputSection *sec : outputSections)
     if (sec->type == SHT_REL || sec->type == SHT_RELA)
       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
 
   for (OutputSection *sec : outputSections)
     if (sec->type != SHT_REL && sec->type != SHT_RELA)
       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
 }
 
-// Split one uint8 array into small pieces of uint8 arrays.
-static std::vector<ArrayRef<uint8_t>> split(ArrayRef<uint8_t> arr,
-                                            size_t chunkSize) {
-  std::vector<ArrayRef<uint8_t>> ret;
-  while (arr.size() > chunkSize) {
-    ret.push_back(arr.take_front(chunkSize));
-    arr = arr.drop_front(chunkSize);
-  }
-  if (!arr.empty())
-    ret.push_back(arr);
-  return ret;
-}
-
 // Computes a hash value of Data using a given hash function.
 // In order to utilize multiple cores, we first split data into 1MB
 // chunks, compute a hash for each chunk, and then compute a hash value
 // of the hash values.
 static void
 computeHash(llvm::MutableArrayRef<uint8_t> hashBuf,
             llvm::ArrayRef<uint8_t> data,
             std::function<void(uint8_t *dest, ArrayRef<uint8_t> arr)> hashFn) {

lld/MachO/Writer.cpp

 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "UnwindInfoSection.h"
 
+#include "lld/Common/Arrays.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/xxhash.h"
 
 #include <algorithm>
 
 using namespace llvm;
 using namespace llvm::MachO;

 
 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
   for (const OutputSegment *seg : outputSegments)
     for (const OutputSection *osec : seg->getSections())
       osec->writeTo(buf + osec->fileOff);
 }
 
+// In order to utilize multiple cores, we first split the buffer into chunks,
+// compute a hash for each chunk, and then compute a hash value of the hash
+// values.
 void Writer::writeUuid() {
   TimeTraceScope timeScope("Computing UUID");
-  uint64_t digest =
-      xxHash64({buffer->getBufferStart(), buffer->getBufferEnd()});
+  ArrayRef<uint8_t> data{buffer->getBufferStart(), buffer->getBufferEnd()};
+  unsigned chunkCount = parallel::strategy.compute_thread_count() * 10;
+  // Round-up integer division
+  size_t chunkSize = (data.size() + chunkCount - 1) / chunkCount;
+  std::vector<ArrayRef<uint8_t>> chunks = split(data, chunkSize);
+  std::vector<uint64_t> hashes(chunks.size());
+  parallelForEachN(0, chunks.size(),
+                   [&](size_t i) { hashes[i] = xxHash64(chunks[i]); });
+  uint64_t digest = xxHash64({reinterpret_cast<uint8_t *>(hashes.data()),
+                              hashes.size() * sizeof(uint64_t)});
   uuidCommand->writeUuid(digest);
 }
 
 void Writer::writeCodeSignature() {
   if (codeSignatureSection)
     codeSignatureSection->writeHashes(buffer->getBufferStart());
 }
 

lld/include/lld/Common/Arrays.h

+//===- Arrays.h ------------------------------------------------*- C++ -*-===//
+//
+// 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 LLD_ARRAYS_H
+#define LLD_ARRAYS_H
+
+#include "llvm/ADT/ArrayRef.h"
+
+#include <vector>
+
+namespace lld {
+// Split one uint8 array into small pieces of uint8 arrays.
+inline std::vector<llvm::ArrayRef<uint8_t>> split(llvm::ArrayRef<uint8_t> arr,
+                                                  size_t chunkSize) {
+  std::vector<llvm::ArrayRef<uint8_t>> ret;
+  while (arr.size() > chunkSize) {
+    ret.push_back(arr.take_front(chunkSize));
+    arr = arr.drop_front(chunkSize);
+  }
+  if (!arr.empty())
+    ret.push_back(arr);
+  return ret;
+}
+
+} // namespace lld
+
+#endif