This is the mail archive of the
mailing list for the GCC project.
Re: [PATCH] PR libstdc++/81476 Optimise vector insertion from input iterators
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: libstdc++ at gcc dot gnu dot org
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 20 Jul 2017 14:54:21 +0100
- Subject: Re: [PATCH] PR libstdc++/81476 Optimise vector insertion from input iterators
- Authentication-results: sourceware.org; auth=none
- Authentication-results: ext-mx05.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com
- Authentication-results: ext-mx05.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=jwakely at redhat dot com
- Dkim-filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 02F662FFC53
- Dmarc-filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 02F662FFC53
- References: <20170719201030.GA25796@redhat.com> <alpine.DEB.firstname.lastname@example.org>
On 19/07/17 22:19 +0200, Marc Glisse wrote:
On Wed, 19 Jul 2017, Jonathan Wakely wrote:
The PR shows a fairly pathological case where ranges of InputIterators
are repeatedly inserted at the start of a vector. Each insertion from
an InputIterator moves every element after the insertion point by a
single position. So if we insert 1000 elements at the start we move
each existing element 1000 times to reach its final position.
This patch changes insertions that aren't at the end to use a
temporary vector, which starts empty so insertions are at the end, and
so fast. Then we do a range insert to copy everything from that vector
at once. That uses random access iterators, so we know how far to move
the existing elements and can just move them to their final position
in one step.
Is it legal to use the allocator even though capacity-size is large
enough for the inserted range?
The spec says no *reallocation* happens until the size would exceed
the capacity, and my change conforms to that. The vector's existing
storage is not REallocated (instead we perform one or more temporary
allocations and deallocations that are separate to the storage of
Unless I'm forgetting something, there's no requirement that we don't
perform any such additional allocations. It might be nice if we didn't
(otherwise something like a stack allocator that can't do more than
one allocation can't be used here), but I don't want to waste too much
time on this. Inserting ranges of input iterators into the middle of a
vector is a design flaw and should be avoided anyway.