haskell array access

[Lex Stein]

Actually, to be completely correct, the access is the movl 2 instructions
above the "-->". The "-->" points to the accumulation in the local
variable k.

Any ideas how I can further narrow this 20x gap and improve GHC's
observed relative array access performance ?

int main () {
  int i, k = 0;
  int a [16];
  for (i=0; i<100000000; i++) {
    k += a [i % 16];
  }
  return k;
}

Thanks!
Lex

--
Lex Stein                     http://www.eecs.harvard.edu/~stein/
stein@eecs.harvard.edu        TEL: 617-233-0246


On Thu, 26 Jun 2003, Lex Stein wrote:

>
> You must be using my old example, with gcc -O3 my new example does access
> the array and is 20x faster than the ghc -O code. Scroll down for
> "-->" that I inserted beside the instruction to see the array access.
>
> 	.file	"arrayloop.c"
> 	.version	"01.01"
> gcc2_compiled.:
> .text
> 	.p2align 2,0x90
> .globl main
> 		.type		 main,@function
> main:
> 	pushl %ebp
> 	movl %esp,%ebp
> 	subl $80,%esp
> 	pushl %esi
> 	pushl %ebx
> 	xorl %ebx,%ebx
> 	xorl %ecx,%ecx
> 	leal -64(%ebp),%esi
> 	.p2align 2,0x90
> .L6:
> 	movl %ecx,%edx
> 	testl %ecx,%ecx
> 	jge .L7
> 	leal 15(%ecx),%edx
> .L7:
> 	andl $-16,%edx
> 	movl %ecx,%eax
> 	subl %edx,%eax
> -->	addl (%esi,%eax,4),%ebx
> 	incl %ecx
> 	cmpl $99999999,%ecx
> 	jle .L6
> 	movl %ebx,%eax
> 	popl %ebx
> 	popl %esi
> 	leave
> 	ret
> .Lfe1:
> 		.size		 main,.Lfe1-main
> 	.ident	"GCC: (GNU) c 2.95.4 20020320 [FreeBSD]"
>
> On Thu, 26 Jun 2003, Hal Daume wrote:
>
> > This has been hinted to before: gcc gets rid of the loop.
> >
> > bash-2.05b$ gcc -O3 arr.c -S -o arr.s
> > bash-2.05b$ cat arr.s
> > 	.file	"arr.c"
> > 	.def	___main;	.scl	2;	.type	32;	.endef
> > 	.text
> > 	.align 2
> > 	.align 16
> > .globl _main
> > 	.def	_main;	.scl	2;	.type	32;	.endef
> > _main:
> > 	pushl	%ebp
> > 	movl	%esp, %ebp
> > 	subl	$72, %esp
> > 	xorl	%eax, %eax
> > 	andl	$-16, %esp
> > 	call	__alloca
> > 	call	___main
> > 	xorl	%eax, %eax
> > 	.align 16
> > L7:
> > 	incl	%eax
> > 	cmpl	$100000000, %eax
> > 	jle	L7
> > 	leave
> > 	ret
> >
> > the inside of the loop is exactly:
> >
> > L7:
> > 	incl	%eax
> > 	cmpl	$100000000, %eax
> > 	jle	L7
> >
> > which doesn't read the array!  essentially you are being unfare to ghc
> > by making it seq the array element, but not doing the same to GCC.  even
> > with -O0, gcc gets rid of the loop body.
> >
> > one solution: add in the assembly to actually read the array (i'm too
> > lazy and busy to do this).
> >
> >  - hal
> >
> >
> > --
> >  Hal Daume III                                   | hdaume@isi.edu
> >  "Arrest this man, he talks in maths."           | www.isi.edu/~hdaume
> >
> >
> > > -----Original Message-----
> > > From: haskell-cafe-admin@haskell.org
> > > [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Lex Stein
> > > Sent: Thursday, June 26, 2003 3:46 PM
> > > To: Sven Panne
> > > Cc: haskell-cafe@haskell.org
> > > Subject: Re: haskell array access
> > >
> > >
> > >
> > > 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)
> > >
> > > Thanks!
> > > Lex
> > >
> > > Haskell (GHC) source:
> > >
> > > import Array
> > > k :: Array Int Int
> > > k = Array.array (0,15) [(i, i+1) | i <- [0 .. 15] ]
> > > acc :: Int -> Int
> > > acc 0 = 0
> > > acc n = seq (k Array.! (n `mod` 16)) (acc (n-1))
> > > main = do
> > >     print (acc 100000000)
> > >
> > > Caml test source:
> > >
> > > let a = Array.make 16 0;;
> > > let rec do1 i z =
> > >     if (i>100000000) then z else
> > >         do1 (i+1) (z + a.(i mod 16));;
> > > do1 0 0;;
> > >
> > > C (gcc) test source:
> > >
> > > int main () {
> > >     int i, k = 0;
> > >     int a [16];
> > >     for (i=0; i<100000000; i++) {
> > >         k += a [i % 16];
> > >     }
> > >     return (k);
> > > }
> > >
> > >
> > > On Fri, 27 Jun 2003, Sven Panne wrote:
> > >
> > > > Well, part of the answer is definitely that the Haskell
> > > program is the
> > > > *only* one which really uses the array elements. :-) I
> > > guess that the
> > > > compilers for the other languages simply remove the array
> > > access from
> > > > the generated code (gcc definitely does, only an empty loop
> > > remains).
> > > >
> > > > Another reason is that the type signatures are missing, so
> > > Integer is
> > > > used instead of Int, which is a bit unfair. Adding
> > > >
> > > >     k :: Array Int Int
> > > >     acc :: Int -> Int
> > > >
> > > > cuts down the time by more than factor 5 on my machine.
> > > >
> > > > Cheers,
> > > >     S.
> > > >
> > > >
> > > > _______________________________________________
> > > > 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
> > >
> > _______________________________________________
> > 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
>