5

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 .

Shubham
  • 35
  • 4
Geek
  • 26,489
  • 43
  • 149
  • 227

1 Answers1

7

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 )

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • 2
    The ArrayList is not necessarily cache friendly either. First of all, you have no general way to know how Java object instances are actually stored in physical memory. Even arrays may be fragmented and do not have to be places in contiguous memory. Even if the reference array backing an ArrayList would have been in contiguous memory, the referenced objects is most likely not. – jarnbjo Aug 30 '12 at 10:42
  • 4
    array are always continuous in memory in all the JVMs I am aware of. Its not guaranteed, but it is the simplest way of doing this. If the objects only appear in the list, they can be continuous in memory because a) objects are created continuously in the TLAB b) objects are copied between generation as they are found (For HotSpot this appears to be the reverse order but basically the same) – Peter Lawrey Aug 30 '12 at 10:47
  • In any case we can be almost 100% sure that, even if not contiguous, arrays will not be severely fragmented. An implementation that freely fragments arrays would not be able to provide expected performance for array access, even discounting the effects of slow main memory. – Marko Topolnik Aug 30 '12 at 10:54
  • @PeterLawrey so what you are saying is contrary to what I have been reading – Geek Aug 30 '12 at 10:57
  • @Geek Can you provide any references which say LinkedList is cache friendly? – Peter Lawrey Aug 30 '12 at 11:05
  • @PeterLawrey posted the link in the question itself. – Geek Aug 30 '12 at 11:09
  • @Geek Commented on a quote which you might be thinking of. – Peter Lawrey Aug 30 '12 at 11:24