Speed wars 4: OCaml, F#, Clojure, Pascal

[Unknown]

Dr. Harrop suggested reducing the runs to 1 in order to prevent
cheating.

I increased max_iterations to 99888.

Pentium 4, 3.2 GHz
Windows XP

2.323 sec. -- F#
2.854 sec. -- Clojure (java -server)
6.015 sec. -- OCaml (ocamlopt)
5.031 sec. -- FreePascal

F# --------------------------------------------------

let runs = 1
let max_iterations = 99888

let iterate ci cr =
let bailout = 4.0 in
let rec loop zi zr i =
if i > max_iterations then
0
else
let temp = zr * zi and
zr2 = zr * zr and
zi2 = zi * zi in
if zi2 + zr2 > bailout then
i
else
loop (temp + temp + ci) (zr2 - zi2 + cr) (i + 1)
in
loop 0.0 0.0 1

let mandelbrot n =
for y = -39 to 38 do
if 1 = n then printf "\n";
for x = -39 to 38 do
let i = iterate
(float x / 40.0) (float y / 40.0 - 0.5) in
if 1 = n then
printf "%s" ( if 0 = i then "*" else " " );
done
done;;

let timer = Stopwatch.StartNew () in
for i = 1 to runs do
mandelbrot i
done;
printf "\n%d\n" timer.ElapsedMilliseconds;

Clojure -------------------------------------------------------

(def runs 1)
(def max_iterations 99888)

(defn iter [ci cr]
(let [max_iter (int max_iterations)
ci (double ci)
cr (double cr)]
(loop [zi (double ci) zr (double cr) i (int 1)]
(if (<= i max_iter)
(let [zr2 (* zr zr) zi2 (* zi zi)]
(if (<= (+ zr2 zi2) (double 4.0))
(recur (+ (* (* zr zi) (double 2.0)) ci)
(+ (- zr2 zi2) cr)
(inc i))
i))
0))))

(defn mand [n]
(doseq [y (range -39 39)]
(when (= 1 n) (print "\n"))
(doseq [x (range -39 39)]
(let [i (iter (/ x 40.0) (- (/ y 40.0) 0.5))]
(when (= 1 n) (print (if (= 0 i) "*" " ")))))))

(defn time-mand []
(time
(doseq [i (range 1 (inc runs))]
(mand i))))

(time-mand)

OCaml ---------------------------------------------------------

let runs = 1
let max_iterations = 99888

let iterate ci cr =
let bailout = 4.0 in
let rec loop zi zr i =
if i <= max_iterations then
let
zr2 = zr *. zr and
zi2 = zi *. zi in
if zi2 +. zr2 <= bailout then
loop (zr *. zi *. 2.0 +. ci) (zr2 -. zi2 +. cr) (i + 1)
else
i
else
0
in
loop 0.0 0.0 1

let mandelbrot n =
for y = -39 to 38 do
if 1 = n then print_endline "";
for x = -39 to 38 do
let i = iterate
(float x /. 40.0) (float y /. 40.0 -. 0.5) in
if 1 = n then
print_string ( if 0 = i then "*" else " " );
done
done;;

let start_time = Unix.gettimeofday () in
for iter = 1 to runs do
mandelbrot iter
done;
print_endline "";
print_float ( Unix.gettimeofday () -. start_time );
print_endline "";

FreePascal ----------------------------------------------------

uses sysutils; { for timing }

const
runs = 1;
max_iterations = 99888;

function iterate( ci, cr: real): longint;
var
count : longint;
zr, zi, zr2, zi2 : real;
begin
count := 1;
zr := 0.0; zi := 0.0; zr2 := 0.0; zi2 := 0.0;
while (count <= max_iterations) and (zr2 + zi2 < 4.0) do
begin
zi := zr * zi * 2.0 + ci;
zr := zr2 - zi2 + cr;
inc( count );
zr2 := zr * zr;
zi2 := zi * zi
end;
if count > max_iterations then
exit( 0 )
else
exit( count )
end;

procedure mandelbrot( n: longint );
var
y, x, i : longint;
begin
for y := -39 to 38 do
begin
if 1 = n then writeln;
for x := -39 to 38 do
begin
i := iterate( (x / 40.0), ( y / 40.0 - 0.5) );
if 1 = n then
if 0 = i then write( '*' ) else write( ' ' );
end
end
end;

var
when : tDateTime;
iter : longint;
begin
when := Time;
for iter := 1 to runs do
mandelbrot( iter );
writeln;
writeln( ((time - when) * secsPerDay):0:3, ' seconds' )
end.

[William James]

William James wrote:

>
> Pentium 4, 3.2 GHz
> Windows XP
>
> 2.323 sec. -- F#
> 2.854 sec. -- Clojure (java -server)
> 6.015 sec. -- OCaml (ocamlopt)
> 5.031 sec. -- FreePascal

Those of you who have multiple cores (I don't), try
this Clojure version that uses "pmap".

(def max_iterations 99888)

(defn iter [ci cr]
(let [max_iter (int max_iterations)
ci (double ci)
cr (double cr)]
(loop [zi (double ci) zr (double cr) i (int 1)]
(if (<= i max_iter)
(let [zr2 (* zr zr) zi2 (* zi zi)]
(if (<= (+ zr2 zi2) (double 4.0))
(recur (+ (* (* zr zi) (double 2.0)) ci)
(+ (- zr2 zi2) cr)
(inc i))
i))
0))))

(defn mand []

(doseq [y (range -39 39)]

(println (apply str
(pmap
#(if (= 0 (iter (/ % 40.0) (- (/ y 40.0) 0.5))) "*" " " )
(range -39 39))))))

(defn time-mand []
(time (mand)))

(time-mand)

[Zak Wilson]

The speed of the parallel Clojure version is significantly affected by
the terminal in which it is run. It also varies significantly between
runs. The non-parallel version has less variation, but is still
affected by the terminal. Here are some test runs of the parallel
version on a Core Duo T2300:

xterm: 2535, 2541, 2442
Emacs Slime: 2397, 2614, 2532
Gnome terminal: 2901, 2886, 2724
Aterm: 2997, 2447, 2500

Did you use the Windows cmd program for the output of every language?

[William James]

Zak Wilson wrote:

Yes. When I change max_iterations to 99, the time is something
like 112.798974 msecs. So output to the screen doesn't seem to
be a big factor.

Does it seem to you that "pmap" is using both cores?
I wish that I could run this on a quad-core machine.

[Zak Wilson]

The pmap version is certainly using both cores, but not especially
efficiently; I get about 120% CPU usage. I've had better results than
that using pmap in other situations - in general, it likes slow
functions and short sequences better than fast functions and long
sequences. Your version calculates each point in parallel. Here's a
definition of mand that calculates each line in parallel:

(defn mand-point [x y]
(if (= 0 (iter (/ y 40.0) (- (/ x 40.0) 0.5)))
"*"
" "))

(defn mand-line [x]
(str (apply str
(concat (map #(mand-point x %)
(range -39 39))))
"\n"))

(defn mand []
(println
(apply str
(pmap mand-line
(range -39 39)))))

This version achieves nearly 100% usage on both cores and averages
just over 1600ms - almost exactly twice as fast as the non-parallel
version.

[Tom Davies]

Here's another functional language in the mix.

I've written a version for CAL (http://openquark.org), modelled on the
F# code.

It runs in 2.2 seconds (Java 1.6, 64 bit, with output redirected to a
file, and including jvm startup time, i.e. 'time java ...') on my
MacBook Pro 2.33GHz.

For comparison, the Clojure version reports 2.1 seconds (again
redirected to a file, but *not* including JVM startup time)

I've been careful to make the types Double, not Num a => a, and to use
strictness so that CAL can use the unboxed version of functions and
avoid thunk building.

module TDavies.SpeedWar;

import Cal.Core.Prelude using
typeConstructor = Double, String;
function = seq;
;

import Cal.IO.Console using
function = print;
;

for :: Double -> Double -> Double -> (Double -> ()) -> ();
for !start !end !i !f = if i <= end then (f i) `seq` for start end (i
+1.0) f else ();
speedWar :: [String] -> ();
speedWar args =
let runs = 1 :: Double;
maxIterations = 99888 :: Double;
iterate :: Double -> Double -> Double;
iterate !ci !cr =
let bailout = 4.0 :: Double;
in
let loop :: Double -> Double -> Double -> Double;
loop !zi !zr !i =
if i > maxIterations then
0.0
else
let temp = zr * zi;

zr2 = zr * zr;

zi2 = zi * zi;

in
if zi2 + zr2 > bailout then
i
else
loop (temp + temp + ci) (zr2 - zi2 +

cr) (i + 1.0);
in
loop 0.0 0.0 1.0;
mandlebrot !n =
let is = for (-39.0) 38.0 (-39.0);
point :: Double -> Double -> String;
point !x !y = if (iterate (x/40.0) (y/40.0 - 0.5)) ==
0.0 then "*" else " ";
in
for 1 runs 1 (\r -> is (\!y -> (print "\n") `seq` (is
(\!x -> print $ point x y))));
in
mandlebrot runs;

[Tom Davies]

And here's a version using CAL's parallelMap function.

Running 100 iterations takes 191 seconds on one core, and 104 seconds
using two cores. I'll try it on 4 (and perhaps 8) cores later. Again
that's including JVM startup time and redirecting output to a file,
although sending output to Terminal.app doesn't seem to slow things
down.

module TDavies.SpeedWar;

import Cal.Core.Prelude using
typeConstructor = Double, String;

function = concat, seq, upFromTo;
;

import Cal.IO.Console using
function = print;
;

import Cal.Collections.List using
function = concatMap, map;
;

import Cal.Experimental.Concurrent.Parallel using
function = parallelMap;
;

for :: Double -> Double -> Double -> (Double -> ()) -> ();
for !start !end !i !f = if i <= end then (f i) `seq` for start end (i
+1.0) f else ();
speedWar :: [String] -> ();
speedWar args =

let runs = 100 :: Double;

maxIterations = 99888 :: Double;
iterate :: Double -> Double -> Double;
iterate !ci !cr =
let bailout = 4.0 :: Double;
in
let loop :: Double -> Double -> Double -> Double;
loop !zi !zr !i =
if i > maxIterations then
0.0
else
let temp = zr * zi;
zr2 = zr * zr;
zi2 = zi * zi;
in
if zi2 + zr2 > bailout then
i
else
loop (temp + temp + ci) (zr2 - zi2 +
cr) (i + 1.0);
in
loop 0.0 0.0 1.0;
mandlebrot !n =

let is = upFromTo (-39.0) 38.0;

point :: Double -> Double -> String;
point !x !y = if (iterate (x/40.0) (y/40.0 - 0.5)) ==
0.0 then "*" else " ";

run n = print $ concat (parallelMap (\!y -> (concatMap
(\!x -> point x y) is) ++ "\n") is);
in
for 1 runs 1 run;
in
mandlebrot runs;

[Zak Wilson]

I tried the three Clojure versions on a quad-core machine (2x 2.66 GHz
Xeon dual-core Mac Pro). Here are the results:

Non-parallel: 2033ms
Parallel points: 1204ms
Parallel lines: 499ms

[Tom Davies]

Two dual core 2.66GHz Xeons: single threaded: 161 seconds, 4 CPUS: 45
seconds (100 iterations, including JVM startup time)

[William James]

Zak Wilson wrote:

Impressive.

I'm surprised at how fast JIT can be. And Clojure is a lot more
to my taste than Common Lisp.

[William James]

William James wrote:

I borrowed from Zak Wilson's code in order to clean up
the Clojure version and to make it use pmap effeciently.

(def max_iterations 99888)
(def span (range -39 39))

(defn iter [ci cr]
(let [max_iter (int max_iterations)
ci (double ci)
cr (double cr)]
(loop [zi (double ci) zr (double cr) i (int 1)]
(if (<= i max_iter)
(let [zr2 (* zr zr) zi2 (* zi zi)]
(if (<= (+ zr2 zi2) (double 4.0))
(recur (+ (* (* zr zi) (double 2.0)) ci)
(+ (- zr2 zi2) cr)
(inc i))
i))
0))))

(defn mand-point [x y]
(let [ scale #(/ % 40.0) ]
(if (= 0 (iter (scale x) (- (scale y) 0.5))) "*" " " )))

(defn mand-line [y]
(apply str (map #(mand-point % y) span)))

(defn mand []
(doseq [ line (pmap mand-line span) ]
(println line)))

(time (mand))

[Dimiter "malkia" Stanev]

Nice! Thanks!

I had troubles using pmap myself, because I was unaware of how lazyness
worked in Clojure (my mistake - I was trying to fill up an array with
data, but did not care of what pmap returns).

[William James]

William James wrote:

>
> I borrowed from Zak Wilson's code in order to clean up
> the Clojure version

That should be "my Clojure version". Zak wrote in Clojure
also.