91 lines
3.2 KiB
Python
91 lines
3.2 KiB
Python
"""Unit test for electrum-0002: is_forwarded_htlc linear scan O(F*H).
|
|
|
|
The defect is in LNWallet.is_forwarded_htlc which iterates all active
|
|
forwarding sets and checks list membership for each, creating O(F*H)
|
|
where F is the number of active forwarding payment keys and H is the
|
|
average number of HTLCs per forwarding set.
|
|
|
|
Fix: maintain a reverse index dict _htlc_to_forwarding mapping
|
|
htlc_key -> payment_key for O(1) lookups.
|
|
"""
|
|
|
|
import time
|
|
|
|
|
|
def is_forwarded_htlc_BEFORE(active_forwardings, htlc_key):
|
|
"""Original: iterate all forwardings, linear scan each list."""
|
|
for payment_key, htlcs in active_forwardings.items():
|
|
if htlc_key in htlcs: # O(H) scan on list
|
|
return payment_key
|
|
return None
|
|
|
|
|
|
def is_forwarded_htlc_AFTER(htlc_to_forwarding, htlc_key):
|
|
"""Fixed: O(1) dict lookup via reverse index."""
|
|
return htlc_to_forwarding.get(htlc_key)
|
|
|
|
|
|
def make_test_data(num_forwardings, htlcs_per_forwarding):
|
|
"""Create test data simulating active forwarding sets."""
|
|
active_forwardings = {}
|
|
htlc_to_forwarding = {}
|
|
all_htlc_keys = []
|
|
for f in range(num_forwardings):
|
|
payment_key = f"payment_{f:06d}"
|
|
htlcs = []
|
|
for h in range(htlcs_per_forwarding):
|
|
htlc_key = f"htlc_{f:06d}_{h:04d}"
|
|
htlcs.append(htlc_key)
|
|
htlc_to_forwarding[htlc_key] = payment_key
|
|
all_htlc_keys.append(htlc_key)
|
|
active_forwardings[payment_key] = htlcs
|
|
return active_forwardings, htlc_to_forwarding, all_htlc_keys
|
|
|
|
|
|
def test_correctness():
|
|
"""Both implementations must return the same results."""
|
|
active_forwardings, htlc_to_forwarding, all_htlc_keys = make_test_data(50, 10)
|
|
for htlc_key in all_htlc_keys:
|
|
r1 = is_forwarded_htlc_BEFORE(active_forwardings, htlc_key)
|
|
r2 = is_forwarded_htlc_AFTER(htlc_to_forwarding, htlc_key)
|
|
assert r1 == r2, f"Mismatch for {htlc_key}: {r1} vs {r2}"
|
|
# Test missing key
|
|
assert is_forwarded_htlc_BEFORE(active_forwardings, "nonexistent") is None
|
|
assert is_forwarded_htlc_AFTER(htlc_to_forwarding, "nonexistent") is None
|
|
print("PASS: correctness")
|
|
|
|
|
|
def test_performance():
|
|
"""Measure O(F*H) vs O(1) performance for routing node scenario."""
|
|
F = 200 # active forwarding payment sets
|
|
H = 10 # HTLCs per forwarding
|
|
active_forwardings, htlc_to_forwarding, all_htlc_keys = make_test_data(F, H)
|
|
|
|
# Look up the last HTLC (worst case for linear scan)
|
|
target = all_htlc_keys[-1]
|
|
iterations = 5000
|
|
|
|
# Benchmark BEFORE
|
|
t0 = time.perf_counter()
|
|
for _ in range(iterations):
|
|
is_forwarded_htlc_BEFORE(active_forwardings, target)
|
|
t_before = (time.perf_counter() - t0) / iterations
|
|
|
|
# Benchmark AFTER
|
|
t0 = time.perf_counter()
|
|
for _ in range(iterations):
|
|
is_forwarded_htlc_AFTER(htlc_to_forwarding, target)
|
|
t_after = (time.perf_counter() - t0) / iterations
|
|
|
|
ratio = t_before / t_after if t_after > 0 else float('inf')
|
|
print(f"F={F}, H={H}")
|
|
print(f" BEFORE: {t_before*1e6:.1f} us")
|
|
print(f" AFTER: {t_after*1e6:.1f} us")
|
|
print(f" Ratio: {ratio:.1f}x")
|
|
assert ratio > 5.0, f"Expected at least 5x speedup, got {ratio:.1f}x"
|
|
print("PASS: performance")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
test_correctness()
|
|
test_performance()
|