7

Brainfuck コードを解析して実行する小さなスクリプトを作成しようとしています。最適化の GHC オプションを理解するために、コードを最適化して、少し高速化し、そこで何が起こっているのかを理解しようとしています。

パーツの 1 つは BF コードの内部表現です。これには特別なデータ型を使用します。ソースコードは次のとおりです。変換を行う 2 つの関数が含まれています。

data BFinstruction
  = AdjustValue Int
  | MovePointer Int
  | GetChar
  | PutChar
  | Loop BFcode
  deriving (Eq)

type BFcode = [BFinstruction]

unsafeCompileBrainfuck :: String -> BFcode
unsafeCompileBrainfuck = fst . parse [] where
  -- arguments: input string, built code; output: output code, rest of input
  parse :: BFcode -> String -> (BFcode,String)
  parse c ('+':s) = parse (AdjustValue   1 :c) s
  parse c ('-':s) = parse (AdjustValue (-1):c) s
  parse c ('>':s) = parse (MovePointer   1 :c) s
  parse c ('<':s) = parse (MovePointer (-1):c) s
  parse c ('.':s) = parse (PutChar         :c) s
  parse c (',':s) = parse (GetChar         :c) s
  parse c (']':s) = (reverse c, s)
  parse c ('[':s) = parse (Loop l          :c) s' where (l,s') = parse [] s
  parse c []      = (reverse c ,"")
  parse c ( _ :s) = parse                   c  s

simplifyBrainfuck :: BFcode -> BFcode
simplifyBrainfuck ((AdjustValue x):(AdjustValue y):zs) = if x + y /= 0
  then simplifyBrainfuck (AdjustValue (x + y):zs)
  else simplifyBrainfuck zs
simplifyBrainfuck ((MovePointer x):(MovePointer y):zs) = if x + y /= 0
  then simplifyBrainfuck (MovePointer (x + y):zs)
  else simplifyBrainfuck zs
simplifyBrainfuck (x                              :zs) = x: simplifyBrainfuck zs
simplifyBrainfuck []                                   = []

アイデアは、コードが何らかの入力 (文字列) から読み取られ、上記のコードによって事前に解析および単純化されてから、他の関数によって実行されるというものです。(入力が有効であると仮定します)。

この例を最適化するために、次のような domething を実行して、コンストラクターMovePointerとコンストラクターの Int パラメーターをアンボックスしようとしました。AdjustValue

data BFinstruction -- BangPatterns
  = AdjustValue {-# UNPACK #-} !Int
  | MovePointer {-# UNPACK #-} !Int
  | GetChar
  | PutChar
  | Loop BFcode
  deriving (Eq)

これにより、ボックス化された型が、GHcの実装の詳細であるボックス化Intされていない生の型に変わります。Int#私が読んだように、このオプションはいくつかの場合にのみ有効です。そのため、この種の最適化を実行する場合、どの点に注意する必要があるかを尋ねたいと思います。私の目標は、Haskell の利点を利用して BF コードを実行できるようにすることです。

4

2 に答える 2

3

これは本当に必要ですか？ボックス化された値の結果であると思われるこのコードで、パフォーマンスの問題が発生していますか? そうでない場合は、気にしないでください。

これが事実だと思うなら、GHC マニュアルのこのページは必要な制限を便利なリスト形式で提供しているようです。

主なポイントは、多態的な関数または名前と、コンパイラによって拒否されないボックス化されていない型との間のあらゆる種類の相互作用が、依然として厄介なスペースリークにつながる可能性があることです。また、試してみないと、たとえばオーバーフローの場合に例外がスローされないのではないかと思うので、おそらくこの種のことを自分で検出する必要があります。これが実際に当てはまるかどうかは、簡単なテストで確認できます。

于 2010-09-04T15:34:43.767 に答える
2

これは、私には時期尚早の最適化のように見えます。UNPACK は、非常に多数BFInstructionの が周囲にある場合に最も役立ちます。価値のあるものにするのに十分なbrainf ** kコードがあるとは思えません。私はGianに同意します。テストするのに十分簡単であるべきなので、最初にそれを行ってください。

いずれにせよ、UNPACK された値で注意すべきことは、コンパイラがそれらを再ボックス化する必要がないということです。数値操作は問題ありませんが、それ以外は、使用している関数を注意深く調べて、非厳密な引数としてアンパックされた値を使用するかどうかを確認する必要があります。確認する唯一の方法は、コアまたはインターフェイス ファイルを調べて、厳密なパラメーターとそうでないパラメーターを確認することです。いつものように、少なくとも "-O" を付けてコンパイルしてください。

于 2010-09-04T16:44:43.913 に答える