Changes between Version 7 and Version 8 of Frisby2013Q1


Ignore:
Timestamp:
Feb 11, 2013 4:28:12 PM (3 years ago)
Author:
nfrisby
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Frisby2013Q1

    v7 v8  
    114114
    115115TODO
     116
     117Using -flate-float-in-thunk-limit=10, -fprotect-last-arg, and -O1, I tested the libraries+NoFib for four variants.
     118
     119  * nn - do not float a binding that applies one of its free variables.
     120  * yn - do not float a binding that applies one of its free variables saturated or oversaturated.
     121  * ny - do not float a binding that applies one of its free variables undersaturated.
     122  * yy - do not restrict application of bindings free variables
     123
     124Roughly, we expect that more floating means (barely) less allocation but worse runtime (by how much?) because some known calls become unknown calls.
     125
     126==== Anchoring let-no-escapes ====
     127
     128I discovered this while experimenting with the fast preservation variants above.
     129
     130TODO: Mitigate it.
     131
     132In fish (1.6%), hpg (~4.5%), and sphere (10.4%), allocation gets worse for ny and yy compared to nn and yn. The nn and ny do not change the allocation compared to the baseline library (ie no LLF).
     133
     134The nn -> ny comparison is counter to our rough idea: floating more bindings (those that saturate/oversaturate some free variables) worsens allocation. Thus, I investigate.
     135
     136The sphere program hammers `hPutStr`. Its extra allocation is mostly due to a regression in `GHC.IO.Encoding.UTF8`. Here's the situation.
     137
     138With the nn variant:
     139
     140{{{
     141outer a b c ... =
     142  let-no-escape f x = CTX[let-no-escape $j y = ... (f ...) ... in CTX2[$j]]
     143  in ...
     144}}}
     145
     146In this case, `$j` is not floated because it applies `f`. With the ny variant, `$j` gets floated.
     147
     148{{{
     149poly_$j a b c ... f y = ...
     150
     151outer a b c ... =
     152  let f x = CTX[CTX2[poly_$j a b c ... f]]
     153  in ...
     154}}}
     155
     156Thus `f` cannot be let-no-escape because it now occurs as an argument to `poly_$j`.
     157
     158This contributes to sphere's 1 megabyte of extra allocation for two reasons:
     159
     160  * `outer` is entered about 60,000 times.
     161  * The RHS of `f` has 13 free variables, so it's closure is rather large.
     162
     16313*60,000 ~ 750,000. I suspect the rest of sphere's increase is due to a similar issue in `GHC.IO.Handle`.
     164
     165In hpg, it's principally due to GHC`.IO.Encoding.UTF8` again, with a second place contributor of `GHC.IO.FD`, where the function `$wa17` is again like the `outer` example above, but with fewer free variables and thus less effect.
    116166
    117167=== Discovered Benefits of LLF ===