Hacker News Reader

Comment by twic | Hacker News Reader

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

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.

View on HN

I 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.

Yes, 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

This 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. :)

Reply on news.ycombinator.com