Вопросы Теги

Любопытный на предмет проблем работы HashTable

Я считал, что хеш-таблицы в Haskell имели проблемы производительности (на Haskell-кафе в 2006 и Летающем блоге Консультирования Лягушки в 2009), и так как мне нравится Haskell, это волновало меня.

Это было год назад, каково состояние теперь (июнь 2010)? Имеет "проблема хеш-таблицы" зафиксированный в GHC?

50
задан rob mayoff 5 June 2016 в 13:18
поделиться

3 ответа

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

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

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

Если вы используете хэш-таблицы в 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 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 (который является оберткой Haskell, вызывающей код C через интерфейс foreign-function): 

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

135
ответ дан 7 November 2019 в 10:29
поделиться

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

Джон Харроп выдвинул несколько интересных утверждений о 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 будет в четыре раза быстрее, чем хэш-таблица (процессорное время) или в два раза быстрее по времени wall-clock.

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

26
ответ дан 7 November 2019 в 10:29
поделиться

Короче говоря, даже с исправлением в последней версии GHC, Haskell по-прежнему не может предоставить словарь (изменяемый или неизменяемый), который был бы конкурентоспособным.

Хеш-таблицы Haskell были в 32 раза медленнее, чем альтернативы, такие как C ++ и .NET с GHC 6.10. Частично это было из-за ошибки производительности в сборщике мусора GHC, которая была исправлена ​​в GHC 6.12.2 . Но результаты Саймона Марлоу показывают только 5-кратное улучшение производительности, что по-прежнему оставляет хеш-таблицы Haskell во много раз медленнее, чем большинство альтернатив.

Чисто функциональные альтернативы также намного медленнее, чем приличная хеш-таблица.Например, Haskell IntMap в 10 раз медленнее, чем хеш-таблица .NET .

Использование F # 2010 и последней версии Haskell Platform 2010.2.0.0 (выпущенной вчера!) С GHC 6.12.3 на E5405 Xeon 2,0 ГГц под управлением 32-разрядной Windows Vista для вставки 20M привязок int-> int в пустую хеш-таблицу мы обнаруживаем, что Haskell по-прежнему в 29 раз медленнее, чем F # в реальном времени, и более чем в 200 раз медленнее с точки зрения процессорного времени, потому что Haskell сжигает все ядра: 

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

Если вы запускаете только краткосрочные микробенчмарки, вы можете отключить сборщик мусора GHC, как предлагает Дон Стюарт выше. Запрашивая создание такого большого детского поколения, что эта конкретная программа никогда его не заполнит, он сократил время для хэш-таблицы Haskell до 1,5 с. Однако это полностью подрывает весь смысл создания дочернего поколения и значительно ухудшает производительность другого кода, потому что недавно выделенные значения теперь всегда будут холодными в кеше (вот почему дочернее поколение обычно имеет размер кеша L2, на порядки меньше этого).

6
ответ дан 7 November 2019 в 10:29
поделиться
Другие вопросы по тегам:

Похожие вопросы: