Why such poor recursive behaviour?

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/gp...rsive&lang=all

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.

I know in the grand scheme of things, such timings are not that bad,
not orders of magnitude slower like some of the dynamic scripting
stinkers in the bottom, specially in the face of such classy and easy
syntax and semantics adding to programmer productivity. Still, kind
of a let down, like buying a Playstation 3 and waiting for a killer
app that never comes...

Any thoughts?

namekuseijin <namekuseijin@gmail.com> writes:

> 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/gp...rsive&lang=all
>
> 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.
>
> I know in the grand scheme of things, such timings are not that bad,
> not orders of magnitude slower like some of the dynamic scripting
> stinkers in the bottom, specially in the face of such classy and easy
> syntax and semantics adding to programmer productivity. Still, kind
> of a let down, like buying a Playstation 3 and waiting for a killer
> app that never comes...
>
> Any thoughts?

I think the difference is not due to the speed of recursive function
calls but due to the speed of arithmetic. Most functional languages
check for overflow at every arithmetic operations, which adds a
considerable overhead. C does not.

Torben

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/gp...rsive&lang=all
>
> 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

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)

På Thu, 31 Jul 2008 10:01:37 +0200, skrev namekuseijin
<namekuseijin@gmail.com>:

> 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/gp...rsive&lang=all
>
> 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.
>
> I know in the grand scheme of things, such timings are not that bad,
> not orders of magnitude slower like some of the dynamic scripting
> stinkers in the bottom, specially in the face of such classy and easy
> syntax and semantics adding to programmer productivity. Still, kind
> of a let down, like buying a Playstation 3 and waiting for a killer
> app that never comes...
>
> Any thoughts?

The fastest applicative code is in OCALM and Haskell.
For better performance in CL you might try the series library.
In a nutshell the above mentioned languages were based on experiences and
reflections on performance in Lisp.
It is based on experience with type inference and lazy evaluation.
SBCL is better at type inference than other Lisp's so perhaps series under
SBCL would give CL a more faveroable result.
Most compilers today (Allegro Common Lisp, LispWorks) have focused more on
OO performance under CLOS and fast memory management which matters more to
many of the users of Lisp. Note that most users of Lisp used a mixed
paradigm approach and that loop plays a important role in why the
applicative performance has not been a priority. As in all compiled
languages it depends more on the quality of the programmer than the
compiler. Anyhow short example code doesn't accurately reflect the users
perceived performance running real programs. Java's long loading time and
memory use tend to shadow algorithm performance in real programs. In this
sense CL scores a lot better.

--------------
John Thingstad

On Thu, 31 Jul 2008, Kjetil S. Matheussen 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/gp...rsive&lang=all
> >
> > 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
>

Options:
/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -march=athlon-xp recursivec.c -o recursive.gcc_run

gcc version:
gcc (GCC) 4.2.4 (Gentoo 4.2.4 p1.0)



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

Don't bother about the not quite accurate printing of numbers,
the calculations themself are correct with the same input
and output values as the C version.



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

Well, the types are dynamic unless stalin can't infere the types,
which it obviously could in this example. :-)

Pah. This challenge screams for a Gordian Knot solution:
With the most simple memoization applied to the functions, the run
time of the common lisp version is down to a few milliseconds.
--
(espen)

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/gp...rsive&lang=all
>
> 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.
>
> I know in the grand scheme of things, such timings are not that bad,
> not orders of magnitude slower like some of the dynamic scripting
> stinkers in the bottom, specially in the face of such classy and easy
> syntax and semantics adding to programmer productivity. Still, kind
> of a let down, like buying a Playstation 3 and waiting for a killer
> app that never comes...
>
> Any thoughts?

Yes. These programs not only perform recursion but also perform
small numerical computations. Because of Scheme's numeric tower,
a system that supports bignums cannot compile these benchmarks as
fast as systems that have fixed precision numbers (all the rest?).

The benchmark program itself can be converted to use fixnum-specific
or flonum-specific operators. This in turn gives some compiler
better chance of recovering some information regarding the size and
representation of the arguments. For example, in the development
version of Ikarus, the run time on my machine the given benchmark
program is:

real 0m6.529s
user 0m6.386s
sys 0m0.088s

Now modifying the program to use fixnum and flonum operations when
appropriate, the run time becomes:

real 0m4.508s
user 0m4.421s
sys 0m0.077s

If you can interpolate these numbers to the ones you give in the
list above, Ikarus will be in the low 3.x range. Note that the
program is still fully safe and still performs overflow check for
the fixnum arithmetic operations.

In short, the benchmark in Scheme measures how fast you do fixnum
and flonum computations more than how fast you do recursion.


Aziz,,,

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/gp...rsive&lang=all
>
> 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.
>
> I know in the grand scheme of things, such timings are not that bad,
> not orders of magnitude slower like some of the dynamic scripting
> stinkers in the bottom, specially in the face of such classy and easy
> syntax and semantics adding to programmer productivity. Still, kind
> of a let down, like buying a Playstation 3 and waiting for a killer
> app that never comes...
>
> Any thoughts?

Yes. These programs not only perform recursion but also perform
small numerical computations. Because of Scheme's numeric tower,
a system that supports bignums cannot compile these benchmarks as
fast as systems that have fixed precision numbers (all the rest?).

The benchmark program itself can be converted to use fixnum-specific
or flonum-specific operators. This in turn gives some compiler
better chance of recovering some information regarding the size and
representation of the arguments. For example, in the development
version of Ikarus, the run time on my machine the given benchmark
program is:

real 0m6.529s
user 0m6.386s
sys 0m0.088s

Now modifying the program to use fixnum and flonum operations when
appropriate, the run time becomes:

real 0m4.508s
user 0m4.421s
sys 0m0.077s

If you can interpolate these numbers to the ones you give in the
list above, Ikarus will be in the low 3.x range. Note that the
program is still fully safe and still performs overflow check for
the fixnum arithmetic operations.

In short, the benchmark in Scheme measures how fast you do fixnum
and flonum computations more than how fast you do recursion.

Aziz,,,

On Thu, 31 Jul 2008, Abdulaziz Ghuloum wrote:
>
> Now modifying the program to use fixnum and flonum operations when
> appropriate, the run time becomes:
>
> real 0m4.508s
> user 0m4.421s
> sys 0m0.077s
>

In addition, you can probably shave off a few more ms by using
bitwise-ior in tak:

(define (ack x y)
(if (= 0 x)
(+ y 1)
(ack (- x 1)
(if (= 0 (bitwise-ior y 0))
1
(ack x (- y 1))))))


That's what gcc does. It made a significant
difference for stalin as well.

On 31 jul, 05:28, torb...@pc-003.diku.dk (Torben Ægidius Mogensen)
wrote:
> I think the difference is not due to the speed of recursive function
> calls but due to the speed of arithmetic. *Most functional languages
> check for overflow at every arithmetic operations, which adds a
> considerable overhead. *C does not.

Hmm, I thought languages like Ada, Oberon-2 or Java did check for
arithmetic overflow as well.