Use emplace_back to replace size() and resize().

[danielcdh]

Summary

This speeds-up thin-link for ~29% for large programs.

[grandinj]

I'm curious if you know why emplace_back is so much faster than resize(size+1) ?

[tejohnson]

LGTM

In D35145#802899, @grandinj wrote:

I'm curious if you know why emplace_back is so much faster than resize(size+1) ?

My understanding is that resize copies in the default value whereas emplace_back constructs one in place, and the latter is more efficient (especially when only 1 element being added to the list). Dehao - is that the reasoning you had?

[danielcdh]

In D35145#803115, @tejohnson wrote:

LGTM

In D35145#802899, @grandinj wrote:

I'm curious if you know why emplace_back is so much faster than resize(size+1) ?

My understanding is that resize copies in the default value whereas emplace_back constructs one in place, and the latter is more efficient (especially when only 1 element being added to the list). Dehao - is that the reasoning you had?

To calculate size(), one needs to traverse the entire list, which is O(n). resize also need to traverse to the end of the list and append on the tail.

[craig.topper]

Doesn't C++11 guarantee constant time for std::list::size?

[danielcdh]

Looks like it's implementation dependent, both gcc and clang uses loop to implement std::list::size:

#cat test.cc
#include <list>

int p(std::list<int> t) {

return t.size();

}
#g++ --std=c++11 test.cc -S -O2 -o - |grep jne -B4
.L4:
movq (%rdx), %rdx
addq $1, %rax
cmpq %rdx, %rdi
jne .L4
#clang --std=c++11 test.cc -S -O2 -o - |grep jne -B4
.LBB0_1: # =>This Inner Loop Header: Depth=1
movq (%rcx), %rcx
incl %eax
cmpq %rcx, %rdi
jne .LBB0_1

[craig.topper]

Hmm I was going off this complexity section here http://en.cppreference.com/w/cpp/container/list/size

tools/gold/gold-plugin.cpp

handleAllErrors(ObjOrErr.takeError(), [&](const ErrorInfoBase &EI) {
                 EI.message().c_str());
     });
 
     return *claimed ? LDPS_ERR : LDPS_OK;
   }
 
   std::unique_ptr<InputFile> Obj = std::move(*ObjOrErr);
 
-  Modules.resize(Modules.size() + 1);
+  Modules.emplace_back();
   claimed_file &cf = Modules.back();
 
   cf.handle = file->handle;
   // Keep track of the first handle for each file descriptor, since there are
   // multiple in the case of an archive. This is used later in the case of
   // ThinLTO parallel backends to ensure that each file is only opened and
   // released once.
   auto LeaderHandle =