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 im3w1l on Sunday November 28, 2021 @08:11AM (#29368640)

So iiuc:

The libc++ implementation is bad. The libstdc++ implementation is fine. The issue with the former is that it doesn't have enough spare capacity so it has to shift elements around too often.

Actually I think the push_front is even worse than stated: O(n). Consider an array with capacity N+1, contains N elements. Now if you alternate push_front and pop_back then every push_front will cause memmove of N elements.

Oh and to make like a 4th addition to this comment: It's kind of funny that the code is so unreadable that the author found it more helpful to look at the generated assembler code.

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by rightbyte on Sunday November 28, 2021 @10:01AM (#29369373)

Reading those C or C++ standard libraries is like a joke. Almost nothing is done in a direct or clear way and internal methods have cryptic names hidden in macros.

Maybe for a good reason I dunno. But it would be nice if the code was clearer so you could make sense of it when gdb or callgrind jumps into an inlined chunk ...

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by brandmeyer on Sunday November 28, 2021 @01:02PM (#29371156)

> internal methods have cryptic names

They choose names like _Capitalized and __lowercase because those identifiers are reserved for the implementation. Its a consequence of the preprocessor's lack of hygiene.

So where you might see a convention of naming members like m_thingish_foo, in the implementation's library headers they would be named _M_thingish_foo or __m_thingish_foo.

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by rightbyte on Sunday November 28, 2021 @01:33PM (#29371494)

Ye true. Maybe I am just whining because the inlined chunks in e.g. callgrind or gdb looks so random. I should use "-Og" more often ...

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by brandmeyer on Sunday November 28, 2021 @07:05PM (#29374690)

GDB has a pluggable pretty-printing system.

http://sourceware.org/gdb/wiki/STLSupport

That doesn't necessarily help if you are backtracing from your own lambda up through some <algorithm>. But it does help many other use cases with the standard library.

[ Parent | on HN ]