3 ms·

cons lists are kind of slow because they don't play well with CPU caches. Are there any ideas how to adapt Lisp (or LISP) so that it plays well with current CPU

cons lists are kind of slow because they don't play well with CPU caches. Are there any ideas how to adapt Lisp (or LISP) so that it plays well with current CPU architectures?

psykotic 7y ago
Clojure uses persistent vectors which are essentially trees of array chunks (I think 32 elements per array chunk) that support structure sharing and a version of cons called conj that runs in order log32(n) time. But the language isn't really designed for high performance in practice despite some of the early marketing. Anyway, caches are only part of the problem with linked lists. The root problem is that they inhibit out of order execution. Work out the data dependencies and scheduling of a simple summation loop for an array compared to a linked list. Assume everything fits in L1. The out-of-order core goes to town with the array code and overlaps the fetches for subsequent iterations of the loop. But the linked list code is serialized with almost no instruction-level parallelism; you can overlap the summation of an element into the accumulator with the start of the deref of the next pointer, but that only saves you one cycle per iteration compared to what an in-order core would do with the same code. Now suppose the data is in L2. In that case the out-of-order core can overlap the loads of the subsequent array elements and the throughput is only diminished by a little if at all compared to the L1 case. The linked list code, on the other hand, works the same as before but because it cannot overlap the fetches for sequential elements due to the dependent loads, you go from say 5 cycles per iteration to 15 cycles per iteration. If you have to go out to L3 or DRAM the chasm dramatically widens even further. More obviously, linked structures also increase pressure on cache capacity since they have to store their links explicitly. Yet another factor is that modern caches will expend bandwidth on speculative prefetches to reduce latency. This can help for both flat and linked data structures. For example, if you have an AST you should linearly allocate the nodes in the anticipated traversal order to get help from the prefetcher. (And please slim down those fat AST nodes.) If you did that for our linked-list summation example, you'd pay the 15 cycles for the first iteration but then you'd pay 5 cycles for the remaining entries in the same cacheline and also 5 cycles for all remaining entries in other cachelines since the prefetcher will have kicked in. So aside from the startup latency, you're back to running at the same speed as when the list started out in L1. But you're still losing out on the out-of-order execution for the L1 fetches: 4 cycles on a modern core is an opportunity cost of 16 instructions. You're reducing your core to a souped up 486. By the way, for this particular toy example you should go beast mode with SIMD instructions for the array case which will net you another factor of 4x to 32x depending on the element size and the width of your vector unit and then you parallelize across your cores to get another factor of 4x. While those particulars might not generalize to less simple problems, it illustrates that the major issue with linked structures is that they force serial processing.
kazinator 7y ago
> cons lists are kind of slow because they don't play well with CPU caches. Cons lists were slow on the IBM 704 too. Good thing that didn't stop anyone, right? > Are there any ideas how to adapt Lisp (or LISP) so that it plays well with current CPU architectures? An ARRAY feature was described in the 1960 Lisp manual. That's probably because it was recognized that linked lists weren't the be-all data structure even on the IBM 704; sometimes it's nice to have compact storage and fast random access. Can we move past this in 2020? Let's leave this to the people who have a single aggregate structure in their programming language that is ambiguous between list and array.
- chrisseaton 7y ago
  > Cons lists were slow on the IBM 704 too. Good thing that didn't stop anyone, right? The IBM 704 didn't have a cache hierarchy. The problem that the person you're replying to is talking about didn't exist on that architecture. Accessing any memory location on an IBM 704 took the same time, so it doesn't matter if your values are consecutive in memory as in an array, or somewhere far away as possibly in a linked list. But on a modern architecture reading a value far away can cause a cache miss. What do you think the time penalty is for a full cache miss? Something small? Maybe a couple of times slower? No, the difference between a level 1 hit as often in an array, and a cache miss, as often in a linked list, is around two orders of magnitude. It's literally multiple orders of magnitude worse relatively than it was on the 704. Ideally modern Lisp implementations would use some kind of variant of the storage strategies pattern, as used for languages like JavaScript, to give the same semantics as a cons cell but actually using a cache-friendly implementation, but I think this is an unsolved research problem.
- dreamcompiler 7y ago
  If I can elaborate just a bit on kazinator's comment: While it's still possible to use cons cells as one's sole data structure in Lisp, no Lisp programmer with any experience does that. Making cons cells faster would be like forcing horses to drink Red Bull so they could pull chariots as fast as cars. It's a solved problem -- just use a car (npi) -- and there's no need to abuse any horses.

cons lists are kind of slow because they don't play well with CPU caches. Are there any ideas how to adapt Lisp (or LISP) so that it plays well with current CPU architectures?

psykotic 7y ago

Clojure uses persistent vectors which are essentially trees of array chunks (I think 32 elements per array chunk) that support structure sharing and a version of cons called conj that runs in order log32(n) time. But the language isn't really designed for high performance in practice despite some of the early marketing. Anyway, caches are only part of the problem with linked lists. The root problem is that they inhibit out of order execution. Work out the data dependencies and scheduling of a simple summation loop for an array compared to a linked list. Assume everything fits in L1. The out-of-order core goes to town with the array code and overlaps the fetches for subsequent iterations of the loop. But the linked list code is serialized with almost no instruction-level parallelism; you can overlap the summation of an element into the accumulator with the start of the deref of the next pointer, but that only saves you one cycle per iteration compared to what an in-order core would do with the same code. Now suppose the data is in L2. In that case the out-of-order core can overlap the loads of the subsequent array elements and the throughput is only diminished by a little if at all compared to the L1 case. The linked list code, on the other hand, works the same as before but because it cannot overlap the fetches for sequential elements due to the dependent loads, you go from say 5 cycles per iteration to 15 cycles per iteration. If you have to go out to L3 or DRAM the chasm dramatically widens even further. More obviously, linked structures also increase pressure on cache capacity since they have to store their links explicitly. Yet another factor is that modern caches will expend bandwidth on speculative prefetches to reduce latency. This can help for both flat and linked data structures. For example, if you have an AST you should linearly allocate the nodes in the anticipated traversal order to get help from the prefetcher. (And please slim down those fat AST nodes.) If you did that for our linked-list summation example, you'd pay the 15 cycles for the first iteration but then you'd pay 5 cycles for the remaining entries in the same cacheline and also 5 cycles for all remaining entries in other cachelines since the prefetcher will have kicked in. So aside from the startup latency, you're back to running at the same speed as when the list started out in L1. But you're still losing out on the out-of-order execution for the L1 fetches: 4 cycles on a modern core is an opportunity cost of 16 instructions. You're reducing your core to a souped up 486. By the way, for this particular toy example you should go beast mode with SIMD instructions for the array case which will net you another factor of 4x to 32x depending on the element size and the width of your vector unit and then you parallelize across your cores to get another factor of 4x. While those particulars might not generalize to less simple problems, it illustrates that the major issue with linked structures is that they force serial processing.

kazinator 7y ago

> cons lists are kind of slow because they don't play well with CPU caches. Cons lists were slow on the IBM 704 too. Good thing that didn't stop anyone, right? > Are there any ideas how to adapt Lisp (or LISP) so that it plays well with current CPU architectures? An ARRAY feature was described in the 1960 Lisp manual. That's probably because it was recognized that linked lists weren't the be-all data structure even on the IBM 704; sometimes it's nice to have compact storage and fast random access. Can we move past this in 2020? Let's leave this to the people who have a single aggregate structure in their programming language that is ambiguous between list and array.

chrisseaton 7y ago
> Cons lists were slow on the IBM 704 too. Good thing that didn't stop anyone, right? The IBM 704 didn't have a cache hierarchy. The problem that the person you're replying to is talking about didn't exist on that architecture. Accessing any memory location on an IBM 704 took the same time, so it doesn't matter if your values are consecutive in memory as in an array, or somewhere far away as possibly in a linked list. But on a modern architecture reading a value far away can cause a cache miss. What do you think the time penalty is for a full cache miss? Something small? Maybe a couple of times slower? No, the difference between a level 1 hit as often in an array, and a cache miss, as often in a linked list, is around two orders of magnitude. It's literally multiple orders of magnitude worse relatively than it was on the 704. Ideally modern Lisp implementations would use some kind of variant of the storage strategies pattern, as used for languages like JavaScript, to give the same semantics as a cons cell but actually using a cache-friendly implementation, but I think this is an unsolved research problem.
dreamcompiler 7y ago
If I can elaborate just a bit on kazinator's comment: While it's still possible to use cons cells as one's sole data structure in Lisp, no Lisp programmer with any experience does that. Making cons cells faster would be like forcing horses to drink Red Bull so they could pull chariots as fast as cars. It's a solved problem -- just use a car (npi) -- and there's no need to abuse any horses.