Benchmarking Emacs stuff

juliet-0ac22.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))))))))))

(defvar sums-table (make-hash-table :test #'equal))
(defvar timeouts-table (make-hash-table :test #'equal))

(defun count-sums-3 (a b c n)
  (let* ((key (list a b c n)))
    (unwind-protect
        (or (gethash key sums-table)
            (puthash key (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)))))
                     sums-table))
      (let ((existing-timer (gethash key timeouts-table))
            (timeout-to-use memoize-default-timeout))
        (when existing-timer
          (cancel-timer existing-timer))
        (when timeout-to-use
          (puthash key
                   (run-at-time timeout-to-use nil
                                (lambda ()
                                  (remhash key sums-table)))
                   timeouts-table))))))

(defun count-sums-4 (a b c n)
  (let* ((key (vector a b c n)))
    (unwind-protect
        (or (gethash key sums-table)
            (puthash key (cond ((< n 0) 0)
                               ((= n 0) 1)
                               ((+ (count-sums-4 a b c (- n a))
                                   (count-sums-4 a b c (- n b))
                                   (count-sums-4 a b c (- n c)))))
                     sums-table))
      (let ((existing-timer (gethash key timeouts-table))
            (timeout-to-use memoize-default-timeout))
        (when existing-timer
          (cancel-timer existing-timer))
        (when timeout-to-use
          (puthash key
                   (run-at-time timeout-to-use nil
                                (lambda ()
                                  (remhash key sums-table)))
                   timeouts-table))))))

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

(setf sums-table (make-hash-table :test #'equal))
(setf timeouts-table (make-hash-table :test #'equal))

;;  (bench 'count-sums-4)

(defun count-sums-5 (a b c n)
  (let* ((key (vector a b c n)))
    (or (gethash key sums-table)
        (puthash key (cond ((< n 0) 0)
                           ((= n 0) 1)
                           ((+ (count-sums-5 a b c (- n a))
                               (count-sums-5 a b c (- n b))
                               (count-sums-5 a b c (- n c)))))
                 sums-table))))

(setf sums-table (make-hash-table :test #'equal))

(bench 'count-sums-5)

(defun count-sums-6 (a b c n)
  (let* ((sums-table (eval-when-compile (make-hash-table :test 'equal)))
         (key (vector a b c n)))
    (or (gethash key sums-table)
        (puthash key (cond ((< n 0) 0)
                           ((= n 0) 1)
                           ((+ (count-sums-6 a b c (- n a))
                               (count-sums-6 a b c (- n b))
                               (count-sums-6 a b c (- n c)))))
                 sums-table))))

(bench 'count-sums-6)

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

(bench 'count-sums-7)

(defun count-sums-8 (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-8 a b c (- n a))
                        (count-sums-8 a b c (- n b))
                        (count-sums-8 a b c (- n c))))))))))

(bench 'count-sums-8)

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

(bench 'count-sums-9)

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

(bench 'count-sums-10)

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

;;  (bench 'count-sums-11)

(defun count-sums-12 (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-12 a b c (- n a))
                        (count-sums-12 a b c (- n b))
                        (count-sums-12 a b c (- n c))))))))))

(bench 'count-sums-12)

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

(bench 'count-sums-13)