5 ms·
Typically, lisps will implement their lists internally in terms of a VList[1] or similar data structure, which has some of the benefits of both linked lists and
by sparkie 8y ago
Typically, lisps will implement their lists internally in terms of a VList[1] or similar data structure, which has some of the benefits of both linked lists and vectors, and the downsides of each are minimized. VLists are [O(1) cons, car, cdr, index average] and [O(log N) length, index worst case], making them a pretty good all-rounder. There is also improved cache locality as compared to a linked-list.
[1]:http://lampwww.epfl.ch/papers/techlists.pdf http://lampwww.epfl.ch/papers/techlists.pdf
- kazinator 8y agoLisps do not "typically" use this relatively obscure data structure. Can you name one Lisps that use it? If so, how about two more?
- lispm 8y agoIt's also fascinating that none of the 'benchmarks' in the paper practically matter (today) in a native Lisp implementation: creating, copying, appending, mapping, ...
- kazinator 8y agoThe paper is annoyingly undated; the highest year that occurs among the citations is 1999, so I'm taking that to be its date. The discussion on garbage collection of these vlists is noteworthy. The paper admits that their aggregation causes retention of garbage ("Large parts of the unused list structure may not be garbage collected."), and since they have heterogeneous sizes, fragmentation also. But, oh, that's totally okay, because all you have to do is make your collector copying to compact these things and you're good! cons cells cause no fragmentation whatsoever (they can be placed in a dedicated cons heap in which everything is a cons of the same size), and an unreachable cons cell is always reclaimable.
- lispm 8y agoThat would be surprising. Typically Lisp implements lists in terms of cons cells and the empty list.