🚀 go-pugleaf

On Mon, 4 Aug 2008, Vend wrote:

> On 31 Lug, 12:50, "Kjetil S. Matheussen" <k.s.matheus...@notam02.no>
> wrote:
> > On Thu, 31 Jul 2008, namekuseijin wrote:
> > > I wonder why most functional programming languages fail so badly at
> > > what should be one of their primary main strengths:  recursive
> > > functions.
> >
> > > In the well-known benchmarking game called "The computer game
> > > shootout", most such languages fail miserably in the face of blazing
> > > fast imperative code during the benchmarking of recursive functions
> > > such as ackermann or fibonacci:
> >
> > >http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&la...
> >
> > > The best is clean, only 1.6 slower than gcc C.
> >
> > > The chart:
> > > 1.6 Clean
> > > 3.2 OCaml (just behind Fortran and Java!)
> > > 3.3 F# (running in mono)
> > > 3.4 SML on MLton (just after FreeBasic!)
> > > 3.4 Haskell GHC (just after Java on gcj!  almost a tie-in)
> > > 3.6 CL on SBCL (almost as good as compiled lazy static Haskell)
> > > 3.7 Scheme on Chicken (just after sbcl)
> > > 4.0 SML/NJ (just after C# on mono)
> > > 4.6 Scheme on Ikarus (just after Java -client!)
> > > 8.1 Scheme PLT (just after Fortran, again)
> >
> > > Well, that's about it.
> >
> > Well, Stalin scheme is not on the list. My results:
> >
> > * GCC:
> > kjetil@ttleush ~/c $ time ./recursive.gcc_run 11
> > Ack(3,11): 16381
> > Fib(38.0): 63245986.0
> > Tak(30,20,10): 11
> > Fib(3): 3
> > Tak(3.0,2.0,1.0): 2.0
> >
> > real    0m2.112s
> > user    0m2.021s
> > sys     0m0.002s
> >
> > * Stalin 0.11:
> > kjetil@ttleush ~/c $ time ./recursive 11
> > Ack(3,11): 16381
> > Fib(3.7999999523162841796875e1.0): 6.32459926605224609375e7.0
> > Tak(30,20,10): 11
> > Fib(3): 3
> > Tak(3.0,2.0,1.0): 2.0.0
> >
> > real    0m1.725s
> > user    0m1.635s
> > sys     0m0.003s
> >
> > Which means that Stalin scheme is about 22% faster than C
> > for this particular benchmark, and stalin scheme is a
> > dynamic typed functional language.
> >
> > Source:http://www.notam02.no/~kjetism/recursive.scm
> 
> Can you post the parts of C code generated by Stalin that are faster
> than the hand-coded C, please?
> 

Okay.

Integer versions of Ack and Tak below.
The float versions are probably similar, I would think,
except that all "int"s are replaced with "float"s,
so I didn't include that code.

Stalin's version of Fibonacci probably performs similar
to the gcc version, so I didn't include that code
either.

In this case, the code produced by Stalin isn't that
spectacular (I mean, it's pretty straight forward),
so I'm surprised no other languages have produced
something similar. The reason for the increased
performance compared to the gcc version seems
to only be because a couple of function
calls are translated into gotos. But maybe Stalin
has done some more sophisticated, but less obvious,
optimization here as well, I don't know. :-)


Ack(x,y)
  x = 0     = y+1
  y = 0     = Ack(x-1,1)
  otherwise = Ack(x-1, Ack(x,y-1))

/* ACK[6] */
int f6(int a666, int a667)
{
    int t1307;
    int t1308;
    int t1309;
    int t1310;
    int t1311;
    int t1312;
    int t1313;
    int t1314;
    int t1315;
    int t1316;
    int t1317;
    int t1318;
    int t1319;
    int t1320;
  h6:
    t1307 = 0;
    t1308 = a666;
    if (!(t1307 == t1308))
	goto l368;
    t1319 = a667;
    t1320 = 1;
    return t1319 + t1320;
  l368:
    t1311 = a666;
    t1312 = 1;
    t1309 = t1311 - t1312;
    t1313 = 0;
    t1314 = a667;
    if (t1313 == t1314)
	goto l370;
    t1315 = a666;
    t1317 = a667;
    t1318 = 1;
    t1316 = t1317 - t1318;
    t1310 = f6(t1315, t1316);
    goto l371;
  l370:
    t1310 = 1;
  l371:
    a666 = t1309;
    a667 = t1310;
    goto h6;
}


Tak(x,y,z)
  y < x     = Tak(Tak(x-1.0,y,z),Tak(y-1.0,z,x),Tak(z-1.0,x,y))
  otherwise = z

/* TAK[13] */
int f13(int a670, int a671, int a672)
{
    int t1267;
    int t1268;
    int t1269;
    int t1270;
    int t1271;
    int t1272;
    int t1273;
    int t1274;
    int t1275;
    int t1276;
    int t1277;
    int t1278;
    int t1279;
    int t1280;
    int t1281;
    int t1282;
    int t1283;
    int t1284;
    int t1285;
    int t1286;
  h13:
    t1267 = a671;
    t1268 = a670;
    if (!(t1267 < t1268))
	goto l362;
    t1275 = a670;
    t1276 = 1;
    t1272 = t1275 - t1276;
    t1273 = a671;
    t1274 = a672;
    t1269 = f13(t1272, t1273, t1274);
    t1280 = a671;
    t1281 = 1;
    t1277 = t1280 - t1281;
    t1278 = a672;
    t1279 = a670;
    t1270 = f13(t1277, t1278, t1279);
    t1285 = a672;
    t1286 = 1;
    t1282 = t1285 - t1286;
    t1283 = a670;
    t1284 = a671;
    t1271 = f13(t1282, t1283, t1284);
    a670 = t1269;
    a671 = t1270;
    a672 = t1271;
    goto h13;
  l362:
    return a672;
}



> > Compile with
> > stalin -On -no-clone-size-limit -Ob -Om -Or -Ot -copt -O3 -copt
> > -fomit-frame-pointer -copt -march=athlon-xp -dC -dh -architecture
> > IA32-align-double -copt -malign-double -copt -freg-struct-return -d0 -d1
> > -d5 -d6 -k recursive.scm
> >
> > (most of these options probably don't make any difference regarding
> > execution speed, I just tried various
> > things to see if it improved, and kept most that didn't make a difference)
> 
>