The time complexity of the libc++ deque push_front implementation is O(log n)

Re:The time complexity of the libc++ deque push_front implem... by blahgeek on Sunday November 28, 2021 @09:30AM (#29369156)

While I very much appreciate and respect author's detailed analysis, I am still not 100% convinced without a corresponding benchmark result. If it's really O(log n) vs O(1), it should be very easy to verify in some micro-benchmark.

Instead of that, the author mentioned that:

> The tests that I did run, initially the libstdc++ and the libc++ versions have roughly the same performance, but the performance diverges after a number of insertions somewhere between 6,400 and 12,800. After that the runtime of the libc++ version is roughly 2-3 times that of the libstdc++ version. (...) the outcomes of which depend on the compiler version anyway.

This does not seem right.

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by x1f604 on Sunday November 28, 2021 @09:41AM (#29369243)

Here are the results of the benchmark that I did: https://imgur.com/a/2lCktTO

It didn't look quite right to me so I didn't post it.

Here's another benchmark that I did where you can clearly see that something has gone wrong: https://imgur.com/a/s2rA8qE

[ Parent | on HN ]