Hi John, Any chance of seeing the benchmark? You're not the only one with an optimising compiler tucked away somewhere :-) I have one "benchmark" where I outperform GHC by 21 times, although saying it's artificial is a bit of an understatement... Thanks, Neil On Fri, Mar 26, 2010 at 6:27 PM, John Meacham wrote:

Here are jhc's timings for the same programs on my machine. gcc and ghc both used -O3 and jhc had its full standard optimizations turned on.

jhc: ./hs.out  5.12s user 0.07s system 96% cpu 5.380 total

gcc: ./a.out  5.58s user 0.00s system 97% cpu 5.710 total

ghc: ./try  31.11s user 0.00s system 96% cpu 32.200 total

As you can see, jhc shines at this example, actually beating gcc -O3. It isn't too surprising, this is exactly the sort of haskell code that jhc excels at.

       John

-- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

John Meacham wrote:

Here are jhc's timings for the same programs on my machine. gcc and ghc both used -O3 and jhc had its full standard optimizations turned on.

jhc: ./hs.out 5.12s user 0.07s system 96% cpu 5.380 total

gcc: ./a.out 5.58s user 0.00s system 97% cpu 5.710 total

ghc: ./try 31.11s user 0.00s system 96% cpu 32.200 total

As you can see, jhc shines at this example, actually beating gcc -O3. It isn't too surprising, this is exactly the sort of haskell code that jhc excels at.

What's the property of that code which makes jhc excels in it? What makes ghc perform so poorly in comparison?

Lennart Augustsson wrote:

It's important to switch from mod to rem. This can be done by a simple abstract interpretation. I'm nore sure if it's jhc or gcc that does this for jhc.

It's not just adding rem. Ghc still runs much slower using rem. It's only when switching to -fvia-C and using rem that ghc gets close to gcc speed (even though, still slower). Now jhc seems to get it fast right away. What's going on here? Is ghc backend wrose than using gcc as a backend (which is what via-C seems to accomplish)? Are there cases when one way is preferred over the other? What are the tradeoffs here?

Does anything change if you swap the first two rhss? On Sun, Mar 28, 2010 at 1:28 AM, Roman Leshchinskiy wrote:

On 28/03/2010, at 09:47, Lennart Augustsson wrote:

...

It's important to switch from mod to rem.  This can be done by a simple abstract interpretation.

Also, changing the definition of rem from

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

to

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

speeds up the GHC version by about 20%. Figuring out why is left as an exercise to the reader :-)

Roman

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

On Sat, Mar 27, 2010 at 07:30:30PM -0300, Rafael Cunha de Almeida wrote:

John Meacham wrote:

...

Here are jhc's timings for the same programs on my machine. gcc and ghc both used -O3 and jhc had its full standard optimizations turned on.

jhc: ./hs.out 5.12s user 0.07s system 96% cpu 5.380 total

gcc: ./a.out 5.58s user 0.00s system 97% cpu 5.710 total

ghc: ./try 31.11s user 0.00s system 96% cpu 32.200 total

As you can see, jhc shines at this example, actually beating gcc -O3. It isn't too surprising, this is exactly the sort of haskell code that jhc excels at.

I have not thoroughly checked it, but I think there are a couple things going on here: jhc is able to determine that all the arguments to the various functions are strict, so it can avoid all heap allocations and evaluations. ghc also benefits from this optimization. jhc sees that all the functions are fully applied to all their arguments, this means that they can always be directly called with optimized calling conventions as they will never have to represent generic 'eval' thunks or partial applications. it sees that all the functions are local to 'main' and not exported, so it can actually translate them to local functions in main in grin, allowing some more useful optimizations. Now the most important one, after optimizing the local functions, jhc sees that they are only called in tail-call position, so jhc is able to turn the function calls into direct jumps, turning them directly into C while/for loops operating fully on automatic variables on the stack. These last two optimizations are enabled by an incredibly useful extension to boquist's GRIN which is to allow a form of local function definitions, which solve a number of issues raised in his paper. Via a series of Grin->Grin transformations I am able to turn these local funciton definitions into direct conditional jumps in the resulting code. (which translate to looping constructs, if's and goto's in C) John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/

On 27/03/2010, at 05:27, John Meacham wrote:

Here are jhc's timings for the same programs on my machine. gcc and ghc both used -O3 and jhc had its full standard optimizations turned on.

jhc: ./hs.out 5.12s user 0.07s system 96% cpu 5.380 total

gcc: ./a.out 5.58s user 0.00s system 97% cpu 5.710 total

ghc: ./try 31.11s user 0.00s system 96% cpu 32.200 total

I really don't understand these GHC numbers. I get about 3s for the C version, about 5s for GHC with rem and about 7.5s for GHC with mod. Is this perhaps on a 64-bit system? What is sizeof(int) in C and sizeOf (undefined :: Int) in Haskell? That said, I suspect the only thing this benchmark really measures is how fast the various compilers can compute i * i + j * j + k * k `mod` 7. Roman

On Fri, Mar 26, 2010 at 2:33 PM, Bryan O'Sullivan wrote:

On Fri, Mar 26, 2010 at 10:46 AM, Rafael Cunha de Almeida < almeidaraf@gmail.com> wrote:

...

During a talk with a friend I came up with two programs, one written in C and another in haskell.

Your Haskell code builds a huge thunked accumulator value, so of course it's slow (put bang patterns on all arguments). Also, you should use rem instead of mod. Make those tiny changes and you'll get a 5x speedup, to half the performance of the C code.

Interesting. I had to add -fvia-C to get within half the performance of C. Just bang patterns and rem and I'm 1/5th of C. I'm on a x86_64 machine. I wonder if that plays in. Jason

On Fri, Mar 26, 2010 at 6:16 PM, Felipe Lessa wrote:

I'd guess that the LLVM backend could generate code that is at least as fast as gcc. It would be nice if you could test it.

NCG done with GHC 6.12.1 w/ -O3 LLVM using a version of HEAD w/ -O3 GCC version 4.4.3 w/ -O3 Please take note Johns benchmark of JHC showing it beats everything here (including C). Also note -Odph did not alter performance from -O3. [tommd@Mavlo Test]$ time ./blahC 143 real 0m4.124s user 0m4.032s sys 0m0.013s [tommd@Mavlo Test]$ time ./blahLLVM 143 real 0m5.045s user 0m4.984s sys 0m0.006s [tommd@Mavlo Test]$ time ./blahNCG 143 real 0m5.960s user 0m5.872s sys 0m0.008s Cheers, Thomas

Using bang patterns didn't help almost anything here. Using rem instead of mod made the time go from 45s to 40s. Now, using -fvia-C really helped (when I used rem but not using mod). It went down to 10s.

Bang patterns should have helped tons - it isn't GHC thats at fault here and yes it does tco. I attached a version w/ excessive bangs below. Did you compile with "ghc --make -O3 -fforce-recomp"? Cheers, Thomas main = print $ rangeI 0 0 rangeK :: Int -> Int -> Int -> Int -> Int rangeK !i !j !k !acc = if k < 1000 then if i * i + j * j + k * k `rem` 7 == 0 then rangeK i j (k+1) (acc+1) else rangeK i j (k+1) acc else acc rangeJ :: Int -> Int -> Int -> Int rangeJ !i !j !acc = if j < 1000 then rangeJ i (j+1) (acc + rangeK i j 0 0) else acc rangeI :: Int -> Int -> Int rangeI !i !acc = if i < 1000 then rangeI (i+1) (acc + (rangeJ i 0 0)) else acc

David Menendez wrote:

On Sat, Mar 27, 2010 at 12:56 AM, Thomas DuBuisson wrote:

...

...

Using bang patterns didn't help almost anything here. Using rem instead of mod made the time go from 45s to 40s. Now, using -fvia-C really helped (when I used rem but not using mod). It went down to 10s. Bang patterns should have helped tons - it isn't GHC thats at fault here and yes it does tco. I attached a version w/ excessive bangs below. Did you compile with "ghc --make -O3 -fforce-recomp"?

Does -O3 actually do anything? GHC only goes up to -O2.

Well GHC has an -O3[1], but it's not a good idea to use it. Some of the "optimizations" that -O3 does can result in slower code for particular programs. Whereas -O2 is safe and never results in pessimizations. [1] Unless recent versions have removed it. -- Live well, ~wren

On Fri, 26 Mar 2010 21:56:16 -0700, Thomas DuBuisson wrote:

...

Using bang patterns didn't help almost anything here. Using rem instead of mod made the time go from 45s to 40s. Now, using -fvia-C really helped (when I used rem but not using mod). It went down to 10s.

Bang patterns should have helped tons - it isn't GHC thats at fault here and yes it does tco. I attached a version w/ excessive bangs below. Did you compile with "ghc --make -O3 -fforce-recomp"?

I can verify that it is not bang patterns that helped, it is an issue related to `mod' vs. `rem'. mod w/o bang: 30.73s user 0.15s system 99% cpu 30.954 total rem w/o bang: 6.52s user 0.00s system 99% cpu 6.528 total mod w/ bang: 30.53s user 0.25s system 99% cpu 30.878 total rem w/ bang: 6.34s user 0.00s system 99% cpu 6.359 total Compiled with: ghc --make -fexcess-precision -funbox-strict-fields -O3 -Wall -optc-O3 -optc-march=native -optl-Wl,-s -fvia-c -fforce-recomp test.hs -o test-hs And for comparison, c version: 4.35s user 0.04s system 99% cpu 4.403 total Linux 2.6.33-ARCH #1 SMP PREEMPT Mon Mar 15 19:11:52 CET 2010 x86_64 GenuineIntel GNU/Linux Best, jxy -- J c/* __o/* X <\ * (__ Y */\ <

On Sat, Mar 27, 2010 at 12:43 AM, Rafael Almeida wrote:

On Fri, Mar 26, 2010 at 6:49 PM, Jason Dagit wrote:

...

On Fri, Mar 26, 2010 at 2:33 PM, Bryan O'Sullivan wrote:

...

On Fri, Mar 26, 2010 at 10:46 AM, Rafael Cunha de Almeida wrote:

...

During a talk with a friend I came up with two programs, one written in C and another in haskell.

Your Haskell code builds a huge thunked accumulator value, so of course it's slow (put bang patterns on all arguments). Also, you should use rem instead of mod. Make those tiny changes and you'll get a 5x speedup, to

half

...

...

the performance of the C code.

Interesting. I had to add -fvia-C to get within half the performance of C. Just bang patterns and rem and I'm 1/5th of C. I'm on a x86_64 machine. I wonder if that plays in.

Jason

Using bang patterns didn't help almost anything here. Using rem instead of mod made the time go from 45s to 40s. Now, using -fvia-C really helped (when I used rem but not using mod). It went down to 10s.

It's worth pointing out that there's a bit of bang-pattern mysticism going on in this conversation (which has not been uncommon of late!). A non-buggy strictness analyzer should expose the strictness of these functions without difficulty. If bang patterns make any difference at all with a -O flag, either there's a strictness analysis bug, or some very interesting effects from shifting the order of forcing of strict variables. Putting in bang patterns is a good idea to plug the obvious space leak when run without optimization, but isn't going to make a difference for optimizing compilation of obviously-strict functions. -Jan-Willem Maessen

On Sat, Mar 27, 2010 at 1:45 PM, Tillmann Rendel wrote:

Jan-Willem Maessen wrote:

...

It's worth pointing out that there's a bit of bang-pattern mysticism going on in this conversation (which has not been uncommon of late!).  A non-buggy strictness analyzer should expose the strictness of these functions without difficulty.

Could the result of strictness analysis reported in terms of the original Haskell program?

That would be nice. Even if you're willing to read core, I'm not aware that the output of -ddump-stranal is explained anywhere. Incidentally, the results of -ddump-simpl when running on -O2 say that GHC has unboxed every argument except the first argument to rangeJ. -- Dave Menendez http://www.eyrie.org/~zednenem/

On Sat, Mar 27, 2010 at 8:16 PM, Roman Leshchinskiy wrote:

On 28/03/2010, at 01:36, Jan-Willem Maessen wrote:

...

It's worth pointing out that there's a bit of bang-pattern mysticism going on in this conversation (which has not been uncommon of late!). A non-buggy strictness analyzer should expose the strictness of these functions without difficulty.

Actually, rangeJ is lazy in i and rangeK is lazy in i and j. GHC does unbox everything important here but that needs more optimisations than just strictness analysis. You are right, though, that GHC doesn't need bang patterns here.

Quite right, the condition in rangeK that mentions all variables is under another condition: rangeK :: Int -> Int -> Int -> Int -> Int rangeK i j k acc | k < 1000 = if i * i + j * j + k * k `mod` 7 == 0 ... So we need to apply some constructor specialization as well to notice that i and j are always of the form (Int# i#). -Jan Roman

On Fri, Mar 26, 2010 at 10:42 PM, Bernie Pope wrote:

On 27 March 2010 04:46, Rafael Cunha de Almeida wrote:

...

During a talk with a friend I came up with two programs, one written in C and another in haskell.

snip

...

The Haskell version: real    0m45.335s user    0m45.275s sys     0m0.004s

against the C version: real    0m6.021s user    0m6.004s sys     0m0.004s

Could you please report which version of each compiler, which operating system, and which CPU?

My operating system is a Debian Lenny GNU/Linux, my CPU is: $ grep 'model name' /proc/cpuinfo model name : Intel(R) Core(TM)2 Duo CPU T5550 @ 1.83GHz I'm using ghc 6.8.2 and gcc 4.3.2, both from lenny package. I tried the same code with ghc 6.12.1 and the result was the same: real 0m45.121s user 0m45.075s sys 0m0.000s