3 ms·
> 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?
by 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 agoIf 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.