Duncan Coutts wrote:
On Fri, 2008-12-19 at 10:42 -0600, Jake McArthur wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
fibs = 0 : 1 : zipWith (+) fibs (tail fibs) This is a CAF (Constant Applicative Form). Since it is actually a constant it is never garbage collected, and is always shared, so each
Paul Keir wrote: thread is only calculating it once. You have essentially created a lookup table.
Though note that with all our obvious suggestions there is still no speedup:
heavytask m n = putMVar m $! (fibs !! 100000) where fibs = n : (n+1) : zipWith (+) fibs (tail fibs)
-- so now fibs is not globally shared but is used per-heavytask -- it is also evaluated by heavy task rather than just putting a thunk -- into the MVar
main = do ms <- sequence $ replicate 8 newEmptyMVar sequence_ [ forkIO (heavytask m n) | (m, n) <- zip ms [0..] ] ms' <- mapM takeMVar ms mapM_ print ms'
Looking at the GC stats (+RTS -t -RTS) we see that the majority of the time in this program is spent doing GC and that when we run with -N4 the time spent doing GC is even higher.
This is an interesting example. It shows up a weakness in the GC that I'm working on fixing right now. The interesting aspect of this example is that the thread stacks get large. You can see this by using +RTS -hT: a large chunk of the heap is taken up by TSOs. Each of those (fibs !! 100000) requires linear stack, because (fibs 100000) depends on (fibs 99999), and so on. That could probably be fixed by adding some strictness, but that's not the goal here - we should still be able to run the program in parallel. So when there are large stacks around, GC takes a long time because it has to traverse stacks. But we should be able to alleviate the problem by (a) using a larger heap, and (b) using parallel GC. Not doing parallel GC is seriously going to hurt peformance, because the data will have to be moved from one CPU's cache to another. But it turns out that parallel GC is misbehaving on this example too, because it doesn't force each stack to be scanned by the same thread that is executing it - I'm working on fixing that. Having each CPU be able to GC independently would be a big improvement, of course. We think we understand how this can be done in the context of GHC, it's just a matter of doing it, but it's a big job. Parallel performance is something that we expect to make dramatic improvements over the next few months as we investigate more programs and improve the tools. The current HEAD is already a lot better than 6.10.1. Cheers, Simon