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.

Hécate via ghc-devs 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