
Hécate via ghc-devs
Hi everyone,
I was asked at work today why I went for Vector instead plain old List in order to store an API result that is quite small.
While writing my reasons (pointer indirection, conversion to Aeson's internal representation of a JSON array using Vector), I remember that I heard that in some cases, GHC would be able to lay down in memory the elements of a linked list next to each other. I don't think this gets rid of the pointer-chasing, but I'm interested to know more about the circumstances in which linked lists are optimised.
As Andreas suggests, you are likely thinking of the the fact that copying GC tends to re-layout the heap such that topologically proximate closures also tend to be nearby in memory. This result in a considerable improvement in cache locality over traditionally non-moving allocators although, as you point out, the pointer chasing cost and representation size of a cons cell with small payload is still considerable compared to a dense representation. I don't think the wiki has any discussion of this but, e.g., Steve Blackburn's Immix paper [1] does have some representative measurements of the effect of non-moving (mark-sweep) and compacting (mark-compact and Immix) allocation schemes on mutator performance. Cheers, - Ben [1] https://www.steveblackburn.org/pubs/papers/immix-pldi-2008.pdf