3 ms·
In theory a linked list has lots of attractive features as a data structure and when LISP Machines were a thing that theory translated into reality pretty well.
by tialaramex 5y ago
In theory a linked list has lots of attractive features as a data structure and when LISP Machines were a thing that theory translated into reality pretty well.
Today losing data locality hurts really badly. Rust does provide a linked list, for the handful of cases where that really is what you wanted, but almost always even though in theory a vector should be worse, in practice it's better.
For example if you build a toy system with a thousand small integers on the list, you might reason that removing the 500th via a vector instead of a linked list would be awful - you'd need to shuffle 500 of them forward compared to just swapping a pointer. But wait, on today's hardware the linked list approach involves about five hundred dependent cache misses. Before you find the 500th on the list to remove it, you have stalled the CPU for so long the vector implementation would have already finished doing its shuffling of 500 items forward in memory and moved on to something else.
Now, if your list has 500 million items in it, and you often want to remove just the first item while appending to the far end, a Vector is indeed a bad fit. But there are still better alternatives than a Linked List, Rust provides a Deque but unlike the one a Lisp-enthusiastic professor may have showed you in data structures class, it's actually a similar structure to a vector not a linked list.
- brundolf 5y agoI'm not here to debate the virtues of linked-lists, I'm just pointing out that they're extremely idiomatic in Lisp, so it's weird to implement a basic Lisp that doesn't use them, because anybody running idiomatic code in it will be in for a big surprise.
- rjsw 5y agoLisp Machines could also implement lists using vectors [1]. [1] https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding
- nerpderp82 5y agoIt would be interesting to have a List trait and a cons operation on that trait and one could swap out for different list implementations. A DebugList might keep track of operation on the list and recommend allocation hints or operations that could be sped up. One could absolutely use a Dequeue or some other optimized structure for a Lisp list, really depends on how the code is written.
- jhgb 5y ago> One could absolutely use a Dequeue or some other optimized structure for a Lisp list How? With naked deque nodes? Since otherwise you wouldn't get Lisp lists, you couldn't have structure sharing, etc. And where would the reverse deque node pointer point to if multiple nodes pointed to the node in question?
- lispm 5y agoAre there any numbers with actual implementations? it seems to me that removing single number from a random position in a list is also not what Lisp lists address, especially since Lisp implementations have vectors, too.