2 ms·
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
by creata 6y ago
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.
- 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