Recursive functions and constant parameter closures (inlining/strictness analyzer question)

[Dan Doel]

On Friday 30 May 2008, Duncan Coutts wrote:
> This is for two reasons. One is because your second foldl' is directly
> recursive so does not get inlined. The static argument transformation it
> what you're doing manually to turn the latter into the former. The SAT
> is implemented in ghc 6.9 (though it seems to be having integration
> problems).

Apologies for replying to this thread after around a month, but I've been 
looking at performance of code with and without this transformation a bit 
lately, and I'm rather curious what is being planned to go on in GHC 6.10 
with regard to it.

Specifically, will GHC simply always perform the static argument transform, or 
will it have some kind of heuristic to decide when it's useful? It seems, 
according to some tests I've done, that it's not always a win, and is 
sometimes a loss (and not just with regard to code duplication). I've been 
hard pressed to come up with a definite rule for when it's a benefit, other 
than simply testing and seeing what works.

For instance, consider some code from a recent benchmark I posted (I'm running 
this all under 6.8.2):

    bench :: Int -> Int -> ST s ()
    bench (I# k) (I# n) = ST go
     where
     go s = case sizeOf (0 :: Int)        of { I# w ->
            case newByteArray# (n *# w) s of { (# s, arr #) ->
            case fill arr n s             of { s ->
            go' arr k s } } }
     go' arr 0# s = (# s, () #)
     go' arr k  s = case reverse arr 0# (n -# 1#) s of { s ->
                    go' arr (k -# 1#) s }

    reverse :: MutableByteArray# s -> Int# -> Int# -> State# s -> State# s
    reverse arr i j s
      | i <# j    = case readIntArray#  arr i    s of { (# s, ei #) ->
                    case readIntArray#  arr j    s of { (# s, ej #) ->
                    case writeIntArray# arr j ei s of { s ->
                    case writeIntArray# arr i ej s of { s ->
                    reverse arr (i +# 1#) (j -# 1#) s } } } }
      | otherwise = s

The above is without the SAT on 'arr', obviously. This code runs fast. Doing 
SAT on reverse, but not on go' causes lots of heap allocation (for high 
iteration counts), slowing things way down. Doing it on go' but not reverse 
yields results about the same as not doing it at all. Doing it on both go' 
*and* reverse eliminates the heap allocation of the first case, *but* it 
results in overall slower code (which may, in fact, invalidate my bug about 
MBA# performance; I'll have to check. Just goes to show, even the most 
straightforward benchmark may not be measuring what you intend to measure).

Another example is this function from the MBA# version of the fannkuch 
benchmark:

    shift :: MutableByteArray# s -> Int# -> State# s -> State# s
    shift arr r s = case readIntArray# arr 0# s of { (# s, p0 #) ->
                    case go arr 0# r s of { s ->
                    writeIntArray# arr r p0 s } }
     where
     go arr i r s
       | i <# r    = case readIntArray# arr (i +# 1#) s of { (# s, e #) ->
                     case writeIntArray# arr i e s of { s ->
                     go arr (i +# 1#) r s } }
       | otherwise = s
    {-# INLINE shift #-}

Now, obviously, arr and r are static arguments for go (already in scope, no 
less), so one would likely write go without them (it's certainly what I did 
initially). However, eliminating either one of them causes heap allocation 
and, thus, slowdowns (eliminating both is even worse).

So, I suppose my question is: will GHC be better at this than I am? :) Will it 
know that performing the transform on shift above would cause extra heap 
allocation/slowdowns? Will it know that transforming reverse (and go') is 
slower than not doing so (I suppose it may be suspicious that this is all 
low-level code, but I've tried fiddling with higher-level code that I know 
gets compiled to this sort of code, and the above results seemed to hold)?

I'm also not yet skilled enough at reading assembly to figure out what exactly 
is causing all this. Are values getting kicked out of registers or some such?

Cheers,
-- Dan