Merak karma tablosu etkinliği

SORU

17 HAZİRAN 2010, PERŞEMBE

Merak karma tablosu etkinliği

Haskell karma tabloları performans sorunları (2009 a blog) olduğunu okudum, ve Haskell gibi beni endişelendirdi. Bu bir yıl önceydi, şimdi durum (Haziran 2010) nedir? "Tablo sorunu" DZD sabit? karma var

CEVAP

17 HAZİRAN 2010, PERŞEMBE

Sorun çöp toplayıcı işaretçiler traverse değişken dizileri için gerekli olan ("kutulu diziler") ayırması için hazır olabilir veri işaretçileri arıyor. Kutulu, değişken diziler bir karma tablosu uygulamak için temel mekanizma, belirli bir yapısı GC geçişi sorunu ortaya çıktı. Bu birçok dilde ortaktır. Belirtisidir aşırı çöp toplama (GC saat harcanan zaman �'e kadar).

Düzeltme 17 ** geç 2009 yılında meydana gelen göstericiler, değişken dizileri için. Haskell, işaretçileri değişken diziler şimdi kullanırken aşırı GC görmesinler. Basit kriterler üzerinde, büyük karma için karma tablo ekleme 10x tarafından geliştirilmiş.

GC yürüme sorunu ne Kutusuz diziler purely functional structures, (Haskell parallel arrays vector-gibi diziler en çok veri gibi. etkilemez unutmayın Ne hashtables C yığında saklı (judy gibi) etkiler. Etkilemedi yani günlük zorunlu hash tabloları kullanarak değil Haskellers.

Eğer Haskell içinde hashtables kullanıyorsanız, herhangi bir sorun, şimdi incelemek gerekir. Burada, örneğin, bir karma 10 milyon değer vermez karma tablo ekler basit bir program. Orijinal alıntı herhangi bir kod veya kriterler mevcut olmadığından kıyaslama yaparım.

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

DZD önce düzeltme 6.10.2, ile, 10M in ekleme:

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

6.13 Düzelt sonra DZD ile:

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

Varsayılan yığın bölgede artan:

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

Hashtables kaçınarak ve bir İntMap kullanarak:

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

Ve elde ederiz

$ time ./A 10000000  RTS -s        
./A 10000000  RTS -s
6s

Ya da, alternatif olarak, judy bir dizi kullanarak Haskell sarıcı C yabancı fonksiyon arayüzü ile kod arama ():

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

Bu çalışan