66 lines
2.1 KiB
Markdown
66 lines
2.1 KiB
Markdown
# 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
|
||
|
||
```elisp
|
||
(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:
|
||
|
||
```elisp
|
||
;; 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
|