2
我在Haskell中编写了一个trie实现并获得了一些性能问题。我相应地将我的代码简介为http://book.realworldhaskell.org/read/profiling-and-optimization.html,并可以确定问题。这是我的线索的insertWith
方法:Haskell中的Spaceleak trie
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 [email protected](Trie Nothing _) = t { value = Just a }
insertWith f [] a [email protected](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方法更好一些?
由于
总是很好的注意你正在使用什么GHC以及如何编译 – jberryman 2013-04-23 19:05:42
无法重现。它在7.6.1和7.6.2都有良好表现。你在哪个平台上? (并且,你的编译标志是什么?) – 2013-04-23 20:10:29
Arch Linux 64位内核3.8.8.1 flags:-O3 -rtsopts -prof -auto-all -caf-all – SvenK 2013-04-23 21:09:21