Bit Stream Benchmarks

Implementing Bit Stream Manipulating Programs in Many languages

This is a website which describes benchmarks that each entail operations on bit streams. So far there are five different benchmarks:

  1. drop3
  2. five11
  3. huffman
  4. uudecode
  5. uuencode

These benchmarks have all been implemented in Erlang, O'Caml and Haskell. They are in the process of being implemented in C and Java as well. The general rules of the game are that the functional languages are not allowed to use mutable arrays to do anything but read the input. More complete rules for benchmarking are available for each benchmark.


Results

The table shows some preliminary results when running the benchmarks on a 2.4 GHz pentium IV with 1 GB of memory. The OS is Fedora Core 3.

Style FunctionalFunctional Functional Imperative Imperative
Benchmark Erlang Haskell O'Caml C Java
drop3 2.090 5.849 2.254 0.957 1.990
five11 4.970 8.657 7.692 9.798 18.405
huffman 2.290 7.383 10.815 0.974 1.753
uudecode 3.210 6.042 2.657 0.863 0.971
uuencode 2.850 7.775 2.824 1.041 0.981
Table 1: Runtimes for the benchmarks

The runtimes on this machine is shown in Table 1, whereas the number of lines of code necessary to implement the benchmarks is recorded in Table 2. The number of lines does not include code used to measure time or setup before the benchmark. Furthermore some lines are not counted to avoid punishing certain coding styles. Exactly which lines are counted is reflected in the source file by a comment containing a line number.

Style FunctionalFunctional Functional Imperative Imperative
Benchmark Erlang Haskell O'Caml C Java
drop3 2 47 45 31 47
five11 9 38 23 64 78
huffman 14 30 54 67 81
uudecode 20 91 65 43 57
uuencode 25 70 70 54 64
Table 2: Line Numbers for the benchmarks

These numbers are still provisional, some of the Haskell programs can probably be improved a little bit further while remaining readable, but they have already been improved immensly by the help of some of the people at haskell-cafe, many thanks to Spencer Janssen, Chris Kuklewicz and Donald Bruce Stewart among others.

Updates:

drop3 and huffman written in O'Caml have been improved by removing unnecessary list-building, thanks to Xavier Leroy


Compiling and running

The O'Caml programs have been compiled using the ocamlopt compiler version 3.09.1 with the following command:

ocamlopt -noassert -unsafe -ccopt -O2 benchmark.ml -o benchmarkocaml.run

The Haskell programs have been compiled using the Glasgow Haskell Compiler version 6.4 with the following command:

touch benchmark.hs;
ghc -O2 -optc-O3 -fglasgow-exts -fexcess-precision -o benchmarkhaskell.run benchmark.hs

The touch command is used to convince GHC to recompile from source in case it has already been compiled with different flags.

The Java programs are compiled to native code using Gnu's compiler for Java with the following command:

gcj -O2 --main=benchmark -o benchmarkjava.run benchmark.java

The C programs are compiled to native code using Gnu's compiler for C with the following command:

gcc -O2 -o benchmarkcrun benchmark.c

The Erlang programs are compiled using an extended P11 compiler. The following compile command was used:

erlc +native +"{hipe,[bincomp,O2]}" benchmark.erl

Since the Erlang compiler does not produce a standalone executable the following command is used to run the Erlang benchmark:

erl -noshell -pa -run benchmark test ARGUMENT

Since the other compilers produces executables the benchmarks can simply be run by:

benchmarkocaml.run ARGUMENT
benchmarkhaskell.run ARGUMENT
benchmarkjava.run ARGUMENT
benchmarkc.run ARGUMENT

Runtime measurements are taken inside the benchmarks and reported by printing a floating point number to stdout. The process of compiling and running these benchmarks was automated using this Erlang program


Running benchmarks on you own machine

  1. Download the P11 snapshot
  2. Unpack otp.tar.gz
  3. Change directory to otp
  4. .\configure
  5. make (takes quite some time)
  6. Download the benchmarks
  7. Unpack benchmarks and change directory to benchmarks/
  8. Make sure that ocamlopt, ghc and gcc are all in your $PATH
  9. Edit bit_bench.erl so that ERLPATH contains the path to the otp directory
  10. Start an erlang shell e.g. ERLPATH/bin/erl
  11. Compile bit_bench.erl in erlang shell using c(bit_bench).
  12. Run benchmarks with bit_bench:run()

Questions

If you have any questions about this project please contact Per Gustafsson