[Haskell-cafe] Floyd Warshall performance (again)

[Daniel Fischer]

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 -}