Haskell中的Spaceleak trie

Question

我在Haskell中編寫了一個trie實現並獲得了一些性能問題。我相應地將我的代碼簡介爲http://book.realworldhaskell.org/read/profiling-and-optimization.html，並可以確定問題。這是我的線索的insertWith方法：

import qualified Data.Map.Strict as M 
-- i have also tried Data.Map.Lazy 

data Trie k a = Trie { value :: !(Maybe a) 
        , childs :: !(Map.Map k (Trie k a)) 
        } 

empty :: Trie a k 
empty = Trie Nothing Map.empty 

insertWith :: Ord k => (a -> a -> a) -> [k] -> a -> Trie k a -> Trie k a 
insertWith f [] a t@(Trie Nothing _) = t { value = Just a } 
insertWith f [] a t@(Trie (Just b) _) = t { value = Just $ f a b } 
insertWith f (k:ks) a t = t { childs = m } 
    where 
     recurse = insertWith f ks a 
     m = Map.insertWith (\_ child -> recurse child) k (recurse empty) (childs t) 

我的配置代碼：

import qualified MyTrie as T 
main = do 
    let nums = zipWith (\a b -> (show a, b)) [0..100000] [0..] 
     trie = foldl' (flip $ uncurry $ T.insertWith (+)) T.empty nums 
    putStrLn $ show $ T.lookup "100" trie 

的分析結果：

CAF:main4    Main     113   0 0.0 0.0 55.2 38.3 
    main     Main     126   0 2.6 0.0 55.2 38.3 
    main.trie    Main     127   0 12.6 2.7 52.6 38.3 
    childs    Text.NGram.Trie   137  1000001 0.0 0.0  0.0 0.0 
    insertWith   Text.NGram.Trie   135  1123337 3.2 6.2 40.1 35.6 
    insertWith.recurse Text.NGram.Trie   140  123336 0.4 0.0  0.4 0.0 
    insertWith.m   Text.NGram.Trie   138  1123334 31.4 29.1 36.4 29.4 
     insertWith.recurse Text.NGram.Trie   142   0 0.0 0.0  0.0 0.0 
     insertWith.m.\  Text.NGram.Trie   139  123333 1.5 0.0  5.0 0.3 
     insertWith.recurse Text.NGram.Trie   141   0 3.5 0.3  3.5 0.3 
     childs   Text.NGram.Trie   143  123333 0.0 0.0  0.0 0.0 

和

1,403,625,328 bytes allocated in the heap 
    1,699,102,256 bytes copied during GC 
    393,716,888 bytes maximum residency (11 sample(s)) 
     4,565,856 bytes maximum slop 
      771 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  2673 colls,  0 par 0.97s 0.98s  0.0004s 0.0027s 
    Gen 1  11 colls,  0 par 1.41s 1.41s  0.1285s 0.6767s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 0.69s ( 0.70s elapsed) 
    GC  time 2.38s ( 2.39s elapsed) 
    RP  time 0.00s ( 0.00s elapsed) 
    PROF time 0.00s ( 0.00s elapsed) 
    EXIT time 0.06s ( 0.06s elapsed) 
    Total time 3.14s ( 3.15s elapsed) 

    %GC  time  75.8% (75.9% elapsed) 

    Alloc rate 2,021,450,981 bytes per MUT second 

    Productivity 24.2% of total user, 24.2% of total elapsed 

GHC版本：7.6 .2

有沒有人知道如何讓insertWith方法更好一些？

由於

Answer 1

在

insertWith f [] a t@(Trie Nothing _) = t { value = Just a } 
insertWith f [] a t@(Trie (Just b) _) = t { value = Just $ f a b } 

a和f a b被存儲未計算的。嘗試

insertWith f [] a t@(Trie Nothing _) = a `seq` t { value = Just a } 
insertWith f [] a t@(Trie (Just b) _) = t { value = Just $! f a b }