Skip to content

Replace `SizedSeq` with flatten memory representation `FlatBag`

Hannes Siebenhandl requested to merge fendor/ghc:wip/fendor/array-bag into master

LinkedLists are notoriously memory ineffiecient when all we do is traversing a structure. As 'UnlinkedBCO' has been identified as a data structure that impacts the overall memory usage of GHCi sessions, we avoid linked lists and prefer flattened structure for storing.

We introduce a new memory efficient representation of sequential elements, called FlatBag which has special support for the cases:

  • Empty
  • Singleton
  • Tuple Elements

This improves sharing in the 'Empty' case and avoids the overhead of 'SmallArray' until its constant overhead is justified.

FlatBag is supposed to be used when an object is long-lived, rarely written to, and mostly traversed.

Addresses parts of #24539 (closed)

Edited by Hannes Siebenhandl

Merge request reports