Я прочитал, что в хэш-таблицах в Haskell были проблемы с производительностью (в Haskell-Cafe в 2006 году и Flying Frog Consultancy blog в 2009 году), и поскольку мне нравится Haskell, это меня беспокоило.
Это был год назад, каков статус сейчас (июнь 2010 года)? Устранена ли проблема "хэш-таблицы" в GHC?
Проблема заключалась в том, что сборщик мусора должен пересекать измененные массивы указателей ( "массивы в штучной упаковке" ), которые ищут указатели на данные, которые могут быть готовы освободить. Вмещенные, измененные массивы являются основным механизмом реализации хеш-таблицы, так что в конкретной структуре возникла проблема обхода GC. Это характерно для многих языков. Симптомом является чрезмерная сборка мусора (до 95% времени, проведенного в GC).
Исправление было реализовать "маркировку карт" в GC для изменяемых массивов указателей, которые произошли в конце 2009 года. Вы не должны см. чрезмерный GC при использовании изменяемых массивов указателей в Haskell. В простых тестах добавление хэш-таблицы для больших хешей улучшилось на 10 раз.
Обратите внимание, что проблема хождения GC не влияет на чисто функциональные структуры, а также не распакованные массивы (например, большинство данных параллельные массивы или vector-like массивы, в Haskell. Также это не влияет на hashtables сохраненный на куче C (например, judy). Это означает, что он не повлиял на повседневных Haskellers, не используя настоящие хеш-таблицы.
Если вы используете hashtables в Haskell, вы не должны наблюдать за какой-либо проблемой сейчас. Здесь, например, есть простая хеш-таблица, которая вставляет 10 миллионов ints в хэш. Я сделаю бенчмаркинг, так как исходная цитата не содержит никакого кода или тестов.
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 через интерфейс внешней функции):
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 и других функциональных языках. Вы также можете прочитать работу Криса Окасаки и Энди Гилла на деревьях Патрисии в Хаскелле, посмотреть, как их опыт рассматривается. Вы также можете найти, чьи претензии, если таковые имеются, были проверены третьей стороной. Тогда вы можете сами подумать, как серьезно принимать разные требования людей о производительности разных функциональных языков.
О, и не кормите тролля.
P.S. Было бы вполне разумно, если бы вы сделали свои собственные эксперименты, но, возможно, не обязательно, так как надежный Дон Стюарт в своем прекрасном ответе предлагает приятные микрофункции. Здесь добавляется добавление к Дону:
Приложение: Использование кода Дона Стюарта на AMD Phenom 9850 Black Edition с тактовой частотой 2,5 ГГц с 4 ГБ оперативной памяти в 32-битном режиме с ghc -O,
IntMap на 40% быстрее, чем хеш-таблица.IntMap.IntMap будет в четыре раза быстрее, чем хеш-таблица (время процессора) или в два раза быстрее, настенное время.Я немного удивлен этим результатом, но заверил, что функциональные структуры данных работают очень хорошо. И подтвердил в своем убеждении, что действительно стоит запланировать свой код в реальных условиях, в которых он будет использоваться.
Короче говоря, даже с исправлением в последнем GHC, Haskell по-прежнему не в состоянии предоставить словарь (изменяемый или неизменный), который является конкурентоспособным.
Хэш-таблицы Haskell были 32 × медленнее, чем альтернативы, такие как С++ и .NET с GHC 6.10. Отчасти это было связано с ошибкой производительности . Но результаты Simon Marlow показывают только улучшение производительности 5 ×, которое по-прежнему оставляет хэш-таблицы Haskell во много раз медленнее, чем большинство альтернатив.
Чисто функциональные альтернативы также намного медленнее, чем приличная хеш-таблица. Например, Haskell IntMap в 10 раз медленнее, чем хеш-таблица .NET.
Использование F # 2010 и последняя версия Haskell Platform 2010.2.0.0 (выпущена вчера!) с GHC 6.12.3 на этом 2.0GHz E5405 Xeon running 32-разрядная Windows Vista для вставки 20M int- > int привязок в пустую хеш-таблицу, мы обнаруживаем, что Haskell по-прежнему на 29 × медленнее F # в реальном времени и более чем на 200 × медленнее с точки зрения времени процессора, поскольку Haskell сжигает все ядра:/p >
GHC 6.12.3 Data.HashTable: 42.8s (new!) .NET hash table: 1.47s
Если вы запускаете только краткосрочные микрозахваты, вы можете отключить сборщик мусора GHC, о котором говорит Дон Стюарт. Прося о том, чтобы такое детское производство было настолько большим, что эта конкретная программа никогда не заполнит его, он привел время для хэш-таблицы Haskell до 1,5 с здесь. Тем не менее, это полностью подрывает весь смысл создания детского сада и будет значительно ухудшать производительность другого кода, потому что свежевыпущенные значения теперь будут всегда холодными в кеше (поэтому генерация детского сада обычно представляет собой размер кэша L2, на порядок меньше этого).