6 ms·

Something the article does not touch on is the huge cache performance penalty you pay with linked lists. With a linked list, all of the nodes are scattered arou

Something the article does not touch on is the huge cache performance penalty you pay with linked lists. With a linked list, all of the nodes are scattered around your heap. So whenever you iterate a linked list, you are accessing random memory locations. Random access is not really cacheable. Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is frequently 3-10x slower. This is because the CPU will load contiguous chunks of memory into cache. On x86, the cache block size is 64 bytes. So for an array of 4 byte ints, you are loading 16 ints into cache at a time. With a linked list, you will likely get a cache miss on most nodes and have to access RAM. Access time for L1 cache is 0.5 nanoseconds, access time for RAM is ~100 nanoseconds.

eutectic 10y ago
This is not necessarily true in garbage-collected languages.
- gamegoblin 10y ago
  For what it's worth, I did the following benchmarks in Java 8: Make two List<Object>s. One is LinkedList one is ArrayList. Then timed how long it took to empty the list by deleting random indexes. For LinkedList this is O(n) to iterate up to the element and O(1) to remove it. For ArrayList isn't O(n) to shift all of the following elements down by 1 index. As the list size approaches infinity, the benchmark shows that the ArrayList is 10x faster. That's because even though you are copying a ton of memory, it's all contiguous in memory and highly cacheable. In the LinkedList you are just chasing pointers to iterate the array, but they are not cacheable. A more common example is the case of queues. I made two Queue<Object>s, one was LinkedList and another ArrayDeque. Then I polled the head of the queue until empty. As N gets larger, the ArrayDeque is 3x faster.
kazinator 10y ago
List nodes being scattered depends on the memory management. When you start out with a blank heap, if you grab successive cons cells, they can be adjacent (in the same cache line). Also, when a garbage collection pass reclaims unreachable conses and puts them into a free list, it can sweep them in heap order, so physically neighboring free cells end up together in the free list.
- AnimalMuppet 10y ago
  That's true. You still have the heap overhead, though. If the heap allocates an int (for the block size) just before the block it returns, then if your linked list contains ints, the heap memory overhead is 50%. This means you get half as many entries in a cache line, even if they were allocated in order.
hajile 10y ago
Haskell's garbage collector is compacting (see below). When the GC compacts, it is very easy to put linked list entries together for more efficient access. http://simonmar.github.io/bib/papers/parallel-gc.pdf http://simonmar.github.io/bib/papers/parallel-gc.pdf
- jblow 10y ago
  "it is very easy" but have you ever actually measured whether it does, and whether the resulting performance is high?
  - coolsunglasses 10y ago
    Haskell has list fusion so efficient list code never actually constructs a list that lives on the heap to be GC'd to start with. So, with that proviso, the answer to your question is yes and that as a result sometimes list code can be faster than vectors.
    - jblow 10y ago
      [citation needed, in the form of actual benchmarks] The thing is that list fusion and whatnot is all just there to get around the handicap that was placed there in the first place by the language paradigm. So you start by insisting on shooting yourself in the foot, then put lots of armor on your boot so the bullet hopefully bounces off. I assume by "vectors" you mean arrays ... there is no case in which this can be faster than arrays, because in the limit, if the list fusion system works perfectly, it is just making an array. A thing can't be faster than itself.
      - coolsunglasses 10y ago
        If you need something predictable, you'll usually use a vector in Haskell. Nothing obligates you to use a list. I regard it as more of a pleasant surprise and something that surprises/confuses people when they benchmark `String` (which is `[Char]` under the hood) against `Text` (which is an `Array` under the hood: http://hackage.haskell.org/package/text-1.2.2.1/docs/src/Data-Text-Internal.html#Text http://hackage.haskell.org/package/text-1.2.2.1/docs/src/Dat... ) I've had `String` come out faster than `Text` in benchmarks plenty of times, including for a colleague when we were writing up this post https://lorepub.com/post/2016-12-17-Haskell-Pitfalls https://lorepub.com/post/2016-12-17-Haskell-Pitfalls What I'm not going to do is perform free labor for a man with a bad attitude who is 100x wealthier than I am. I'm not saying you should design a performance oriented language around short-cut fusion, but the "cost" of using Haskell is generally not what people think it is. The span of applicability for Haskell, IME, ranges from Java/Golang to Ruby. It's no replacement for C++, but it does come close in some applications that aren't hard/soft real-time.
DonaldFisk 10y ago
There are two advantages of lists, however: you can add elements to a list without modifying the original list or ever having to reallocate it, and garbage collection never requires defragmentation as all lists (except NIL) are implemented as exactly two words, the head and a pointer to the tail. If you're processing huge quantities of data or writing games, the speed hit you take from frequent cache misses probably means you should avoid lists whenever you can. You should certainly avoid them in non-garbage collecting languages such as C where you have the additional inconvenience of manual memory management of two word data structures. But those kinds of programs are atypical - most involve frequent user interaction. Almost all languages (including Lisp) have contiguous data structures and these will often fit the data better. Also, lists which aren't built up a cell at a time will be CDR-coded if the language implementation supports that.
rbehrends 10y ago
> Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is frequently 3-10x slower. Careful. I've actually done some recent benchmarking (in OCaml, not Haskell), and the results don't necessarily bear that out, especially if you need dynamic arrays rather than static arrays. A particular use case is the creation of dynamically sized temporary data. A bump allocator will put list nodes in a contiguous section of memory, but does not require resizing. A dynamic array may be resized several times, requiring additional copying and allocations (and possibly expensive major heap allocations). As a result, the relative performance difference not only may not be as dramatic, but can actually swing in the favor of linked lists. Note that I'm not saying that performance degradation due to poor memory locality of linked lists won't happen, just that there are plenty of use cases where this is not a problem.
- wcummings 10y ago
  You can allocate more space than you might need to avoid resizing. It's not uncommon for Java programmers to pass a size when initializing empty array lists, knowing they will be filled.
  - rbehrends 10y ago
    I am well aware of that, but you often don't have that information.
gpderetta 10y ago
Even if the list were fully cached in L1, traversing an array can be significantly faster as the CPU can extract a lot of parallelism. On the other hand a list is a long dependency chain of non trivial latency instructions. Linked lists (and other node-based data structures) of course shine for modification heavy work, when traversal is uncommon or when you need to preserve addresses.
LeanderK 10y ago
just some personal experience: While i don't doubt it's true, GHC and it's GC are so optimised for this scenario that (compared to for example java) i don't notice much of a slowdown. Also haskells different execution-model comes into play. You don't really iterate much over lists, but instead execute "specific code blocks".

eutectic 10y ago

This is not necessarily true in garbage-collected languages.

gamegoblin 10y ago
For what it's worth, I did the following benchmarks in Java 8: Make two List<Object>s. One is LinkedList one is ArrayList. Then timed how long it took to empty the list by deleting random indexes. For LinkedList this is O(n) to iterate up to the element and O(1) to remove it. For ArrayList isn't O(n) to shift all of the following elements down by 1 index. As the list size approaches infinity, the benchmark shows that the ArrayList is 10x faster. That's because even though you are copying a ton of memory, it's all contiguous in memory and highly cacheable. In the LinkedList you are just chasing pointers to iterate the array, but they are not cacheable. A more common example is the case of queues. I made two Queue<Object>s, one was LinkedList and another ArrayDeque. Then I polled the head of the queue until empty. As N gets larger, the ArrayDeque is 3x faster.

kazinator 10y ago

List nodes being scattered depends on the memory management. When you start out with a blank heap, if you grab successive cons cells, they can be adjacent (in the same cache line). Also, when a garbage collection pass reclaims unreachable conses and puts them into a free list, it can sweep them in heap order, so physically neighboring free cells end up together in the free list.

AnimalMuppet 10y ago
That's true. You still have the heap overhead, though. If the heap allocates an int (for the block size) just before the block it returns, then if your linked list contains ints, the heap memory overhead is 50%. This means you get half as many entries in a cache line, even if they were allocated in order.

hajile 10y ago

Haskell's garbage collector is compacting (see below). When the GC compacts, it is very easy to put linked list entries together for more efficient access. http://simonmar.github.io/bib/papers/parallel-gc.pdf http://simonmar.github.io/bib/papers/parallel-gc.pdf

jblow 10y ago
"it is very easy" but have you ever actually measured whether it does, and whether the resulting performance is high?
- coolsunglasses 10y ago
  Haskell has list fusion so efficient list code never actually constructs a list that lives on the heap to be GC'd to start with. So, with that proviso, the answer to your question is yes and that as a result sometimes list code can be faster than vectors.
  - jblow 10y ago
    [citation needed, in the form of actual benchmarks] The thing is that list fusion and whatnot is all just there to get around the handicap that was placed there in the first place by the language paradigm. So you start by insisting on shooting yourself in the foot, then put lots of armor on your boot so the bullet hopefully bounces off. I assume by "vectors" you mean arrays ... there is no case in which this can be faster than arrays, because in the limit, if the list fusion system works perfectly, it is just making an array. A thing can't be faster than itself.
    - coolsunglasses 10y ago
      If you need something predictable, you'll usually use a vector in Haskell. Nothing obligates you to use a list. I regard it as more of a pleasant surprise and something that surprises/confuses people when they benchmark `String` (which is `[Char]` under the hood) against `Text` (which is an `Array` under the hood: http://hackage.haskell.org/package/text-1.2.2.1/docs/src/Data-Text-Internal.html#Text http://hackage.haskell.org/package/text-1.2.2.1/docs/src/Dat... ) I've had `String` come out faster than `Text` in benchmarks plenty of times, including for a colleague when we were writing up this post https://lorepub.com/post/2016-12-17-Haskell-Pitfalls https://lorepub.com/post/2016-12-17-Haskell-Pitfalls What I'm not going to do is perform free labor for a man with a bad attitude who is 100x wealthier than I am. I'm not saying you should design a performance oriented language around short-cut fusion, but the "cost" of using Haskell is generally not what people think it is. The span of applicability for Haskell, IME, ranges from Java/Golang to Ruby. It's no replacement for C++, but it does come close in some applications that aren't hard/soft real-time.

DonaldFisk 10y ago

There are two advantages of lists, however: you can add elements to a list without modifying the original list or ever having to reallocate it, and garbage collection never requires defragmentation as all lists (except NIL) are implemented as exactly two words, the head and a pointer to the tail. If you're processing huge quantities of data or writing games, the speed hit you take from frequent cache misses probably means you should avoid lists whenever you can. You should certainly avoid them in non-garbage collecting languages such as C where you have the additional inconvenience of manual memory management of two word data structures. But those kinds of programs are atypical - most involve frequent user interaction. Almost all languages (including Lisp) have contiguous data structures and these will often fit the data better. Also, lists which aren't built up a cell at a time will be CDR-coded if the language implementation supports that.

rbehrends 10y ago

> Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is frequently 3-10x slower. Careful. I've actually done some recent benchmarking (in OCaml, not Haskell), and the results don't necessarily bear that out, especially if you need dynamic arrays rather than static arrays. A particular use case is the creation of dynamically sized temporary data. A bump allocator will put list nodes in a contiguous section of memory, but does not require resizing. A dynamic array may be resized several times, requiring additional copying and allocations (and possibly expensive major heap allocations). As a result, the relative performance difference not only may not be as dramatic, but can actually swing in the favor of linked lists. Note that I'm not saying that performance degradation due to poor memory locality of linked lists won't happen, just that there are plenty of use cases where this is not a problem.

wcummings 10y ago
You can allocate more space than you might need to avoid resizing. It's not uncommon for Java programmers to pass a size when initializing empty array lists, knowing they will be filled.
- rbehrends 10y ago
  I am well aware of that, but you often don't have that information.

gpderetta 10y ago

Even if the list were fully cached in L1, traversing an array can be significantly faster as the CPU can extract a lot of parallelism. On the other hand a list is a long dependency chain of non trivial latency instructions. Linked lists (and other node-based data structures) of course shine for modification heavy work, when traversal is uncommon or when you need to preserve addresses.

LeanderK 10y ago

just some personal experience: While i don't doubt it's true, GHC and it's GC are so optimised for this scenario that (compared to for example java) i don't notice much of a slowdown. Also haskells different execution-model comes into play. You don't really iterate much over lists, but instead execute "specific code blocks".