The Little Schemer vs. regular Clojure versions of the Collatz function

benchmark.clj

(ns little-schemer.benchmark
  "Benchmarking the function C of the Collatz Conjencture:

  http://en.wikipedia.org/wiki/Collatz_conjecture

  in regular Clojure (C*) and as it is defined in the book The Little Schemer,
  where all of the parts are defined recursively in terms of add1 and sub1."
  (:gen-class)
  (:refer-clojure :exclude [even?])
  (:require [criterium.core :refer [quick-bench]]))

(def add1 inc)

(def sub1 dec)

(defn gt [n m]
  (cond
    (zero? n) false
    (zero? m) true
    :else (gt (sub1 n) (sub1 m))))

(defn lt [n m]
  (cond
    (zero? m) false
    (zero? n) true
    :else (lt (sub1 n) (sub1 m))))

(defn eq= [n m]
  (cond
    (gt n m) false
    (lt n m) false
    :else true))

(defn one? [n] (eq= n 1))

(defn minus [n m]
  (cond
    (zero? m) n
    :else (sub1 (minus n (sub1 m)))))

(defn plus [n m]
  (cond
    (zero? m) n
    :else (add1 (plus n (sub1 m)))))

(defn times [n m]
  (cond
    (zero? m) 0
    :else (plus n (times n (sub1 m)))))

(defn div [n m]
  (cond
    (lt n m) 0
    :else (add1 (div (minus n m) m))))

(defn even? [n] (= (times (div n 2) 2) n))

(defn C [n]
  (cond
    (one? n) 1
    (even? n) (C (div n 2))
    :else (C (add1 (times 3 n)))))

(defn C-recur [n]
  (cond
    (one? n) 1
    (even? n) (recur (div n 2))
    :else (recur (add1 (times 3 n)))))

(defn C* [n]
  (cond
    (= 1 n) 1
    (clojure.core/even? n) (C* (quot n 2))
    :else (C* (inc (* n 3)))))

(defn C*-recur [n]
  (cond
    (= 1 n) 1
    (clojure.core/even? n) (recur (quot n 2))
    :else (recur (inc (* n 3)))))

(defn benchmark-with-C [f upto]
  (quick-bench
   (map (fn [n]
          (try (f n)
               (catch Exception e "Exception")))
        (range 1 (inc upto)))))

(defn -main [& args]
  (println "---------------------------")
  (println "*** Version: C ***")
  (benchmark-with-C C 100)
  (println "*** Version: C* ***")
  (benchmark-with-C C* 100)
  (println "*** Version: C-recur ***")
  (benchmark-with-C C-recur 100)
  (println "*** Version: C*-recur ***")
  (benchmark-with-C C*-recur 100)
  (println "---------------------------")
  (println "Done."))

(comment

;;; Running in the REPL ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  (benchmark-with-C C 100)
  ;; WARNING: Final GC required 39.21590953593276 % of runtime
  ;; Evaluation count : 24028626 in 6 samples of 4004771 calls.
  ;; Execution time mean : 24.110505 ns
  ;; Execution time std-deviation : 0.488287 ns
  ;; Execution time lower quantile : 23.756427 ns ( 2.5%)
  ;; Execution time upper quantile : 24.769063 ns (97.5%)
  ;; Overhead used : 1.521922 ns

  (benchmark-with-C C-recur 100)
  ;; WARNING: Final GC required 39.86826196520184 % of runtime
  ;; Evaluation count : 24155772 in 6 samples of 4025962 calls.
  ;; Execution time mean : 23.743675 ns
  ;; Execution time std-deviation : 0.172086 ns
  ;; Execution time lower quantile : 23.465398 ns ( 2.5%)
  ;; Execution time upper quantile : 23.914141 ns (97.5%)
  ;; Overhead used : 1.521922 ns

  (benchmark-with-C C* 100)
  ;; WARNING: Final GC required 40.32870542053569 % of runtime
  ;; Evaluation count : 23990526 in 6 samples of 3998421 calls.
  ;; Execution time mean : 23.953926 ns
  ;; Execution time std-deviation : 0.128054 ns
  ;; Execution time lower quantile : 23.785568 ns ( 2.5%)
  ;; Execution time upper quantile : 24.102693 ns (97.5%)
  ;; Overhead used : 1.521922 ns

  (benchmark-with-C C*-recur 100)
  ;; WARNING: Final GC required 41.4618926444039 % of runtime
  ;; Evaluation count : 22538304 in 6 samples of 3756384 calls.
  ;; Execution time mean : 25.145302 ns
  ;; Execution time std-deviation : 0.294451 ns
  ;; Execution time lower quantile : 24.854774 ns ( 2.5%)
  ;; Execution time upper quantile : 25.581137 ns (97.5%)
  ;; Overhead used : 1.521922 ns

;;; AOT compiled as JAR: ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  (benchmark-with-C C 100)
  ;; WARNING: Final GC required 6.9430291532975765 % of runtime
  ;; Evaluation count : 26723670 in 6 samples of 4453945 calls.
  ;; Execution time mean : 20.673350 ns
  ;; Execution time std-deviation : 0.336379 ns
  ;; Execution time lower quantile : 20.229325 ns ( 2.5%)
  ;; Execution time upper quantile : 21.036474 ns (97.5%)
  ;; Overhead used : 1.381180 ns

  (benchmark-with-C C* 100)
  ;; WARNING: Final GC required 5.392905913662796 % of runtime
  ;; Evaluation count : 28502220 in 6 samples of 4750370 calls.
  ;; Execution time mean : 26.439109 ns
  ;; Execution time std-deviation : 7.557624 ns
  ;; Execution time lower quantile : 20.460697 ns ( 2.5%)
  ;; Execution time upper quantile : 35.534286 ns (97.5%)
  ;; Overhead used : 1.381180 ns

  (benchmark-with-C C-recur 100)
  ;; WARNING: Final GC required 4.406003961839898 % of runtime
  ;; Evaluation count : 27925104 in 6 samples of 4654184 calls.
  ;; Execution time mean : 21.065146 ns
  ;; Execution time std-deviation : 0.474596 ns
  ;; Execution time lower quantile : 20.569821 ns ( 2.5%)
  ;; Execution time upper quantile : 21.625538 ns (97.5%)
  ;; Overhead used : 1.381180 ns

  (benchmark-with-C C*-recur 100)
  ;; WARNING: Final GC required 4.944241733173213 % of runtime
  ;; Evaluation count : 26429832 in 6 samples of 4404972 calls.
  ;; Execution time mean : 21.332169 ns
  ;; Execution time std-deviation : 0.513333 ns
  ;; Execution time lower quantile : 20.862548 ns ( 2.5%)
  ;; Execution time upper quantile : 22.140252 ns (97.5%)
  ;; Overhead used : 1.381180 ns

  )

So it turns out that my benchmark wasn't actually doing any work, because of the lazyness of using map. After using dorun as suggsted by @puredanger, I got the following results:

(benchmark-with-C C 100)
;; Evaluation count : 6 in 6 samples of 1 calls.
;;              Execution time mean : 13.696979 sec
;;     Execution time std-deviation : 192.185389 ms
;;    Execution time lower quantile : 13.472868 sec ( 2.5%)
;;    Execution time upper quantile : 13.997174 sec (97.5%)
;;                    Overhead used : 1.394051 ns

(benchmark-with-C C-recur 100)
;; Evaluation count : 5994 in 6 samples of 999 calls.
;;              Execution time mean : 104.407516 µs
;;     Execution time std-deviation : 1.769333 µs
;;    Execution time lower quantile : 102.315924 µs ( 2.5%)
;;    Execution time upper quantile : 106.295153 µs (97.5%)
;;                    Overhead used : 1.394051 ns

(benchmark-with-C C* 100)
;; Evaluation count : 6 in 6 samples of 1 calls.
;;              Execution time mean : 13.568804 sec
;;     Execution time std-deviation : 342.483994 ms
;;    Execution time lower quantile : 13.299620 sec ( 2.5%)
;;    Execution time upper quantile : 14.032113 sec (97.5%)
;;                    Overhead used : 1.394051 ns

(benchmark-with-C C*-recur 100)
;; WARNING: Final GC required 4.2569939630224995 % of runtime
;; Evaluation count : 6096 in 6 samples of 1016 calls.
;;              Execution time mean : 99.754020 µs
;;     Execution time std-deviation : 1.614855 µs
;;    Execution time lower quantile : 97.834236 µs ( 2.5%)
;;    Execution time upper quantile : 101.441397 µs (97.5%)
;;                    Overhead used : 1.394051 ns