Любопытно узнать о проблемах с производительностью HashTable

Проблема заключалась в том, что сборщику мусора необходимо обходить изменяемые массивы указателей («массивы в коробках») в поисках указателей на данные, которые могут быть готовы к освобождению. Коробочные, изменяемые массивы являются основным механизмом реализации хеш-таблицы, поэтому эта конкретная структура выявила проблему обхода сборщика мусора. Это свойственно многим языкам. Симптом — чрезмерная сборка мусора (до 95% времени, затрачиваемого на сборку мусора).

Исправление состояло в том, чтобы внедрить "маркировку карт" в GC для изменяемые массивы указателей, что произошло в конце 2009 года. Вы не должны видеть чрезмерного GC при использовании изменяемых массивов указателей в Haskell сейчас. В простых тестах вставка хеш-таблиц для больших хэшей улучшилась в 10 раз.

Обратите внимание, что проблема обхода сборщика мусора не затрагивает чисто функциональные структуры, а также неупакованные массивы (как и большинство данных). параллельные массивы или векторные-подобные массивы в Haskell. Это также не влияет на хэш-таблицы, хранящиеся в куче C (например, judy). Это означает, что это не повлияло на повседневных пользователей Haskeller, не использующих императивные хэш-таблицы.

Если вы используете хэш-таблицы в Haskell, сейчас вы не должны наблюдать никаких проблем. Вот, например, простая программа для создания хеш-таблиц, которая вставляет в хеш 10 миллионов целых чисел. Я проведу бенчмаркинг, поскольку исходная цитата не содержит кода или бенчмарков.

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, который поддерживает диапазон изменяемых хеш-таблиц изначально.

Такой вопрос действительно может быть решен только экспериментальным путем. Но если у вас нет времени или денег на эксперименты, вы должны спросить других людей, что они думают. Когда вы это сделаете, вы, возможно, захотите рассмотреть источник и подумать, была ли предоставленная информация проверена или проверена каким-либо образом.

Джон Харроп выдвинул несколько интересных утверждений о Haskell. Позвольте мне предложить вам поискать в Google Groups и других источниках доказательства опыта Харропа в Haskell, Lisp и других функциональных языках. Вы также можете прочитать работу Криса Окасаки и Энди Гилла о деревьях Патрисии в Haskell, чтобы узнать, как оценивается их опыт. Вы также можете узнать, чьи претензии, если таковые имеются, были проверены третьей стороной. Затем вы сможете сами решить, насколько серьезно относиться к утверждениям разных людей о производительности различных функциональных языков.

Ой, и не кормите тролля.

P.S. Для вас было бы вполне разумно провести свои собственные эксперименты, но, возможно, в этом нет необходимости, поскольку верный Дон Стюарт в своем прекрасном ответе представляет несколько хороших микротестов. Вот дополнение к ответу Дона:

Приложение: использование кода Дона Стюарта на процессоре AMD Phenom 9850 Black Edition с тактовой частотой 2,5 ГГц и 4 ГБ ОЗУ в 32-разрядном режиме с ghc -O,

• С кучей по умолчанию IntMap на 40% быстрее, чем хэш-таблица.
• С кучей 2G хэш-таблица на 40% быстрее, чем IntMap.
• Если я перейду к десяти миллионам элементов с кучей по умолчанию, IntMap в четыре раза быстрее, чем хеш-таблица (время процессора), или в два раза быстрее по времени настенных часов.

Я немного удивлен этим результатом, но уверен, что функциональные структуры данных работают довольно хорошо. И подтвердил мою уверенность в том, что действительно стоит протестировать ваш код в реальных условиях, в которых он будет использоваться.