3

384ビットベクトルを保持でき、効率的なXORと「ビットカウント」（1に設定されたビット数）操作をサポートする効率的な（空間と時間の両方で）データ型を探しています。

以下に、私のデモプログラムを見つけてください。必要な操作はすべてSOQuestionOps型クラスにあり、 と に実装しましNaturalたData.Vector.Unboxed.Bit。特に後者は、zipWords「ビットカウント」やビットごとではなく単語ごとの XOR などの操作を実行できる操作があるため、完璧に思えます。また、パックされたビット (1 バイトあたり 8 ビット) を格納すると主張しています。

{-# LANGUAGE FlexibleInstances #-}
import Data.Bits
import Data.List (foldl')
import Numeric.Natural
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed.Bit as BV

class SOQuestionOps a where
    soqoXOR :: a -> a -> a
    soqoBitCount :: a -> Int
    soqoFromList :: [Bool] -> a

alternating :: Int -> [Bool]
alternating n =
    let c = n `mod` 2 == 0
     in if n == 0
           then []
           else c : alternating (n-1)

instance SOQuestionOps Natural where
    soqoXOR = xor
    soqoBitCount = popCount
    soqoFromList v =
        let oneIdxs = map snd $ filter fst (zip v [0..])
         in foldl' (\acc n -> acc `setBit` n) 0 oneIdxs

instance SOQuestionOps (BV.Vector BV.Bit) where
    soqoXOR = BV.zipWords xor
    soqoBitCount = BV.countBits
    soqoFromList v = BV.fromList (map BV.fromBool v)

main =
    let initialVec :: BV.Vector BV.Bit
        initialVec = soqoFromList $ alternating 384
        lotsOfVecs = V.replicate 10000000 (soqoFromList $ take 384 $ repeat True)
        xorFolded = V.foldl' soqoXOR initialVec lotsOfVecs
        sumBitCounts = V.foldl' (\n v -> n + soqoBitCount v) 0 lotsOfVecs
     in putStrLn $ "folded bit count: " ++ show (soqoBitCount xorFolded) ++ ", sum: " ++ show sumBitCounts

それでは、最良のケースの数値を計算してみましょう。lotsOfVecs同じ vector の 10,000,000 倍にすぎないため、多くを割り当てる必要はありませんinitialVec。foldl は明らかに、フォールド操作ごとにこれらのベクトルの 1 つを作成するため、10,000,000 ビット ベクトルを作成する必要があります。ビット カウントは、10,000,000Int秒以外のものを作成する必要があります。したがって、最良の場合、私のプログラムはごくわずかな (そして一定の) メモリを使用する必要があり、割り当ての合計はおよそ 10,000,000 * sizeof(bit vector) + 10,000,000 * sizeof(int) = 520,000,000 バイトになるはずです。

では、次のプログラムを実行してみましょうNatural:

作っinitialVec :: Naturalてコンパイルしよう

ghc --make -rtsopts -O3 MemStuff.hs

結果 (これは GHC 7.10.1 の場合):

$ ./MemStuff +RTS -sstderr
folded bit count: 192, sum: 3840000000
1,280,306,112 bytes allocated in the heap
201,720 bytes copied during GC
80,106,856 bytes maximum residency (2 sample(s))
662,168 bytes maximum slop
78 MB total memory in use (0 MB lost due to fragmentation)

Tot time (elapsed)  Avg pause  Max pause
Gen  0      2321 colls,     0 par    0.056s   0.059s     0.0000s    0.0530s
Gen  1         2 colls,     0 par    0.065s   0.069s     0.0346s    0.0674s

INIT    time    0.000s  (  0.000s elapsed)
MUT     time    0.579s  (  0.608s elapsed)
GC      time    0.122s  (  0.128s elapsed)
EXIT    time    0.000s  (  0.002s elapsed)
Total   time    0.702s  (  0.738s elapsed)

%GC     time      17.3%  (17.3% elapsed)

Alloc rate    2,209,576,763 bytes per MUT second

Productivity  82.7% of total user, 78.7% of total elapsed


real    0m0.754s
user    0m0.704s
sys 0m0.037s

これは1,280,306,112 bytes allocated in the heap、予想される数字の球場 (2x) にあります。GHC 7.8 では、これは 353,480,272,096 バイトを割り当て、GHC 7.8popCountではあまり効率的ではないため、絶対年齢に対して実行されNaturalます。

編集：コードを少し変更しました。元のバージョンでは、他のすべてのベクトルが0フォールドに含まれていました。Naturalこれにより、バージョンの割り当て数値が大幅に向上しました。ベクトルが異なる表現 (多くのビットが設定された状態) に切り替わるように変更したところ2x、予想される割り当てが表示されるようになりました。Naturalこれは(and )のもう 1 つの欠点ですInteger。割り当て率は値によって異なります。

しかし、もっとうまくできるかもしれません。密集した を試してみましょうData.Vector.Unboxed.Bit:

それinitialVec :: BV.Vector BV.Bitは、同じオプションで再コンパイルして再実行することです。

$ time ./MemStuff +RTS -sstderr
folded bit count: 192, sum: 1920000000
75,120,306,536 bytes allocated in the heap
54,914,640 bytes copied during GC
80,107,368 bytes maximum residency (2 sample(s))
664,128 bytes maximum slop
78 MB total memory in use (0 MB lost due to fragmentation)

Tot time (elapsed)  Avg pause  Max pause
Gen  0     145985 colls,     0 par    0.543s   0.627s     0.0000s    0.0577s
Gen  1         2 colls,     0 par    0.065s   0.070s     0.0351s    0.0686s

INIT    time    0.000s  (  0.000s elapsed)
MUT     time   27.679s  ( 28.228s elapsed)
GC      time    0.608s  (  0.698s elapsed)
EXIT    time    0.000s  (  0.002s elapsed)
Total   time   28.288s  ( 28.928s elapsed)

%GC     time       2.1%  (2.4% elapsed)

Alloc rate    2,714,015,097 bytes per MUT second

Productivity  97.8% of total user, 95.7% of total elapsed


real    0m28.944s
user    0m28.290s
sys 0m0.456s

それは非常に遅く、割り当ての約100倍です:(。

では、両方の実行を再コンパイルしてプロファイリングしましょう ( ghc --make -rtsopts -O3 -prof -auto-all -caf-all -fforce-recomp MemStuff.hs):

Naturalバージョン:

COST CENTRE         MODULE  %time %alloc
main.xorFolded      Main     51.7   76.0
main.sumBitCounts.\ Main     25.4   16.0
main.sumBitCounts   Main     12.1    0.0
main.lotsOfVecs     Main     10.4    8.0

Data.Vector.Unboxed.Bitバージョン:

COST CENTRE         MODULE  %time %alloc
soqoXOR             Main     96.7   99.3
main.sumBitCounts.\ Main      1.9    0.2

Natural固定サイズのビットベクトルに最適なオプションは本当にありますか? そしてGHC 6.8はどうですか？SOQuestionOpsそして、私の型クラスを実装できるより良いものはありますか?

4

1 に答える 1

1

パッケージData.LargeWord内のモジュールを見てください。Crypto

http://hackage.haskell.org/package/Crypto-4.2.5.1/docs/Data-LargeWord.html

Bits96 ビットから 256 ビットなど、さまざまなサイズのラージ ワードのインスタンスを提供します。

于 2015-07-23T12:20:03.510 に答える