Hacker News new | ask | show | jobs
by avodonosov 3131 days ago
> if you're accessing data sequentially it's more likely the data you're going to access next is already in cache

Why?

2 comments

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.

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.