Re: [Haskell-cafe] newbie optimization question
Ryan Dickie wrote: One thing I've noticed is that turning on optimizations significantly increases the speed of haskell code. Are you comparing code between languages with -O2 or without opts? I had done no optimization, but neither -O nor -O2 make a significant difference in either the C or Haskell programs. But using `rem` instead of `mod`, together with the type annotation, makes the two programs take pretty much the same amount of time. --PR ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] newbie optimization question
For the purposes of learning, I am trying to optimize some variation of the following code for computing all perfect numbers less than 1. divisors i = [j | j-[1..i-1], i `mod` j == 0] main = print [i | i-[1..1], i == sum (divisors i)] I know this is mathematically stupid, but the point is to do a moderate nested-loops computation. On my 2.33GHz dual-core MacBookPro, the obvious C program takes about .3 seconds, and a compiled OCaML program (tail recursion, no lists) about .33 seconds. The above takes about 4 seconds. I've tried using foldl', and doing explicit tail recursion with strict accumulators, but I can't get the running time below 3 seconds. Is it possible to come within striking distance of the other languages? Thanks. --PR ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
On 10/28/07, Prabhakar Ragde [EMAIL PROTECTED] wrote: For the purposes of learning, I am trying to optimize some variation of the following code for computing all perfect numbers less than 1. divisors i = [j | j-[1..i-1], i `mod` j == 0] main = print [i | i-[1..1], i == sum (divisors i)] I know this is mathematically stupid, but the point is to do a moderate nested-loops computation. On my 2.33GHz dual-core MacBookPro, the obvious C program takes about .3 seconds, and a compiled OCaML program (tail recursion, no lists) about .33 seconds. The above takes about 4 seconds. You could try giving divisors type signature: divisors :: Int - [Int] I've tried using foldl', and doing explicit tail recursion with strict accumulators, but I can't get the running time below 3 seconds. Is it possible to come within striking distance of the other languages? Thanks. --PR ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
Jaak Randmets wrote: On 10/28/07, Prabhakar Ragde [EMAIL PROTECTED] wrote: For the purposes of learning, I am trying to optimize some variation of the following code for computing all perfect numbers less than 1. divisors i = [j | j-[1..i-1], i `mod` j == 0] main = print [i | i-[1..1], i == sum (divisors i)] I know this is mathematically stupid, but the point is to do a moderate nested-loops computation. On my 2.33GHz dual-core MacBookPro, the obvious C program takes about .3 seconds, and a compiled OCaML program (tail recursion, no lists) about .33 seconds. The above takes about 4 seconds. You could try giving divisors type signature: divisors :: Int - [Int] Thank you. That brings the time down to 0.5 seconds. I'm glad it was something as simple as that. --PR ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
Prabhakar Ragde writes: For the purposes of learning, I am trying to optimize some variation of the following code for computing all perfect numbers less than 1. divisors i = [j | j-[1..i-1], i `mod` j == 0] main = print [i | i-[1..1], i == sum (divisors i)] I know this is mathematically stupid, but the point is to do a moderate nested-loops computation. On my 2.33GHz dual-core MacBookPro, the obvious C program takes about .3 seconds, and a compiled OCaML program (tail recursion, no lists) about .33 seconds. The above takes about 4 seconds. I've tried using foldl', and doing explicit tail recursion with strict accumulators, but I can't get the running time below 3 seconds. Is it possible to come within striking distance of the other languages? Thanks. Just a trivial comment... 1. Don't speak about comparing *languages* when you compare *algorithms*, and in particular data structures. 2. Please, DO code the above in C, using linked lists. Compare then. 3. Check the influence of bare printing, separated from the computation. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
On Sun, Oct 28, 2007 at 11:26:46AM -0400, Prabhakar Ragde wrote: Jerzy Karczmarczuk wrote: Just a trivial comment... 1. Don't speak about comparing *languages* when you compare *algorithms*, and in particular data structures. 2. Please, DO code the above in C, using linked lists. Compare then. 3. Check the influence of bare printing, separated from the computation. Isn't GHC clever enough to optimize away the entire computation if there is no I/O? Yes, but GHC is not clever enough to solve the perfect number classification problem. 'length' will suffice, and is prefered for most enumeration benchmarks. Note, however, that there are a grand total of 4 perfect numbers less than 10,000. Not exactly an IO problem. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
Prabhakar Ragde wrote: You could try giving divisors type signature: divisors :: Int - [Int] Thank you. That brings the time down to 0.5 seconds. I'm glad it was something as simple as that. --PR I assume GHC was smart enough to do inlining and such in this case, so the difference is that it defaulted to Integer, whose operations are somewhat slower. Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
Stefan O'Rear adds to the dialogue: Prabhakar Ragde wrote: Jerzy Karczmarczuk wrote: Just a trivial comment... 1. Don't speak about comparing *languages* when you compare *algorithms*, and in particular data structures. 2. Please, DO code the above in C, using linked lists. Compare then. 3. Check the influence of bare printing, separated from the computation. Isn't GHC clever enough to optimize away the entire computation if there is no I/O? Yes, but GHC is not clever enough to solve the perfect number classification problem. 'length' will suffice, and is prefered for most enumeratioon benchmarks. My point didn't concern that point. Haskell compiler cannot change an algorithm using lists into something which deals with indexable arrays, usually faster. Indexing may be faster than the indirection, and the allocation of memory costs. And there is laziness... That's why I proposed to check what happens if one uses linked links in C. Well, the follow-ups seem to suggest that the main time eater was the overloading. I must say that I am really astonished. It is hard to believe that such a signature can make a factor of 8. Never seen that before. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
On Sun, 2007-10-28 at 10:23 -0400, Prabhakar Ragde wrote: Jaak Randmets wrote: On 10/28/07, Prabhakar Ragde [EMAIL PROTECTED] wrote: For the purposes of learning, I am trying to optimize some variation of the following code for computing all perfect numbers less than 1. divisors i = [j | j-[1..i-1], i `mod` j == 0] main = print [i | i-[1..1], i == sum (divisors i)] I know this is mathematically stupid, but the point is to do a moderate nested-loops computation. On my 2.33GHz dual-core MacBookPro, the obvious C program takes about .3 seconds, and a compiled OCaML program (tail recursion, no lists) about .33 seconds. The above takes about 4 seconds. You could try giving divisors type signature: divisors :: Int - [Int] Thank you. That brings the time down to 0.5 seconds. I'm glad it was something as simple as that. --PR I'm not sure if Jaak Randmets explained this, but the reason this makes a difference is that Haskell defaults to Integer, an arbitrary precision integer type, that is far more costly than an Int. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
jerzy.karczmarczuk: Stefan O'Rear adds to the dialogue: Prabhakar Ragde wrote: Jerzy Karczmarczuk wrote: Just a trivial comment... 1. Don't speak about comparing *languages* when you compare *algorithms*, and in particular data structures. 2. Please, DO code the above in C, using linked lists. Compare then. 3. Check the influence of bare printing, separated from the computation. Isn't GHC clever enough to optimize away the entire computation if there is no I/O? Yes, but GHC is not clever enough to solve the perfect number classification problem. 'length' will suffice, and is prefered for most enumeratioon benchmarks. My point didn't concern that point. Haskell compiler cannot change an algorithm using lists into something which deals with indexable arrays, usually faster. Indexing may be faster than the indirection, and the allocation of memory costs. And there is laziness... That's why I proposed to check what happens if one uses linked links in C. Well, the follow-ups seem to suggest that the main time eater was the overloading. I must say that I am really astonished. It is hard to believe that such a signature can make a factor of 8. Never seen that before. That fits with my experience writing low level numeric code -- Integer can be a killer. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
On Sun, 2007-10-28 at 12:01 -0700, Don Stewart wrote: jerzy.karczmarczuk: Stefan O'Rear adds to the dialogue: Prabhakar Ragde wrote: Jerzy Karczmarczuk wrote: Just a trivial comment... 1. Don't speak about comparing *languages* when you compare *algorithms*, and in particular data structures. 2. Please, DO code the above in C, using linked lists. Compare then. 3. Check the influence of bare printing, separated from the computation. Isn't GHC clever enough to optimize away the entire computation if there is no I/O? Yes, but GHC is not clever enough to solve the perfect number classification problem. 'length' will suffice, and is prefered for most enumeratioon benchmarks. My point didn't concern that point. Haskell compiler cannot change an algorithm using lists into something which deals with indexable arrays, usually faster. Indexing may be faster than the indirection, and the allocation of memory costs. And there is laziness... That's why I proposed to check what happens if one uses linked links in C. Well, the follow-ups seem to suggest that the main time eater was the overloading. I must say that I am really astonished. It is hard to believe that such a signature can make a factor of 8. Never seen that before. That fits with my experience writing low level numeric code -- Integer can be a killer. Inline machine operations v. out-of-line calls to an arbitrary precision integer C library: there shouldn't be any surprise here. I could make it even slower by making a Nat type and giving it the type Nat - [Nat]. Also, this is a well known issue. It is common for people to, for example, write naive fib and then say that Haskell is useless because it's orders of magnitude slower than naive fib in C or whatever. Then you tell them to add an Int - Int type signature and all of a sudden Haskell is beating C soundly. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
Am Sonntag, 28. Oktober 2007 20:09 schrieb Derek Elkins: snip That fits with my experience writing low level numeric code -- Integer can be a killer. Inline machine operations v. out-of-line calls to an arbitrary precision integer C library: there shouldn't be any surprise here. Obviously. However, what if 32 bit integers aren't sufficient? What perpetually puzzles me is that in C long long int has very good performance, *much* faster than gmp, in Haskell, on my computer, Int64 is hardly faster than Integer. So I stick to Integer mostly, it may be slow but it's correct. Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
Hi,
Prabhakar Ragde wrote:
divisors i = [j | j-[1..i-1], i `mod` j == 0]
main = print [i | i-[1..1], i == sum (divisors i)]
Jerzy Karczmarczuk wrote:
My point didn't concern that point. Haskell compiler cannot change an
algorithm using lists into something which deals with indexable arrays,
usually faster. Indexing may be faster than the indirection, and the
allocation of memory costs. And there is laziness...
This may be true, but it isn't relevant in this case, since the obvious
c program doesn't need any arrays, only two loops:
for (int i = 1; i = 1; i++) {
int sum = 0;
for (int j = 1; j i; j++)
if (i % j == 0)
sum += i;
if (sum == i)
print(i);
}
Loops can be expressed with lazy lists in Haskell. Therefore, the
presented Haskell program is perfectly equivalent to the obvious c
program.
Tillmann Rendel
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
One thing I've noticed is that turning on optimizations significantly increases the speed of haskell code. Are you comparing code between languages with -O2 or without opts? On 10/28/07, Prabhakar Ragde [EMAIL PROTECTED] wrote: For the purposes of learning, I am trying to optimize some variation of the following code for computing all perfect numbers less than 1. divisors i = [j | j-[1..i-1], i `mod` j == 0] main = print [i | i-[1..1], i == sum (divisors i)] I know this is mathematically stupid, but the point is to do a moderate nested-loops computation. On my 2.33GHz dual-core MacBookPro, the obvious C program takes about .3 seconds, and a compiled OCaML program (tail recursion, no lists) about .33 seconds. The above takes about 4 seconds. I've tried using foldl', and doing explicit tail recursion with strict accumulators, but I can't get the running time below 3 seconds. Is it possible to come within striking distance of the other languages? Thanks. --PR ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
On Sun, Oct 28, 2007 at 08:40:28PM +0100, Daniel Fischer wrote: Am Sonntag, 28. Oktober 2007 20:09 schrieb Derek Elkins: snip That fits with my experience writing low level numeric code -- Integer can be a killer. Inline machine operations v. out-of-line calls to an arbitrary precision integer C library: there shouldn't be any surprise here. Obviously. However, what if 32 bit integers aren't sufficient? What perpetually puzzles me is that in C long long int has very good performance, *much* faster than gmp, in Haskell, on my computer, Int64 is hardly faster than Integer. So I stick to Integer mostly, it may be slow but it's correct. Int64 in Glasgow Haskell is not implemented for speed - it uses the FFI to call a number of addition/subtraction/whatever primitives in the runtime. If this is a problem for you, file a feature request on the GHC bugtracker. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newbie optimization question
G'day all. Quoting Don Stewart [EMAIL PROTECTED]: That fits with my experience writing low level numeric code -- Integer can be a killer. Mind you, if you're intending to work with large integers or rationals, Integer is great! The bottleneck is almost always show. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
