memoize-bench.el

;;; Memoization benchmark -*- lexical-binding: t; -*-

;; Ref: https://github.com/skeeto/emacs-memoize

;; $ emacs -Q --batch -L path/to/memoize -f batch-byte-compile memoize-bench.el
;; $ emacs -Q --batch -L path/to/memoize -l memoize-bench.elc

;; Note: Benchmark requires at least 64-bit integers. Choose one of:
;; * Emacs >= 27
;; * Emacs <= 26 on 64-bit host
;; * Emacs <= 26 on 32-bit host with --with-wide-int

;; The `count-sums' function, an ideal target for memoization, computes
;; the number of ways to sum three numbers (A, B, C) to some target (N).
;; For example, there are 8 ways to sum 1, 3, 5 into 6:
;;   6 = 1+1+1+1+1+1
;;   6 = 1+1+1+3
;;   6 = 1+1+3+1
;;   6 = 1+3+1+1
;;   6 = 3+1+1+1
;;   6 = 3+3
;;   6 = 1+5
;;   6 = 5+1

;; Output on my machine:
;;   count-sums-1     (1.558840815 298 1.0068730169999998)
;;   count-sums-2     (0.000993427 0 0.0)
;; Takeaway: The memoize package is 3 orders of magnitude slower than
;; just doing it yourself!

(require 'benchmark)
(require 'cl-lib)
(require 'memoize)

(defun bench (f)
  (princ
   (format "%-16s %S\n" f
           (benchmark-run 1
             (cl-assert (= (funcall f 1 3  5  95) 2125576354395057369))
             (cl-assert (= (funcall f 1 3  7 103) 2274358910569289778))
             (cl-assert (= (funcall f 1 3  9 107) 1982808156511599680))
             (cl-assert (= (funcall f 1 5  7 128) 1656941458726184233))
             (cl-assert (= (funcall f 1 5  9 137) 1827027431869835658))
             (cl-assert (= (funcall f 1 5 11 143) 1996711042862723685))
             (cl-assert (= (funcall f 1 7 11 168) 1910877262550578250))
             (cl-assert (= (funcall f 1 9 11 188) 2198774630014494641))))))

(defun count-sums-1 (a b c n)
  (cond ((< n 0) 0)
        ((= n 0) 1)
        ((+ (count-sums-1 a b c (- n a))
            (count-sums-1 a b c (- n b))
            (count-sums-1 a b c (- n c))))))
(memoize 'count-sums-1)

(defun count-sums-2 (a b c n)
  (let ((table (eval-when-compile (make-hash-table :test 'equal)))
        (key (vector a b c n)))
    (let ((result (gethash key table)))
      (if result
          result
        (setf (gethash key table)
              (cond ((< n 0) 0)
                    ((= n 0) 1)
                    ((+ (count-sums-2 a b c (- n a))
                        (count-sums-2 a b c (- n b))
                        (count-sums-2 a b c (- n c))))))))))

(defun simple-memoize (fun)
  (let ((table (make-hash-table :test 'equal)))
    (lambda (&rest args)
      (let ((result (gethash args table)))
        (if result
            result
          (setf (gethash args table)
                (apply fun args)))))))

(defun count-sums-3 (a b c n)
  (cond ((< n 0) 0)
        ((= n 0) 1)
        ((+ (count-sums-3 a b c (- n a))
            (count-sums-3 a b c (- n b))
            (count-sums-3 a b c (- n c))))))
(fset 'count-sums-3 (simple-memoize (symbol-function 'count-sums-3)))

(bench 'count-sums-1)
(bench 'count-sums-2)
(bench 'count-sums-3)