3 ms·
There is such a thing as an unrolled linked list, which is a bit like a flat B-tree: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.or
by twic 6y ago
There is such a thing as an unrolled linked list, which is a bit like a flat B-tree:
https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list
They ought to have quite good properties. In particular, if you are appending one element at a time, they never need to copy, but are also quite dense. Iteration is then fast. Feels like it should be useful for buffering and aggregation type jobs. I have never seen one in a library.
- creata 6y agoI wonder whether someone's invented a way to take a nice ADT like data List a = Cons a (List a) | Nil and automatically unroll it to fill at least a cache line. That sounds like it'd be a small win for performance, but I don't know.
- gsg 6y agoYes, this has been done a few times. CDR-coding was a hardware-assisted method of unrolling a Lisp list (complicated somewhat by the need to support mutation of car and cdr) that appeared on Lisp machines, and there's a Appel/Reppy/Shao paper on unrolling linked lists in the context of Standard ML. There's also some interesting work on flattened versions of arbitrary tree structures: https://engineering.purdue.edu/~milind/docs/ecoop17.pdf https://engineering.purdue.edu/~milind/docs/ecoop17.pdf
- winrid 6y agoThis was actually the correct answer to "build a linked list" interview question I did. They didn't explicitly ask for it to be unrolled, just sounded frustrated that I didn't make a fancy unrolled one. :)