Skip to content

Instantly share code, notes, and snippets.

@alphapapa
Last active January 30, 2020 06:24
Show Gist options
  • Save alphapapa/36b117c178dec677258f372c3a01d8b5 to your computer and use it in GitHub Desktop.
Save alphapapa/36b117c178dec677258f372c3a01d8b5 to your computer and use it in GitHub Desktop.
Benchmarking list intersections

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))))
Formx faster than nextTotal runtime# of GCsTotal GC runtime
hash-intersection297.610.04381300
seq-intersectionslowest13.03905200

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))))
Formx faster than nextTotal runtime# of GCsTotal GC runtime
hash-intersection-loop340.850.03606600
seq-intersectionslowest12.29317600

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))))
Formx faster than nextTotal runtime# of GCsTotal GC runtime
hash-intersection-loop1.150.03528500
hash-intersection18.540.04071100
-intersection9.080.75487200
cl-intersection1.856.85447800
seq-intersectionslowest12.70881500
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment