@dkf said in Best Linked List Ever:
@ixvedeusi said in Best Linked List Ever:
And why would that be (assuming you never have to traverse it in reverse)?
The information flow inside the processor results in better handling of memory, whereas complex tricks with address arithmetic force the main ALU to be used to generate the address, so you tend to get a longer pipeline stall. By contrast, array accesses have been extremely well optimised for you already, as they're utterly critical to so much performance. (Structure accesses are also really quick.)
Essentially, if you store the address in "plain sight" (i.e., you store the actual address, and not some value from which it can be derived), your CPU may be able to prefetch memory related to it. If you need to compute the address, it's much less likely that the CPU will see the address ahead of time and be able to prefetch based on that.
There's a talk at one of the recent CppCon by (IIRC) a LLVM guy. Essentially, arrays work well with cache and prefetch, linked lists can maybe be prefetched one node ahead and you might get lucky with the cache (but probably not). He suggests an array of pointers as a middle ground in some cases (i.e., with big nodes), since that allows prefetching to be more efficient (look-ahead is easier).
Disclaimer: This assumes a modern CPU. Your problem might be different. Use
protectionprofilers. Etc etc etc.