I’ve Consed Every Pair

Which in turn makes me think of New Math by Tom Lehrer :)

I am ready to be corrected but I'm a fairly sure there have been a few other continuation-based web frameworks, Seaside in Smalltalk was the one that made the idea popular if I recall correctly. "Href considered harmful" comes from that.

I apologize if the comment upset you, that wasn't my intention.

The thread was about Lisp, Johnny Cash, and Peter Norvig, the last of whom I was quoting. It seemed perfectly relevant.

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?

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.