Shootout benchmark: fannkuch

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Shootout benchmark: fannkuch

Andrei Formiga
   Greetings,

   Attached are two programs for submission to the Computer Language
Shootout at
   http://shootout.alioth.debian.org/

   They both run the benchmark fannhuck (see below) and I'm sending
them so anyone can improve on them or suggest improvements. Keep in
mind that I'm programming in Scala for just 2 weeks or so now, and I
may be missing idiomatic ways to express a lot of things. The first
version is mostly functional, very clearly expressed (I believe) but
too slow. The second version (fannkuch2.scala) is imperative and much
more efficient. I tested both and they seem to be working. The
imperative version exhibited performance on par with the Java version
tested on the site.

   The URL for this specific benchmark is
   http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=all

--
[]s, Andrei Formiga

fannkuch.scala (1K) Download Attachment
fannkuch2.scala (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: Shootout benchmark: fannkuch

Judson, Ross
I had a brief look over your code, and unless Scala2's code generation
has changed your functional version is at something of a disadvantage,
possibly unfairly.  Scala1's code generator knows when erasure kicks in,
and generates classes that simply manipulate "object"; unless the type
bound on a generic class's declaration limits the possible types to
primitives, it will manipulate them as objects, performing boxing and so
forth.  Your imperative version has a tight bound on its arrays
(Array[int]) which means that the code generator probably generated java
int[] underneath, versus the functional version using List[Integer].
The short version is that the functional version uses lots and lots of
wrapper objects, and the imperative one doesn't -- hence the difference
in performance.  Run javap on the .class files and you'll be able to see
what core Java types got generated for your program.

This appears to be generally true is functional languages, although
specific optimizations are out there (Haskell's specializing, for
example).

Performance issues aside, I have calculated your functional version to
be 9,786,455 times easier to read than the imperative one. :)  

These micro-benchmarks are sort of foolish.  Think about what the Scala
compiler does and about how fast it does it (real fast, as far as I can
tell).  The performance of such complex programs is what we care about,
mostly.  Although we sure do write a lot of small things, as
programmers, so it's nice when the micro-stuff runs quickly too.

RJ


Reply | Threaded
Open this post in threaded view
|

RE: Shootout benchmark: fannkuch

Judson, Ross
In reply to this post by Andrei Formiga
One further note -- your imperative version is specified as a single
method.  Note that certain Java VMs use the number of invocations to a
method as the trigger for JIT compilation.  As your program is a single
method, this method itself may not be compiled.  You might want to
separate it into smaller methods so that the "fast" stuff gets called
many times and triggers compilation (the VM will figure out it's a
"hotspot").   On the other hand with such a small benchmark, the
compilation time may distort the results.  Still, it's worth trying.

RJ
Reply | Threaded
Open this post in threaded view
|

Re: Shootout benchmark: fannkuch

Andrei Formiga
In reply to this post by Judson, Ross
On 1/16/06, Judson, Ross <[hidden email]> wrote:

> I had a brief look over your code, and unless Scala2's code generation
> has changed your functional version is at something of a disadvantage,
> possibly unfairly.  Scala1's code generator knows when erasure kicks in,
> and generates classes that simply manipulate "object"; unless the type
> bound on a generic class's declaration limits the possible types to
> primitives, it will manipulate them as objects, performing boxing and so
> forth.  Your imperative version has a tight bound on its arrays
> (Array[int]) which means that the code generator probably generated java
> int[] underneath, versus the functional version using List[Integer].
> The short version is that the functional version uses lots and lots of
> wrapper objects, and the imperative one doesn't -- hence the difference
> in performance.  Run javap on the .class files and you'll be able to see
> what core Java types got generated for your program.
>
> This appears to be generally true is functional languages, although
> specific optimizations are out there (Haskell's specializing, for
> example).

   I was aware of the performance problems. I wrote the functional
version first and then decided to try my hand at an imperative one for
efficiency reasons.

>
> Performance issues aside, I have calculated your functional version to
> be 9,786,455 times easier to read than the imperative one. :)

   Yes, and it was far easier to write too :) I thought about the
problem, then came up with a solution, wrote the solution and it
worked. Well, almost; my first idea was to create a big list with all
permutations, then map a function to calculate the number of flips
over it, then extract the maximum. But for n = 10 it would consume too
much memory, so I abandoned this "pure functional" idea. The
imperative version, on the other hand, gave me some headaches with
loops and other minor annoyances; it really is harder to reason about
imperative code.

>
> These micro-benchmarks are sort of foolish.  Think about what the Scala
> compiler does and about how fast it does it (real fast, as far as I can
> tell).  The performance of such complex programs is what we care about,
> mostly.  Although we sure do write a lot of small things, as
> programmers, so it's nice when the micro-stuff runs quickly too.

   I agree. To further that point, the benchmarks don't include in the
final score a variable that makes great difference: how much work has
been employed writing the programs. The MLton guys and the Haskell
community, for example, work hard to improve the performance of their
implementations. As a result, GHC is scored highly, but almost every
program uses hacks and tricks to get there, tricks most people
wouldn't employ in "everyday" Haskell programs. From my POV, I'm
learning Scala, so these little programs are nice exercises. It is
interesting to promote the language too, in a way, since users
considering Scala might want to take a look at the shootout to see
where it stands, and having a complete set of benchmarks helps with
that.

>
> RJ
>

--
[]s, Andrei Formiga