haskell array access

[Shawn P. Garbett]

=2D----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thursday 26 June 2003 05:46 pm, Lex Stein wrote:
> Great, thanks. Those suggestions narrow the gap from GHC -O being 330x
> slower than GCC -O3 to it being 20x slower. Here are the new results:
>
> gcc -O3      0.54s
> ocamlopt     1.11s
> ghc -O      10.76s
> ocamlc      14.10s
>
> GHC is still pretty slow for native x86 instruction code. Is there any way
> to further explain the performance gap ? (new code below)

I redid both programs to make them equivalent in action. The haskell progra=
m=20
was not actually summing the results, the C program was not checking array=
=20
bounds (Haskell does), the C program did not initialize the array and the C=
=20
program didn't print the result.

Times on my laptop (Crusoe 933):

62.061s : Haskell (Array -O2)  Note: lot's 'o disk grinding!
18.231s : Haskell (UArray -O2)
18.108s : Haskell (UArray -O2 -fvia-c)
17.443s : Haskell (UArray -O2 -funfolding-update-in-place)
 0.807s : C (-O3 without bound check)
 1.127s : C (-O3 with bound check)

At best case for Haskell, 15.5 times slower. The thing about bounds checkin=
g,=20
in Haskell it's always there. In C, you might have it, you might not there =
is=20
no certainty by the language, only by design and implementation. So with C,=
=20
one is free to live dangerously.

I changed the "mod" value to 17, so that out of bound access takes place in=
=20
the Haskell program. It gives me the following:
=46ail: Ix{Int}.index: Index (16) out of range ((0,15))

I did the same to the C program (without the bounds checking), it spits out=
 a=20
value and give no indication that anything improper was done.


=2D ---------------------------------------------
Haskell Original (redone to be funtionally equivalent)
=2D ----------------------------------------------
import Array

a :: Array Int Int
a =3D  array (0,15) [(i, i) | i <- [0 .. 15] ]

acc :: Int -> Int -> Int
acc s 0  =3D s
acc s n  =3D acc (s + (a ! (n `mod` 16))) (n-1)

main :: IO ()
main =3D do
         print $ acc 0 100000000

=2D -----------------------------------------------------
C Version with some modifications as well
=2D ----------------------------------------------------------
#include <stdio.h>

int main ()
{
    int i;
    int k;
    int idx;=20
    int a[16];

    for (i=3D0; i<16; ++i)
    {
      a[i] =3D i;
    }
    for (k=3D0, i=3D100000000; i>0; --i)
    {
       idx =3D i % 16;
       if((idx > 15) || (idx < 0))
       {
         fprintf(stderr, "Out of range access (0,15) value is %d\n", idx);
         exit(1);
       }
      =20
       k +=3D a [idx];=20
    }

    printf("%d\n", k);
}
=2D --------------------------------------
New Haskell version with Unboxed Array
Note:it was a simple change of import and type
=2D -----------------------------------------
import Data.Array.Unboxed

a :: UArray Int Int
a =3D  array (0,15) [(i, i) | i <- [0 .. 15] ]

acc :: Int -> Int -> Int
acc s 0  =3D s
acc s n  =3D acc (s + (a ! (n `mod` 16))) (n-1)

main :: IO ()
main =3D do
         print $ acc 0 100000000
=2D----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iEYEARECAAYFAj78eqEACgkQDtpPjAQxZ6AgPQCePRrgaAmxMzfW7d2akvaXLJU7
SxAAnj7wO7vx6zXQwRVBXpMrbqw2wZDF
=3DoMhR
=2D----END PGP SIGNATURE-----