jhc vs ghc and the surprising result involving ghc generated assembly.

skaller skaller at users.sourceforge.net
Tue Nov 1 12:50:07 EST 2005

On Tue, 2005-11-01 at 17:30 +0100, Florian Weimer wrote:

> > use C control constructs rather than gotos.
> With GCC version 4, this will have no effect because the gimplifier
> converts everything to goto-style anyway.

Felix generates C with gotos. The result is FASTER
than native C using gcc 4.0 on x86_64.


C code:

     4: int Ack(int M, int N) {
     5:   if (M==0) return N +1;
     6:   else if(N==0) return Ack(M-1,1);
     7:   else return Ack(M-1, Ack(M,N-1));
     8: }

It is known gcc is correctly optimising tail calls here.


     5: fun ack(x:int,y:int):int =>
     6:   if x == 0 then y + 1
     7:   elif y == 0 then ack(x-1, 1)
     8:   else ack(x-1, ack(x, y-1))
     9:   endif
    10: ;

Felix generated C(++) code -- compiled with same options:

int FLX_REGPARM _i1860_f1301_ack( 
int _i1864_v1303_x, int _i1865_v1304_y)
  _us2 _i1867_v1799_ack_mv_74;
  _us2 _i1868_v1821_ack_mv_84;
  _i1867_v1799_ack_mv_74 = _i1864_v1303_x==0 ;
  if(!(_i1867_v1799_ack_mv_74==1))goto _1797;
  return _i1865_v1304_y+1 ;
  _i1868_v1821_ack_mv_84 = _i1865_v1304_y==0 ;
  if(!(_i1868_v1821_ack_mv_84==1))goto _1798;
  _i1865_v1304_y = 1;
  _i1864_v1303_x = _i1864_v1303_x-1 ;
  goto start_1828;
  _i1865_v1304_y = _i1860_f1301_ack(_i1864_v1303_x, _i1865_v1304_y-1 );
  _i1864_v1303_x = _i1864_v1303_x-1 ;
  goto start_1828;

[The FLX_REGPARM says __attribute__((regparm(3)) when
gcc is the compiler for i386 .. but it has no effect
on x86_64]

AFAICS gcc 4.x generates much better code if you just use
gotos everywhere instead of C control structures.

I have no real idea why the Felix generated C is faster.
Two guesses:

(a) the two 'mv' variables declared at the top are optimised
away, so the Felix version is only using 3 words of stack.

(b) the "parallel assigment in tail calls optimisation"
is saving one word on the stack (evaluating y before x
saves a temporary across the non-tail recursion).

but I don't really know.

John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

More information about the Glasgow-haskell-users mailing list