Test fib parallelization

readme.md

fib isn't really a parallelize-able algorithm and your impl does worse than nothing. Theoretically, if setting up call stacks is slow, it could be faster if you compute lower Fibonacci numbers while the higher ones are setting up their call stacks. I actually implemented this as a test, because I'm looking for a CL job (:waves:). On my machine at least, this parallelized version isn't better, no surprise there.

The result, even with 40,000... the standard dfib is beating the pdfib. The pdfib on average is using 120% CPU. I could probably partition the threads better, but, its pretty much useless to try to race call stack creation with the computation.

fibs.lisp

(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)))