Replace `SizedSeq` with flatten memory representation `FlatBag`

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)

assigned to @fendor

added 1 commit

• 09669bf7 - Replace `SizedSeq` with `ArrayBag` for flattened structure

Compare with previous version

added 1 commit

• fc741d3a - Replace `SizedSeq` with `FlatBag` for flattened structure

Compare with previous version

How big is the perf loss from just using an Array?

I think using an empty array would overal take up more memory, as the empty case is not reliably shared over all instances of UnlinkedBCO. Further, on the agda code base, the size distribution of SizedSeq (360_000 * 2 instances of SizedSeq) looks as follows:

      #  length
 283147  0 
 198237  1 
 126478  2 
  69233  3 
  26596  4 
   5587  5 
   3903  6 
   2943  7 

Thus, we have a special-case for size 0, 1 and 2. Without the special case for size 2, there is only a very little difference in space behaviour.

Run-time performance-wise, I expect no tangible difference.

added 1 commit

• 74822663 - Replace `SizedSeq` with `FlatBag` for flattened structure

Compare with previous version

changed title from Replace SizedSeq with {-Array-}Bag for flattened structure to Replace SizedSeq with {+Flat+}Bag for flattened structure

changed title from Replace SizedSeq with {-FlatBag for flattened structure-} to Replace SizedSeq with {+flatten memory representation FlatBag+}

mentioned in issue #24539 (closed)

mentioned in merge request !12140 (closed)

added 79 commits

• 74822663...bd8209eb - 77 commits from branch ghc:master
• 45ab59df - Replace `SizedSeq` with `FlatBag` for flattened structure
• 308b6be9 - Compact FlatBag array representation

Compare with previous version

resolved all threads

changed the description

added 1 commit

• ac6a01bf - Compact FlatBag array representation

Compare with previous version

added Blocked on Review label

approved this merge request

assigned to @marge-bot and unassigned @fendor

I will attempt to batch this MR (!12365 (closed))...