Discussion:
Speed wars 4: OCaml, F#, Clojure, Pascal
(too old to reply)
unknown
2009-02-19 20:46:02 UTC
Permalink
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
2009-02-22 04:54:01 UTC
Permalink
Post by unknown
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
2009-02-22 15:15:12 UTC
Permalink
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
2009-02-22 21:05:29 UTC
Permalink
Post by 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
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?
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
2009-02-23 18:00:28 UTC
Permalink
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.
Zak Wilson
2009-02-25 01:03:54 UTC
Permalink
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
William James
2009-02-25 08:32:53 UTC
Permalink
Post by Zak Wilson
I tried the three Clojure versions on a quad-core machine (2x 2.66 GHz
Non-parallel: 2033ms
Parallel points: 1204ms
Parallel lines: 499ms
Impressive.

I'm surprised at how fast JIT can be. And Clojure is a lot more
to my taste than Common Lisp.
Tom Davies
2009-02-24 12:36:22 UTC
Permalink
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
2009-02-24 13:26:55 UTC
Permalink
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;
Tom Davies
2009-02-25 01:57:01 UTC
Permalink
Two dual core 2.66GHz Xeons: single threaded: 161 seconds, 4 CPUS: 45
seconds (100 iterations, including JVM startup time)
William James
2009-02-25 10:54:52 UTC
Permalink
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
2009-02-25 19:44:05 UTC
Permalink
Post by William James
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))
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
2009-02-25 23:34:54 UTC
Permalink
Post by William James
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.

Loading...