Haskell Hashtable Performance

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

Вот мой код Python:

y = {}
for x in xrange(10000000):
    y[x] = x
print y[100]

Вот мой соответствующий код на Haskell:

import qualified Data.HashTable.IO as H
import Control.Monad

main = do
  y <- H.new :: IO (H.CuckooHashTable Int Int)
  forM_ [1..10000000] $ \x -> H.insert y x x
  H.lookup y 100 >>= print

Вот еще одна версия, использующая Data.Map, которая медленнее, чем обе для меня:

import qualified Data.Map as Map
import Data.List
import Control.Monad
main = do
  let m = foldl' (\m x -> Map.insert x x m) Map.empty [1..10000000]
  print $ Map.lookup 100 m

Интересно, что Data.HashMap работает очень плохо:

import qualified Data.HashMap.Strict as Map
import Data.List
main = do
  let m = foldl' (\m x -> Map.insert x x m) Map.empty [1..10000000]
  print $ Map.lookup 100 m

Я подозреваю, что Data.HashMap работает плохо, в отличие от Data.Map, он не строгий (я думаю), поэтому foldl' - это просто foldl, со связанными с этим проблемами наращивания thunk.

Обратите внимание, что я использовал -prof и убедился, что большую часть времени я провожу в hashtables или Data.Map, но не в forM или что-то в этом роде. Весь код скомпилирован с -O2 и без других параметров.

7 голосов | спросил Andrew Gibiansky 5 32014vEurope/Moscow11bEurope/MoscowWed, 05 Nov 2014 22:15:18 +0300 2014, 22:15:18

3 ответа


0

Как предложил reddit.com/u/cheecheeo здесь , используя Data.Judy , вы получите аналогичную производительность для своего конкретного микробенчмарка:

module Main where

import qualified Data.Judy as J
import Control.Monad (forM_)

main = do
    h <- J.new :: IO (J.JudyL Int)
    forM_ [0..10000000] $ \i -> J.insert (fromIntegral i) i h
    v <- J.lookup 100 h
    putStrLn $ show v

Время вышесказанного:

$ time ./Main
Just 100

real    0m0.958s
user    0m0.924s
sys     0m0.032s

Синхронизация Python-кода OP:

$ time ./main.py
100

real    0m1.067s
user    0m0.886s
sys     0m0.180s
ответил 6 42014vEurope/Moscow11bEurope/MoscowThu, 06 Nov 2014 12:22:58 +0300 2014, 12:22:58
0

Документация для hashtables отмечает, что «хеширование с кукушкой, как и в реализации базовой хеш-таблицы с использованием линейного зондирования, может иметь большие задержки при изменении размера таблицы». Вы используете new, который создает новую таблицу размера по умолчанию. Из просмотра источника , похоже, что размер по умолчанию равен 2. Вставка 10000000 элементов, вероятно, влечет за собой многочисленные изменения размера.

Попробуйте использовать newSized.

ответил Christian Conkle 5 32014vEurope/Moscow11bEurope/MoscowWed, 05 Nov 2014 22:20:43 +0300 2014, 22:20:43
0

Учитывая вышеприведенное время, я решил добавить решение Data.Map, которое похоже на использование newSized.

import qualified Data.Map as M

main = do
       print $ M.lookup 100 $ M.fromList $ map (\x -> (x,x)) [1..10000000]
ответил jamshidh 5 32014vEurope/Moscow11bEurope/MoscowWed, 05 Nov 2014 22:39:55 +0300 2014, 22:39:55

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132