Benchmarking list intersections

intersection-benchmarks.org

Note that the update to the macros which provide the :setup argument is not published yet…

(bench-multi-lexical ;; :ensure-equal t
  :times 100
  :setup (progn
           (setq lst1 (make-random-list 1000)
                 lst2 (make-random-list 1000))
           (defun make-random-list (n)
             (let ((l nil))
               (dotimes (i n l)
                 (push (random 1500) l))))
           (defun hash-intersection (l1 l2)
             (let ((ht (make-hash-table :test #'equal))
                   (acc nil))
               (mapc (lambda (x) (puthash x t ht)) l1)
               (mapc (lambda (x) (if (gethash x ht nil)
                                     (push x acc)))
                     l2)
               acc)))
  :forms (("seq-intersection" (seq-intersection lst1 lst2))
          ("hash-intersection" (hash-intersection lst1 lst2))))

Form	x faster than next	Total runtime	# of GCs	Total GC runtime
hash-intersection	297.61	0.043813	0	0
seq-intersection	slowest	13.039052	0	0

Now let’s use cl-loop:

(bench-multi-lexical ;; :ensure-equal t
  :times 100
  :setup (progn
           (setq lst1 (make-random-list 1000)
                 lst2 (make-random-list 1000))
           (defun make-random-list (n)
             (let ((l nil))
               (dotimes (i n l)
                 (push (random 1500) l))))
           (defun hash-intersection-loop (l1 l2)
             (let ((ht (make-hash-table :test #'equal) ))
               (cl-loop for e1 in l1
                        do (puthash e1 t ht))
               (cl-loop for e2 in l2
                        when (gethash e2 ht)
                        collect it))))
  :forms (("seq-intersection" (seq-intersection lst1 lst2))
          ("hash-intersection-loop" (hash-intersection-loop lst1 lst2))))

Form	x faster than next	Total runtime	# of GCs	Total GC runtime
hash-intersection-loop	340.85	0.036066	0	0
seq-intersection	slowest	12.293176	0	0

All together:

(bench-multi-lexical ;; :ensure-equal t
  :times 100
  :setup (progn
           (setq lst1 (make-random-list 1000)
                 lst2 (make-random-list 1000))
           (defun make-random-list (n)
             (let ((l nil))
               (dotimes (i n l)
                 (push (random 1500) l))))
           (defun hash-intersection (l1 l2)
             (let ((ht (make-hash-table :test #'equal))
                   (acc nil))
               (mapc (lambda (x) (puthash x t ht)) l1)
               (mapc (lambda (x) (if (gethash x ht nil)
                                     (push x acc)))
                     l2)
               acc))
           (defun hash-intersection-loop (l1 l2)
             (let ((ht (make-hash-table :test #'equal) ))
               (cl-loop for e1 in l1
                        do (puthash e1 t ht))
               (cl-loop for e2 in l2
                        when (gethash e2 ht)
                        collect it))))
  :forms (("-intersection" (-intersection lst1 lst2))
          ("cl-intersection" (cl-intersection lst1 lst2 :test #'equal))
          ("seq-intersection" (seq-intersection lst1 lst2))
          ("hash-intersection" (hash-intersection lst1 lst2))
          ("hash-intersection-loop" (hash-intersection-loop lst1 lst2))))

Form	x faster than next	Total runtime	# of GCs	Total GC runtime
hash-intersection-loop	1.15	0.035285	0	0
hash-intersection	18.54	0.040711	0	0
-intersection	9.08	0.754872	0	0
cl-intersection	1.85	6.854478	0	0
seq-intersection	slowest	12.708815	0	0