Update output (random changes?)
[nofib.git] / Simon-nofib-notes
index 2a6f859..2b4654c 100644 (file)
@@ -13,6 +13,11 @@ whereas it didn't before.  So allocations go up a bit.
        Imaginary suite
 ---------------------------------------
 
+integrate
+~~~~~~~~~
+integrate1D is strict in its second argument 'u', but it also passes 'u' to
+function 'f'.  Hence it now does some reboxing, which pushes up allocation
+slightly.
 
 gen_regexps
 ~~~~~~~~~~~
@@ -28,7 +33,7 @@ I found that there were some very bad loss-of-arity cases in PrelShow.
                          ...
                          (x:xs) -> let f = showLitChar x
                                        g = showl xs
-                                   in \s -> f (g x)
+                                   in \s -> f (g s)
   which is TERRIBLE.  We can't spot that showLitChar has arity 2 because
   it looks like this:
 
@@ -61,11 +66,176 @@ specialisation is broken.
        Spectral suite
 ---------------------------------------
 
+rewrite
+~~~~~~~
+It's important to inline p_ident.
+
+There's a very delicate CSE in p_expr
+   p_expr = seQ q_op [p_term1, p_op, p_term2] ## p_term3
+
+(where all the pterm1,2,3 are really just p_term).  
+
+This expands into
+   p_expr s = case p_term1 s of
+               Nothing -> p_term3 s
+               Just (v,s') -> case p_op s' of ...
+                                Nothing -> p_term3 s
+
+Notice that if the bit before (##) fails, we call p_term3 s, and if
+CSE notices we can re-use the result of the first call.  But that
+depends on how much inlining takes place.  In particular, the follow-up
+calls p_term3 can get hidden inside join points, which don't "see" the first
+call.
+
+
+
+cse
+~~~
+The functions 'go' and 'go1', called from draw, get arity 1, but they
+should get arity 2. We need a better arity analysis, a la Gill. 'go' looks
+like this:
+    go_r1og =
+      \ (ds_aGI :: [GHC.Base.Char]) ->
+        case ds_aGI of wild_aGJ {
+          [] -> z_r1oe;
+          : y_aGN ys_aGO ->
+       let {
+         xs7_s1i8 :: GHC.Prim.Int# -> [GHC.Base.Char]
+         [Str: DmdType]
+         xs7_s1i8 = go_r1og ys_aGO
+       } in 
+         \ (m_XWf :: GHC.Prim.Int#) ->
+           case GHC.Prim.<=# m_XWf 1 of wild1_aSI {
+             GHC.Base.False ->
+               GHC.Base.: @ GHC.Base.Char y_aGN (xs7_s1i8 (GHC.Prim.-# m_XWf 1));
+             GHC.Base.True -> GHC.Base.: @ GHC.Base.Char y_aGN lvl13_r1n0
+           }
+        }
+Notice the 'let' which stops the lambda moving out.
+
+
+Eliza
+~~~~~
+In June 2002, GHC 5.04 emitted four successive
+    NOTE: Simplifier still going after 4 iterations; bailing out.
+messages.  I suspect that the simplifer is looping somehow.
+
+
+Expert
+~~~~~~
+In spectral/expert/Search.ask there's a statically visible CSE. Catching this 
+depends almost entirely on chance, which is a pity.
+
+
+Fish
+~~~~
+The performance of fish depends crucially on inlining scale_vec2.
+It turns out to be right on the edge of GHC's normal threshold size, so
+small changes to the compiler can knock it to and fro.
+
+[Sept 08]  The new instance-declaration story makes show slightly worse.
+Look at Main.showl in the simplified core.  You'll see this:
+
+  a79_aRZ :: GHC.Types.Int
+             -> (GHC.Types.Int, GHC.Types.Int, GHC.Types.Int, GHC.Types.Int)
+             -> GHC.Show.ShowS
+  [Str: DmdType]
+  a79_aRZ =
+    GHC.Show.showsPrec9 @ Int @ Int @ Int @ Int
+         GHC.Show.$f16 GHC.Show.$f16 GHC.Show.$f16 GHC.Show.$f16
+
+  Rec {
+  showl_sWK :: [Main.Line_segment] -> String -> String
+  [Arity 2
+   Str: DmdType SL]
+  showl_sWK =
+    \ (ds_dQJ :: [Main.Line_segment]) (s_alB :: GHC.Base.String) ->
+      case ds_dQJ of wild_X1d [ALWAYS Just A] {
+        [] -> GHC.Types.: @ GHC.Types.Char lvl_sYT s_alB;
+        : x_alD [ALWAYS Just L] xs_alF [ALWAYS Just L] ->
+          GHC.Base.++
+            @ GHC.Types.Char
+            a_s12R
+            (a79_aRZ a_s1uS x_alD (showl_sWK xs_alF s_alB))
+      }
+  end Rec }
+
+Note the non-inlined call to GHC.Show.showsPrec9, which looks like this:
+  showsPrec9 :: forall a b c d. (Show a, Show b, Show c, Show d) =>
+                GHC.Types.Int -> (a, b, c, d) -> GHC.Show.ShowS
+    {- Arity: 4 Strictness: LLLL
+       Unfolding: (\ @ a b c d
+                     $dShow :: GHC.Show.Show a
+                     $dShow1 :: GHC.Show.Show b
+                     $dShow2 :: GHC.Show.Show c
+                     $dShow3 :: GHC.Show.Show d ->
+                   let {
+                     shows1 :: d -> GHC.Show.ShowS = GHC.Show.shows @ d $dShow3
+                   } in
+                   let {
+                     shows2 :: c -> GHC.Show.ShowS = GHC.Show.shows @ c $dShow2
+                   } in
+                   let {
+                     shows3 :: b -> GHC.Show.ShowS = GHC.Show.shows @ b $dShow1
+                   } in
+                   let {
+                     shows4 :: a -> GHC.Show.ShowS = GHC.Show.shows @ a $dShow
+                   } in
+                   \ ds :: GHC.Types.Int ds1 :: (a, b, c, d) s :: GHC.Base.String ->
+                   case @ GHC.Base.String ds1 of wild { (a79, b, c, d) ->
+                   GHC.Show.show_tuple
+                     (GHC.Types.:
+                        @ GHC.Show.ShowS
+                        (shows4 a79)
+                        (GHC.Types.:
+                           @ GHC.Show.ShowS
+                           (shows3 b)
+                           (GHC.Types.:
+                              @ GHC.Show.ShowS
+                              (shows2 c)
+                              (GHC.Types.:
+                                 @ GHC.Show.ShowS
+                                 (shows1 d)
+                                 (GHC.Types.[] @ GHC.Show.ShowS)))))
+                     s }) -}
+
+We would do better to inpline showsPrec9 but it looks too big.  Before
+it was inlined regardless by the instance-decl stuff.  So perf drops slightly.
+
+
+Integer
+~~~~~~~
+A good benchmark for beating on big-integer arithmetic
+
+Knights
+~~~~~~~
+In knights/KnightHeuristic, we don't find that possibleMoves is strict
+(with important knock-on effects) unless we apply rules before floating
+out the literal list [A,B,C...].
+Similarly, in f_se (F_Cmp ...) in listcompr (but a smaller effect)
+
+
+Lambda
+~~~~~~
+This program shows the cost of the non-eta-expanded lambdas that arise from
+a state monad.  
+
+mandel2
+~~~~~~~
+check_perim's several calls to point_colour lead to opportunities for CSE
+which may be more or less well taken.
+
 Mandel
 ~~~~~~
 Relies heavily on having a specialised version of Complex.magnitude
 (:: Complex Double -> Double) available.
 
+Mandel.mandelset has a go-loop inside an enumDeltaToIntegerFB, out of which
+4.08.2 managed to float a constant expression, but HEAD did not.  I think
+this is because the pre-let-floating simplification did too little inlining;
+in particular, it did not inline windowToViewport
+
+
 Multiplier
 ~~~~~~~~~~
 In spectral/multiplier, we have 
@@ -80,15 +250,6 @@ In spectral/multiplier, we have
   So allocation goes up.  I don't see a way around this.
 
 
-Mandel
-~~~~~~
-Mandel.mandelset has a go-loop inside an enumDeltaToIntegerFB, out of which
-4.08.2 managed to float a constant expression, but HEAD did not.  I think
-this is because the pre-let-floating simplification did too little inlining;
-in particular, it did not inline windowToViewport
-
-
-
 Parstof
 ~~~~~~~
 spectral/hartel/parstof ends up saying
@@ -96,40 +257,20 @@ spectral/hartel/parstof ends up saying
   quite a bit.   We should spot these and behave accordingly.
 
 
-Knights
-~~~~~~~
-In knights/KnightHeuristic, we don't find that possibleMoves is strict
-(with important knock-on effects) unless we apply rules before floating
-out the literal list [A,B,C...].
-Similarly, in f_se (F_Cmp ...) in listcompr (but a smaller effect)
-
-
-Expert
-~~~~~~
-In spectral/expert/Search.ask there's a statically visible CSE. Catching this 
-depends almost entirely on chance, which is a pity.
-
-
+Power
+~~~~~
+With GHC 4.08, for some reason the arithmetic defaults to Double.  The
+right thing is to default to Rational, which accounts for the big increase
+in runtime after 4.08
 
-Fish
-~~~~
-The performance of fish depends crucially on inlining scale_vec2.
-It turns out to be right on the edge of GHC's normal threshold size, so
-small changes to the compiler can knock it to and fro.
-
-
-Integer
-~~~~~~~
-A good benchmark for beating on big-integer arithmetic
-
-Lambda
-~~~~~~
-This program shows the cost of the non-eta-expanded lambdas that arise from
-a state monad.  
 
 Puzzle
 ~~~~~~
 The main function is 'transfer'.  It has some complicated join points, and
+a big issue is the full laziness can float out many small MFEs that then 
+make much bigger closures.  It's quite delicate: small changes can make
+big differences, and I spent far too long gazing at it.
+
 I found that in my experimental proto 4.09 compiler I had 
 
        let ds = go xs in
@@ -208,19 +349,36 @@ Sphere also does 60,000 calls to hPutStr, so I/O plays a major role.  Currently
 this I/O does a *lot* of allocation, much of it since the adddition of thread-safety.
 
 
-Treejoin
+treejoin
 ~~~~~~~~
-Does a lot of IO.readFile.
+Does a lot of IO.readFile.  In GHC.IO.Encoding.UTF8 the demand
+analyser sees a strict function with type
+ a_s1gj :: GHC.IO.Buffer.Buffer GHC.Word.Word8
+       -> GHC.IO.Buffer.Buffer GHC.Types.Char
+       -> GHC.Prim.State# GHC.Prim.RealWorld
+       -> (# GHC.Prim.State# GHC.Prim.RealWorld,
+             (GHC.IO.Encoding.Types.CodingProgress,
+              GHC.IO.Buffer.Buffer GHC.Word.Word8,
+              GHC.IO.Buffer.Buffer GHC.Types.Char) #)
+Unboxing both Buffer arguments makes a HUGE difference (halves
+allocation); but that makes the worker function have 12 arguments.  A
+good reason for unboxing even if the worker gets a lot of args.
+
+sorting
+~~~~~~~
+Same issue with GHC.IO.Encoding.UTF8 as treejoin
+
 
 ---------------------------------------
        Real suite
 ---------------------------------------
 
-
+gg
+~~
+Same issue with GHC.IO.Encoding.UTF8 as treejoin
        
 Maillist
 ~~~~~~~~
-
 Uses appendFile repeatedly rather than opening the output file once,
 which leads to numerous file opens/closes.  Allocations will rise with
 the new I/O subsystem in 5.02 because the I/O buffer will be