记录第一次给 GNU/Emacs 上游贡献代码的经历

Recently, I noticed that when I open a large number of buffers in Emacs (for example, all 1000+ files in a Rust project), switching between tabs using tab-line becomes noticeably sluggish. I suspected a performance issue somewhere.

After conducting a thorough investigation using (profiler-start) and (profiler-report), I obtained the following CPU usage statistics:

3344  84% - redisplay_internal (C function)
2665  67%  - eval
2608  66%   - tab-line-format
2607  66%    - tab-line-tabs-fixed-window-buffers
2520  63%     - #<byte-code-function 337>
2507  63%      - seq-position
2489  63%       - seq-do
2485  63%        - mapc
2130  54%         - #<byte-code-function 3A4>
 623  15%            equal
   2   0%            throw
  12   0%         make-closure
  84   2%     + tab-line-tabs-window-buffers
   1   0%    + tab-line-cache-key-default
  48   1%   + mode--line-format-right-align
   5   0%   + breadcrumb--header-line
   2   0%   + if
   1   0%     unless

Upon identifying the corresponding code, it became clear that the performance bottleneck was within the tab-line-tabs-fixed-window-buffers function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


(defun tab-line-tabs-fixed-window-buffers ()
  "Like `tab-line-tabs-window-buffers' but keep stable sorting order.
This means that switching to a buffer previously shown in the same
window will keep the same order of tabs that was before switching.
And newly displayed buffers are added to the end of the tab line."
  (let* ((old-buffers (window-parameter nil 'tab-line-buffers))
         (new-buffers (sort (tab-line-tabs-window-buffers)
                            :key (lambda (buffer)
                                   (or (seq-position old-buffers buffer)
                                       most-positive-fixnum)))))
    (set-window-parameter nil 'tab-line-buffers new-buffers)
    new-buffers))

When old-buffers is large, using seq-position within a sort results in an O(N^2) time complexity—a significant performance problem.

The seq-position implementation essentially looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


(cl-defgeneric seq-position (sequence elt &optional testfn)
  "Return the (zero-based) index of the first element in SEQUENCE \"equal\" to ELT.
\"Equality\" is defined by the function TESTFN, which defaults to `equal'."
  (let ((index 0))
    (catch 'seq--break
      (seq-doseq (e sequence)
        (when (funcall (or testfn #'equal) e elt)
          (throw 'seq--break index))
        (setq index (1+ index)))
      nil)))

Finding an element’s index requires nearly traversing the entire list, which is inefficient. To resolve this issue, I used a space-for-time optimization by caching the list’s indices in a hash table.

Here’s the improved function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


(defun tab-line-tabs-fixed-window-buffers ()
  "Like `tab-line-tabs-window-buffers' but keep stable sorting order.
This means that switching to a buffer previously shown in the same
window will keep the same order of tabs that was before switching.
And newly displayed buffers are added to the end of the tab line."
  (let* ((old-buffers (window-parameter nil 'tab-line-buffers))
         (buffer-positions (let ((index-table (make-hash-table :test 'eq)))
                             (seq-do-indexed
                              (lambda (buf idx) (puthash buf idx index-table))
                              old-buffers)
                             index-table))
         (new-buffers (sort (tab-line-tabs-window-buffers)
                            :key (lambda (buffer)
                                   (gethash buffer buffer-positions
                                            most-positive-fixnum)))))
    (set-window-parameter nil 'tab-line-buffers new-buffers)
    new-buffers))

By caching buffer indices in a hash-map, the function now handles any number of buffers without perceptible slowdowns.

I submitted this patch to bug-gnu-emacs, and the upstream maintainer confirmed it as the right fix: https://lists.gnu.org/archive/html/bug-gnu-emacs/2024-07/msg00332.html.

This is my first contribution to GNU/Emacs, and from version 31.0.51 onwards, my code will be included—what an exhilarating experience!

Interestingly, Richard Stallman commented on my thread, although he later mentioned it was a mistake: https://lists.gnu.org/archive/html/bug-gnu-emacs/2024-07/msg00380.html.