StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>how to find out why this solution is so slow. Are there any commands that tell me where most of the computation-time is spend so I know which part of my haskell-program is slow?</p> </blockquote> <p>Precisely! GHC provides many excellent tools, including:</p> <ul> <li><a href="http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/runtime-control.html" rel="noreferrer">runtime statistics</a></li> <li><a href="http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/prof-time-options.html" rel="noreferrer">time profiling</a></li> <li><a href="http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/prof-heap.html" rel="noreferrer">heap profiling</a></li> <li><a href="http://research.microsoft.com/en-us/projects/threadscope/" rel="noreferrer">thread analysis</a></li> <li><a href="http://hackage.haskell.org/package/ghc-core" rel="noreferrer">core analysis.</a></li> <li><a href="http://hackage.haskell.org/package/criterion" rel="noreferrer">comparative benchmarking</a></li> <li><a href="http://hackage.haskell.org/package/ghc-gc-tune" rel="noreferrer">GC tuning</a></li> </ul> <p>A tutorial on using time and space profiling is <a href="http://book.realworldhaskell.org/read/profiling-and-optimization.html" rel="noreferrer">part of Real World Haskell</a>.</p> <p><strong>GC Statistics</strong></p> <p>Firstly, ensure you're compiling with ghc -O2. And you might make sure it is a modern GHC (e.g. GHC 6.12.x)</p> <p>The first thing we can do is check that garbage collection isn't the problem. Run your program with +RTS -s</p> <pre><code>$ time ./A +RTS -s ./A +RTS -s 749700 9,961,432,992 bytes allocated in the heap 2,463,072 bytes copied during GC 29,200 bytes maximum residency (1 sample(s)) 187,336 bytes maximum slop **2 MB** total memory in use (0 MB lost due to fragmentation) Generation 0: 19002 collections, 0 parallel, 0.11s, 0.15s elapsed Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 13.15s ( 13.32s elapsed) GC time 0.11s ( 0.15s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 13.26s ( 13.47s elapsed) %GC time **0.8%** (1.1% elapsed) Alloc rate 757,764,753 bytes per MUT second Productivity 99.2% of total user, 97.6% of total elapsed ./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total </code></pre> <p>Which already gives us a lot of information: you only have a 2M heap, and GC takes up 0.8% of time. So no need to worry that allocation is the problem.</p> <p><strong>Time Profiles</strong></p> <p>Getting a time profile for your program is straight forward: compile with -prof -auto-all</p> <pre><code> $ ghc -O2 --make A.hs -prof -auto-all [1 of 1] Compiling Main ( A.hs, A.o ) Linking A ... </code></pre> <p>And, for N=200:</p> <pre><code>$ time ./A +RTS -p 749700 ./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total </code></pre> <p>which creates a file, A.prof, containing:</p> <pre><code> Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final) A +RTS -p -RTS total time = 13.18 secs (659 ticks @ 20 ms) total alloc = 4,904,116,696 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc numDivs Main 100.0 100.0 </code></pre> <p>Indicating that <em>all</em> your time is spent in numDivs, and it is also the source of all your allocations.</p> <p><strong>Heap Profiles</strong></p> <p>You can also get a break down of those allocations, by running with +RTS -p -hy, which creates A.hp, which you can view by converting it to a postscript file (hp2ps -c A.hp), generating:</p> <p><img src="https://i.imgur.com/OoSB6.png" alt="alt text"></p> <p>which tells us there's nothing wrong with your memory use: it is allocating in constant space.</p> <p>So your problem is algorithmic complexity of numDivs:</p> <pre><code>toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2 </code></pre> <p>Fix that, which is 100% of your running time, and everything else is easy.</p> <p><strong>Optimizations</strong></p> <p>This expression is a good candidate for the <a href="https://stackoverflow.com/questions/578063/what-is-haskells-stream-fusion">stream fusion</a> optimization, so I'll rewrite it to use <a href="http://hackage.haskell.org/package/vector" rel="noreferrer">Data.Vector</a>, like so:</p> <pre><code>numDivs n = fromIntegral $ 2 + (U.length $ U.filter (\x -> fromIntegral n `rem` x == 0) $ (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int)) </code></pre> <p>Which should fuse into a single loop with no unnecessary heap allocations. That is, it will have better complexity (by constant factors) than the list version. You can use the ghc-core tool (for advanced users) to inspect the intermediate code after optimization.</p> <p>Testing this, ghc -O2 --make Z.hs</p> <pre><code>$ time ./Z 749700 ./Z 3.73s user 0.01s system 99% cpu 3.753 total </code></pre> <p>So it reduced running time for N=150 by 3.5x, without changing the algorithm itself.</p> <p><strong>Conclusion</strong></p> <p>Your problem is numDivs. It is 100% of your running time, and has terrible complexity. <strong>Think about numDivs, and how, for example, for each N you are generating [2 .. n <code>div</code> 2 + 1] N times. Try memoizing that, since the values don't change.</strong></p> <p>To measure which of your functions is faster, consider using <a href="http://hackage.haskell.org/package/criterion" rel="noreferrer">criterion</a>, which will provide statistically robust information about sub-microsecond improvements in running time.</p> <hr> <p><strong>Addenda</strong></p> <p>Since numDivs is 100% of your running time, touching other parts of the program won't make much difference, however, for pedagogical purposes, we can also rewrite those using stream fusion.</p> <p>We can also rewrite trialList, and rely on fusion to turn it into the loop you write by hand in trialList2, which is a "prefix scan" function (aka scanl):</p> <pre><code>triaList = U.scanl (+) 0 (U.enumFrom 1 top) where top = 10^6 </code></pre> <p>Similarly for sol:</p> <pre><code>sol :: Int -> Int sol n = U.head $ U.filter (\x -> numDivs x > n) triaList </code></pre> <p>With the same overall running time, but a bit cleaner code.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload