The Computer Language
Benchmarks Game

binary-trees Lisp SBCL #3 program

source code

;;   The Computer Language Benchmarks Game
;;   http://benchmarksgame.alioth.debian.org/
;;;
;;; contributed by Dmitry Ignatiev
;;;

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

(defstruct (node
            ;; vector :type layout optimizes away type information
            ;;  and reduces consing
            (:type vector)
            (:constructor node (item left right)))
  (item 0 :type fixnum)
  (left nil :type (or null node))
  (right nil :type (or null node)))

(deftype node () '(simple-array t (3)))

(defun create-tree (item depth)
  (declare (type fixnum item depth))
  ;; Use of LABELS will force SBCL to use local call convention
  ;;  which will speed up function call
  (labels ((create-node (item depth)
             (declare (type fixnum item depth))
             (let ((node (node item nil nil))
                   (item2 (* item 2)))
               (declare (type fixnum item2))
               (when (> depth 0)
                 (setf (node-left node)
                       (create-node (1- item2) (1- depth))
                       (node-right node)
                       (create-node item2 (1- depth))))
               node)))
    (create-node item (1- depth))))

(defun check-tree (node)
  (declare (type node node))
  ;; Force local call
  (labels ((check-node (node)
             (if (node-left node)
               (the fixnum (- (+ (node-item node)
                                 (check-node (node-left node)))
                              (check-node (node-right node))))
               (node-item node))))
    (check-node node)))

(defun main (&optional (n (parse-integer (or (cdr (last sb-ext:*posix-argv*))
                                             "1"))))
  (declare (type (integer 0 255) n))
  (let* ((min-depth 4)
         (max-depth (max (+ min-depth 2) n))
         (stretch-depth (1+ max-depth)))
    (format t "stretch tree of depth ~d	 check: ~d~%"
            stretch-depth (check-tree (create-tree 0 stretch-depth)))
    (let ((long-lived-tree (create-tree 0 max-depth)))
      (do ((depth min-depth (+ depth 2)))
          ((> depth max-depth))
        (declare (type fixnum depth))
        (do* ((iterations (ash 1 (+ max-depth min-depth (- depth))))
              (check 0)
              (i 1 (1+ i)))
             ((> i iterations)
              (format t "~D	 trees of depth ~D	 check: ~D~%"
                      (the fixnum (* iterations 2)) depth check))
          (declare (type fixnum iterations check i))
          (incf check (check-tree (create-tree i depth)))
          (incf check (check-tree (create-tree (- i) depth)))))
      (format t "long lived tree of depth ~D	 check: ~D~%"
              max-depth (check-tree long-lived-tree)))))
    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
SBCL 1.3.10


Sat, 01 Oct 2016 03:22:15 GMT

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

; compiling file "/home/dunham/benchmarksgame/bench/binarytrees/binarytrees.sbcl-3.sbcl" (written 26 SEP 2015 01:49:11 PM):
; compiling (DECLAIM (OPTIMIZE # ...))
; compiling (DEFSTRUCT (NODE # ...) ...)
; compiling (DEFTYPE NODE ...)
; compiling (DEFUN CREATE-TREE ...)
; compiling (DEFUN CHECK-TREE ...)
; compiling (DEFUN MAIN ...)

; /home/dunham/benchmarksgame_onecore/binarytrees/tmp/binarytrees.sbcl-3.fasl written
; compilation finished in 0:00:00.032
[undoing binding stack and other enclosing state... done]
[saving current Lisp image into sbcl.core:
writing 3120 bytes from the read-only space at 0x1000000
writing 2304 bytes from the static space at 0x1100000
writing 28151808 bytes from the dynamic space at 0x9000000
done]
### START binarytrees.sbcl-3.sbcl_run
(main) (quit)
### END binarytrees.sbcl-3.sbcl_run

0.61s to complete and log all make actions

COMMAND LINE:
/usr/local/bin/sbcl   --noinform --core sbcl.core --userinit /dev/null --load binarytrees.sbcl-3.sbcl_run 12

UNEXPECTED OUTPUT 

1,4c1,7
< stretch tree of depth 7	 check: -1
< 128	 trees of depth 4	 check: -128
< 32	 trees of depth 6	 check: -32
< long lived tree of depth 6	 check: -1
---
> stretch tree of depth 13	 check: -1
> 8192	 trees of depth 4	 check: -8192
> 2048	 trees of depth 6	 check: -2048
> 512	 trees of depth 8	 check: -512
> 128	 trees of depth 10	 check: -128
> 32	 trees of depth 12	 check: -32
> long lived tree of depth 12	 check: -1

PROGRAM OUTPUT:
stretch tree of depth 7	 check: -1
128	 trees of depth 4	 check: -128
32	 trees of depth 6	 check: -32
long lived tree of depth 6	 check: -1