News for hackers. Stuff that matters.
Re:How can List be faster than native arrays? (2018) by msclrhd on Sunday August 04, 2019 @11:24AM (#20607056)
It will depend on the allocation method. For example, you could use a pooled allocator that allocates a contiguous array of list items in a block, then use those in order as required. That would help with cached locality. IIRC, the Borland C++ STL implementation did something like this.
Re:How can List be faster than native arrays? (2018) by tfigment on Sunday August 04, 2019 @11:29AM (#20607090)
The deque collection was this efficient. Allocated blocks based on pagesize (4k). A truly beautiful data structure and one of the few good reasons to use stl.
Re:How can List be faster than native arrays? (2018) by rwbt on Sunday August 04, 2019 @11:45AM (#20607197)
Only the libc implementation of std::deque allocates 4KiB blocks and lives upto it's performance and utility. The MSVC implementation is terrible (8 bytes) and even the GCC one isn't that efficient (512 bytes).

Even though boost has a customizable deque block size, it's performance is still way behind Clang's libc.

Re:How can List be faster than native arrays? (2018) by Something1234 on Sunday August 04, 2019 @12:55PM (#20607679)
Wait why wouldn't std::deque allocate blocks as some multiple of the sizeof the thing it holds?
Re:How can List be faster than native arrays? (2018) by tfigment on Sunday August 04, 2019 @03:12PM (#20608626)
> Wait why wouldn't std::deque allocate blocks as some multiple of the sizeof the thing it holds?

It does in the semicontiguous 4k blocks. And at least one msvc was that smart as i used it.

Re:How can List be faster than native arrays? (2018) by mycall on Sunday August 04, 2019 @04:53PM (#20609162)
What is so magical about 4k?
Re:How can List be faster than native arrays? (2018) by gpderetta on Sunday August 04, 2019 @02:42PM (#20608435)
If you laid down all the list nodes in a contiguous array in the correct order, sequential iteration would still be slower than an array scan.