Page MenuHomePhabricator

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

Authored by danielcdh on Jul 7 2017, 2:35 PM.

Event Timeline

danielcdh created this revision.Jul 7 2017, 2:35 PM

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

tejohnson accepted this revision.Jul 9 2017, 7:15 AM

LGTM

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?

This revision is now accepted and ready to land.Jul 9 2017, 7:15 AM

LGTM

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.

danielcdh closed this revision.Jul 10 2017, 8:32 AM

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

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

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