This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
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. There are other possible strategies, such as inserting the input range at the end of *this and then rotating them into place once we have inserted them all. However, when the insertions trigger a reallocation we need to transfer all the existing elements (not only those past the insertion point). The patch I've committed only has to move the existing elements if the final insertion from the temporary vector to *this causes a reallocation. PR libstdc++/81476 * include/bits/vector.tcc (vector::_M_range_insert<_InputIterator>): Only insert elements one-by-one when inserting at the end. * testsuite/performance/23_containers/insert/81476.cc: New. Tested x86_64-linux, committed to trunk.
Attachment:
patch.txt
Description: Text document
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |