# 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