llvm / llvm/llvm-project

[libc++] inefficient implementation for inserting an unsized input range at the start of a deque

Open
#199,788 1 comment 0 reactions 0 assignees View on GitHub
libc++ performance
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

libc++'s `std::deque` implementation of `prepend_range` (as well as `insert` at the start of the deque), when inserting a range whose size cannot be determined in advance, copies the range to a `__split_buffer` then inserts that buffer. This seems needlessly inefficient, and will allocate memory even when all the elements fit into the deque's front capacity. It would likely be better to insert the elements in reverse order (as if by repeated `push_front`) and then `std::reverse` the added sequence, as this would involve no extraneous memory allocations. (It may be more expensive if `swap` costs substantially more than two moves, but avoiding the heap allocations probably offsets that.)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.