93 lines
2.7 KiB
Python
93 lines
2.7 KiB
Python
"""
|
|
zebra-0001: ZIP-317 has_direct_dependencies O(T*S) -> O(T*D) benchmark.
|
|
|
|
Simulates the dependency satisfaction check in block template construction.
|
|
Measures the cost of the Vec-scan approach vs the HashSet approach.
|
|
"""
|
|
|
|
import time
|
|
import random
|
|
import hashlib
|
|
|
|
def make_tx_id(n):
|
|
return hashlib.sha256(str(n).encode()).digest()
|
|
|
|
def simulate_vec_scan(tx_chain_len):
|
|
"""Simulate the buggy Vec scan approach: O(S) per dep check."""
|
|
selected_txs = [] # list of tx_ids (simulating Vec<SelectedMempoolTx>)
|
|
ops = 0
|
|
|
|
for i in range(tx_chain_len):
|
|
tx_id = make_tx_id(i)
|
|
if i > 0:
|
|
# has_direct_dependencies: iterate ALL selected_txs to find 1 dep
|
|
dep_id = make_tx_id(i - 1)
|
|
for sel in selected_txs: # O(S)
|
|
ops += 1
|
|
if sel == dep_id:
|
|
break
|
|
selected_txs.append(tx_id)
|
|
|
|
return ops
|
|
|
|
def simulate_hashset_check(tx_chain_len):
|
|
"""Simulate the fixed HashSet approach: O(D) per dep check."""
|
|
selected_tx_ids = set() # HashSet<tx_id>
|
|
ops = 0
|
|
|
|
for i in range(tx_chain_len):
|
|
tx_id = make_tx_id(i)
|
|
if i > 0:
|
|
# has_direct_dependencies: check each dep against HashSet - O(1)
|
|
dep_id = make_tx_id(i - 1)
|
|
ops += 1 # single O(1) set lookup
|
|
_ = dep_id in selected_tx_ids
|
|
selected_tx_ids.add(tx_id)
|
|
|
|
return ops
|
|
|
|
def benchmark(tx_chain_len, label):
|
|
t0 = time.perf_counter()
|
|
vec_ops = simulate_vec_scan(tx_chain_len)
|
|
t1 = time.perf_counter()
|
|
set_ops = simulate_hashset_check(tx_chain_len)
|
|
t2 = time.perf_counter()
|
|
|
|
vec_time = t1 - t0
|
|
set_time = t2 - t1
|
|
ratio = vec_ops / max(set_ops, 1)
|
|
|
|
print(f"T={tx_chain_len:6d} ({label}): "
|
|
f"vec_ops={vec_ops:9,d} set_ops={set_ops:6,d} "
|
|
f"ratio={ratio:.1f}x "
|
|
f"vec_time={vec_time*1000:.2f}ms set_time={set_time*1000:.2f}ms")
|
|
return ratio
|
|
|
|
def test_zip317_dep_check():
|
|
print("\nzebra-0001: ZIP-317 dep satisfaction check benchmark")
|
|
print("=" * 70)
|
|
|
|
ratios = []
|
|
for t in [10, 50, 100, 500, 1000]:
|
|
r = benchmark(t, "chain deps")
|
|
ratios.append((t, r))
|
|
|
|
print()
|
|
print("Expected O(T²) for Vec scan vs O(T) for HashSet check.")
|
|
print()
|
|
|
|
# Assert ratios scale with T (roughly T/2 ratio in chain topology)
|
|
t10, r10 = ratios[0]
|
|
t1000, r1000 = ratios[-1]
|
|
|
|
assert r1000 > r10 * 5, (
|
|
f"Ratio should grow significantly with T: "
|
|
f"r@T={t10} = {r10:.1f}x, r@T={t1000} = {r1000:.1f}x"
|
|
)
|
|
assert r1000 > 100, (
|
|
f"Expected >100x op-count ratio at T=1000, got {r1000:.1f}x"
|
|
)
|
|
print(f"PASS: op-count ratio at T=1000 is {r1000:.1f}x (expected >100x)")
|
|
|
|
if __name__ == "__main__":
|
|
test_zip317_dep_check()
|