[Haskell-cafe] Floyd Warshall performance (again)

[John Lato]

On Fri, Apr 16, 2010 at 5:02 PM, Daniel Fischer
<daniel.is.fischer at web.de> wrote:
> Am Freitag 16 April 2010 17:41:06 schrieb John Lato:
>> > From: Mathieu Boespflug <mboes at tweag.net>
>> >
>> > 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