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

[Viktor Dukhovni]

On Wed, Nov 13, 2024 at 01:39:46PM +0100, Hécate via ghc-devs wrote:

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

An intesting question to which I have only a very partial answer.

If the linked list a `String`, and it is actually stored in memory as a
packed UTF-8 array of bytes (modified for C-friendly NUL-termination by
representing \x00 as the denormalised \xc000), then its "list" form is
really just a lazy computation over the byte array, which if not used
repeatedly, but rather consumed just once, would remain a
lazily-evaluation iterator over the stored byte array.

Similar considerations might apply in any situation where the list
elements are "Storable", (perhaps even unboxed) and the list is really
an iterator over the Storable or Unboxed array.

In simple enough situations, where you're not using the fancier features
of the `Vector` API, you might also find that the IArray, MArray,
UArray, STUArray set of types meets your needs.

I'm eager to hear about new contexts in which one might expect a list to
be automatically represented by some densely packed pre-computed array,
other than by explicit prior construction of such an array, for which
the list is an iterator.  At the very list the list elements would have
to be known to all be strictly evaluated, and precomputation to store
the entire list would have to be justified.

-- 
    Viktor.