(defparameter *fibs* (make-hash-table :synchronized t))
(defparameter *cores* 4)

(defun pdfib (n)
  (labels ((dfib (n stop prev-thread)
             (let ((ans (gethash n *fibs*)))
               (if ans
                   ans
                   (setf (gethash n *fibs*)
                         (cond
                           ((= n 0) 0)
                           ((= n 1) 1)
                           ((= n stop) (progn (sb-thread:join-thread prev-thread) (gethash n *fibs*)))
                           (t (+ (dfib (- n 1) stop prev-thread) (dfib (- n 2) stop prev-thread)))))))))

    (let ((step (floor n *cores*)) (threads '()))
      (loop for i from 0 to 3
            do (let ((i i) (thread (car threads))) ;; capture for lambda
                   (setf threads (cons (sb-thread:make-thread
                                        (lambda ()
                                          (sb-thread:return-from-thread
                                           (dfib (if (= (+ 1 i) *cores*)
                                                     n
                                                     (* step (+ 1 i)))
                                                 (* step i)
                                                 thread))))
                                       threads))))
      (sb-thread:join-thread (car threads)))))

(defun dfib (n)
  (let ((ans (gethash n *fibs*)))
    (if ans
        ans
        (setf (gethash n *fibs*)
              (cond ((= n 0) 0)
                    ((= n 1) 1)
                    (t (+ (dfib (- n 1)) (dfib (- n 2)))))))))

(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1)) (fib (- n 2))))))


(defun test-pdfib (n)
  (setf *fibs* (make-hash-table :synchronized t))
  (time (pdfib n) ))

(defun test-dfib (n)
  (setf *fibs* (make-hash-table))
  (format t "~d~%" (hash-table-count *fibs*))
  (time (dfib n)))

(defun test-fib (n) (time (fib n)))