avatar Kisaragi Hiu

Performance comparison between cl-lib, dash, and seq

Caveats: Not compiled

Conclusions

  • In general seq.el is the slowest while dash.el and cl-lib.el can be really similar

  • dash.el anaphoric forms are really slow unless your code is compiled

Hardware

uname -a
emacs -Q --batch --eval "(princ (format \"Emacs: %s\\n\" emacs-version))"
neofetch cpu gpu memory
Linux MF-PC 5.15.45-1-lts #1 SMP Mon, 06 Jun 2022 09:19:52 +0000 x86_64 GNU/Linux
Emacs: 28.1
cpu: AMD Ryzen 5 2600 (12) @ 3.400GHz
gpu: AMD ATI Radeon RX 460/560D / Pro 450/455/460/555/555X/560/560X
memory: 4027MiB / 7958MiB

Comparisons

  • cl-remove-duplicates, -uniq, seq-uniq

    (let ((lst (make-list 1000 8)))
      (k/benchmark-run-compiled 10000
        (cl-remove-duplicates lst)
        (-uniq lst)
        (seq-uniq lst)))
    form# total gc-count gc-time
    1 1.2218649209999999 0 0.0
    2 0.782352202 4 0.572720627999999
    3 7.634342811 10 1.6153261860000008
  • cl-some, -some, seq-some

    (let ((lst (make-list 1000000 8)))
      (k/benchmark-run-compiled 100
        (cl-some #'cl-oddp lst)
        (-some #'cl-oddp lst)
        (seq-some #'cl-oddp lst)))
    form# total gc-count gc-time
    1 3.544746294 0 0.0
    2 3.492227451 0 0.0
    3 8.25177755 0 0.0
  • cl-remove-if-not, -filter, seq-filter

    (let ((lst (make-list 100000 8)))
      (k/benchmark-run 100
        (cl-remove-if-not #'cl-oddp lst)
        (-filter #'cl-oddp lst)
        (--filter (cl-oddp it) lst)
        (seq-filter #'cl-oddp lst)))
    form# total gc-count gc-time
    1 0.714135675 0 0.0
    2 0.32884339 0 0.0
    3 37.158839579 24 4.404030558999999
    4 1.093679718 1 0.17384918300000152

    Wait what? -filter is built on --filter, how is -filter faster?

    Let me try it compiled:

    (let ((lst (make-list 100000 8)))
      (k/benchmark-run-compiled 100
        (cl-remove-if-not #'cl-oddp lst)
        (-filter #'cl-oddp lst)
        (--filter (cl-oddp it) lst)
        (seq-filter #'cl-oddp lst)))
    form# total gc-count gc-time
    1 0.729619645 0 0.0
    2 0.326527578 0 0.0
    3 0.721325904 0 0.0
    4 1.14963817 1 0.1869714140000056

    This is still weird: -filter shouldn't be faster than --filter. Maybe this has something to do with -filter being native-compiled but this code block only being byte-compiled?

  • cl-reduce, -reduce-from, seq-reduce

    (let (alist)
      (dotimes (i 10000)
        (push (cons i (random 100000)) alist))
      (k/benchmark-run 1000
        (cl-reduce #'+ alist :key #'cdr)
        (-reduce-from
         (lambda (acc it)
           (+ acc (cdr it)))
         0 alist)
        (--reduce-from
         (+ acc (cdr it))
         0 alist)
        (seq-reduce
         (lambda (acc it)
           (+ acc (cdr it)))
         alist 0)))
    form# total gc-count gc-time
    1 0.8153121590000001 1 0.1710438879999998
    2 3.079067781 7 1.247929268
    3 21.216195114 16 2.8402992590000053
    4 3.4168706170000003 6 1.0671503399999978

    As before, the anaphoric version takes a surprisingly long time when the call site is not compiled.

    (let (alist)
      (dotimes (i 10000)
        (push (cons i (random 100000)) alist))
      (k/benchmark-run-compiled 1000
        (cl-reduce #'+ alist :key #'cdr)
        (-reduce-from
         (lambda (acc it)
           (+ acc (cdr it)))
         0 alist)
        (--reduce-from
         (+ acc (cdr it))
         0 alist)
        (seq-reduce
         (lambda (acc it)
           (+ acc (cdr it)))
         alist 0)))
    form# total gc-count gc-time
    1 0.883532752 1 0.16912953199999947
    2 0.5679064039999999 0 0.0
    3 0.541812232 0 0.0
    4 1.07259567 0 0.0

    This is more in line with what I expect.

Appendix: Support code

(defmacro k/benchmark-run (n &rest forms)
  "Benchmark each of FORMS with `benchmark-run' with N repetitions."
  (declare (indent 1))
  `(list
    '(form\# total gc-count gc-time)
    'hline
    ,@(cl-loop with index = 1
               for form in forms
               collect
               (prog2
                   (garbage-collect)
                   `(cons ,index (benchmark-run ,n
                                   ,form))
                 (cl-incf index)))))

(defmacro k/benchmark-run-compiled (n &rest forms)
  "Benchmark each of FORMS, byte-compiled, with N repetitions."
  (declare (indent 1))
  `(list
    '(form\# total gc-count gc-time)
    'hline
    ,@(cl-loop with index = 1
               for form in forms
               collect
               (prog2
                   (garbage-collect)
                   `(cons ,index
                          ;; Because `benchmark-run-compiled'
                          ;; quotes the lambda, it is not able to
                          ;; see any let form around it.
                          (benchmark-call (byte-compile (lambda () ,form))
                                          ,n))
                 (cl-incf index)))))