On February 17, 2009 19:24:44 Max Bolingbroke wrote:

2009/2/17 Tyson Whitehead :

...

It also seems the extra levels of indirection are defeating the strictness analyzer on eta_s1CN in a_s1Gv as all code branches either directly force it or ultimately pass it to digit_s1l3 as in the included branch.

Also, why isn't digit_s1l3 optimized to take its first parameter unboxed? It is strict in its first argument, and grepping the core shows that it is only ever used like in lvl_s1mF (i.e., passed things like lvl_s1mG).

Yeah, that's weird. I don't know the answer to this. Have you actually got to the worker-wrapper stage at the point you copied this core?

Yes. You are right. Contrary to what the top of the email said, I created that output with -ddump-stranal, and -dshow-passes indicates that the worker- wrapper stage comes next. If I dump it (or just the final core with -ddump- simpl), digit* is entirely replaced with a first-argument-unboxed $wdigit*. The inner lambdas (i.e., the second and third arguments) remain boxed. It seems I should have just used the -ddump-simpl output instead of the - ddump-stranal output. I had just got thinking the the -ddump-simpl output did not include strictness analysis because I didn't see it on a bunch of the code (in retrospect, that was because that code was created by later stages) Cheers! -Tyson

2009/2/18 Tyson Whitehead :

On February 17, 2009 19:24:44 Max Bolingbroke wrote:

...

2009/2/17 Tyson Whitehead :

...

(compiled with ghc 6.10 with options -O2 -ddump-simpl)

That should have been -ddump-stranal instead of -ddump-simpl.

Right. Mystery solved. In case you were wondering, the reason the other two lambdas in "digit" are not worker/wrappered is because GHC only performs strictness analysis on lambdas that occur /immediately/ in the binding. So increasing the arity of digit is CRUCIAL to getting your program to compile well, as that will cause: * Strictness analysis on the inner lambdas * Inlining of lvl_s1mF * Fewer updateable thunks to be created by callers (as we won't try to cache the results of a partial application)

...

...

I was wondering why lvl_s1mF is not being inlined into a_s1Gv in the core at the bottom of this email as that is the only place it is ever referenced.

The relevant GHC code is SimplUtils.preInlineUnconditionally. It looks like it dosen't get inlined for two reasons: 1) It's not a manifest lambda (it's an application) so inlining inside another lambda would change the number of times the FVs of lvl_s1mF might occur

I have to confess my ignorance here as my google fu failed and so I still don't know what a manifest lambda is (other than not a application). : )

Sorry :-). Manifest lambdas are just lambdas that occur manifestly! So e.g.: f = \x -> g x HAS a manifest lambda, whereas: f' = g Does NOT have one. No lambda immediately starts the binding. Lambdas, manifest or otherwise, are important in this context because any value with a leading lambda is certainly very cheap and so can be inlined inside other lambdas - which is what you are trying to achieve with lvl_s1mF. (snip code and explanation)

I just finished adding the Parse q Int type to help with email line wrapping. As I alluded to in my original email, if I don't have the Int overflow check in digit, it is not chosen as the loop breaker, all the StateT stuff is compiled away, and you get a really nice efficient assembler loop (which is important because the final FSM has to actually chew through GBs of data).

The part of the code under the first lambda in digit is as follows (I didn't keep the original dump, so the uniques have changed here). It's the second part of the Int overflow bounds check (i.e., y <= (maxBound-x)`div`10), and, indeed, something you don't want to compute unless the easy check fails.

Yes - GHC wants to share the work of (maxBound-x)`div`10 between several partial applications of "digit". This is usually a good idea, but in this case it sucks because it's resulted in a massively increased arity. IMHO GHC should fix this by: * Marking divInt# INLINE in the base library. This would result in your code would just containing uses of quotInt# * Making some operations cheap even if they may fail (PrimOp.primpOpIsCheap should change). Though this might mean that we turn non-terminating programs into terminating ones (such operations get pushed inside lambdas) but this is consistent with our treatment of lambdas generally. Actually, your divInt# call wouldn't even usually be floated out to between two lambdas, but at the time FloatOut runs there is something in between the \x lambda and the lambdas from the state monad - the monadic bind operator! So FloatOut feels free to move the computation for "x" up even though that >>= will go away as soon as we run the simplifier. What a disaster! For me, making digit INLINE fixes all this, but that's probably because the context of my code is not the same as yours (I had to invent parts of a program to bind the bs, q and n variables). For your immediate problem, I would suggest this bit of GHC witchdoctory: where digit :: Int -> ParseInt Int Int digit !x = do !y <- lift get ( if y <= (maxBound-9)`quot`10 || y <= ghc_hacks then let !y' = y*10+x in (lift $ put y') >> s2 else throwError "integer overflow" ) where {-# INLINE ghc_hacks #-} ghc_hacks = (maxBound-x)`div`10 With luck, this should make the loop-invariant cheap in GHC's eyes, preventing it from trying to share it. It works for me - but like I say things may differ in your program.

...

In general, the -ddump-inlinings flag is useful for working out why something wasn't inlined - but it wouldn't have helped you in this case, because it only dumps information about inlining at call sites, and you actually want an unconditional inlining to occur.

I also tried that, and didn't have much luck with it. I didn't understand the output, which there was 48k lines worth of, and the uniques kept changing which made it hard to grep for names from previous -ddump-simpl runs.

Right. I tend to use -ddump-inilnings and -dverbose-core2core (or -ddump-simpl) together, and I have a little script that partitions the output up by the "=====" seperators. Then I can look at the output of a phase (which is split into it's own file) and if I see something that should have been inlined I can go to the output of the previous simplifier run (also in it's own file) and grep for it's name in the -ddump-inlinings output of that phase. This means you don't have to match uniques between two entierly seperate runs, although annoyingly the output format for identifier in -ddump-inlinings is slightly different from that in Core output so grepping is not as easy as it could be. If you are interested in trying my script, it's available via Git at http://github.com/batterseapower/scripts/blob/da1f24ba16c27e3994aa66f9db352e... and is called as "ghc-dump-split ghc-dump-file", where ghc-dump-file results from redirection of GHC stdout+stderr to a file. Hope all that helps, Max

On February 18, 2009 04:29:42 Max Bolingbroke wrote:

...

The part of the code under the first lambda in digit is as follows (I didn't keep the original dump, so the uniques have changed here). It's the second part of the Int overflow bounds check (i.e., y <= (maxBound-x)`div`10), and, indeed, something you don't want to compute unless the easy check fails.

Yes - GHC wants to share the work of (maxBound-x)`div`10 between several partial applications of "digit". This is usually a good idea, but in this case it sucks because it's resulted in a massively increased arity. IMHO GHC should fix this by: * Marking divInt# INLINE in the base library. This would result in your code would just containing uses of quotInt# * Making some operations cheap even if they may fail (PrimOp.primpOpIsCheap should change). Though this might mean that we turn non-terminating programs into terminating ones (such operations get pushed inside lambdas) but this is consistent with our treatment of lambdas generally.

Reading your response got me thinking, "quot and div, I thought I had changed everything to quot because earlier I found that GHC was leaving evaluation of constant expressions like "maxBound-9`div`10" until runtime if I used div." Turns out I had missed that one in the second bounds check, and changing it from "y <= (maxBound-x)`div`10" to "y <= (maxBound-x)`qout`10" resulted in GHC "just doing the right thing". I presume this is because quot must be either marked INLINE and/or primOpIsCheap like you said div should be. I am guess this is because quot maps directly onto the x86 idiv instruction due to both of them truncating towards zero, while div, with its truncation towards negative infinity, does not. Running with -ddump-asm seems to back this up as quotInt# compiles down to an idiv instruction and divInt# to a call through base_GHCziBase_divIntzh_info. Unfortunately for me, I always seem to instinctively go with div and mod ahead of quot and rem.

Actually, your divInt# call wouldn't even usually be floated out to between two lambdas, but at the time FloatOut runs there is something in between the \x lambda and the lambdas from the state monad - the monadic bind operator! So FloatOut feels free to move the computation for "x" up even though that >>= will go away as soon as we run the simplifier. What a disaster!

I would like to try combining the GHC optimizer with a genetic algorithm so you could set it to pound away on your core loops for an hour or so to find the right sequence of ghc optimization steps to generate the tightest code. Maybe it could then write out an optimization hint file that regular GHC could optionally take in for use alongside the standard rules of thumb to produce great code. All I need is more time and more knowledge. Maybe someday. : )

For me, making digit INLINE fixes all this, but that's probably because the context of my code is not the same as yours (I had to invent parts of a program to bind the bs, q and n variables).

Sorry about that. I've put the entire routine at http://www.sharcnet.ca/~tyson/haskell/Example1.hs I should have done this in the first place as it allows me to provide the full code while also stripping it down in the emails to make them more readable.

For your immediate problem, I would suggest this bit of GHC witchdoctory:

where digit :: Int -> ParseInt Int Int digit !x = do !y <- lift get ( if y <= (maxBound-9)`quot`10 || y <= ghc_hacks then let !y' = y*10+x in (lift $ put y') >> s2 else throwError "integer overflow" ) where {-# INLINE ghc_hacks #-} ghc_hacks = (maxBound-x)`div`10

With luck, this should make the loop-invariant cheap in GHC's eyes, preventing it from trying to share it. It works for me - but like I say things may differ in your program.

I tried that as well, and am pleased to report that it works great. I think I actually understand what is going on here and will hopefully be able to wield it in the future to my advantage. Generally I've had very little luck with the INLINE hammer when the function is at all complex. GHC always seems to finds a way to thwart my pathetic attempts and punish me with even worse code (like then not inlining the monad bind operation in the code resulting from the inlining). : )

If you are interested in trying my script, it's available via Git at http://github.com/batterseapower/scripts/blob/da1f24ba16c27e3994aa66f9db352 ec1102c39d2/ghc-dump-split and is called as "ghc-dump-split ghc-dump-file", where ghc-dump-file results from redirection of GHC stdout+stderr to a file.

I'll grab a copy of that. : )

Hope all that helps,

It sure did. Thanks very much for all your time! I'm really impressed with GHC and the people hacking on it. I've actually managed to get it to produce some truly tight assembler. It's also great, unlike a lot of projects, having papers that you can read on many details. Thanks again! -Tyson

I was surprised to see this case expression:

case GHC.Prim.-# 9223372036854775807 ipv_s1bD of wild2_a1xi [ALWAYS Just L] {

What is the purpose to compare the value with maxBound before the division? The case expression doesn't disappear even if I use quot instead of div. Krasimir 2009/2/18 Tyson Whitehead :

digit_s1lk = \ (x_aqR [ALWAYS Just U(L)] :: GHC.Types.Int) -> case x_aqR of x_XsQ [ALWAYS Just A] { GHC.Types.I# ipv_s1bD [ALWAYS Just L] -> let { lvl_s1my [ALWAYS Just D(T)] :: GHC.Types.Int [Str: DmdType] lvl_s1my = case GHC.Prim.-# 9223372036854775807 ipv_s1bD of wild2_a1xi [ALWAYS Just L] { __DEFAULT -> case GHC.Base.divInt# wild2_a1xi 10 of wild21_a1xj [ALWAYS Just L] { __DEFAULT -> GHC.Types.I# wild21_a1xj }; (-9223372036854775808) -> case GHC.Base.divInt# (-9223372036854775808) 10 of wild21_a1xl [ALWAYS Just L] { __DEFAULT -> GHC.Types.I# wild21_a1xl } } } in (\ (eta_X1sU [ALWAYS Just L] :: GHC.Types.Int) (eta_s1G7 [ALWAYS Just U(L)] :: GHC.Types.Int) ->

Oh. I looked at the primops.txt.pp for something suspicious but I didn't checked the actual implementation of quot. I thought that quot calls quotInt# directly. When I use quotInt in the code I can get the real idiv assembly instruction. Still the code generated by GHC is strange it doesn't throw any exception actually. It just evaluates the same expression but with the constant maxBound. On Thu, Feb 19, 2009 at 11:19 PM, Max Bolingbroke wrote:

2009/2/19 Krasimir Angelov :

...

I was surprised to see this case expression:

...

case GHC.Prim.-# 9223372036854775807 ipv_s1bD of wild2_a1xi [ALWAYS Just L] {

What is the purpose to compare the value with maxBound before the division? The case expression doesn't disappear even if I use quot instead of div.

Have a look at this snippet of the base library, file GHC/Real.lhs:

a `quot` b | b == 0 = divZeroError | a == minBound && b == (-1) = overflowError | otherwise = a `quotInt` b

quotInt is defined in GHC/Base.lhs as:

(I# x) `quotInt` (I# y) = I# (x `quotInt#` y)

And quotInt# is a primitive, which I guess is implemented via machine division (though I don't work on the codegen stuff at all) - so your offending case must come from those tests in GHC/Real.lhs.

In general, if you want to answer questions like this you can usually find the answer by looking at the base code: it's all in Haskell, so very readable! You can get it online at http://darcs.haskell.org/libraries/base/GHC/

Cheers, Max

I think that what happens is that this function: a `quot` b | b == 0 = divZeroError | a == minBound && b == (-1) = overflowError | otherwise = a `quotInt` b is expanded to: a `quot` b = if b == 0 then divZeroError else if a == minBound then if b == (-1) then overflowError else a `quotInt` b else a `quotInt` b Then the compiler sees that b is a constant and computes that b == 0 is False and b == (-1) is also False so it could eliminate two If statements. The result is: a `quot` b = if a == minBound then a `quotInt` b else a `quotInt` b and this is exactly what we get. I bet that if the original function was: a `quot` b | b == 0 = divZeroError | b == (-1) && a == minBound = overflowError -- Note the changed order here | otherwise = a `quotInt` b then we would get what we want. I think that it is much more often to have division where the divisor is known so we will get the best code in this case. Regards, Krasimir On Fri, Feb 20, 2009 at 4:00 AM, Tyson Whitehead wrote:

On February 19, 2009 18:20:33 Krasimir Angelov wrote:

...

Oh. I looked at the primops.txt.pp for something suspicious but I didn't checked the actual implementation of quot. I thought that quot calls quotInt# directly. When I use quotInt in the code I can get the real idiv assembly instruction. Still the code generated by GHC is strange it doesn't throw any exception actually. It just evaluates the same expression but with the constant maxBound.

On Thu, Feb 19, 2009 at 11:19 PM, Max Bolingbroke

...

a `quot` b

| b == 0 = divZeroError | a == minBound && b == (-1) = overflowError | otherwise = a `quotInt` b

I checked the quot one like you said. Kind of strange all right.

It looks like it is performing the a == minBound check (where a = maxBound-x) despite the b == (-1) check (where b = 10) being optimized away.

Cheers! -Tyson

Well I actually did, almost. I added this function: quotX :: Int -> Int -> Int a `quotX` b | b == 0 = error "divZeroError" | b == (-1) && a == minBound = error "overflowError" | otherwise = a `quotInt` b It does the right thing. However to be sure that this doesn't interfere with some other GHC magic the real quot function have to be changed and tested. I haven't build GHC from source for 2-3 years now and I don't have the time to do it just to test whether this works. Regards, Krasimir On Fri, Feb 20, 2009 at 9:22 AM, Bulat Ziganshin wrote:

Hello Krasimir,

Friday, February 20, 2009, 11:00:30 AM, you wrote:

...

and this is exactly what we get. I bet that if the original function was:

well, you check this yourself! :)

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

How mod is affected by the change in quot? Currently mod is defined as: a `mod` b | b == 0 = divZeroError | a == minBound && b == (-1) = overflowError | otherwise = a `modInt` b and modInt is defined via remInt# which is primitive. Did you change the definition of mod as well? I agree that this change in the definition of quot is just a workaround. The best solution would be to do something clever in the compiler itself. For now if someone wants fast division then he/she should use quotInt. On Sat, Feb 21, 2009 at 9:52 AM, Bertram Felgenhauer wrote:

Krasimir Angelov wrote:

...

Well I actually did, almost. I added this function:

quotX :: Int -> Int -> Int a `quotX` b | b == 0 = error "divZeroError" | b == (-1) && a == minBound = error "overflowError" | otherwise = a `quotInt` b

It does the right thing. However to be sure that this doesn't interfere with some other GHC magic the real quot function have to be changed and tested. I haven't build GHC from source for 2-3 years now and I don't have the time to do it just to test whether this works.

It works, and it has the desired effect. It's not always a win though; the nofib prime sieve benchmark suffers.

For a patch, see http://int-e.home.tlink.de/haskell/ghc-libraries-base-tune-division.patch

Nofib results extract:

------------------------------------------------------------------------ Program Size Allocs Runtime Elapsed ------------------------------------------------------------------------ fish -0.7% -5.3% 0.05 0.04 primes -0.0% +28.5% +25.6% +25.5% wheel-sieve2 -0.0% -0.3% -17.9% -18.6% ------------------------------------------------------------------------ Min -0.9% -5.3% -17.9% -18.6% Max +0.1% +28.5% +25.6% +25.5% Geometric Mean -0.2% +0.2% -0.0% +0.2%

'primes' is an outlier - the other slowdowns are below 3%

What happens in 'primes' is that 'mod' no longer gets inlined; apparently it now looks bigger to the compiler than before.

Using -funfolding-use-threshold=10 brings the benchmark back to its original speed, despite the extra comparison before doing the division.

In 'wheel-sieve2', the first different optimization choice I see is again a 'mod' that is no longer inlined; this leads to a change in other inlining choices that result in a speedup for reasons that I have not investigated.

Bertram _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users