9 ms·
> There are a few operations where List is slower than native arrays. One of these is random accessing. What about sequential access? Surely array gets a benef
by Myrmornis 7y ago
> There are a few operations where List is slower than native arrays. One of these is random accessing.
What about sequential access? Surely array gets a benefit from data locality, where CPU caches pull in surrounding values automatically?
- msclrhd 7y agoIt 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.
- tfigment 7y agoThe 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.
- rwbt 7y agoOnly 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.
- Something1234 7y agoWait why wouldn't std::deque allocate blocks as some multiple of the sizeof the thing it holds?
- gpderetta 7y agoIf 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.