[BUG] Duplicate `ATag` error during sharing recovery with parallel GC

オープン
  • 何か問題がありますか？
#587 コメント 7 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
35/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
活発
技術スタック
haskell
領域
compilers

調査の方向性

The bug is in Data.Array.Accelerate.Trafo.Sharing (Sharing.hs); start at internalError (line 2243) and buildInitialEnvAcc (line 2623). Read sharing recovery near line 3084 and reproduce with given Main.hs via ghc -O1 -threaded -rtsopts -package accelerate then ./repro +RTS -A64k -RTS. Done when 1000 conversions succeed without duplicate ATag errors under parallel GC.

索引モデルが issue の本文から書いたものです。

説明

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 -RTS

Expected 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 -RTS

I 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.

主要言語
Haskell
スター
1k
フォーク
138
30日以内にマージされた PR はありません

環境構築

  • Dockerfile・Docker Compose ファイルなし
  • プルリクエストのテンプレートあり
  • コントリビューションガイドなし

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

AccelerateHS/accelerate のほかの issue

AccelerateHS/accelerate の issue をすべて見る

似ている issue

Haskell の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。