Cache results of flycheck-goto-line to speed up overlay creation

[cpitclaudel]

Overlay creation can have significant costs in large buffers, even with a relatively small numbers of errors. The previous implementation of flycheck-goto-line counted lines from (point-min) for each error, while this new implementation starts counting from the last position returned by flycheck-goto-line, when possible. This is particularly valuable when errors are sorted by line, because we end up scanning the whole buffer at most once, instead of once per error.

I wrote the following benchmark to measure the impact of this:

;; Save as `flycheck-benchmark.el'
;; Run as `cask exec emacs -Q --batch -l flycheck-benchmark.el'

(byte-compile-file "flycheck.el")
(require 'flycheck "flycheck.elc")

;; environment.py in Sphinx
(defconst flycheck-benchmark-nerrors 120)
(defconst flycheck-benchmark-file "flycheck.el")

(defconst flycheck-benchmark-buffer
  (with-current-buffer (get-buffer-create "*flycheck-benchmarks*")
    (insert-file-contents flycheck-benchmark-file)
    (current-buffer)))

(defconst flycheck-benchmark-nlines
  (with-current-buffer flycheck-benchmark-buffer
    (goto-char (point-max))
    (line-number-at-pos)))

(defconst flycheck-benchmark-lines
  (let ((lines nil)
        (rng (cl-make-random-state)))
    (dotimes (_ flycheck-benchmark-nerrors)
      (push (cl-random (1- flycheck-benchmark-nlines) rng) lines))
    lines))

(defconst flycheck-benchmark-errors
  (mapcar
   (lambda (line)
     (flycheck-error-new
      :line line :column 1
      :end-line (1+ line) :end-column 1
      :buffer flycheck-benchmark-buffer
      :checker 'emacs-lisp
      :message "dummy error"
      :filename flycheck-benchmark-file
      :level 'warning))
   flycheck-benchmark-lines))

(progn
  (with-current-buffer flycheck-benchmark-buffer
    (delete-all-overlays)
    (goto-char (point-min))
    (setq flycheck-current-errors nil)
    (print
     (benchmark-run-compiled 1
       (flycheck-report-current-errors flycheck-benchmark-errors)))))

It reports a configurable number of overlays (default: 120) in a buffer containing the contents of flycheck.el (which we can hopefully agree is "reasonably" large, at ~12k lines ^^).

Running the benchmark I get a fairly consistent 290ms with one GC (15ms) for the old version, and a fairly consistent 27-28ms with one GC (15ms) for the old version, so this patch provides a roughly 10x speedup on this example.

With a smaller number of errors (57, the number of errors currently in subr.el in the Emacs distribution) I get 160ms vs 27ms, and even with 15 errors I get 58ms vs 27ms. With a larger number of errors (400, the current threshold), I get 850ms vs 16ms (50x).

I'm not sure the fluctuations in the faster code (16 vs 27ms) are significant, but the speedup definitely is :)

I'm not a fan of the added complexity, but since this is a case where we're causing measurable Emacs pauses on even moderately-sized files I think it's worth considering.

[fmdkdd]

10x is a huge speedup for the added complexity. Great work!

Couldn't the cache be buffer-local?

[cpitclaudel]

Couldn't the cache be buffer-local?

Good point! And it saves the buffer check.

[fmdkdd]

Yup, still looks good.