| Issue |
141707
|
| Summary |
deque::push_back/pop_front are not amortized constant time
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
leni536
|
### Observed behavior
`deque::push_back()` and `deque::pop_front()` don't have amortized O(1)
complexity when they are called in any arbitrary order.
Through analyzing the source of deque, I found the following access problematic pattern:
* The deque can be initialized to a state where its buffer of pointers to chunks is almost
full.
* After this push_back and pop_front called alternately.
* Every time a chunk worth of elements are pushed back and popped from the front then all
of the chunk pointers (around size/chunk_size worth) are moved together one place to the
front in their buffer. The average number of pointer copies in one iteration of push_back + pop_front is around size/(chunk_size^2).
To demonstrate, I tested this with a custom allocator with a fancy pointer that tracks the
number of pointer copies:
https://godbolt.org/z/esTovP1Tb
output:
```
n, #ptr copies per (push_back + pop_front)
31, 6.16129
95, 6.65263
223, 7.49776
479, 8.63466
991, 10.6963
2015, 14.7256
4063, 22.7398
8159, 38.7469
16351, 70.7504
32735, 134.752
65503, 262.753
131039, 518.753
262111, 1030.75
524255, 2054.75
```
### Expected behavior
The standard wording leaves out the number of pointer copies in the complexity requirements of deque. There were some recent discussions on the isocpp-lib reflector on specifying amortized constant time for the pointer operations: thread starts on https://lists.isocpp.org/lib/2025/03/30825.php
Arguably alternating push_back and pop_front is a typical access pattern for deque, therefore slowdowns for this pattern at particular deque sizes are undesirable, even if there is no standard wording (yet) to mandate complexity here.
### Possible fix
One possible direction is to ensure that there is O(size()) space in the front and the back after reallocation, instead of a fixed number of chunks.
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
