CppCon 2014: Mike Acton "Data-Oriented Design and C++
Re:Linked List Problems (2002) [pdf]
by coliveira on Saturday November 25, 2017 @01:11PM
(#15777058)
If you already know your data (which must be the case with arrays anyway), you can simply pre-allocate a pool from where the elements of the linked list will be taken. This guarantees that elements will be allocated from the same region in memory. It is a simple technique that I use whenever I believe that a linked list will be needed in a high-performance context.
Re:Linked List Problems (2002) [pdf]
by stochastic_monk on Saturday November 25, 2017 @03:57AM
(#15775112)
Vectors are also usually more memory-efficient, period. A singly-linked list uses a pointer for each element an a doubly-linked uses two, while a vector has constant [a pointer and two integers (size and capacity)] overhead. (Unless the vector was dynamically resized and isn't near capacity.)
Re:Linked List Problems (2002) [pdf]
by avodonosov on Saturday November 25, 2017 @06:58AM
(#15775638)
> if you're accessing data sequentially it's more likely the data you're going to access next is already in cache
Why?
Cache consists of cache lines (usually 64 bytes). If an element in the list is smaller than the cache line a whole line is put in the cache anyway. This means that data is cached that you have not read yet. When using a contiguous array this unread data contains the next elements. So they are cached without ever having been read.
Cache prefetching. (https://en.wikipedia.org/wiki/Cache_prefetching)
Essentially, many workloads access data sequentially and therefore modern cache architectures have special optimizations to make these memory accesses as fast as possible, by prefetching the next item in the sequence before it is actually needed.
Re:Linked List Problems (2002) [pdf]
by avodonosov on Sunday November 26, 2017 @04:49AM
(#15780186)
Ah, yes.
Well, anyways I value code simplicity more than anything.
Maybe CPUs will learn to do cache prefetch for link oriented languages: if a "load and dereference" pattern is detected, CPU could prefetch the data referenced by pointers it has in registers or recently fetched cache line.
BTW, linked list elements are not necessary located far away from each other, if we allocated them one after another chance are they are near each other in memory.
Most (all I've read/looked at) benchmarks in Java have data structures backed by linked lists utterly smashed by things implemented by an array.
There was in the last year or two a good c++ talk where a game or game engine changed their storage to be more array like and got roughly a 30% boost in performance. Memory locality is usually king, which is why linked lists are rarely used.