performance measurements

Each table row shows performance measurements for this Lisp SBCL program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
120.050.05?649  0% 0% 0% 80%
161.001.0041,588649  100% 1% 0% 1%
2026.6026.64293,668649  1% 1% 100% 1%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read binary-trees-redux benchmark to see what this program should do.

 notes

This is SBCL 1.2.5, an implementation of ANSI Common Lisp.

 binary-trees-redux Lisp SBCL #2 program source code

;;   The Computer Language Benchmarks Game

;;   http://benchmarksgame.alioth.debian.org/

;;;

;;; contributed by Manuel Giraud

;;; modified by Nicolas Neuss

;;; modified by Juho Snellman 2005-10-26

;;;

;;; modified by Witali Kusnezow 2009-01-20

;;;  * simplified structure of leaf nodes

;;;  * optimize GC usage

;;;  * optimize all functions

;;;

;;; modified by Witali Kusnezow 2009-08-20

;;;  * remove GC hacks to satisfy new versions of the sbcl

;;;

;;; modified by Marko Kocic 2011-02-18

;;;  * add declaim to optimize for speed

;;;


;;; Node is either (DATA) (for leaf nodes) or an improper list (DATA LEFT . RIGHT)


(declaim (optimize (speed 3) (debug 0) (space 0) (safety 0)))

(defun build-btree (item depth)
  (declare (fixnum item depth))
  (if (zerop depth) (list item)
      (let ((item2 (+ item item))
            (depth-1 (1- depth)))
        (declare (fixnum item2 depth-1))
        (cons item
				(cons (build-btree (the fixnum (1- item2)) depth-1) 
					  (build-btree item2 depth-1))))))

(defun check-node (node)
  (declare (values fixnum))
  (let ((data (car node))
        (kids (cdr node)))
    (declare (fixnum data))
    (if kids
        (- (+ data (check-node (car kids)))
           (check-node (cdr kids)))
        data)))

(defun loop-depths (max-depth &key (min-depth 4))
  (declare (type fixnum max-depth min-depth))
  (loop for d of-type fixnum from min-depth by 2 upto max-depth do
       (loop with iterations of-type fixnum = (ash 1 (+ max-depth min-depth (- d)))
          for i of-type fixnum from 1 upto iterations
          sum (+ (the fixnum (check-node (build-btree i d)))
                 (the fixnum (check-node (build-btree (- i) d))))
          into result of-type fixnum
          finally
            (format t "~D	 trees of depth ~D	 check: ~D~%"
                    (the fixnum (+ iterations iterations )) d result))))

(defun main (&optional (n (parse-integer
                           (or (car (last #+sbcl sb-ext:*posix-argv*
                                          #+cmu  extensions:*command-line-strings*
                                          #+gcl  si::*command-args*))
                               "1"))))
  (declare (type (integer 0 255) n))
  (format t "stretch tree of depth ~D	 check: ~D~%" (1+ n) (check-node (build-btree 0 (1+ n))))
  (let ((*print-pretty* nil) (long-lived-tree (build-btree 0 n)))
    (purify)
    (loop-depths n)
    (format t "long lived tree of depth ~D	 check: ~D~%" n (check-node long-lived-tree))))

 make, command-line, and program output logs

Tue, 25 Nov 2014 05:01:43 GMT

MAKE:
cp: ‘binarytreesredux.sbcl-2.sbcl’ and ‘./binarytreesredux.sbcl-2.sbcl’ are the same file
SBCL built with: /usr/local/bin/sbcl --userinit /dev/null --batch --eval '(load "binarytreesredux.sbcl-2.sbcl_compile")'
### START binarytreesredux.sbcl-2.sbcl_compile
(handler-bind ((sb-ext:defconstant-uneql      (lambda (c) (abort c))))      (load (compile-file "binarytreesredux.sbcl-2.sbcl" ))) (save-lisp-and-die "sbcl.core" :purify t)
### END binarytreesredux.sbcl-2.sbcl_compile

; compiling file "/home/dunham/benchmarksgame/bench/binarytreesredux/binarytreesredux.sbcl-2.sbcl" (written 07 FEB 2013 10:59:55 AM):
; compiling (DECLAIM (OPTIMIZE # ...))
; compiling (DEFUN BUILD-BTREE ...)
; compiling (DEFUN CHECK-NODE ...)
; compiling (DEFUN LOOP-DEPTHS ...)
; file: /home/dunham/benchmarksgame/bench/binarytreesredux/binarytreesredux.sbcl-2.sbcl
; in: DEFUN LOOP-DEPTHS
;     (+ MAX-DEPTH MIN-DEPTH (- D))
; ==>
;   (+ (+ MAX-DEPTH MIN-DEPTH) (- D))
; 
; note: forced to do GENERIC-+ (cost 10)
;       unable to do inline fixnum arithmetic (cost 2) because:
;       The first argument is a (INTEGER -9223372036854775808 9223372036854775806), not a FIXNUM.
;       The second argument is a (INTEGER -4611686018427387903
;                                 4611686018427387904), not a FIXNUM.
;       The result is a (VALUES
;                        (INTEGER -13835058055282163711 13835058055282163710)
;                        &OPTIONAL), not a (VALUES FIXNUM &REST T).
;       unable to do inline (signed-byte 64) arithmetic (cost 5) because:
;       The result is a (VALUES
;                        (INTEGER -13835058055282163711 13835058055282163710)
;                        &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T).
;       etc.

;     (ASH 1 (+ MAX-DEPTH MIN-DEPTH (- D)))
; 
; note: forced to do full call
;       unable to do inline ASH (cost 3) because:
;       The second argument is a (INTEGER -13835058055282163711
;                                 13835058055282163710), not a (UNSIGNED-BYTE 62).
;       unable to do inline ASH (cost 3) because:
;       The second argument is a (INTEGER -13835058055282163711
;                                 13835058055282163710), not a (UNSIGNED-BYTE 62).
;       etc.

;     (+ MAX-DEPTH MIN-DEPTH (- D))
; ==>
;   (+ (+ MAX-DEPTH MIN-DEPTH) (- D))
; 
; note: doing signed word to integer coercion (cost 20), for:
;       the first argument of GENERIC-+
; 
; note: doing signed word to integer coercion (cost 20), for:
;       the second argument of GENERIC-+

; compiling (DEFUN MAIN ...); 
; compilation unit finished
;   printed 4 notes


; /home/dunham/benchmarksgame_quadcore/binarytreesredux/tmp/binarytreesredux.sbcl-2.fasl written
; compilation finished in 0:00:00.024
[undoing binding stack and other enclosing state... done]
[saving current Lisp image into sbcl.core:
writing 5680 bytes from the read-only space at 0x20000000
writing 3120 bytes from the static space at 0x20100000
writing 50298880 bytes from the dynamic space at 0x1000000000
done]
### START binarytreesredux.sbcl-2.sbcl_run
(main) (quit)
### END binarytreesredux.sbcl-2.sbcl_run

0.42s to complete and log all make actions

COMMAND LINE:
/usr/local/bin/sbcl --dynamic-space-size 512 --noinform --core sbcl.core --userinit /dev/null --load binarytreesredux.sbcl-2.sbcl_run 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1

Revised BSD license

  Home   Conclusions   License   Play