Under which circumstances are the elements of a linked list laid next to each-other in memory?

[Ben Gamari]

Hécate via ghc-devs <ghc-devs at 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20241113/1d0419a6/attachment.sig>