UNDF: UNDF-2026-000000389

emacs-0002: bytecomp--code-strings member O(F²) per file — MEDIUM

Summary

lisp/emacs-lisp/bytecomp.el deduplicates bytecode strings within a compiled file using (member code bytecomp--code-strings). The list bytecomp--code-strings grows by one entry per unique lambda compiled in the file. For a file with F lambdas/defuns, total membership-check work is O(1 + 2 + … + F) = O(F²/2).

Location

lisp/emacs-lisp/bytecomp.el — around line 3173

(let* ((code (cadr compiled))
       (prev (member code bytecomp--code-strings)))   ; ← O(N) scan, N grows
  (if prev
      (car prev)
    (push code bytecomp--code-strings)                ; list grows here
    code))

bytecomp--code-strings is reset to nil once per top-level compilation pass (per file), so all lambdas in the file share the same accumulating list.

Severity

MEDIUM — Affects the byte-compiler. Large Emacs Lisp files are disproportionately slow to byte-compile:

File	Approx functions	Op count
Small util	30	~450
`bytecomp.el` (~200 fns)	200	~20 000
`org.el` (~1 000 fns)	1 000	~500 000
Monolith package (3 000 fns)	3 000	~4 500 000

Measured ratio for F=1000: ~250× vs O(F) using a hash table.

Fix

Replace the list with a hash table keyed on bytecode string identity:

;; Initialize (in byte-compile-from-buffer and reset sites):
(bytecomp--code-strings-ht (make-hash-table :test 'equal))

;; At deduplication site:
(let* ((code (cadr compiled))
       (prev (gethash code bytecomp--code-strings-ht)))
  (if prev
      prev
    (puthash code code bytecomp--code-strings-ht)
    code))

This reduces per-lambda dedup from O(F) → O(1) amortized, making the full file compile in O(F) instead of O(F²).

References

lisp/emacs-lisp/bytecomp.el line ~3173 (member code bytecomp--code-strings)
lisp/emacs-lisp/bytecomp.el line ~498 (defvar bytecomp--code-strings)
lisp/emacs-lisp/bytecomp.el line ~2424, ~2588 (reset sites)
CWE-407: Inefficient Algorithmic Complexity

2.1 KiB Raw Permalink Blame History Unescape Escape