Use a buffer when allocating relocations

[• espindola]

Summary

This reduces peak allocations from 564.2 to 545.7 MB when linking chrome.

[ruiu]

This seems a bit tricky. Doesn't shrink_to_fit work?

[• espindola]

In D46145#1080123, @ruiu wrote:

This seems a bit tricky. Doesn't shrink_to_fit work?

At least on linux with libstdc++ it doesn't seem to move the data to a smaller buffer. I still get a peak of 564.2 with it.

[ruiu]

Does your code make this part of code faster? It reduces memory allocation but it does extra memcpy, so I'm wondering.

[• espindola]

In D46145#1080172, @ruiu wrote:

Does your code make this part of code faster? It reduces memory allocation but it does extra memcpy, so I'm wondering.

On my machine the difference is in the noise. Note that it is not a given that this has more copying. When the vector is resized there is a copy, and we should expect fewer resizes with the single buffer.

[grimar]

I confirm the peak allocation difference. I think that implementation can be a bit simpler though, my suggestion is below.

ELF/Writer.cpp

875

It can be a bit simpler I think:
(RAM profiling shows that the version below consume the same amount of memory).

std::vector<Relocation> Buffer;

// <new comment>
auto WithBuffer = [&](InputSectionBase &Sec) {
  Fn(Sec);
  Buffer = std::move(Sec.Relocations);
  Sec.Relocations = Buffer;
};

[• espindola]

ELF/Writer.cpp

875

That would reduce peak allocation, but each call to Fn is still allocating a new buffer, no?

But does suggest a way to simplify it a bit.

[grimar]

ELF/Writer.cpp

875

CPU time was about the same as the original code for my way I think.
Your way should be slightly faster though:

I observed a minor speed up between original and your version. It was:
Original CPU time total (3 runs): 2632, 2637, 2622.
Patch: 2604, 2610, 2592.

So it is about 0.5% I think. Results seem was more or less stable. I do not have precise numbers for my version underhand (I can retest it if you think it worth, but it was something about original code numbers). I think the simplicity of implementation makes more sense here probably (and I hope we will be able to use shrink_to_fit one day).

[• espindola]

ELF/Writer.cpp

875

Testing the suggestion the peak memory is indeed the same, but the total memory allocated is actually higher:

master 765.92 564.2
patch 748.16, 545.7
patch2 865.48, 545.7

[ruiu]

I wonder if you can make a guess on how many relocations will be inserted to the vector. We know the number of relocations for each input section, so calling reserve() might work.

[grimar]

In D46145#1081117, @ruiu wrote:

I wonder if you can make a guess on how many relocations will be inserted to the vector. We know the number of relocations for each input section, so calling reserve() might work.

I think reserve() is exactly what causes high peaks now. We already call it. See:
https://github.com/llvm-mirror/lld/blob/master/ELF/Relocations.cpp#L1020

[ruiu]

Then maybe we should remove it?

[• espindola]

In D46145#1081118, @grimar wrote:

In D46145#1081117, @ruiu wrote:

I wonder if you can make a guess on how many relocations will be inserted to the vector. We know the number of relocations for each input section, so calling reserve() might work.

I think reserve() is exactly what causes high peaks now. We already call it. See:
https://github.com/llvm-mirror/lld/blob/master/ELF/Relocations.cpp#L1020

Yes, currently using reserve is critical for performance, but wastes memory.

[• espindola]

Use end() when inserting. Doesn't make a difference in here, but is the canonical way of concatenating vectors.

[grimar]

ELF/Writer.cpp

875

Did not see that (my profiler seem shows only peak memory).
Then, do we really need to care too much about total memory allocated if performance and peak memory consumption are about the same?

[grimar]

In D46145#1081129, @espindola wrote:

Use end() when inserting. Doesn't make a difference in here, but is the canonical way of concatenating vectors.

Wrong review page :)

[• espindola]

In D46145#1081120, @ruiu wrote:

Then maybe we should remove it?

Just removing it would be disastrous for performance. It was a 6% improvement when it was added in r319976.

It might be possible to remove it after this patch.

[• espindola]

correct patch .

[ruiu]

I tried this patch and found that at least for Chrome, we wasted memory by calling reserve() on ".data.rel.ro" sections. Such section in Chrome doesn't add any item to Sec.Relocations while their Rels.size() is relatively large, so reserved memory is totally wasted. If you don't call reserve on such section, you can save almost the same memory as you did in this patch. Can you take a look?

[• espindola]

In D46145#1081212, @ruiu wrote:

I tried this patch and found that at least for Chrome, we wasted memory by calling reserve() on ".data.rel.ro" sections. Such section in Chrome doesn't add any item to Sec.Relocations while their Rels.size() is relatively large, so reserved memory is totally wasted. If you don't call reserve on such section, you can save almost the same memory as you did in this patch. Can you take a look?

The issue is that chrome is linked with -pie. The section in question has a lot of

.quad foo
.quad bar
...

They become dynamic relocation instead of static ones.

I don't see how to predict that in general. I will try removing the reserve in combination with this patch.

[• espindola]

Delete call to reserve.

The results are

master 765.5 total, 563.7 peak
with reserve 747.76 total, 545.3 peak
without reserve 747.63 total, 545.3 peak

[grimar]

Few more ideas about that one.

ELF/Writer.cpp

861

Less tricky way probably could be to pass std::vector<Relocation> Buffer to Fn, so it could populate it.
That would need to add this argument to few functions. Though also seem would remove argument from some of them,
for example handleMipsTlsRelocation uses InputSectionBase &C to access to C.Relocations. It could take the buffer instead
of the section.

And code would be something like next then:

auto WithBuffer = [&](InputSectionBase &Sec) {
  Fn(Sec, Buffer);
  Sec.Relocations.insert(Sec.Relocations.end(), Buffer.begin(), Buffer.end());
  Buffer.clear();
};

866

I would probably add that we do that to decrease total memory consumption.
Maybe "the exact internal buffer size" would make comment more understandable.

[• espindola]

ELF/Writer.cpp

861

This would require passing a buffer to a lot of places. For example, RelocationBaseSection::addReloc would need it.

As written the code with swap is a bit more complicated, but it is completely local.

ELF/Relocations.cpp

static void scanReloc(InputSectionBase &Sec, OffsetGetter &GetOffset, RelTy *&I,
   }
 
   processRelocAux<ELFT>(Sec, Expr, Type, Offset, Sym, Rel, Addend);
 }
 
 template <class ELFT, class RelTy>
 static void scanRelocs(InputSectionBase &Sec, ArrayRef<RelTy> Rels) {
   OffsetGetter GetOffset(Sec);
-
-  // Not all relocations end up in Sec.Relocations, but a lot do.
-  Sec.Relocations.reserve(Rels.size());
-
   for (auto I = Rels.begin(), End = Rels.end(); I != End;)
     scanReloc<ELFT>(Sec, GetOffset, I, End);
 }
 
 template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
   if (S.AreRelocsRela)
     scanRelocs<ELFT>(S, S.relas<ELFT>());
   else

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::addRelIpltSymbols() {
   addOptionalRegular(S, InX::RelaIplt, 0, STV_HIDDEN, STB_WEAK);
 
   S = Config->IsRela ? "__rela_iplt_end" : "__rel_iplt_end";
   ElfSym::RelaIpltEnd =
       addOptionalRegular(S, InX::RelaIplt, 0, STV_HIDDEN, STB_WEAK);
 }
 
 template <class ELFT>
 void Writer<ELFT>::forEachRelSec(std::function<void(InputSectionBase &)> Fn) {
+  std::vector<Relocation> Buffer;
+
+  // We allocate a lot of relocations. By using a single buffer for
+  // all sections we ensure that the final vector in each section has
+  // the exact size.
+  auto WithBuffer = [&](InputSectionBase &Sec) {
+    swap(Sec.Relocations, Buffer);
+    Fn(Sec);
+    swap(Sec.Relocations, Buffer);
+    Sec.Relocations.insert(Sec.Relocations.end(), Buffer.begin(), Buffer.end());
+    Buffer.clear();
+  };
+
   // Scan all relocations. Each relocation goes through a series
   // of tests to determine if it needs special treatment, such as
   // creating GOT, PLT, copy relocations, etc.
   // Note that relocations for non-alloc sections are directly
   // processed by InputSection::relocateNonAlloc.
   for (InputSectionBase *IS : InputSections)
     if (IS->Live && isa<InputSection>(IS) && (IS->Flags & SHF_ALLOC))
-      Fn(*IS);
+      WithBuffer(*IS);
   for (EhInputSection *ES : InX::EhFrame->Sections)
-    Fn(*ES);
+    WithBuffer(*ES);
 }
 
 // This function generates assignments for predefined symbols (e.g. _end or
 // _etext) and inserts them into the commands sequence to be processed at the
 // appropriate time. This ensures that the value is going to be correct by the
 // time any references to these symbols are processed and is equivalent to
 // defining these symbols explicitly in the linker script.
 template <class ELFT> void Writer<ELFT>::setReservedSymbolSections() {