The Computer Language
Benchmarks Game

binary-trees Clojure #2 program

source code

;; The Computer Language Benchmarks Game
;; http://benchmarksgame.alioth.debian.org/

;; Adapted from the Java -server version
;; contributed by Marko Kocic
;; modified by Kenneth Jonsson, restructured to allow usage of 'pmap'
;; modified by Andy Fingerhut to use faster primitive math ops, and
;; deftype instead of defrecord for smaller tree nodes.
;; modified by Rich Hickey for Clojure 1.3
;; modified promise/delivery improvement by Stuart Halloway
;; small hints by David Nolen and Alex Miller
                                        ;
(ns binarytrees
  (:gen-class))

(set! *warn-on-reflection* true)
(set! *unchecked-math* true)

(def ^:const ^long min-depth 4)

(deftype TreeNode [left right ^long item])

(defn make-tree [^long item ^long depth]
  (if (zero? depth)
    (TreeNode. nil nil item)
    (let [i2 (* 2 item)
          ddec (dec depth)]
      (TreeNode. (make-tree (dec i2) ddec) (make-tree i2 ddec) item))))

(defn item-check ^long [^TreeNode node]
  (if (nil? (.left node))
    (.item node)
    (- (+ (.item node)
          (item-check (.left node)))
       (item-check (.right node)))))

(defn iterate-trees [^long mx ^long mn ^long d]
  (let [iterations (bit-shift-left 1 (long (+ mx mn (- d))))]
    (format "%d\t trees of depth %d\t check: %d"
            (* 2 iterations)
            d
            (loop [result 0
         i 1]
    (if (= i (inc iterations))
      result
      (recur (+ result
                (item-check (make-tree i d))
                (item-check (make-tree (- i) d)))
             (inc i)))))))

(defn main [^long max-depth]
  (let [stretch-depth (inc max-depth)]
    (let [tree (make-tree 0 stretch-depth)
          check (item-check tree)]
      (println (format "stretch tree of depth %d\t check: %d" stretch-depth check)))
    (let [agents (repeatedly (.availableProcessors (Runtime/getRuntime)) #(agent []))
          long-lived-tree (make-tree 0 max-depth)]
      (loop [depth min-depth
             [a & more] (cycle agents)
             results []]
        (if (> depth stretch-depth)
          (doseq [r results] (println @r))
          (let [result (promise)]
            (send a (fn [_]
                      (deliver result (iterate-trees max-depth min-depth depth))))
            (recur (+ 2 depth) more (conj results result)))))
        (println (format "long lived tree of depth %d\t check: %d" max-depth (item-check long-lived-tree))))))

(defn -main [& args]
  (let [n (if (first args) (Long/parseLong (first args)) 0)
        max-depth (if (> (+ min-depth 2) n) (+ min-depth 2) n)]
    (main max-depth)
    (shutdown-agents)))
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
Clojure 1.8.0
java version "1.8.0_45"
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)


Sun, 26 Mar 2017 03:55:23 GMT

MAKE:
mv binarytrees.clojure-2.clojure binarytrees.clj
/usr/local/src/jdk1.8.0_121/bin/java -Dclojure.compiler.direct-linking=true -Dclojure.compile.path=. -cp .:/usr/local/src/clojure/clojure-1.8.0.jar clojure.lang.Compile binarytrees
Compiling binarytrees to .
1.20s to complete and log all make actions

COMMAND LINE:
/usr/local/src/jdk1.8.0_121/bin/java  -cp .:/usr/local/src/clojure/clojure-1.8.0.jar binarytrees 7

UNEXPECTED OUTPUT 

1,5c1,4
< stretch tree of depth 8	 check: -1
< 256	 trees of depth 4	 check: -256
< 64	 trees of depth 6	 check: -64
< 16	 trees of depth 8	 check: -16
< long lived tree of depth 7	 check: -1
---
> stretch tree of depth 8	 check: 511
> 128	 trees of depth 4	 check: 3968
> 32	 trees of depth 6	 check: 4064
> long lived tree of depth 7	 check: 255

PROGRAM OUTPUT:
stretch tree of depth 8	 check: -1
256	 trees of depth 4	 check: -256
64	 trees of depth 6	 check: -64
16	 trees of depth 8	 check: -16
long lived tree of depth 7	 check: -1