russell@unturf.com
24052ec668
Both were flagged in Wave 17 survey as borderline real defects deferred for follow-up because the fix needed careful design beyond a single-line set hoist. Both shipped now with full bench + ticket + intel. UNDF-1310 symfony-0001 (HIGH) - PropertyAccessor::writeCollection. Doctrine entity collection diff: in_array($item, $collection, true) per item in $previousValue, then in_array($item, $previousValue, true) per item in $collection. O(P*C). Fix: dual lookup (SplObjectStorage for objects + serialize-keyed array for scalars, in_array fallback for resources). Bench: 5.2x at P=C=100, 88x at P=C=2000. UNDF-1311 pyright-0001 (HIGH) - CallHierarchyProvider outgoing/incoming call dedup. _outgoingCalls.find / _incomingCalls.find with composite key (uri, range) walks the list per call expression. O(C^2). Fix: parallel Map<string, entry> keyed by composite serialized form (uri|start.line|start.char|end.line|end.char). Bench: 2.7x at C=100, 22x at C=2000. Total session flagships: 11 (was 9) — 7 CWE-407 + 3 MOAD-0003 + 1 MOAD-0004. Wave 17 borderline backlog now empty.
93 lines
3.2 KiB
Python
93 lines
3.2 KiB
Python
"""
|
|
Benchmark for UNDF-2026-000001310 / symfony-0001
|
|
PropertyAccessor::writeCollection — O(P*C) -> O(P+C) via dual lookup
|
|
(SplObjectStorage for objects + serialize-keyed array for scalars).
|
|
|
|
The Symfony PropertyAccessor walks `previousValue` and `collection` doing
|
|
in_array($item, $other, true) per pass. For P previous items + C new items
|
|
the cost is O(P*C) per write. For a Doctrine entity with a OneToMany
|
|
association of N items being updated to N different items, the cost is
|
|
O(N^2).
|
|
|
|
This Python bench models the cost in equivalent terms (set operations
|
|
mirror SplObjectStorage / serialize lookup). The PHP fix is in the .patch
|
|
file; this bench validates the complexity-class change is real.
|
|
"""
|
|
import random
|
|
import time
|
|
|
|
|
|
class Item:
|
|
__slots__ = ("id",)
|
|
def __init__(self, id_):
|
|
self.id = id_
|
|
|
|
|
|
def bench_defective(previous, collection):
|
|
# Symfony's current shape: in_array($item, $other, true) per pass.
|
|
# In Python: list membership via `in`.
|
|
removed = 0
|
|
for item in previous:
|
|
if item not in collection:
|
|
removed += 1
|
|
added = 0
|
|
for item in collection:
|
|
if item not in previous:
|
|
added += 1
|
|
return removed, added
|
|
|
|
|
|
def bench_fixed(previous, collection):
|
|
# Build object lookup (id() set) once, then O(1) membership.
|
|
# SplObjectStorage / WeakSet equivalent via id().
|
|
prev_set = {id(x) for x in previous}
|
|
coll_set = {id(x) for x in collection}
|
|
removed = sum(1 for item in previous if id(item) not in coll_set)
|
|
added = sum(1 for item in collection if id(item) not in prev_set)
|
|
return removed, added
|
|
|
|
|
|
def best_of(fn, *args, trials=3):
|
|
best = float("inf")
|
|
for _ in range(trials):
|
|
t0 = time.perf_counter()
|
|
fn(*args)
|
|
t = time.perf_counter() - t0
|
|
if t < best:
|
|
best = t
|
|
return best
|
|
|
|
|
|
def main():
|
|
random.seed(42)
|
|
out = []
|
|
out.append("=== symfony-0001: PropertyAccessor::writeCollection O(P*C) -> O(P+C) ===")
|
|
out.append("")
|
|
out.append(f"{'scale':>22} {'defective':>12} {'fixed':>10} {'speedup':>10}")
|
|
out.append("-" * 60)
|
|
for n_prev, n_coll in [
|
|
(100, 100), # small entity collection
|
|
(300, 300), # mid (e.g. user with many tags)
|
|
(500, 500), # large
|
|
(1000, 1000), # very large
|
|
(2000, 2000), # extreme (denormalized media library)
|
|
]:
|
|
# Pool of objects; ~50% overlap between previous and new (typical
|
|
# update pattern: most stays, some added, some removed).
|
|
pool = [Item(i) for i in range(n_prev + n_coll)]
|
|
previous = random.sample(pool, n_prev)
|
|
collection = random.sample(pool, n_coll)
|
|
d = best_of(bench_defective, previous, collection)
|
|
f = best_of(bench_fixed, previous, collection)
|
|
speedup = d / f if f > 0 else float("inf")
|
|
out.append(
|
|
f" P={n_prev:>5} C={n_coll:>5} {d * 1000:>9.2f}ms {f * 1000:>7.2f}ms {speedup:>7.1f}x"
|
|
)
|
|
out.append("")
|
|
out.append("Conclusion: dual-lookup hoist (SplObjectStorage + serialize-keyed array).")
|
|
out.append("Symfony Doctrine entities with deep OneToMany hit O(N^2) without this fix.")
|
|
print("\n".join(out))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|