Created
September 2, 2019 18:28
-
-
Save alphapapa/9325593df6305d4f62d8afb1371e8635 to your computer and use it in GitHub Desktop.
Benchmarking Emacs stuff
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;;; 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment