Visitar URL original
Avoid thunks in IntSet minView and maxView by oheliav · Pull Request #1277 · haskell/containers · GitHub
Skip to content

Avoid thunks in IntSet minView and maxView - #1277

Open
oheliav wants to merge 2 commits into
haskell:masterfrom
oheliav:strict-intset-minview
Open

Avoid thunks in IntSet minView and maxView#1277
oheliav wants to merge 2 commits into
haskell:masterfrom
oheliav:strict-intset-minview

Conversation

@oheliav

@oheliav oheliav commented Nov 8, 2026 •
edited
Loading

Copy link
Copy Markdown

Fixes #1251.

minView and maxView now follow IntMap's minViewWithKey/minViewWithKeySure design, as suggested in the issue: they check for the empty set first and return Just right away, with the tree walk in NOINLINE minViewSure/maxViewSure helpers. The helpers return a StrictPair instead of a lazy tuple (IntMap uses its View type, but IntSet has no values), so the rebuilt set is constructed right away instead of being left as a thunk.

With minView/maxView marked INLINE, callers like deleteMin avoid the Maybe and the pair entirely. Core for deleteMin (GHC 9.10.3):

deleteMin = \ x ->
  case x of wild {
    __DEFAULT -> case $wminViewSure wild of { (# ww, ww1 #) -> ww1 };
    Nil -> Nil
  }

Benchmarks (intset-benchmarks, GHC 9.10.3, aarch64-osx):

benchmark before after change
deleteMin 39.1 ns 17.9 ns -54%
deleteMax 11.8 ns 5.93 ns -49%
delete 42.5 μs 39.8 μs same (doesn't use minView, for comparison)

intset-properties passes.

@oheliav
Avoid thunks in IntSet minView and maxView
f2bdca6 
Use a strict pair in the go helpers and force the rebuilt set before wrapping it in Just. Fixes haskell#1251.
@treeowl

treeowl commented Nov 8, 2026

Copy link
Copy Markdown
Contributor

How does this compare to IntMap? Do we want to produce the Just before descending the tree?

@oheliav
Follow IntMap's design for IntSet minView and maxView
b7a9b77 
Check for the empty set first and return Just right away, with the tree walk in NOINLINE minViewSure/maxViewSure helpers, like IntMap's minViewWithKey/minViewWithKeySure. minView and maxView are INLINE, so callers like deleteMin can avoid the Maybe and the pair.
@oheliav

oheliav commented Nov 11, 2026

Copy link
Copy Markdown
Author

Good point, thanks. I've updated the PR to follow IntMap's design, which is also what the issue suggested: minView/maxView now check for Nil and return Just before descending the tree, with the tree walk in NOINLINE minViewSure/maxViewSure helpers, like minViewWithKey/minViewWithKeySure.

With minView/maxView marked INLINE, deleteMin no longer allocates the Maybe or the pair (Core in the description). Compared to my previous commit, deleteMin went from 19.5 ns to 17.9 ns and deleteMax from 6.84 ns to 5.93 ns. That's close to the noise, so the main gain over master is still from removing the thunks.

@meooow25

meooow25 commented Nov 11, 2026

Copy link
Copy Markdown
Contributor

Is this patch LLM-generated?

@oheliav

oheliav commented Nov 11, 2026

Copy link
Copy Markdown
Author

Well, no, I'm not a bot and it's a PR I've implemented and designed. However, of course I use AI to understand concepts and review my work.
If that's not welcome, kindly let me know and I will stop contributing to this project.

meooow25
meooow25 requested changes Nov 11, 2026
View reviewed changes
Comment thread containers/src/Data/IntSet/Internal.hs
_ -> Just $ case maxViewSure t of result :*: t' -> (result, t')
{-# INLINE maxView #-}

maxViewSure :: IntSet -> StrictPair Key IntSet

@meooow25 meooow25 Nov 11, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good overall, but instead of StrictPair we should have View type like for IntMap:

containers/containers/src/Data/IntMap/Internal.hs

Line 2393 in c9c0c88

data View a = View {-# UNPACK #-} !Key a !(IntMap a)

This makes a difference for GHC <9.4, documented here:

containers/containers/src/Data/IntSet/Internal.hs

Lines 1811 to 1815 in c9c0c88

-- This type allows GHC to return unboxed ints from leftmostTipSure, as
-- $wleftmostTipSure :: IntSet -> (# Int#, Word# #)
-- On a modern enough GHC (>=9.4) this is unnecessary, we could use StrictPair
-- instead and get the same Core.
data Tip' = Tip' {-# UNPACK #-} !Int {-# UNPACK #-} !BitMap

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@meooow25 meooow25 meooow25 requested changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

IntSet's minView and maxView creates unwanted thunks

3 participants

@oheliav @treeowl @meooow25