russell@unturf.com
e92597895e
flightgear-0001: addSegment/addParking std::find on m_nodes vector O(S*N), 50x flightgear-0002: Dijkstra findShortestRoute vector unvisited O(V^2), 13.6x flightgear-0003: A* airway search linear findInOpen O(E*V), 4x
106 lines
3.3 KiB
Python
106 lines
3.3 KiB
Python
"""
|
|
flightgear-0001: FGGroundNetwork addSegment/addParking node dedup
|
|
DEFECT: std::find on m_nodes vector O(S*N) per segment add
|
|
FIX: unordered_set for O(1) membership check
|
|
|
|
Simulates our ground network node dedup pattern during airport loading.
|
|
Large airports (KJFK, EGLL, EDDF) have 200-500 nodes and 400-1000 segments.
|
|
"""
|
|
import time
|
|
|
|
|
|
def add_segment_unpatched(nodes_list, from_node, to_node):
|
|
"""Original: linear scan of nodes list for dedup."""
|
|
if from_node not in nodes_list: # O(N) scan
|
|
nodes_list.append(from_node)
|
|
if to_node not in nodes_list: # O(N) scan
|
|
nodes_list.append(to_node)
|
|
|
|
|
|
def add_segment_patched(nodes_list, node_set, from_node, to_node):
|
|
"""Patched: hash set for O(1) dedup."""
|
|
if from_node not in node_set: # O(1)
|
|
node_set.add(from_node)
|
|
nodes_list.append(from_node)
|
|
if to_node not in node_set: # O(1)
|
|
node_set.add(to_node)
|
|
nodes_list.append(to_node)
|
|
|
|
|
|
def build_segments(n_nodes):
|
|
"""Build a realistic ground network segment list.
|
|
Each node connects to 2-4 neighbors (taxiway graph).
|
|
"""
|
|
segments = []
|
|
for i in range(n_nodes):
|
|
# Each node connects to next and one skip-ahead (realistic taxiway topology)
|
|
segments.append((i, (i + 1) % n_nodes))
|
|
if i % 3 == 0:
|
|
segments.append((i, (i + 5) % n_nodes))
|
|
if i % 7 == 0:
|
|
segments.append((i, (i + 13) % n_nodes))
|
|
return segments
|
|
|
|
|
|
def bench_unpatched(segments):
|
|
nodes_list = []
|
|
t0 = time.perf_counter()
|
|
for from_n, to_n in segments:
|
|
add_segment_unpatched(nodes_list, from_n, to_n)
|
|
return time.perf_counter() - t0, len(nodes_list)
|
|
|
|
|
|
def bench_patched(segments):
|
|
nodes_list = []
|
|
node_set = set()
|
|
t0 = time.perf_counter()
|
|
for from_n, to_n in segments:
|
|
add_segment_patched(nodes_list, node_set, from_n, to_n)
|
|
return time.perf_counter() - t0, len(nodes_list)
|
|
|
|
|
|
def test_correctness():
|
|
"""Verify patched produces identical node list."""
|
|
segments = build_segments(200)
|
|
|
|
nodes_unpatched = []
|
|
for f, t in segments:
|
|
add_segment_unpatched(nodes_unpatched, f, t)
|
|
|
|
nodes_patched = []
|
|
node_set = set()
|
|
for f, t in segments:
|
|
add_segment_patched(nodes_patched, node_set, f, t)
|
|
|
|
assert nodes_unpatched == nodes_patched, "Node lists must be identical"
|
|
assert len(nodes_unpatched) == 200
|
|
print(f"PASS correctness: {len(nodes_unpatched)} nodes, lists identical")
|
|
|
|
|
|
def test_performance():
|
|
"""Benchmark at N=500 (large airport like KJFK)."""
|
|
n_nodes = 500
|
|
segments = build_segments(n_nodes)
|
|
print(f"Segments: {len(segments)}, Nodes: {n_nodes}")
|
|
|
|
# Warm up
|
|
bench_unpatched(segments)
|
|
bench_patched(segments)
|
|
|
|
# Benchmark
|
|
iters = 20
|
|
t_unpatched = sum(bench_unpatched(segments)[0] for _ in range(iters)) / iters
|
|
t_patched = sum(bench_patched(segments)[0] for _ in range(iters)) / iters
|
|
|
|
ratio = t_unpatched / t_patched if t_patched > 0 else float('inf')
|
|
print(f"Unpatched: {t_unpatched*1e6:.1f} us")
|
|
print(f"Patched: {t_patched*1e6:.1f} us")
|
|
print(f"Ratio: {ratio:.1f}x")
|
|
|
|
assert ratio > 2.0, f"Expected >2x speedup, got {ratio:.1f}x"
|
|
print(f"PASS performance: {ratio:.1f}x speedup")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
test_correctness()
|
|
test_performance()
|