Aşağıdaki kısa Haskell programını yeterince büyük bir veri kümesinde çalıştırırken Heap exhausted mesajını alıyorum. Örneğin, program yaklaşık 900k satırlı 20 Mb giriş dosyasında (yığın taşmasıyla) başarısız olur. Yığın büyüklüğü (-with-rtsopts aracılığıyla) 1 Gb'ye ayarlandı. longestCommonSubstrB'un daha basit bir şey olarak tanımlanması durumunda, commonPrefix. Dosyaları 100 Mb sırada işlemem gerekiyor.Haskell'de yığın taşması
: girdi sırasına göre (I alan makul bir çalıştırmak bu şeyi yapımında herhangi bir yardım takdir ediyorum
ghc -Wall -O2 -prof -fprof-auto "-with-rtsopts=-M512M -p -s -h -i0.1" SampleB.hs
Dosya boyutu), ama özellikle darboğazın nerede olduğunu ve nerede ve nasıl katılaşmaya zorlanacağını bulma sürecini takdir ediyorum.
Tahminimce, bir şekilde longestCommonSubstrB işlevini zorlamak, bu sorunu kesinlikle çözecektir, ancak bunu nasıl yapacağımı bilmiyorum.
yığın profili, zaman içinde:
{-# LANGUAGE BangPatterns #-}
module Main where
import System.Environment (getArgs)
import qualified Data.ByteString.Lazy.Char8 as B
import Data.List (maximumBy, sort)
import Data.Function (on)
import Data.Char (isSpace)
-- | Returns a list of lexicon items, i.e. [[w1,w2,w3]]
readLexicon :: FilePath -> IO [[B.ByteString]]
readLexicon filename = do
text <- B.readFile filename
return $ map (B.split '\t' . stripR) . B.lines $ text
where
stripR = B.reverse . B.dropWhile isSpace . B.reverse
transformOne :: [B.ByteString] -> B.ByteString
transformOne (w1:w2:w3:[]) =
B.intercalate (B.pack "|") [w1, longestCommonSubstrB w2 w1, w3]
transformOne a = error $ "transformOne: unexpected tuple " ++ show a
longestCommonSubstrB :: B.ByteString -> B.ByteString -> B.ByteString
longestCommonSubstrB xs ys = maximumBy (compare `on` B.length) . concat $
[f xs' ys | xs' <- B.tails xs] ++
[f xs ys' | ys' <- tail $ B.tails ys]
where f xs' ys' = scanl g B.empty $ B.zip xs' ys'
g z (x, y) = if x == y
then z `B.snoc` x
else B.empty
main :: IO()
main = do
(input:output:_) <- getArgs
lexicon <- readLexicon input
let flattened = B.unlines . sort . map transformOne $ lexicon
B.writeFile output flattened
Bu test veri kümesi için profil çıkışına olan (100k hatları, yığın boyutu yani generateSample.exe 100000 1 GB, ayarlanmış, elde edilen dosya boyutu 2.38 MB)
Yürütme istatistikleri:
3,505,737,588 bytes allocated in the heap
785,283,180 bytes copied during GC
62,390,372 bytes maximum residency (44 sample(s))
216,592 bytes maximum slop
96 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 6697 colls, 0 par 1.05s 1.03s 0.0002s 0.0013s
Gen 1 44 colls, 0 par 4.14s 3.99s 0.0906s 0.1935s
INIT time 0.00s ( 0.00s elapsed)
MUT time 7.80s ( 9.17s elapsed)
GC time 3.75s ( 3.67s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 1.44s ( 1.35s elapsed)
EXIT time 0.02s ( 0.00s elapsed)
Total time 13.02s (12.85s elapsed)
%GC time 28.8% (28.6% elapsed)
Alloc rate 449,633,678 bytes per MUT second
Productivity 60.1% of total user, 60.9% of total elapsed
Zaman ve Tahsis profil oluşturma Raporu:
SampleB.exe +RTS -M1G -p -s -h -i0.1 -RTS sample.txt sample_out.txt
total time = 3.97 secs (3967 ticks @ 1000 us, 1 processor)
total alloc = 2,321,595,564 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
longestCommonSubstrB Main 43.3 33.1
longestCommonSubstrB.f Main 21.5 43.6
main.flattened Main 17.5 5.1
main Main 6.6 5.8
longestCommonSubstrB.g Main 5.0 5.8
readLexicon Main 2.5 2.8
transformOne Main 1.8 1.7
readLexicon.stripR Main 1.8 1.9
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 45 0 0.1 0.0 100.0 100.0
main Main 91 0 6.6 5.8 99.9 100.0
main.flattened Main 93 1 17.5 5.1 89.1 89.4
transformOne Main 95 100000 1.8 1.7 71.6 84.3
longestCommonSubstrB Main 100 100000 43.3 33.1 69.8 82.5
longestCommonSubstrB.f Main 101 1400000 21.5 43.6 26.5 49.5
longestCommonSubstrB.g Main 104 4200000 5.0 5.8 5.0 5.8
readLexicon Main 92 1 2.5 2.8 4.2 4.8
readLexicon.stripR Main 98 0 1.8 1.9 1.8 1.9
CAF GHC.IO.Encoding.CodePage 80 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding 74 0 0.0 0.0 0.0 0.0
CAF GHC.IO.FD 70 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD 66 0 0.0 0.0 0.0 0.0
CAF System.Environment 65 0 0.0 0.0 0.0 0.0
CAF Data.ByteString.Lazy.Char8 54 0 0.0 0.0 0.0 0.0
CAF Main 52 0 0.0 0.0 0.0 0.0
transformOne Main 99 0 0.0 0.0 0.0 0.0
readLexicon Main 96 0 0.0 0.0 0.0 0.0
readLexicon.stripR Main 97 1 0.0 0.0 0.0 0.0
main Main 90 1 0.0 0.0 0.0 0.0
GÜNCELLEME: aşağıdaki program örnek verileri oluşturmak için kullanılabilir. Bir argüman, oluşturulan veri kümesindeki satır sayısını bekler. Oluşturulan veriler sample.txt dosyasına kaydedilir. Onunla 900k satırlık veri kümesi oluşturduğumda (generateSample.exe 900000 çalıştırarak), oluşturulan veri kümesi, yığın taşmasıyla yukarıdaki programın başarısız olmasını sağlar (yığın boyutu 1 GB'ye ayarlandı). Ortaya çıkan veri kümesi yaklaşık 20 MB'dir.
module Main where
import System.Environment (getArgs)
import Data.List (intercalate, permutations)
generate :: Int -> [(String,String,String)]
generate n = take n $ zip3 (f "banana") (f "ruanaba") (f "kikiriki")
where
f = cycle . permutations
main :: IO()
main = do
(n:_) <- getArgs
let flattened = unlines . map f $ generate (read n :: Int)
writeFile "sample.txt" flattened
where
f (w1,w2,w3) = intercalate "\t" [w1, w2, w3]
Eh, 'sort' sabit aralıkta çalışamaz: herhangi bir çıktı üretmeden önce tüm girdisini tüketmesi (ve saklaması) gerekir. –
GHC'nin bu sefer problemle ilgili olduğunu düşünmüyorum, ancak soru raporunda GHC sürümünü her zaman profiler raporuna eklemelisiniz. – dfeuer
@dfeuer GHC sürümü 7.8.3 – Glaukon