Performance Problem with Loops

[Simon Peyton-Jones]

I believe that I've fixed this in the HEAD.

Simon

| -----Original Message-----
| From: cvs-all-bounces at haskell.org [mailto:cvs-all-bounces at haskell.org]
On Behalf Of Wolfgang
| Thaller
| Sent: 23 February 2004 14:19
| To: cvs-ghc at haskell.org
| Subject: Performance Problem with Loops
| 
| Hi All,
| 
| Somebody complained about poor performance with mapArray on the GHC
| list. I tried to optimize it, and I discovered that GHC has a quite
| serious performance problem regarding tight loops.
| Take a look at the following programs:
| 
| // File bar.c:
| void bar(int i) {}		// something simple to do inside a loop
:-)
| 
| -- File FastLoop.hs:
| foreign import ccall unsafe bar :: Int -> IO ()
| 
| main = loop 0
|      where
|          loop 100000000 = return ()
|          loop i = bar i >> loop (i+1)
| 
| -- File SlowLoop.hs:
| foreign import ccall unsafe bar :: Int -> IO ()
| 
| doLoop n = loop 0
|      where
|          loop i | i == n    = return ()
|                 | otherwise = bar i >> loop (i+1)
| 
| {-# NOINLINE doLoop #-} -- don't inline the upper loop bound into
| doLoop above
| 
| main = doLoop 100000000
| 
| The FastLoop program takes about one second to execute on my 1GHz
| PowerBook G4. The SlowLoop program takes about fifteen seconds.
| 
| FastLoop gets compiled to a near-optimal loop - the equivalent C code
| takes 0.72 seconds.
| In the slow version, $wloop returns a closure, which then gets
| explicitly applied to the state of the world using stg_ap_v. A bad
| waste of time. Here's the STG code for SlowLoop:
| 
| lvl = \r [s] GHC.Prim.(#,#) [s GHC.Base.()];
| SRT(lvl): []
| Main.doLoop =
|      \r [n]
| 	let {
| 	  $wloop =
| 	      sat-only \r [ww]
| 		  case n of wild1 {
| 		    GHC.Base.I# y ->
| 			case ==# [ww y] of wild {
| 			  GHC.Base.True -> lvl;
| 			  GHC.Base.False ->
| 			      let {
| 				k = \u [] case +# [ww 1] of sat_s1El {
__DEFAULT -> $wloop
| sat_s1El; }; } in
| 			      let {
| 				sat_s1EH =
| 				    \r [eta] case __ccall bar [ww eta]
of wild11 { GHC.Prim.(# #)
| ds -> k ds; };
| 			      } in  sat_s1EH;
| 			};
| 		  };
| 	} in  $wloop 0;
| SRT(Main.doLoop): []
| Main.lvl1 = NO_CCS GHC.Base.I#! [100000000];
| SRT(Main.lvl1): []
| Main.main = \u [] Main.doLoop Main.lvl1;
| SRT(Main.main): []
| :Main.main =
|      \r srt:(0,*bitmap*) [eta] catch# [Main.main
| GHC.TopHandler.topHandler eta];
| SRT(:Main.main): [Main.main, GHC.TopHandler.topHandler]
| 
| 
| Can something be done about this? I guess mapArray isn't the only
| operation that could get a ten-fold speedup from this.
| 
| Cheers,
| 
| Wolfgang
| 
| _______________________________________________
| Cvs-ghc mailing list
| Cvs-ghc at haskell.org
| http://www.haskell.org/mailman/listinfo/cvs-ghc