Re: [Haskell-cafe] Floyd Warshall performance (again)
From: Mathieu Boespflug
Dear haskell-cafe,
I implemented the Floyd Warshall algorithm for finding the shortest path in a dense graph in Haskell, but noted the performance was extremely poor compared to C. Even using mutable unboxed arrays it was running about 30 times slower. I rewrote the program several times, to arrive at the following definition:
My results are basically the same as Max's, but if I change
#define SIZE 1500 to sIZE = 1500
and all references from "SIZE" to "sIZE", something ... changes. A lot. MacBook-1:Desktop johnlato$ time ./FW Allocating ... Allocating ... done real 0m0.027s user 0m0.013s sys 0m0.014s I can't figure this out at all. Can anyone else confirm, or offer a good explanation? John
Hi John, your transformation on the original program amounts to replacing all occurrences of a Haskell literal with a Haskell variable. You will therefore end up with something that looks like this : loop sIZE = return () loop j = ... sIZE is now a pattern variable, that is, the pattern of the first clause is irrefutable, so all calls to loop will return immediately. What you were probably looking for is: loop j | j == sIZE = return () | otherwise = ... -- Mathieu On Fri, Apr 16, 2010 at 04:41:06PM +0100, John Lato wrote:
From: Mathieu Boespflug
Dear haskell-cafe,
I implemented the Floyd Warshall algorithm for finding the shortest path in a dense graph in Haskell, but noted the performance was extremely poor compared to C. Even using mutable unboxed arrays it was running about 30 times slower. I rewrote the program several times, to arrive at the following definition:
My results are basically the same as Max's, but if I change
#define SIZE 1500 to sIZE = 1500
and all references from "SIZE" to "sIZE", something ... changes. A lot.
MacBook-1:Desktop johnlato$ time ./FW Allocating ... Allocating ... done
real 0m0.027s user 0m0.013s sys 0m0.014s
I can't figure this out at all. Can anyone else confirm, or offer a good explanation?
John
Hello John, Friday, April 16, 2010, 7:41:06 PM, you wrote:
sIZE = 1500
and all references from "SIZE" to "sIZE", something ... changes. A lot.
this one too? :D let loop2 SIZE = return () -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Am Freitag 16 April 2010 17:41:06 schrieb John Lato:
From: Mathieu Boespflug
Dear haskell-cafe,
I implemented the Floyd Warshall algorithm for finding the shortest path in a dense graph in Haskell, but noted the performance was extremely poor compared to C. Even using mutable unboxed arrays it was running about 30 times slower. I rewrote the program several times, to arrive at the following definition:
My results are basically the same as Max's, but if I change
#define SIZE 1500
to
sIZE = 1500
and all references from "SIZE" to "sIZE", something ... changes. A lot.
MacBook-1:Desktop johnlato$ time ./FW Allocating ... Allocating ... done
real 0m0.027s user 0m0.013s sys 0m0.014s
I can't figure this out at all. Can anyone else confirm, or offer a good explanation?
let loop1 SIZE = return () loop1 k = let loop2 SIZE = return () loop2 i = let loop3 SIZE = return () loop3 j = do If you replace SIZE, which will be replaced with the literal 1500 by the preprocessor, with sIZE, your loops will become trivial: let loop1 sIZE = return () {- deead code -}
On Fri, Apr 16, 2010 at 5:02 PM, Daniel Fischer
Am Freitag 16 April 2010 17:41:06 schrieb John Lato:
From: Mathieu Boespflug
Dear haskell-cafe,
I implemented the Floyd Warshall algorithm for finding the shortest path in a dense graph in Haskell, but noted the performance was extremely poor compared to C. Even using mutable unboxed arrays it was running about 30 times slower. I rewrote the program several times, to arrive at the following definition:
My results are basically the same as Max's, but if I change
#define SIZE 1500
to
sIZE = 1500
and all references from "SIZE" to "sIZE", something ... changes. A lot.
MacBook-1:Desktop johnlato$ time ./FW Allocating ... Allocating ... done
real 0m0.027s user 0m0.013s sys 0m0.014s
I can't figure this out at all. Can anyone else confirm, or offer a good explanation?
let loop1 SIZE = return () loop1 k = let loop2 SIZE = return () loop2 i = let loop3 SIZE = return () loop3 j = do
If you replace SIZE, which will be replaced with the literal 1500 by the preprocessor, with sIZE, your loops will become trivial:
let loop1 sIZE = return () {- deead code -}
d'oh, thanks. I missed that match. john
participants (4)
-
Bulat Ziganshin -
Daniel Fischer -
John Lato -
Mathieu Boespflug