Hécate via ghc-devs <ghc-devs@haskell.org> writes: > 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
signature.asc
Description: PGP signature
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
