News for hackers. Stuff that matters.
Re:When Big O Fools You by Const-me on Tuesday August 23, 2016 @04:35PM (#12347345)
Ported to C++, added two ATL collections, also added 100M elements data point:

https://github.com/Const-me/CollectionMicrobench

Arrays are still generally faster than lists.

The funny thing is Microsoft’s linked lists are faster than C++ standard vectors.

Re:When Big O Fools You by ric129 on Tuesday August 23, 2016 @04:58PM (#12347572)
>The funny thing is Microsoft’s linked lists are faster than C++ standard vectors.

If I had to guess, it's because the std::vector is more conservative in memory use and it causes more malloc/array copy calls.

Re:When Big O Fools You by Const-me on Tuesday August 23, 2016 @05:16PM (#12347729)
I think the main reason is CAtlList class encapsulates its own memory pool. It allocates RAM in batches. The default batch size for CAtlList is 10 elements/batch, user-adjustable in constructor, but I kept the default value 10.

The elements are created directly adjacent to each other. This makes iteration faster because RAM locality despite the pointer-based data structure.