Проблема заключалась в том, что сборщик мусора необходим для обхода изменяемых массивов указателей («коробочных массивов») в поисках указателей на данные, которые могут быть готовы к освобождению.Изменяемые в штучной упаковке массивы являются основным механизмом реализации хеш-таблицы, поэтому конкретная структура выявила проблему обхода GC.Это характерно для многих языков.Симптом - чрезмерная сборка мусора (до 95% времени, проведенного в GC).
Исправлено: реализована «маркировка карты» в GC для изменяемых массивов указателей, которые происходилив конце 2009 года. Вы не должны видеть чрезмерного GC при использовании изменяемых массивов указателей в Haskell сейчас.Что касается простых тестов, вставка хеш-таблицы для больших хэшей улучшена в 10 раз.
Обратите внимание, что проблема с ходьбой GC не затрагивает чисто функциональные структуры и не распакованные массивы (как большинство данных )параллельные массивы или vector -подобные массивы в Haskell. Также они не влияют на хеш-таблицы, хранящиеся в куче C (например, judy ). Это означает, что это не повлияло на dayна сегодняшний день Haskellers не используют императивные хеш-таблицы.
Если вы используете хеш-таблицы в Haskell, сейчас не должно возникать никаких проблем. Вот, например, простая хеш-таблица, которая вставляет 10 миллионов 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 целых:
$ 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 (который является оболочкой Haskell, вызывающей код C через интерфейс сторонней функции):
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 года вам, вероятно, следует просто использовать пакет hashtables , который поддерживает диапазон изменяемых хеш-таблиц .