Alioth binary-tree benchmark
32 views
Skip to first unread message
Simon Brooke
Nov 18, 2008, 5:58:30 AM11/18/08
to Clojure
As a learning exercise and also to continue to investigate Clojure
performance I've roughly translated the Alioth binary-tree benchmark
into Clojure. I chose the binary-tree simply because it's the first of
the Alioth benchmarks in alphabetical collation; I may do others
later.
I've based my implementation on Manuel Giraud's Common LISP
implementation http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees&lang=sbcl&id=2
and followed his algorithm blindly. However Giraud uses the Common
LISP ASH (arithmetic shift) function, and, if there's a built-in
function in Clojure, I did not find it; consequently I implemented an
arithmetic-shift function of my own. As I'm as yet unfamiliar with
Clojure it's likely that my implementation is less than optimal.
;;; -*- mode: clojure -*-
;;;
;;; http://shootout.alioth.debian.org/
;;;
;;; From: Simon Brooke
;;; Based on Common LISP by: Manuel Giraud
;;; Node is either NIL (for leaf nodes) or an improper list (DATA
LEFT . RIGHT)
(defn build-btree [item depth]
(if (zero? depth)
(cons item
(cons nil nil))
(let [item2 (* 2 item)
depth-1 (- depth 1)]
(cons item
(cons (build-btree (- item2 1) depth-1)
(build-btree item2 depth-1))))))
(defn check-node [node]
(if node
(let [data (first node)
kids (rest node)]
(- (+ data (check-node (first kids)))
(check-node (rest kids))))
0))
;;; The Common LISP implementation used the ASH (arithmetic shift)
function.
;;; Whether this was optimisation or just showing off I'm not sure,
;;; but I'm going to blindly follow their implementation. This
function
;;; could almost certainly be improved upon
(defn arithmetic-shift [n i]
(cond
(zero? i) n
(> i 0) (loop [result n expt 0]
(cond
(= expt i) result
true (recur (* result 2) (+ expt 1))))
true (loop [result n expt 0]
(cond
(= expt i) result
true (recur (/ result 2) (- expt 1))))))
(defn loop-depths [max-depth & others]
(let [min-depth (or (first others) 4)]
(loop [d min-depth]
(let [iterations
(arithmetic-shift 1 (+ max-depth min-depth (- d)))]
(if (> d max-depth)
nil ;; return value
(do
(println (* iterations 2)
"\t trees of depth " d "\t check: "
(loop [i 1 sum 0]
(if (> i iterations)
sum
(recur (+ i 1)
(+ sum
(check-node (build-btree i d))
(check-node (build-btree (- i) d)))))))
(recur
(+ d 2))))))))
(defn main [n]
;;; ignore for now the issue of parsing a command-line variable
(println "stretch trees of depth " (+ n 1) "\t check: "
(check-node (build-btree 0 (+ n 1))))
(let [long-lived-tree (build-btree 0 n)]
(loop-depths n)
(println "long lived tree of depth " n "\t check: "
(check-node long-lived-tree))))
;;(main)
I get the following values (normalised to seconds) for (time (main
16)):
Armed Bear
Interpreted 232.54
Compiled 35.3
CMUCL
Interpreted 600.15
Compiled 6.13
Clojure 57.131432
These are not formal benchmark tests; each test is of one run, not
averaged over several, and is performed on my development machine
which has many other processes running.
What's iinteresting (to me)
performance I've roughly translated the Alioth binary-tree benchmark
into Clojure. I chose the binary-tree simply because it's the first of
the Alioth benchmarks in alphabetical collation; I may do others
later.
I've based my implementation on Manuel Giraud's Common LISP
implementation http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees&lang=sbcl&id=2
and followed his algorithm blindly. However Giraud uses the Common
LISP ASH (arithmetic shift) function, and, if there's a built-in
function in Clojure, I did not find it; consequently I implemented an
arithmetic-shift function of my own. As I'm as yet unfamiliar with
Clojure it's likely that my implementation is less than optimal.
;;; -*- mode: clojure -*-
;;;
;;; http://shootout.alioth.debian.org/
;;;
;;; From: Simon Brooke
;;; Based on Common LISP by: Manuel Giraud
;;; Node is either NIL (for leaf nodes) or an improper list (DATA
LEFT . RIGHT)
(defn build-btree [item depth]
(if (zero? depth)
(cons item
(cons nil nil))
(let [item2 (* 2 item)
depth-1 (- depth 1)]
(cons item
(cons (build-btree (- item2 1) depth-1)
(build-btree item2 depth-1))))))
(defn check-node [node]
(if node
(let [data (first node)
kids (rest node)]
(- (+ data (check-node (first kids)))
(check-node (rest kids))))
0))
;;; The Common LISP implementation used the ASH (arithmetic shift)
function.
;;; Whether this was optimisation or just showing off I'm not sure,
;;; but I'm going to blindly follow their implementation. This
function
;;; could almost certainly be improved upon
(defn arithmetic-shift [n i]
(cond
(zero? i) n
(> i 0) (loop [result n expt 0]
(cond
(= expt i) result
true (recur (* result 2) (+ expt 1))))
true (loop [result n expt 0]
(cond
(= expt i) result
true (recur (/ result 2) (- expt 1))))))
(defn loop-depths [max-depth & others]
(let [min-depth (or (first others) 4)]
(loop [d min-depth]
(let [iterations
(arithmetic-shift 1 (+ max-depth min-depth (- d)))]
(if (> d max-depth)
nil ;; return value
(do
(println (* iterations 2)
"\t trees of depth " d "\t check: "
(loop [i 1 sum 0]
(if (> i iterations)
sum
(recur (+ i 1)
(+ sum
(check-node (build-btree i d))
(check-node (build-btree (- i) d)))))))
(recur
(+ d 2))))))))
(defn main [n]
;;; ignore for now the issue of parsing a command-line variable
(println "stretch trees of depth " (+ n 1) "\t check: "
(check-node (build-btree 0 (+ n 1))))
(let [long-lived-tree (build-btree 0 n)]
(loop-depths n)
(println "long lived tree of depth " n "\t check: "
(check-node long-lived-tree))))
;;(main)
I get the following values (normalised to seconds) for (time (main
16)):
Armed Bear
Interpreted 232.54
Compiled 35.3
CMUCL
Interpreted 600.15
Compiled 6.13
Clojure 57.131432
These are not formal benchmark tests; each test is of one run, not
averaged over several, and is performed on my development machine
which has many other processes running.
What's iinteresting (to me)
J. McConnell
Nov 18, 2008, 7:29:49 AM11/18/08
to clo...@googlegroups.com
On Tue, Nov 18, 2008 at 5:58 AM, Simon Brooke <stil...@googlemail.com> wrote:
>
> However Giraud uses the Common
> LISP ASH (arithmetic shift) function, and, if there's a built-in
> function in Clojure, I did not find it;
>
> However Giraud uses the Common
> LISP ASH (arithmetic shift) function, and, if there's a built-in
> function in Clojure, I did not find it;
find-doc is your friend in this case:
user=> (find-doc "shift")
-------------------------
clojure.core/bit-shift-left
([x n])
Bitwise shift left
-------------------------
clojure.core/bit-shift-right
([x n])
Bitwise shift right
- J.
mb
Nov 18, 2008, 9:55:54 AM11/18/08
to Clojure
Hi,
blindly copying code is usually not a good way to learn a new
language....
I don't know, whether this is more idiomatic Clojure code, but
it works...
(defn build-tree
[item depth]
(when (< 0 depth)
(let [i (* 2 item)
d (dec depth)]
[item (build-tree (dec i) d) (build-tree i d)])))
(defn check-node
[z]
(if z
(+ (z 0) (check-node (z 1)) (- (check-node (z 2))))
0))
(defn iterate-trees
[mx mn d]
(let [iterations (bit-shift-left 1 (+ mx mn (- d)))]
(println (* 2 iterations) "\ttrees of depth" d "\tcheck:"
(reduce + (map (fn [i]
(+ (check-node (build-tree i d))
(check-node (build-tree (- i) d))))
(range 1 (inc iterations)))))))
(defn main
[max-depth]
(let [min-depth 4
str-depth (inc max-depth)]
(let [tree (build-tree 0 str-depth)
x (check-node tree)]
(println "stretch tree of depth" str-depth "\tcheck:" x))
(let [long-lived-tree (build-tree 0 max-depth)]
(doseq d (range min-depth str-depth 2)
(iterate-trees max-depth min-depth d))
(println "long lived tree of depth" max-depth "\tcheck:"
(check-node long-lived-tree)))))
> Armed Bear
> Interpreted 232.54
> Compiled 35.3
> CMUCL
> Interpreted 600.15
> Compiled 6.13
> Clojure 57.131432
>
> These are not formal benchmark tests; each test is of one run, not
> averaged over several, and is performed on my development machine
> which has many other processes running.
user=> (time (main 16))
stretch tree of depth 17 check: -1
131072 trees of depth 4 check: -131072
32768 trees of depth 6 check: -32768
8192 trees of depth 8 check: -8192
2048 trees of depth 10 check: -2048
512 trees of depth 12 check: -512
128 trees of depth 14 check: -128
32 trees of depth 16 check: -32
long lived tree of depth 16 check: -1
"Elapsed time: 24222.279088 msecs"
nil
That is 24.2 seconds on my crappy 1.7 GHz Office machine.
Sincerely
Meikel
blindly copying code is usually not a good way to learn a new
language....
I don't know, whether this is more idiomatic Clojure code, but
it works...
(defn build-tree
[item depth]
(when (< 0 depth)
(let [i (* 2 item)
d (dec depth)]
[item (build-tree (dec i) d) (build-tree i d)])))
(defn check-node
[z]
(if z
(+ (z 0) (check-node (z 1)) (- (check-node (z 2))))
0))
(defn iterate-trees
[mx mn d]
(let [iterations (bit-shift-left 1 (+ mx mn (- d)))]
(println (* 2 iterations) "\ttrees of depth" d "\tcheck:"
(reduce + (map (fn [i]
(+ (check-node (build-tree i d))
(check-node (build-tree (- i) d))))
(range 1 (inc iterations)))))))
(defn main
[max-depth]
(let [min-depth 4
str-depth (inc max-depth)]
(let [tree (build-tree 0 str-depth)
x (check-node tree)]
(println "stretch tree of depth" str-depth "\tcheck:" x))
(let [long-lived-tree (build-tree 0 max-depth)]
(doseq d (range min-depth str-depth 2)
(iterate-trees max-depth min-depth d))
(println "long lived tree of depth" max-depth "\tcheck:"
(check-node long-lived-tree)))))
> Armed Bear
> Interpreted 232.54
> Compiled 35.3
> CMUCL
> Interpreted 600.15
> Compiled 6.13
> Clojure 57.131432
>
> These are not formal benchmark tests; each test is of one run, not
> averaged over several, and is performed on my development machine
> which has many other processes running.
stretch tree of depth 17 check: -1
131072 trees of depth 4 check: -131072
32768 trees of depth 6 check: -32768
8192 trees of depth 8 check: -8192
2048 trees of depth 10 check: -2048
512 trees of depth 12 check: -512
128 trees of depth 14 check: -128
32 trees of depth 16 check: -32
long lived tree of depth 16 check: -1
"Elapsed time: 24222.279088 msecs"
nil
That is 24.2 seconds on my crappy 1.7 GHz Office machine.
Sincerely
Meikel
Michael Wood
Nov 18, 2008, 10:35:39 AM11/18/08
to clo...@googlegroups.com
On Tue, Nov 18, 2008 at 4:55 PM, mb <m...@kotka.de> wrote:
[...]
> I don't know, whether this is more idiomatic Clojure code, but
> it works...
[...]
[...]
> I don't know, whether this is more idiomatic Clojure code, but
> it works...
What revision is that? On r1099 I got:
java.lang.IllegalArgumentException: Don't know how to create ISeq
from: Symbol (NO_SOURCE_FILE:31)
so I updated to r1109 and got the same thing.
OK, I see you're using the old doseq syntax. After fixing that I get:
user=> (time (main 16))
stretch tree of depth 17 check: -1
131072 trees of depth 4 check: -131072
32768 trees of depth 6 check: -32768
8192 trees of depth 8 check: -8192
2048 trees of depth 10 check: -2048
512 trees of depth 12 check: -512
128 trees of depth 14 check: -128
32 trees of depth 16 check: -32
long lived tree of depth 16 check: -1
"Elapsed time: 15129.053 msecs"
nil
That's on a 2.8GHz Xeon.
--
Michael Wood <esio...@gmail.com>
Reply all
Reply to author
Forward
0 new messages