What does it mean when we say that a particular datastructure is cache friendly?

Question

I often read that linked list data structure and its variant skiplists are cache friendly in parallel hardware. What does this mean ? Can some one please explain in an easy to understand way .

Edit: The context is in this link .

Answer 1

I often read that linked list data structure and its variant skiplists are cache friendly

linked list and similar structures are NOT CPU cache friendly because each node can be randomly arranged in memory resulting in many cache misses.

An ArrayList by comparison will have all its references sequentially in memory so when a cache line is read in (typically 64 byte long) this can read in 16 references at once.

Note: The objects the List refers to can still be arranged randomly in memory, something you have no control over. :|

---

From the article in the question.

Besides being well suited for concurrent traversal and update, linked lists also are cache-friendly on parallel hardware. When one thread removes a node, for example, the only memory that needs to be transferred to every other core that subsequently reads the list is the memory containing the two adjacent nodes.

What this is talking about is that a linked list when modified by multiple threads at once (something LinkedList in Java doesn't support) only the nodes of the list which are modified need to be made cache consistent. By comparison if you remove or add an element in the middle or start of an ArrayList, you need to update all the references. Give this is known to be inefficient, its best avoided in any case.

The closest example to this in Java is ConcurrentLinkedQueue which supports concurrent adding and removing. The problem is that any benefit you might gain by being able to update the start and the end in terms of the cache is lost by the fact that this action creates garbage which is much more significant, though still not very significant.

If you use an ArrayBlockingQueue you get better cache and garbage behaviour as the references are continuous in memory, don't require shuffling down like ArrayList and don't create garbage to add an entries. (Unfortunately take() creates an object :P )