Simon Jakobi pushed to branch wip/sjakobi/udfm-placement at Glasgow Haskell Compiler / GHC

Commits:

• 9da8424e
  by Simon Jakobi at 2026-07-02T17:59:23+02:00

  UniqDFM: make head-element cost explicit in Note [Cost of deterministic iteration]
  
  Spell out that producing even the first element allocates an
  O(n)-sized array (or O(n log n) cons cells on the fallback path),
  and that laziness does not make the iteration incremental.
  
  Assisted-by: Claude Fable 5
  

1 changed file:

• compiler/GHC/Types/Unique/DFM.hs

Changes:

 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 -- Deterministic iteration orders elements by insertion tag, and any such

 -- ordering must inspect every element's tag before it can emit the first

--- element. So even the head of the result costs a full O(n) traversal of the

--- map -- the iteration is not incremental, and laziness in the result list (see

--- Note [Placement sort in eltsUDFM]) saves allocation for undemanded

--- elements, not that up-front traversal. #27459 shows this cost biting in

--- consumers that demanded only the head.

+-- element. So even the head of the result costs a full traversal of the map

+-- plus the allocation of an O(n)-sized array -- or, on the fallback path,

+-- O(n log n) cons cells (see Note [Placement sort in eltsUDFM]). Laziness in

+-- the result list only avoids allocating for elements that are never

+-- demanded; it does not make the iteration incremental. #27459 shows this

+-- cost biting in consumers that demanded only the head.

 --

 -- So: to test for emptiness, use isNullUDFM rather than null on eltsUDFM;

 -- for order-oblivious queries, prefer short-circuiting anyUDFM/allUDFM; and