`IntSet.difference`: SpecConstr reboxing defeats the `NOM -> t1` sharing at -O2
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
https://github.com/haskell/containers/blob/722218d1a67dca330b99eeed10d9dbd782ff7b5f/containers/src/Data/IntSet/Internal.hs#L700-L720
Reproducer:
```haskell
{-# LANGUAGE MagicHash #-}
module Main (main) where
import Control.Exception (evaluate)
import GHC.Exts (reallyUnsafePtrEquality#, isTrue#)
import qualified Data.IntSet as IS
ptrEq :: a -> a -> Bool
ptrEq x y = isTrue# (reallyUnsafePtrEquality# x y)
main :: IO ()
main = do
-- t1 nests inside t2's prefix range: BAL/BAR descent ending in NOM
t1 <- evaluate $ IS.fromList [256..511]
t2 <- evaluate $ IS.fromList [0, 1024, 4096, 65536]
d1 <- evaluate $ IS.difference t1 t2
putStrLn $ "nested/NOM : " ++ show (d1 `ptrEq` t1)
-- absent single key (Bin/Tip -> deleteBM path)
d2 <- evaluate $ IS.difference t1 (IS.singleton 5000)
putStrLn $ "absent tip : " ++ show (d2 `ptrEq` t1)
```
With GHC 9.14.1:
| | `-O2` | `-O2 -fno-spec-constr` |
|---|---|---|
| nested/NOM | **False** | True |
| absent tip | **False** | True |
Core:
```
Data.IntSet.Internal.difference_$sdifference1
:: GHC.Exts.Int# -> IntSet -> IntSet -> IntSet -> IntSet
Data.IntSet.Internal.difference_$sdifference1
= \ (sc :: GHC.Exts.Int#)
(sc1 :: IntSet)
(sc2 :: IntSet)
(t2 :: IntSet) ->
...
case t2 of {
Bin bx l2 r2 ->
...
-- NOM -> t1
__DEFAULT -> Data.IntSet.Internal.Bin sc sc3 sc4;
...
-- difference t@(Bin _ _ _) Nil = t
Nil -> Data.IntSet.Internal.Bin sc sc3 sc4
}
```
Analysis from Claude
The `BAL`/`BAR` branches call `difference t1 l2` where `t1` is a case binder with a statically known `Bin` constructor. SpecConstr (on by default at `-O2`) specializes `difference` on the exploded fields of `t1`, and every "return `t1` unchanged" branch of the specialization must rebox them into a fresh `Bin`. This is SpecConstr's known reboxing problem (`Note [Reboxing]` in `GHC.Core.Opt.SpecConstr`, https://gitlab.haskell.org/ghc/ghc/-/issues/27628); GHC #13331 is the same failure shape for `Map.insert` via worker/wrapper.
Likely affected in the same way: `IntSet.intersection`, and `IntMap.difference` (to be fixed together with adding `ptrEq` checks in #1241). `IntMap.withoutKeys`/`restrictKeys` and any future `ptrEq`-based sharing (#835, #1220) face the same hazard.
The impact doesn't seem _too_ bad in this case: It's just the root `Bin` re-allocated when it could be returned unchanged. Still a nasty footgun to be aware of. :/
Contributor guide
Research direction
Start with the linked IntSet.Internal.hs lines 700-720 and run the reproducer under GHC 9.14.1 with -O2 and -fno-spec-constr. Trace the BAL/BAR and NOM or absent-tip paths, then inspect the generated Core around difference_$sdifference1. Done means the unchanged result preserves pointer identity under -O2, with regression coverage for the reported cases.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 50/100