ハッシュテーブルのパフォーマンスの問題に興味があります

StackOverflow https://stackoverflow.com/questions/3058529

  •  27-09-2019
  •  | 
  •  

質問

Haskellのハッシュテーブルにはパフォーマンスの問題があったことを読みました（ Haskell-Cafe 2006年と フライングカエルコンサルタントのブログ 2009年）、そして私はHaskellが好きなので、それは私を心配させました。

それは1年前でしたが、現在のステータスは何ですか（2010年6月）？ 「ハッシュテーブルの問題」はGHCで修正されましたか？

役に立ちましたか？

解決

問題は、ガベージコレクターが、処理する準備ができている可能性のあるデータへのポインターを探しているポインター（「ボックスアレイ」）の可変アレイ（「ボックスアレイ」）を横断するために必要であることでした。箱入りの可変アレイは、ハッシュテーブルを実装するための主なメカニズムであるため、特定の構造がGC横断問題を示しました。これは多くの言語に共通しています。症状は過度のゴミ収集です（GCで費やした時間の最大95％）。

修正はそうでした GCに「カードマーキング」を実装します 2009年後半に発生したポインターの可変アレイの場合。現在、Haskellでポインターの可変配列を使用する場合、過度のGCが表示されません。単純なベンチマークでは、大きなハッシュのハッシュテーブル挿入が10倍改善されました。

GCウォーキングの問題は影響しないことに注意してください 純粋に機能的な構造, 、ボックス化されていないアレイもありません（ほとんどのデータと同様です 平行配列, 、 また ベクター- ハスケルのアレイのようなもの。また、Cヒープに保存されているハッシュテーブルにも影響しません（ ジュディ）。意味のあるハッシュテーブルを使用していない日々のhaskellersには影響しなかったことを意味します。

Haskellでハッシュテーブルを使用している場合、今すぐ問題を遵守しないでください。ここでは、たとえば、1,000万INTをハッシュに挿入する単純なハッシュテーブルプログラムです。元の引用ではコードやベンチマークが表示されないため、ベンチマークを行います。

import Control.Monad
import qualified Data.HashTable as H
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  m <- H.new (==) H.hashInt
  forM_ [1..size] $ \n -> H.insert m n n
  v <- H.lookup m 100
  print v

GHC 6.10.2を使用して、修正の前に、10mのintsを挿入します。

$ time ./A 10000000 +RTS -s
...
47s.

GHC 6.13で、修正後：

./A 10000000 +RTS -s 
...
8s

デフォルトのヒープ領域の増加：

./A +RTS -s -A2G
...
2.3s

ハッシュテーブルを避け、INTMAPを使用してください。

import Control.Monad
import Data.List
import qualified Data.IntMap as I
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  let k = foldl' (\m n -> I.insert n n m) I.empty [1..size]
  print $ I.lookup 100 k

そして、私たちは得ます：

$ time ./A 10000000 +RTS -s        
./A 10000000 +RTS -s
6s

または、あるいは、Judyアレイを使用しています（これは、外部機能インターフェイスを介してCコードを呼び出すHaskellラッパーです）：

import Control.Monad
import Data.List
import System.Environment
import qualified Data.Judy as J

main = do
  [size] <- fmap (fmap read) getArgs
  j <- J.new :: IO (J.JudyL Int)
  forM_ [1..size] $ \n -> J.insert (fromIntegral n) n j
  print =<< J.lookup 100 j

これを実行して、

$ time ./A 10000000 +RTS -s
...
2.1s

だから、あなたが見ることができるように、ハッシュテーブルのGCの問題は 修繕, 、そこにあります 常に他のライブラリとデータ構造でした これは完全に適していました。要約すると、これは問題ではありません。

注：2013年の時点で、おそらく使用する必要があります ハッシュテーブル サポートするパッケージ 可変ハッシュテーブルの範囲 ネイティブに。

他のヒント

このような質問は、実験によってのみ解決できます。しかし、実験をする時間やお金がない場合は、他の人に彼らがどう思うか尋ねなければなりません。そうすると、ソースを検討し、与えられた情報が何らかの方法でレビューされたか審査されたかどうかを検討することをお勧めします。

Jon Harropは、Haskellについての興味深い主張をいくつか進めました。 Haskell、LISP、およびその他の機能的言語におけるHarropの専門知識の証拠をGoogleグループや他の場所で検索することをお勧めします。また、ハスケルのパトリシアの木のクリス・オカサキとアンディ・ギルの作品を読むこともできます。彼らの専門知識がどのように見なされているかを見てください。また、誰の請求が第三者によってチェックされているかを見つけることもできます。次に、さまざまな機能言語のパフォーマンスについてさまざまな人々の主張をどのように真剣に受け止めるかを自分の心に留めることができます。

ああ、トロールに餌を与えないでください。

PSあなた自身の実験を行うことは非常に合理的ですが、おそらく信頼できるので、おそらく必要ではありません ドン・スチュワートはいくつかの素晴らしいマイクロベンチマークを提示します 彼の素晴らしい答えで。これがドンの答えへの補遺です：

補遺：AMD Phenom 9850 Black EditionでDon Stewartのコードを使用して、32ビットモードで4GB RAMを使用して2.5GHzでクロックし、 ghc -O,

  • デフォルトのヒープを使用して、 IntMap ハッシュテーブルよりも40％高速です。
  • 2Gヒープを使用すると、ハッシュテーブルは IntMap.
  • デフォルトのヒープを持つ1,000万の要素に行くと、 IntMap は 4倍速い ハッシュテーブル（CPU時間）または 2倍速い 壁2時間までに。

私はこの結果に少し驚いていますが、機能的なデータ構造が非常にうまく機能することを安心させました。そして、私の信念の中で、それが使用される実際の条件の下であなたのコードをベンチマークすることは本当に報いているということを確認しました。

要するに、最新のGHCでの修正があっても、Haskellは競争力のある効率的な辞書（可変または不変）を提供することができません。

Haskellのハッシュテーブルはそうでした C ++や.NETなどの代替品よりも32×遅い GHC 6.10で。それは部分的にはaのためでした GHC 6.12.2のために修正されたGHCガベージコレクターのパフォーマンスバグ. 。しかし、Simon Marlowの結果では、Haskellのハッシュテーブルがほとんどの代替品よりも何倍も遅い5倍のパフォーマンス改善のみを示しています。

純粋に機能的な代替品は、まともなハッシュテーブルよりもはるかに遅いです。例えば、 Haskell's IntMap .NETのハッシュテーブルより10倍遅いです.

F＃2010を使用して 最新のHaskellプラットフォーム2010.2.0.0 （昨日リリースされた！）この2.0GHz E5405 Xeonが32ビットWindows Vistaを実行して20mのint-> intバインディングを空のハッシュテーブルに挿入して、HaskellはリアルタイムでF＃よりも29倍遅いことがわかります。 Haskellがすべてのコアを燃やすため、CPU時間の点で200×遅い：

GHC 6.12.3 Data.HashTable: 42.8s (new!)
.NET hash table:            1.47s

Don Stewartが上記で示唆しているように、GHCガベージコレクターを無効にすることができる短命のマイクロベンチマークのみを実行している場合。この特定のプログラムが決してそれを埋めないように非常に大きい保育園の世代を求めることで、彼はここでHaskellハッシュテーブルの時間をわずか1.5にしました。ただし、これは保育園の世代を持つことの全体的なポイントを完全に損ない、新たに割り当てられた値が常にキャッシュで冷たくなるため、他のコードのパフォーマンスを大幅に分解するでしょう（そのため、保育園の世代は通常、L2キャッシュのサイズです。これよりも数桁小さい）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top