Note: I've just migrated to a different physical server to run Spivey's Corner,
with a new architecture, a new operating system, a new version of PHP, and an updated version of MediaWiki.
Please let me know if anything needs adjustment! – Mike

Benchmark results for GeomLab

Copyright © 2024 J. M. Spivey
Jump to navigation Jump to search

Fun vs Java

This Fun program computes 2^26 in a very slow way:

let f(0) = 1 | f(n+1) = f(n) + f(n) in f(26)

My Fun language is implemented by dynamic translation into JVM bytecode, and this program takes about 6.0s to run.

So what would be the running time of an equivalent Java program? Let's begin with

public static int f1(int n) {
    if (n == 0)
        return 1;
    else
        return f1(n-1) + f1(n-1);
}

That takes about 0.61s.

But Fun does all its arithmetic in double-precision; so let's try

public static double f2(double n) {
    if (n == 0)
        return 1;
    else
        return f2(n-1) + f2(n-1);
}

That takes about 0.88s.

What's more, Fun uses a boxed representation for all numbers; so next we should try

public static Double f3(Double n) {
    if (n == 0)
        return 1.0;
    else
        return f3(n-1) + f3(n-1);
}

See the difference? The types of the argument and result are specified as Double, and that means that they will be automatically boxed and unboxed as needed. Java gets round its lack of a uniform value representation by providing these boxing classes as part of the library. This program takes about 2.9s; we are beginning to account for some of the time taken by the Fun program.

Another thing about Fun is that all the operators are implemented as primitive functions that are called like any other functions. Let's try to approximate that in Java:

public static boolean eq(Double x, Double y) { return (double) x == y; }
public static Double sub(Double x, Double y) { return x - y; }
public static Double add(Double x, Double y) { return x + y; }
public static Double f4(Double n) {
    if (eq(n, 0.0))
        return 1.0;
    else
        return add(f4(sub(n, 1.0)), f4(sub(n, 1.0)));
}

(See that cast? Without it, the program bombs, because it compares two boxes for identity, not two doubles for equality.) Now this program takes about 5.8s, and that's nearly as long as the Fun program – especially if we allow for the fact that Fun's startup time is a lot longer than the startup time for a little Java program like this.

These numbers are very unscientific, but they give some idea of where the time goes. It seems that the out-of-line primitives cost at least as much as the boxing and unboxing, for example.

Addendum

That Java program isn't really equivalent to the Fun program. It is nearer to this program:

let f(n) = if n = 0 then 1 else f(n-1) + f(n-1) in f(26)

which takes around 10.9s, perhaps because of the rather greater use of function calls to primitives.

The Fun implementation has an interpreter for its intermediate code that is used to avoid the overhead of translation for top-level expressions. With default settings, the interpreter is used in our program for code that forms the closure for f and invokes it with the argument 26, but the body of f is compiled into JVM code and subsequently (I assume) JITted into native code. Using the interpreter for the whole program slows it down immensely, so that f(24) takes 16.8s, compared with 2.2s for the compiled version.