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

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

  •  27-09-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

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

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

Если вы используете Hashtables в Haskell, вы не должны соблюдать любой проблему сейчас. Здесь, например, простая программа Hashtable, которая вставляет 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, до исправления, вставив 10 м INT:

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

С GHC 6.13, после исправления:

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

Увеличение площади кучи по умолчанию:

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

Избегая Hashtables и используя 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 WOPTPER, вызывая C Code Code через интерфейс Function 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 с HASHTABLES фиксированный, и там есть Всегда были другие библиотеки и структуры данных которые были идеально подходящими. Таким образом, это не проблема.

Примечание: по состоянию на 2013 год, вы, вероятно, должны просто использовать hashtables. пакет, который поддерживает Диапазон мусорных хэш родом.

Другие советы

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

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

Да, и не корми тролля.

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

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

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

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

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

Хэш-таблицы Haskell были 32 × медленнее, чем альтернативы, такие как C ++ и .NET с GHC 6.10. Это было частично связано с Ошибка производительности в сборщике мусора GHC, который был зафиксирован для GHC 6.12.2. Отказ Но результаты Simon Marlow's там показывают только улучшение производительности 5 ×, которое по-прежнему оставляет хеш-таблицы HASKELL много раз медленнее, чем большинство альтернатив.

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

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

GHC 6.12.3 Data.hashtable: 42.8S (NEW!) .NET HASH HASH TALLE: 1.47S

При условии, что вы запускаете только короткие микробенки, вы можете отключить сборщик мусора GHC, поскольку Don Stewart предлагает выше. Просив настолько большим поколением питомника, что эта конкретная программа никогда не наполнит ее, он принес время для Haskell Hash Chash Hate Down до 1,5 м. Тем не менее, это полностью подрывает весь смысл создания питомника и будет массивно ухудшать производительность другого кодекса, поскольку в кеше теперь будет холодно выделенные значения, которые теперь всегда будут холодными. порядки магниты меньше, чем это).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top