2

Haskell がコンパイル時にデータ構造をどの程度深く評価するかを知りたいです。

次のリストを検討してください。

simpleTableMultsList :: [Int]
simpleTableMultsList = [n*m | n <- [1 ..9],m <- [1 ..9]]

このリストは、1 から 9 までの掛け算の表を示しています。ここで、2 つの 1 桁の数字の積を数字のペア (1 桁目、2 桁目) として表すように変更したいとします。それから私達は考えるかもしれません

simpleTableMultsList :: [(Int,Int)]
simpleTableMultsList = [(k `div` 10, k `rem` 10) | n <- [1 ..9],m <- [1 ..9],let k = n*m]

これで、テーブル ルックアップとして 1 桁の数値に乗算を実装できます。わーい！！ただし、これよりも効率的になりたいと考えています。したがって、この構造をボックス化されていない配列にしたいと考えています。Haskell は、これを行うための非常に優れた方法を提供します。

import qualified Data.Array.Unboxed as A

次に、次のことができます。

simpleTableMults :: A.Array (Int,Int) (Int,Int)
simpleTableMults = A.listArray ((1,1),(9,9)) simpleTableMultsList

2 つの 1 桁の数値 n と m の定数時間乗算が必要な場合は、次のようにします。

simpleTableMults ! (n,m)

これは素晴らしい！ここで、これまで取り組んできたこのモジュールをコンパイルするとします。simpleTableMults は完全に評価されるので、計算を実行すると simpleTableMults ! (n,m)、プログラムは文字通りメモリ内でルックアップを行います...または最初にメモリ内にデータ構造を構築する必要がありますか? ボックス化されていない配列であるため、配列のすべての要素が完全に評価されるように、配列は一度に作成する必要があり、その要素は完全に厳密であると理解しています。

本当に私の質問は次のとおりです。この評価はいつ行われますか?また、コンパイル時に強制的に行うことはできますか?

- - - - 編集 - - - - - - - -

さらに掘り下げてみました！コアに関する情報をまとめて調べてみました。GHC はコンパイル時にコードに対して多くの削減を実行しているようです。コアについてもっと知りたいと思います。でコンパイルすると

ghc -O2 -ddump-simpl-stats Main.hs

98 のベータ削減が実行され、unpack-list 操作が実行され、多くのものが展開され、一連のインラインが実行されていることがわかります (約 150)。ベータ削減がどこで発生するかについても説明します... IxArray という言葉が登場するので、何らかの単純化が行われているのかどうか、さらに興味があります。私の観点から興味深いのは、追加することです

simpleTableMults = D.deepseq t t
where t = A.listArray ((1,1),(9,9)) simpleTableMultsList

コンパイル時のベータ削減、インライン化、および単純化の数が大幅に増加します。コンパイルされたものを何らかのデバッガーにロードして、データ構造を「表示」できれば、本当に素晴らしいことです! 現状では、私は以前よりも誤解しています。

------ 編集 2 -------------

どのようなベータ削減が実行されているかはまだわかりません。ただし、sassa-nf の応答応答に基づいて、いくつかの興味深いことがわかりました。次の実験では、ghc-heap-view パッケージを使用しました。Sassa-NFの回答に従って、ソースでの配列の表現方法を変更しました。プログラムをGHCiにロードし、すぐに呼び出しました

:printHeap simpleTableMults

そして、予想どおり、インデックスが大きすぎるという例外が発生しました。しかし、提案されたアンパックされたデータ型の下で、toArray と _thunks の束、およびいくつかの _funs を含む let 式を取得しました。これらが何を意味するのかはまだよくわかりません...もう1つの興味深いことは、ソースコードでseqまたはその他の厳密さを強制することにより、let内にすべての_thunksが含まれることになりました。それが役立つ場合は、正確な排出量をアップロードできます。

また、単一のインデックス付けを実行すると、配列はすべての場合で完全に評価されます。

また、最適化で ghci を呼び出す方法がないため、GHC -O2 でコンパイルした場合と同じ結果が得られない可能性があります。

4

1 に答える 1

2

誇張しましょう：

import qualified Data.Array.Unboxed as A

simpleTableMults :: A.Array (Int,Int) (Int,Int)
simpleTableMults = A.listArray ((1,1),(10000,2000))
    [(k `div` 10, k `rem` 10) | n <- [1 ..10000],m <- [1 ..2000],let k = n*m]

main = print $ simpleTableMults A.! (10000,1000)

それで

ghc -O2 -prof b.hs
b +RTS -hy
......Out of memory
hp2hs b.exe.hp

どうしたの？！ヒープ消費グラフが 1GB を超えてから停止したことがわかります。

ペアは精力的に計算されますが、ペアの射影は遅延しているため、大量のサンクを計算することk ``div`` 10になり、 とk ``rem`` 10.

import qualified Data.Array.Unboxed as A

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int deriving (Show)
simpleTableMults :: A.Array (Int,Int) P
simpleTableMults = A.listArray ((1,1),(10000,2000))
          [P (k `div` 10) (k `rem` 10) | 
             n <- [1 ..10000],m <- [1 ..2000],let k = n*m]

main = print $ simpleTableMults A.! (10000,1000)

熱心にペアを計算したので、これは問題ありません。

于 2013-09-13T08:53:16.973 に答える