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: ===================================== compiler/GHC/Types/Unique/DFM.hs ===================================== @@ -351,11 +351,12 @@ nonDetStrictFoldUDFM k z (UDFM m _i) = foldl' k' z m -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -- 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 View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/9da8424e1da6991f9493f5e91f77b46f... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/9da8424e1da6991f9493f5e91f77b46f... You're receiving this email because of your account on gitlab.haskell.org.