News for hackers. Stuff that matters.

A comment on The time complexity of the libc++ deque push_front implementation is O(log n). Parent comment

Re:The time complexity of the libc++ deque push_front implem... by brandmeyer on Sunday November 28, 2021 @12:57PM (#29371111)
> MS STL at around 64bytes.

Citation? Are you sure it isn't 64 size-independent elements?

[ Parent | on HN ]
Re:The time complexity of the libc++ deque push_front implem... by MauranKilom on Sunday November 28, 2021 @01:33PM (#29371487)
It's worse actually. The MSVC STL uses 16 byte (or however large your element is, if greater) chunks. Source:

https://github.com/microsoft/STL/blob/main/stl/inc/deque#L56...

They have made clear that this won't be changed, for ABI stability reasons.

That makes std::dequeue basically unusable in a portable context. In virtually any situation, "allocate each element separately" and "allocate elements in 4k chunks" are on opposite ends of the performance spectrum.

[ Parent | on HN ]
Re:The time complexity of the libc++ deque push_front implem... by brandmeyer on Sunday November 28, 2021 @07:14PM (#29374753)
That is quite unfortunate, and I freely admit that I'm unfamiliar with MSVC's current quirks.

> They have made clear that this won't be changed, for ABI stability reasons.

Also unfortunate. Once upon a time, users had to be extra careful to control which version of the runtime DLL their program transitively linked to since MS would issue a new ABI-breaking version with every major compiler release. Sounds like they got ABI stability religion just in time to lock in some unfortunate decisions.

[ Parent | on HN ]
Re:The time complexity of the libc++ deque push_front implem... by beached_whale on Sunday November 28, 2021 @11:34PM (#29376403)
Thanks, I remembered incorrectly.
[ Parent | on HN ]