This is an archive of the discontinued LLVM Phabricator instance.

[libcxx] Optimize vectors uninitialized construction of trivial types from an iterator range.
ClosedPublic

Authored by EricWF on Mar 6 2015, 8:23 AM.

Details

Summary

In certain cases vector can use memcpy to construct a range of elements at the back of the vector. We currently don't do this resulting in terrible code gen in non-optimized mode and a
very large slowdown compared to libstdc++.

This patch adds a __construct_forward_range(Allocator, Iter, Iter, _Ptr&) and __construct_forward_range(Allocator, Tp*, Tp*, Tp*&) functions to allocator_traits which act similarly to the existing __construct_forward(...) functions.

This patch also changes vectors __construct_at_end(Iter, Iter) to be __construct_at_end(Iter, Iter, SizeType) where SizeType is the size of the range. __construct_at_end(Iter, Iter, SizeType) now calls allocator_traits<Tp>::__construct_forward_range(...).

This patch is based off the design of __swap_out_circular_buffer(...) which uses allocator_traits<Tp>::__construct_forward(...).

On my machine this code performs 4x better than the current implementation when tested against std::vector<int>.

Diff Detail

Event Timeline

EricWF updated this revision to Diff 21364.Mar 6 2015, 8:23 AM
EricWF retitled this revision from to [libcxx] Optimize vectors uninitialized construction of trivial types from an iterator range..
EricWF updated this object.
EricWF edited the test plan for this revision. (Show Details)
EricWF added reviewers: mclow.lists, howard.hinnant.
EricWF added a subscriber: Unknown Object (MLST).
mclow.lists added inline comments.Mar 6 2015, 11:28 AM
include/vector
1029

This is not exception safe.
If one of the constructions throws, then the ASAN annotations will be wrong.

EricWF added inline comments.Mar 6 2015, 11:40 AM
include/vector
1029

This actually is exception safe but I had to think about it for a long time before I understood.

  1. __RAII_IncreaseAnnotate __annotator(*this, __n);: Unpoison the next __n elements.
  2. __annotator.__done(). commits to unpoisoning the elements.
  3. ~__annotator: If __done() has been called the destructor does nothing. Otherwise it re-poisons everything from __end_ on.
EricWF added a reviewer: titus.Mar 6 2015, 1:03 PM
mclow.lists added inline comments.Mar 9 2015, 7:43 AM
include/vector
1029

I don't think that's right - but I think that the problem is in __RAII_IncreaseAnnotate, not here.

__annotate_shrink needs the old size to reset the poisoned area, but it's passing size() + __n, where __n is the sized that was originally grown. This works fine as long as we're only increasing by 1 element, and failure means "no change" to the size. However, now that we're increasing by >1, we have to deal with the idea that failure can still change the size.

One possible way of fixing this is to change __RAII_IncreaseAnnotator so that instead of saving off the __n that is passed in, it saves off size() + __n.

EricWF added a reviewer: kcc.Mar 9 2015, 8:57 AM

Adding Kostya to this patch to discuss the __RAII_IncreaseAnnotate changes.

mclow.lists added inline comments.Mar 17 2015, 7:53 AM
include/vector
1393

This requires traversing the sequence (in the case of non-RA iterators). Do we really want to do that? Is it worth having a separate version for RA iterators?

EricWF added inline comments.Mar 17 2015, 7:59 AM
include/vector
1029

That fix is up for review as D8172.

1393

Maybe but I don't have benchmarks to prove it yet. I didn't add the call to distance in this case so I don't think that should block this patch. However I am aware of this issue and am looking into it separately.

mclow.lists accepted this revision.Mar 31 2015, 9:48 AM
mclow.lists edited edge metadata.

LGTM.

include/vector
1394

I would combine these two lines into one:
size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));

and not bother with __new_size_diff

This revision is now accepted and ready to land.Mar 31 2015, 9:48 AM
EricWF updated this revision to Diff 22969.Mar 31 2015, 9:55 AM
EricWF edited edge metadata.

Address @mclow.lists comments.

EricWF closed this revision.Mar 31 2015, 9:57 AM