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

On Friday 20 June 2008, Max Bolingbroke wrote:

Of course, if you have any suggestions for good heuristics based on your benchmarking experience then we would like to hear them! There was some discussion of this in the original ticket, http://hackage.haskell.org/trac/ghc/ticket/888, but when implementing SAT I tried out the suggestions made there without good results (though to be perfectly honest I didn't really understand the motivations behind some of the suggestions made).

Well, as I said, I was apparently being over-aggressive in my manual application of the transform, so I'm not yet the best person to ask, I suppose. :) However, if I had to pick something out of the air, I'd say this: always do SAT when the argument in question is a function. This is actually the reason I started doing it in the first place. I was working on sorting uvectors, and had what I thought was pretty good performance, and then I did SAT on the comparison function, and suddenly my code was running in half the time. Going back to my sorting (testing on introsort), SAT for the array doesn't seem to do much, but undoing the SAT for the comparison function causes heap allocation to balloon, and everything gets at least a factor of 2 slower. This also seems to match the other manual uses of SAT I've seen in the past. For instance, in the GHC libraries you'll see: foldr f = go where go z (x:xs) = f x (go z xs) go z [ ] = z because it's significantly faster, while earlier in this thread, SPJ said that: xs ++ ys = let go [ ] = ys go (z:zs) = z : go zs in go xs isn't much of a win. I don't have much data currently, but the places I *know* it's been a win have been SAT on functions, while the places I *know* it's been a loss have been SAT on unboxed data. Whether this is because SAT allows more opportunity for inlining/specialization on functions, or because copying functions is inherently more expensive, though, I don't know. I'll keep an eye open from now on, though. (On an additional tentative note, undoing SAT in the first example of my last mail seemed to eliminate the difference between the native code generator and -fvia-c -optc-O3. So whatever SAT was doing to make the code slower (no extra heap allocation, just slower code), GCC may have been fixing. My off-the-top-of-the-head guess was that passing the arguments along kept them in registers, and maybe GCC was putting the SATed arguments back into registers, but as I said, I don't currently have the expertise to verify that.) Cheers, -- Dan

2008/6/22 Simon Peyton-Jones :

| However, if I had to pick something out of the air, I'd say this: always do | SAT when the argument in question is a function.

Yes, that might well be a good heuristic to try, if you are interested to pursue this, Max. Making the function static means that it may be inlined, and that can make a tremendous difference by specializing the loop for that particular function. But that in turn only tends to happen if the enclosing function is inlined. Consider foldr: the real payoff comes when foldr is inlined, so that the function at the call site becomes visible.

I spent quite a bit of time today playing with various heuristics for the SAT including the one suggested above (which I agree sounded promising) but didn't make much progress. The best results were obtained by applying the SAT when: 1) At least two arguments are static, whatever their types 2) Or if at least one of the static arguments is a function type and the SATed functions right hand side is small enough to inline 3) As long as the function is not likely to be compiled as a tail call (because we effectively get staticness there by carrying arguments on the stack) If you just use criteria 2 then you get some bad worst cases in runtime (e.g. Para.dropTail and Constraints.initTree) because the additional inlining opportunity was not utilised enough to overcome the heap allocation cost. If you don't SAT functions that have only non-function static arguments then some other worst cases crop up (e.g. Rsa.power) where we actually quite want to do it. However this represents only a 0.3% decrease in allocations and runtime from the previous heuristic for nofib! Furthermore, it was necessary to run the SAT twice in the compiler pipeline to catch both those functions that only become tail calls after e.g. the let-to-case transform AND to identify the extra common subexpressions producted by SAT early enough that they could have good use made of them by later compiler passes. I'm not particularly happy with the tail call criterion because it's quite fragile to make inferences about how the function will be treated by codegen as early in the pipeline as SAT is running. So in summary I don't think this change is worth integrating. Cheers, Max

On Monday 23 June 2008, Isaac Dupree wrote:

there's no chance for the lower-level near code generation to reverse-SAT to eliminate the heap usage? (which would obviously be a different optimization that might be useful in other ways too, if it could be made to work) (did someone say that -fvia-C with gcc -O3 managed to do that sometimes?)

I said something similar, but I don't actually know the details. What I have is a SAT and non-SAT version of a benchmark: ---- SAT ---- 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 = go'' where go'' 0# s = (# s, () #) go'' k s = case reverse arr 0# (n -# 1#) s of { s -> go'' (k -# 1#) s } reverse :: MutableByteArray# s -> Int# -> Int# -> State# s -> State# s reverse arr = go where go 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 -> go (i +# 1#) (j -# 1#) s } } } } | otherwise = s ---- non-SAT ---- 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 In the SAT version, the native code generator is noticeably slower than -fvia-c -optc-O3, so the latter is doing something right. In the non-SAT version, -fvia-c is somewhat faster than the SAT version, but the NCG is just as fast. I don't know what's going on on the C end in the first case that makes it better, though (heap allocation is the same (low) in all cases; via-c doesn't fix large heap allocation when it happens in my experience). As an aside, I finally got around to compiling 6.9 from a day or so ago, and noticed that one of the functions I'd mentioned earlier does get SATed to the bad version (which causes lots of heap allocation in the program) because it has two static arguments. However, marking it NOINLINE seemed to keep it from having the negative effects. Does that pragma keep SAT from doing its thing, and if so, will that continue to be viable in cases where we decide we know better than GHC? Cheers, -- Dan

2008/6/23 Dan Doel :

On Monday 23 June 2008, Isaac Dupree wrote:

...

there's no chance for the lower-level near code generation to reverse-SAT to eliminate the heap usage? (which would obviously be a different optimization that might be useful in other ways too, if it could be made to work) (did someone say that -fvia-C with gcc -O3 managed to do that sometimes?)

I said something similar, but I don't actually know the details. What I have is a SAT and non-SAT version of a benchmark:

In the SAT version, the native code generator is noticeably slower than -fvia-c -optc-O3, so the latter is doing something right. In the non-SAT version, -fvia-c is somewhat faster than the SAT version, but the NCG is just as fast. I don't know what's going on on the C end in the first case that makes it better, though (heap allocation is the same (low) in all cases; via-c doesn't fix large heap allocation when it happens in my experience).

I've tested this on my own machine (i386-apple-darwin) and I can't replicate it. For me (with 6.8.2), the SATed version is faster by almost 40%, and there is no essentially no difference between the NCG and GCC (GCC is maybe a fraction faster). In any event GHC will not automatically SAT this function because it has only one static argument. Indeed, I'm not quite sure why it should be faster with SAT at all, and my assembly-fu is still too weak to be able to work it out from the code generator output.

As an aside, I finally got around to compiling 6.9 from a day or so ago, and noticed that one of the functions I'd mentioned earlier does get SATed to the bad version (which causes lots of heap allocation in the program) because it has two static arguments.

I devoted yesterday entirely to SAT and came up with some refinements to my earlier heuristics which shave a couple of percent of allocations and runtime off of nofib compared with the existing ones, and also resolve this problem. I found that my tail call detection from the day before was a bit broken. Now that it is fixed I use it to avoid SATing functions which make tail calls, but with the important wrinkle that if the function has static function parameters we should SAT it anyway because this lets us do much more inlining and is a bigger win than avoiding allocation. This criterion avoids the heap allocation you are experiencing in your particular example. I've also added rule generation to rewrite instances of functions that are SATed purely because they have static function parameters back into the non-SATed versions if they do not experience inlinig. This prevents the worst cases that I got before when always SATing functions with static function parameters. What's more, I've found that most if not all SAT opportunities are found early in the pipeline by these new criteria, so we can get away with just one SAT pass instead of the two I reported earlier. All in all, these developments are pretty promising and I suspect I'll be able to integrate them into HEAD in time for 6.10, which will hopefully alleviate some of your worries about the efficacy of SAT. Cheers, Max