On 2008 Jul 11, at 19:46, Mitar wrote:

It is somehow award that passing function as an argument slow down the program so much. Is not Haskell a functional language and this such (functional) code reuse is one of its main points?

That is in fact the case; GHC's version of various Prelude functions refactors them to avoid passing functional arguments. IIRC the problem is that, while Haskell is indeed functional, passing a polymorphic function as an argument causes the runtime to have to look up which type is needed for every call, whereas if it's factored out it can be computed only once and (implicitly) let-bound. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

Hi! (I will reply propely later, I have a project to finish and GHC is playing me around and does not want to cooperate.) This project of mine is getting really interesting. Is like playing table tennis with GHC. Some time it gives a nice ball, sometimes I have to run around after it. But I just wanted to make a simple raycasting engine. Not debug GHC. But it is interesting - just I do not have time just know for playing the change code - compile - run on known input - check if time elapsed increased (I have to do this even when I am thinking that I am optimizing things or even when I am thinking that I am just refactoring code - moving constants to definitions...). And this is a slow process because every iteration runs for a few minutes. The next beautiful example in this series is this function for computing 4D Julia set fractal: julia4DFractal :: BasicReal -> World julia4DFractal param (x,y,z) = julia4D (Q (x / scale) (y / scale) (z / scale) param) iterations where c = (Q (-0.08) 0.0 (-0.8) (-0.03)) alphaBlue = VoxelColor 0 0 (2 / scale) (2 / scale) scale = fromIntegral sceneHeight / 1.8 threshold = 16 iterations = 100 :: Int julia4D _ 0 = (# alphaBlue, 1 #) -- point is (probably) not in the set julia4D q it | qMagnitudeSquared q > threshold = (# noColor, 1 #) -- point is in the set | otherwise = julia4D (qSquared q + c) (it - 1) where distance = scale * (qMagnitude qN) / (2 * (qMagnitude qN')) * log (qMagnitude qN) (# qN, qN' #) = disIter q (Q 1 0 0 0) iterations where disIter qn qn' 0 = (# qn, qn' #) disIter qn qn' i | qMagnitudeSquared qn > threshold = (# qn, qn' #) | otherwise = disIter (qSquared qn + c) (2 * qn * qn') (i - 1) Please observe that distance is never used. And this is also what GHC warns. But the trick is that with having this part of a code in there, the program virtually never finishes (I killed it after 15 minutes). If I remove everything on and after the "where distance" line it finishes in 30 seconds. OK, the problem is with (# qN, qN' #), if this is changed to normal (qN, qN'), then it works. But to notice this ... This is something you have to spend a day for. Mitar

Hi!

My guess is that it was premature optimization that created this bug.

It is the root of all evil. ;-)

Unboxed tuples are not the best answer for every situation. They are evaluated strictly!

Then I have not understood the last paragraph correctly: http://www.haskell.org/ghc/docs/latest/html/users_guide/primitives.html Oh, no. It is like you say. I also use -funbox-strict-fields and Q is defined with strict fields. But I tried also without the switch and is it the same (it takes forever). But then qN and qN' does not have unboxed types. So it should be lazy?

If you are in that phase where you are doing performance tweaks and you think GHC's strictness analysis might not be picking up on some strict behavior in your program, add the annotation. If it makes it faster, great; if it doesn't change things, take it out! Best to underconstrain your program.

I completely agree. I am also a firm believer in the clean and pure code where I would leave all optimization to compiler and just write semantics into a program. But this project just showed me that there is still a long way of compiler development before that would be possible (and usable). That some simple refactoring of code which is not really changing semantics have a big influence on a performance because compiler uses it differently (polymorphic types instead of hardcoded types, passing function as an parameter instead of hardcode it). For example I have now defined my types as: type BasicReal = Double data Quaternion = Q !BasicReal !BasicReal !BasicReal !BasicReal deriving (Eq,Show) So that I can easily change the type everywhere. But it would be much nicer to write: data Quaternion a = Q !a !a !a !a deriving (Eq,Show) Only the performance of Num instance functions of Quaternion is then quite worse. Mitar

Hi! On Fri, Jul 18, 2008 at 3:54 PM, Chaddaï Fouché wrote:

...

So that I can easily change the type everywhere. But it would be much nicer to write:

data Quaternion a = Q !a !a !a !a deriving (Eq,Show)

Only the performance of Num instance functions of Quaternion is then quite worse.

You can probably use a specialization pragma to get around that.

But why is this not automatic? If I use Quaternions of only one type in the whole program then why it does not make specialized version for it? At least with -O2 switch. Why exactly are polymorphic functions slower? Is not this just a question of type checking (and of writing portable/reusable code)? But later on in a compiler process we do know of which type exactly is the called function - so we could use a function as it would be written only for that type. Something what specialization is doing as I see. I thought this is always done. Mitar

ben.franksen:

Mitar wrote:

...

On Fri, Jul 18, 2008 at 3:54 PM, Chaddaï Fouché wrote:

...

...

So that I can easily change the type everywhere. But it would be much nicer to write:

data Quaternion a = Q !a !a !a !a deriving (Eq,Show)

Only the performance of Num instance functions of Quaternion is then quite worse.

You can probably use a specialization pragma to get around that.

But why is this not automatic? If I use Quaternions of only one type in the whole program then why it does not make specialized version for it? At least with -O2 switch.

You could try jhc: it does whole program optimization. Ghc compiles each module separately.

No need to switch compilers. GHC is able to do a pretty good job. Consider, data Q a = Q !a !a !a !a deriving (Eq,Show) -- yeah, polymorphic go :: Num a => Q a -> Q a go (Q 0 0 0 0) = Q 1 2 3 4 go (Q a b c d) = go $! Q (a * a) (b * b) (c * c) (d * d) -- ah, but we fix it. type QI = Q Int -- and try that: main = print (go (Q 2 3 7 13 :: QI)) GHC specialises and gives us, $wgo :: Int# -> Int# -> Int# -> Int# -> Q Int So just use ghc-core to check what you're getting. -- Don

2008/7/18 Mitar :

On Sat, Jul 12, 2008 at 3:33 AM, Max Bolingbroke wrote:

...

If findColor had been a function defined in terms of foldr rather than using explicit recursion, then theres a good chance GHC 6.9 would have fused it with the list to yield your optimized, loop unrolled, version:

My first version was with msum. Is this also covered by this fusion?

Note that as I said the fusion only applies to 6.9 onwards. However, assuming that you were using msum at the list monad then since msum = concat is defined in terms of foldr there is a chance it could happen. The best guide to this kind of thing is not asking me but rather looking at the Core output by GHC for your particular program.

(And it is interesting that my own recursion version is faster than the version with msum. Why?)

I don't know why you find this suprising :-). Your own version is specialized exactly for the situation you wish to use it for. msum is a generic combinator, which naturally makes it less amenable to optimization because there is less information available about it's usage pattern. Note that GHC will of course try to do its best to de-specialize the msum function for any particular scenario it's used in, through inlining etc, but there are no guarantees.

It is a little more tricky. I choose in an IO monad which scene it will render (selected by a program argument). So at compile time it does not yet know which one it will use. But there is a finite number of possibilities (in my case two) - why not inline both versions and at run time choose one?

If there was only one static occurance of each identifier in your module then it would do that. This is because there is no code size implications for inlining a function into it's unitary use site. Inlining is not a cure-all for performance though: if you inline too much then you increase code size and hence increase the amount of main memory you're reading and reduce instruction cache hits, not to mention fill up your disk with multi-MB binaries. Max

I had similar experiences as you when attempting to write "high performance Haskell"; the language makes you want to use high-level abstracted functions but the optimizer (while amazing, to be honest) seems to miss a few cases that it seems like it should hit. The problem seems to be that the compiler is extremely good at optimizing systems-level code, but that any "control-structure" function needs to be extremely inlined to be successful. You might try re-writing "sequence" or "foldM" a few different ways using the same "test" function and see what you can get. One thing that I notice about this code is that if you switch Right and Left you will get the default behavior for the Either monad: worldSceneSwitch point = case redSphere (0,50,0) 50 point of v@(Left _) -> v Right d1 -> case greenSphere (25,-250,0) 50 point of v@(Left _) -> v Right d2 -> Right $ d1 `min` d2 is the same as worldSceneSwitch point = do d1 <- redSphere (0, 50, 0) 50 point d2 <- greenSphere (25, -250, 0) 50 point Right (d1 `min` d2) Here is the same concept using foldM: minimumM (x : xs) = do v0 <- x foldM (return . min) v0 xs worldSceneSwitch point = minimumM [ redSphere (0, 50, 0) 50 point, greenSphere (25, -250, 0) 50 point ] However, the performance here will be terrible if minimumM and foldM do not get sufficiently inlined; you do not want to be allocating list thunks just to execute them shortly thereafter. -- ryan On Sat, Jul 19, 2008 at 6:48 AM, Mitar wrote:

Hi!

I had to change code somewhat. Now I have a function like:

worldScene point = case redSphere (0,50,0) 50 point of v@(Right _) -> v Left d1 -> case greenSphere (25,-250,0) 50 point of v@(Right _) -> v Left d2 -> Left $ d1 `min` d2

(Of course there could be more objects.)

Any suggestion how could I make this less hard-coded? Something which would take a list of objects (object functions) and then return a Right if any object function return Right or a minimum value of all Lefts. But that it would have similar performance? If not on my GHC version (6.8.3) on something newer (which uses fusion or something). Is there some standard function for this or should I write my own recursive function to run over a list of object functions? But I am afraid that this will be hard to optimize for compiler.

(It is important to notice that the order of executing object functions is not important so it could be a good candidate for parallelism.)

Mitar _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Done. http://hackage.haskell.org/trac/ghc/ticket/2465 -- ryan On 7/23/08, Simon Peyton-Jones wrote:

| I had similar experiences as you when attempting to write "high | performance Haskell"; the language makes you want to use high-level | abstracted functions but the optimizer (while amazing, to be honest) | seems to miss a few cases that it seems like it should hit.

Ryan, if you find any of these, do please submit them to GHC's Trac bug-tracker. There's a special category for performance bugs. Small programs of the form "GHC should hit this, but doesn't" are incredibly useful.

Thanks

Simon