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