The Linked List and Modern Architectures
The linked list is a less-than-welcome guest on modern machine architectures, for reasons which are well-known.
I am trying to determine if the difference between current cache and main memory speeds (as well as other concerns) have made CDR coding attractive again. It has traditionally been considered a no-no on any machine lacking hardware-assisted tagging. I may have to settle the question empirically.
Assuming anyone is actually reading this, I will also ask: does anyone know of a Lisp system which uses the Unrolled Linked List (or similarly unorthodox data structure) to store all CONS cells?
With regards to memory-saving cons cell data structures, you might want to look into hash-consing.
Hi,
I had the same idea, you should have a look to Phil Bagwell "Fast Functional Lists"
Since J. McCarthy first introduced Functional Programming, the Linked List has almost universally been used as the underpinning data structure. This paper introduces a new data structure, the VList, that is compact, thread safe and significantly faster to use than Linked Lists for nearly all list operations. Space usage can be reduced by 50% to 90% and in typical list operations speed improved by factors ranging from 4 to 20 or more. Some important operations such as indexing and length are typically changed from O(N) to O(1) and O(lgN) respectively. In the current form the VList structure can provide an alternative heap architecture for functional languages using eager evaluation. To prove the viability of the new structure a language interpreter Visp, a dialect of Common Lisp, has been implemented using VList and a simple benchmark comparison with OCAML reported.