4 ms·

You're misunderstanding the advice about contiguous. It's not that it's more likely to stay in cache, but if you're accessing data sequentially it's more likely

You're misunderstanding the advice about contiguous. It's not that it's more likely to stay in cache, but if you're accessing data sequentially it's more likely the data you're going to access next is already in cache. 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.

posterboy 9y ago
the time complexity of insert etc is superior and a good reason for abstraction on top of an array, I would think.
stochastic_monk 9y ago
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.)
trentmb 9y ago
CppCon 2014: Mike Acton "Data-Oriented Design and C++ https://youtu.be/rX0ItVEVjHc https://youtu.be/rX0ItVEVjHc https://en.m.wikipedia.org/wiki/Data-oriented_design https://en.m.wikipedia.org/wiki/Data-oriented_design
avodonosov 9y ago
> if you're accessing data sequentially it's more likely the data you're going to access next is already in cache Why?
- yorwba 9y ago
  Cache prefetching. (https://en.wikipedia.org/wiki/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.
  - avodonosov 9y ago
    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.
- JelteF 9y ago
  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.
coliveira 9y ago
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.

posterboy 9y ago

the time complexity of insert etc is superior and a good reason for abstraction on top of an array, I would think.

stochastic_monk 9y ago

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.)

trentmb 9y ago

CppCon 2014: Mike Acton "Data-Oriented Design and C++ https://youtu.be/rX0ItVEVjHc https://youtu.be/rX0ItVEVjHc https://en.m.wikipedia.org/wiki/Data-oriented_design https://en.m.wikipedia.org/wiki/Data-oriented_design

avodonosov 9y ago

> if you're accessing data sequentially it's more likely the data you're going to access next is already in cache Why?

yorwba 9y ago
Cache prefetching. (https://en.wikipedia.org/wiki/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.
- avodonosov 9y ago
  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.
JelteF 9y ago
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.

coliveira 9y ago

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.