Hi everyone,
I spent way too much time on something no user will ever notice.
While poking around `org-columns--set-widths' I realized the old code was
O(n×m) for no good reason — it
rescanned the entire cache once per column. So naturally I had to fix it, even
though the absolute
numbers are microscopic.
What changed
------------
The old algorithm computed column widths "vertically" — for each column it
scanned the entire cache
with `assoc', giving O(n×m). The new code reads "horizontally" — it walks each
cache row once, advancing
list pointers in lockstep with the column definitions. Result: O(m).
Why not `cl-loop`
----------------
I tried an elegant cl-loop version first, but Emacs Lisp lists are
singly-linked, so nth inside the
loop reintroduces O(k) lookups. A plain while with manual setq/setcar
pointer-walking turned out
fastest.
Benchmarks
----------
Benchmark (10 runs each, widths auto-computed from cache)
10 columns (practical case — fits on screen without scrolling):
Rows Cols Old O(n×m) cl-loop New while Speedup
───────────────────────────────────────────────────────────
10 10 0.00019 s 0.00016 s 0.00022 s 0.9×
100 10 0.00174 s 0.00116 s 0.00107 s 1.6×
500 10 0.00939 s 0.00694 s 0.00501 s 1.9×
1000 10 0.01863 s 0.01347 s 0.01256 s 1.5×
2000 10 0.05089 s 0.02652 s 0.02515 s 2.0×
20 columns (for completeness):
500 20 0.03454 s 0.01470 s 0.01096 s 3.2×
2000 20 0.09045 s 0.05868 s 0.05020 s 1.8×
Nobody is going to perceive this. But here's the thing — I had so much
fun. Chasing microseconds, trying cl-loop, watching it lose, reverting
to a raw pointer walk, seeing the while consistently beat the prettier
version by 20%... this is the kind of deeply pointless optimization that
makes hacking on Emacs so satisfying.
The patch is on main and I'm also attaching it here.
Feedback welcome — especially if anyone sees a way to squeeze more out of it!
Best,
--
Slawomir Grochowski
>From f06c61e41a38760561a3bea011ac495a2f423218 Mon Sep 17 00:00:00 2001
From: Slawomir Grochowski <[email protected]>
Date: Sun, 10 May 2026 07:27:58 +0200
Subject: [PATCH] org-colview.el: Increase performance of column width
computation
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
* lisp/org-colview.el (org-columns--set-widths): Optimize the
algorithm from O(n*m) to O(m) by iterating through the cache
only once instead of once per column.
How it worked previously (O(n*m)):
The old algorithm read the data "vertically" (by columns).
For each of the `n' columns, it would iterate over the entire
cache of `m' rows and perform an `assoc' lookup for the column's
value.
How it works now (O(m)):
The new algorithm reads the table "horizontally" (by rows).
It takes advantage of the fact that the data in each cache row
is already laid out in the exact same order as the column definitions.
Benefits:
- We iterate through the cache base (rows) only once.
- We avoid the expensive `assoc` search by walking the pointers of
the row list and the results list simultaneously from left to right.
Implementation Details:
An elegant `cl-loop` approach was initially considered:
(dolist (entry cache)
(cl-loop for i from 0
for triplet in (cdr entry)
do (setf (nth i widths)
(max (nth i widths) (string-width (nth 2 triplet))))))
However, Emacs Lisp lists are singly linked, making `nth` an O(k)
operation. Repeatedly using `nth` inside the loop degraded performance
for shorter rows compared to the original O(n*m) algorithm.
To achieve maximum performance, the final implementation uses a
vanilla Elisp `while` loop that walks the list pointers manually,
avoiding both macro overhead and O(k) `nth` lookups.
Benchmark data (10 runs each, all widths auto-computed from cache):
10 columns (practical case — fits on screen without scrolling):
Rows Cols Old O(n×m) cl-loop New while Speedup
───────────────────────────────────────────────────────────
10 10 0.00019 s 0.00016 s 0.00022 s 0.9×
100 10 0.00174 s 0.00116 s 0.00107 s 1.6×
500 10 0.00939 s 0.00694 s 0.00501 s 1.9×
1000 10 0.01863 s 0.01347 s 0.01256 s 1.5×
2000 10 0.05089 s 0.02652 s 0.02515 s 2.0×
20 columns (wider, for completeness):
Rows Cols Old O(n×m) cl-loop New while Speedup
───────────────────────────────────────────────────────────
10 20 0.00048 s 0.00046 s 0.00044 s 1.1×
100 20 0.00444 s 0.00274 s 0.00287 s 1.5×
500 20 0.03454 s 0.01470 s 0.01096 s 3.2×
1000 20 0.04933 s 0.02403 s 0.02540 s 1.9×
2000 20 0.09045 s 0.05868 s 0.05020 s 1.8×
I consider 10 columns the typical case — any more and most users
would have to scroll horizontally. At 50 columns the speedup
reaches ~2.5×.
The new `while` loop avoids both the per-column `assoc` scan (old) and the
O(k) `nth` penalty on singly-linked lists (cl-loop), walking list pointers
in lockstep instead.
---
lisp/org-colview.el | 30 ++++++++++++++++--------------
1 file changed, 16 insertions(+), 14 deletions(-)
diff --git a/lisp/org-colview.el b/lisp/org-colview.el
index 689f811ca..7ff78fa8d 100644
--- a/lisp/org-colview.el
+++ b/lisp/org-colview.el
@@ -339,20 +339,22 @@ where:
and DISPLAYED-VALUE is the value as it should be displayed, as a string.
SPEC is a list as returned by `org-columns-compile-format'."
(setq org-columns-current-maxwidths
- (apply #'vector
- (mapcar
- (lambda (spec)
- (pcase spec
- (`(,_ ,_ ,(and width (pred wholenump)) . ,_) width)
- (`(,_ ,title . ,_)
- ;; No width is specified in the columns format.
- ;; Compute it by checking all possible values for
- ;; PROPERTY.
- (let ((width (string-width title)))
- (dolist (entry cache width)
- (let ((value (nth 2 (assoc spec (cdr entry)))))
- (setq width (max (string-width value) width))))))))
- org-columns-current-fmt-compiled))))
+ (let ((widths (mapcar (lambda (spec)
+ (pcase spec
+ (`(,_ ,_ ,(and width (pred wholenump)) . ,_) width)
+ (`(,_ ,title . ,_) (string-width title))))
+ org-columns-current-fmt-compiled)))
+ (dolist (entry cache)
+ (let ((triplets (cdr entry))
+ (specs org-columns-current-fmt-compiled)
+ (w widths))
+ (while (and triplets specs w)
+ (unless (wholenump (nth 2 (car specs)))
+ (setcar w (max (car w) (string-width (nth 2 (car triplets))))))
+ (setq triplets (cdr triplets))
+ (setq specs (cdr specs))
+ (setq w (cdr w)))))
+ (apply #'vector widths))))
(defun org-columns--new-overlay (beg end &optional string face)
"Create a new column overlay and add it to the list."
--
2.39.5
