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#totalgc-countgc-time
    11.221864920999999900.0
    20.78235220240.572720627999999
    37.634342811101.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#totalgc-countgc-time
    13.54474629400.0
    23.49222745100.0
    38.2517775500.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#totalgc-countgc-time
    10.71413567500.0
    20.3288433900.0
    337.158839579244.404030558999999
    41.09367971810.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#totalgc-countgc-time
    10.72961964500.0
    20.32652757800.0
    30.72132590400.0
    41.1496381710.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#totalgc-countgc-time
    10.815312159000000110.1710438879999998
    23.07906778171.247929268
    321.216195114162.8402992590000053
    43.416870617000000361.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#totalgc-countgc-time
    10.88353275210.16912953199999947
    20.567906403999999900.0
    30.54181223200.0
    41.0725956700.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)))))