Repository navigation
[BUG] Duplicate ATag error during sharing recovery with parallel GC #587
Description
Environment
- Accelerate 1.4.0.0
- GHC 9.8.4 / base 4.19.2.0
- Linux x86_64
Reproducing
Main.hs:
module Main where
import Control.Exception (evaluate)
import Control.Monad (forM_, when)
import qualified Data.Array.Accelerate as A
import qualified Data.Array.Accelerate.Trafo.Sharing as Sharing
import GHC.Conc (setNumCapabilities)
stage :: Int -> A.Acc (A.Vector Double) -> A.Acc (A.Vector Double)
stage n input = foldl1 (A.zipWith (+)) [A.map (\x -> x + A.constant (fromIntegral (n + i))) input | i <- [1 .. 8 :: Int]]
program :: Int -> A.Acc (A.Vector Double) -> A.Acc (A.Vector Double)
program n input = foldl (\x f -> f x) input (replicate 40 (stage n A.>-> stage (n + 1)))
main :: IO ()
main = do
setNumCapabilities 8
forM_ [1 .. 1000 :: Int] $ \n -> do
_ <- evaluate (length (show (Sharing.convertAfun (program n))))
when (n `mod` 100 == 0) (print n)With Accelerate installed and available to GHC:
ghc -O1 -threaded -rtsopts -package accelerate Main.hs -o repro
./repro +RTS -A64k -RTSExpected behavior
All 1000 graph conversions complete successfully.
Actual behavior
Sharing recovery fails with an internal error:
Encountered duplicate 'ATag's
3116: Atag 1, 3100: Atag 1
CallStack (from HasCallStack):
internalError: Data.Array.Accelerate.Trafo.Sharing:2243:19
buildInitialEnvAcc: Data.Array.Accelerate.Trafo.Sharing:2623:48
scopesAfun1: Data.Array.Accelerate.Trafo.Sharing:2346:62
The failing iteration varies between runs.
Disabling parallel GC for the same executable:
./repro +RTS -A64k -qg -RTSI tested five runs in each mode using the same executable, alternating between the two modes:
| GC mode | Runs | Duplicate ATag failures | Successful runs |
|---|---|---|---|
| Parallel GC | 5 | 3 | 2 |
Parallel GC disabled (-qg) |
5 | 0 | 5 |
All five runs with -qg completed 1000 conversions each: 5000 conversions with no errors. In the parallel-GC runs, two failures occurred after the progress message 400; another occurred before the first progress message (100).
Suspected cause
Sharing recovery requires physically shared Atag nodes, as described in Sharing.hs.
GHC's parallel copying GC can duplicate immutable constructors through copy_tag_nolock.
This suggests that physical copies of the same tag receive different stable names and
are subsequently rejected as duplicate tags during sharing recovery.
Discussion
Would it be feasible to fix this by identifying bound variables independently of physical sharing,
or by handling duplicated tags during environment construction?
I’d be happy to try working on a fix with some guidance.
I’m not very familiar with de Bruijn indices or the sharing recovery implementation,
and much of the investigation above was carried out with assistance from LLM,
however, I would like to extend my knowledge in this pretty interesting subject,
so I’d appreciate a review of the diagnosis and advice on where to start.
Activity
luite commentedon Nov 3, 2026
See https://gitlab.haskell.org/ghc/ghc/-/work_items/28069
JktuJQ commentedon Nov 3, 2026
Heh, funny timing - looks like I stumbled across this just before the GHC ticket was opened :)
I reported it here because my understanding was that GHC doesn’t guarantee preservation of physical sharing, and the documented
StableNameguarantees seemed weaker than what sharing recovery relies on. So I wasn’t sure this should be considered a GHC bug, rather than an assumption Accelerate needs to account for.In the meantime, would it make sense to investigate an Accelerate-side fix, or would you advise to wait for a decision on the RTS behavior?
luite commentedon Nov 3, 2026
GHC hasn't really offered any guarantees around this (other than what's stated in the StableName docs), so I don't think it's a bug per se. But it is clearly something that quite a few packages rely on for this kind of observable sharing tasks (a quick search of hackage revealed)
Another common failure mode (in packages on hackage) is a data constructor wrapping a foreign structure allocated with
mallocand having a finalizerfree. Duplicating the datacon could lead to the finalizer being run early and use-after-free of the underlying data.Overall I think it's serious enough to consider changing the GHC behaviour or contacting the maintainers of the packages...
luite commentedon Nov 3, 2026
How much of an inconvenience would it be for accelerate to fix sharing recovery with the current GHC behaviour, where objects may be duplicated by the GC?
tomsmeding commentedon Nov 3, 2026
I read this as "finalizers may run multiple times". Are you sure? If so, that sounds to me like a rather severe undocumented downside of finalizers that is likely to break almost all uses of them: freeing of external resources through ForeignPtr is kind of the prime use-case of them -- it's in the name!
Ultimately a 100% robust, fixed sharing recovery would need to work even in the case that stable names are always distinct, i.e. provide no information. That would be rather difficult, as sharing detection is the way that self-referential terms can be detected and reported as erroneous (e.g.
let a = map (+1) a in ...). If you don't mind looping / exploding in that case (and it's probably fine since failure of stable name equality is likely probabilistic, i.e. succeeds eventually with probably 1), and furthermore don't mind that terms may have (work) duplication in them (where it's notable that Accelerate doesn't really have common subexpression elimination, because GHC normally does that), it may be fixable. However, I've never really understood the algorithm that does the Acc/Exp stratification, so I cannot say for sure.The other challenge is finding someone daring enough to do non-trivial surgery on Accelerate's sharing recovery algorithm.
JktuJQ commentedon Nov 4, 2026
I’d be interested in trying to work on this issue!
After a preliminary look at
Sharing.hs, separating bound-variable identity from observable sharing seems worth exploring.AtagandTagalready receive special treatment during sharing recovery: they becomeAvarSharing/VarSharingreferences regardless of their occurrence count.Could these references use explicit binding identities, while ordinary expressions continue to use
StableNames?This indeed wouldn’t solve consequences that were already mentioned: ordinary expressions could still incur duplicated work and larger graphs, and missed cycles could cause graph conversion to diverge.
I think these might be acceptable limitations: divergence for a cyclic definition doesn’t seem unreasonable (although it would happen during graph conversion rather than execution), missed sharing in acyclic expressions would become a case of "bad optimization" (though the overhead might be substantial).
Would that be a reasonable trade-off, assuming we can preserve correct variable binding and scoping?
If this sounds like a sensible direction, I’d appreciate any pointers on where to start or what pitfalls to watch out for.
luite commentedon Nov 4, 2026
Not everything can be duplicated, so it depends on what exactly the weak reference is keyed on. If you use a
MutVar#(IORef primitive) or other object with identity as key it's safe. They're never duplicated by the GC. I think that's whatForeignPtrdoes.But various packages use
addFinalizerdirectly on a data constructor, which potentially goes wrong. But not often enough for them to have noticed it!I think the
Weak#itself won't be duplicated, so the risk is use-after-free, not double-free (i.e. first copy of the data goes out of scope, finalizer runs because the weak sees the first as key, second copy still uses the data). But I haven't checkedivogabe commentedon Nov 6, 2026
Thanks for reporting this, @JktuJQ, and thanks @luite for your investigation & background info! The code of sharing recovery also already had a comment that the stable names do not provide all the guarantees we need:
(From
Data.Array.Accelerate.Trafo.Sharing, functionrecoverSharingAcc)It seems like it was always fine on typical Accelerate programs, but still this is a correctness problem. Hence it is really nice that we have a consistent reproducer for this issue. If I understand correctly, you generate a huge Accelerate program, and this program often fails (and consistently fails if you compile this program 1000 times, with a parallel GC).
This problem seems to be a fundamental limitation of stable names. A possible solution could be to assign our own names, instead of relying on GHC's stable names to identify equal objects. I think we could implement this by adding a 'name' (unique integer) to each
SmartAccobject:To construct these unique integers, we need to resort to some unsafe tricks, by incrementing an IORef. This breaks referential transparency, but we can keep this internal: Accelerate's semantics are still referential transparent, but performance will be different depending on whether something is shared or not (but that is in general the case, when sharing large computations).
This could potentially be implemented internally via a smart constructor for SmartAcc:
{-# NOINLINE freshId #-} freshId :: IORef Int freshId = unsafePerformIO $ newIORef 0 smartAcc :: PreSmartAcc SmartAcc SmartExp a -> SmartAcc a smartAcc acc = unsafePerformIO $ do i <- atomicModifyIORef (\x -> (x + 1, x)) freshId return $ SmartAcc acc iAll code I showed so far needs to be changed in
Data.Array.Accelerate.Smart. Afterwards, sharing recovery inData.Array.Accelerate.Trafo.Sharingneeds to be updated to use our own indices instead of the stable names.Based on your discussion on finalizers, an alternative solution might be to store an object in SmartAcc that cannot be duplicated by the garbage collector, for instance:
In this case, the last field of
SmartAccis never used for its value. The smart constructor forSmartAccstill needs to perform IO from a pure function, but we don't need a global counter. Sharing recovery needs to be updated to take the stable name of the IORef instead of the SmartAcc or PreSmartAcc object, since the latter can still be duplicated. My first thought is however, that if we are going to work around the limitations of stable names, we can probably best not rely on them any more and go with our own names via the unique integers.Let me know what you think of these options. @JktuJQ if you want to work on a fix for this option, that would be greatly appreciated! I tried to sketch the general direction in this post, but we can of course discuss this further to get you started :)
JktuJQ commentedon Nov 6, 2026
For the first option,
Data.Uniqueseems to provide exactly what you’re suggesting. For the second option,IORefalready has anEqinstance that compares reference identity, so equality checks wouldn’t requireStableName, though efficient table lookup would still need a suitable key.I’m leaning towards
Unique: it expresses the intent clearly and providesEq,Ord, andhashUnique(if needed) for efficient lookup.I’ll try to start working on this in the next 3-4 days and put together a PR once I have an implementation ready for review.
JktuJQ commentedon Nov 6, 2026
Ah, and we’ll also need to take care that optimizer transformations don’t change how often
newUniqueruns insideunsafePerformIO(the same goes forIORef), but this is a known pattern, so existing implementations should provide useful guidance.ivogabe commentedon Nov 6, 2026
Yes good point, Unique is even better than Int here, so let's first try that direction! It would be great if you could create a PR for this; let me know if you need additional guidance.
Also note that everything we discussed for Acc also applied to Exp (but you may have guessed that already).
JktuJQ commentedon Nov 9, 2026
I've opened PR #590 with a proposed fix using stored node identities instead of
StableNameduring sharing recovery.