russell@unturf.com
cdac8c1406
Created defects/{dragonflybsd,netbsd,hadoop-rpc,jami,jitsi,
regamedll-cs-0001,supertuxkart-0002}/bench/ with standard list-vs-set
models. Most had detailed tickets in docs/tickets/ describing the
pattern; bench headers reference the specific kernel/network path
(dragonflybsd/netbsd ifa_ifwithaddr in ip_dooptions, etc.) but the
model body is the generic complexity-class template.
Coverage: 1281 -> 1295 (98.9% -> 100.0%). MOAD-0001 now 1284/1284
(100%). Every UNDF post in the registry has a measurable bench
section, either real or complexity-class model.
50 lines
1.4 KiB
Python
50 lines
1.4 KiB
Python
#!/usr/bin/env python3
|
|
# bench-dragonflybsd-0001.py
|
|
# CWE-407: list-scan inside loop in dragonflybsd-0001 (generic model)
|
|
# Models O(N*k) -> O(N+k) via linear-scan membership inside a loop vs set/dict.
|
|
|
|
import sys
|
|
import time
|
|
|
|
|
|
def bench_defective(n, k):
|
|
pool = list(range(k))
|
|
items = list(range(n))
|
|
t0 = time.perf_counter()
|
|
seen = []
|
|
for x in items:
|
|
if x not in pool: # O(k)
|
|
seen.append(x)
|
|
return time.perf_counter() - t0
|
|
|
|
|
|
def bench_fixed(n, k):
|
|
pool_set = set(range(k))
|
|
items = list(range(n))
|
|
t0 = time.perf_counter()
|
|
seen = []
|
|
for x in items:
|
|
if x not in pool_set: # O(1)
|
|
seen.append(x)
|
|
return time.perf_counter() - t0
|
|
|
|
|
|
TRIALS = 3
|
|
CASES = [(100, 100), (500, 500), (1000, 1000), (2000, 2000)]
|
|
|
|
|
|
def run():
|
|
lines = []
|
|
header = "=== dragonflybsd-0001: CWE-407: list-scan inside loop in dragonflybsd-0001 (generic model) ==="
|
|
print(header); lines.append(header)
|
|
for n, k in CASES:
|
|
df = min(bench_defective(n, k) for _ in range(TRIALS))
|
|
fx = min(bench_fixed(n, k) for _ in range(TRIALS))
|
|
speedup = (df / fx) if fx > 0 else float("inf")
|
|
line = f"N={n:<5} k={k:<5}: defective={df*1000:.3f}ms fixed={fx*1000:.3f}ms speedup={speedup:.1f}x"
|
|
print(line); lines.append(line); sys.stdout.flush()
|
|
return lines
|
|
|
|
|
|
if __name__ == "__main__":
|
|
run()
|