russell@unturf.com
75c7eab158
zulip-0001: user_groups.py lock_subgroups_with_respect_to_supergroup group_ids_found list O(G*F) -> set O(G+F), 142x at N=1000 zulip-0002: user_groups.py update_user_group group_ids_found list O(D*F) -> set O(D+F), 76x at N=1000 zulip-0003: actions/user_groups.py update_users_in_full_members_system_group full_member_group_user_ids list O(M*F) -> set O(M+F), 55x at N=1000 Previous shallow scan marked CLEAN; deeper scan found all 3. MOAD-0002/0003/0004/0005 CLEAN. 3/3 unit tests PASS.
86 lines
2.7 KiB
Python
86 lines
2.7 KiB
Python
"""
|
|
zulip-0002 — CWE-407: group_ids_found list scan in update_user_group
|
|
|
|
Simulates the O(D*F) vs O(D+F) membership check for direct subgroup validation.
|
|
Benchmarks N=100 and N=1000, asserts speedup > 3x.
|
|
"""
|
|
import time
|
|
|
|
|
|
def check_missing_ids_list(direct_subgroups, potential_subgroups):
|
|
"""Original O(D * F): list-based membership."""
|
|
group_ids_found = [group_id for group_id in potential_subgroups]
|
|
group_ids_not_found = [
|
|
group_id for group_id in direct_subgroups if group_id not in group_ids_found
|
|
]
|
|
return group_ids_not_found
|
|
|
|
|
|
def check_missing_ids_set(direct_subgroups, potential_subgroups):
|
|
"""Fixed O(D + F): set-based membership."""
|
|
group_ids_found_set = {group_id for group_id in potential_subgroups}
|
|
group_ids_not_found = [
|
|
group_id for group_id in direct_subgroups if group_id not in group_ids_found_set
|
|
]
|
|
return group_ids_not_found
|
|
|
|
|
|
def benchmark(fn, direct_subgroups, potential_subgroups, reps=200):
|
|
t0 = time.perf_counter()
|
|
for _ in range(reps):
|
|
result = fn(direct_subgroups, potential_subgroups)
|
|
return time.perf_counter() - t0, result
|
|
|
|
|
|
def run_test(N, reps=200):
|
|
potential_subgroups = list(range(N))
|
|
direct_subgroups = list(range(N)) # all match — worst case
|
|
|
|
t_list, r_list = benchmark(check_missing_ids_list, direct_subgroups, potential_subgroups, reps)
|
|
t_set, r_set = benchmark(check_missing_ids_set, direct_subgroups, potential_subgroups, reps)
|
|
|
|
assert r_list == r_set, f"Results differ: {r_list} vs {r_set}"
|
|
speedup = t_list / t_set if t_set > 0 else float("inf")
|
|
|
|
print(f"N={N:5d}: list={t_list*1000:.1f}ms set={t_set*1000:.1f}ms speedup={speedup:.1f}x")
|
|
return speedup
|
|
|
|
|
|
def test_correctness(N):
|
|
# Half the IDs are missing
|
|
potential_subgroups = list(range(0, N, 2))
|
|
direct_subgroups = list(range(N))
|
|
expected = sorted(range(1, N, 2))
|
|
|
|
r_list = check_missing_ids_list(direct_subgroups, potential_subgroups)
|
|
r_set = check_missing_ids_set(direct_subgroups, potential_subgroups)
|
|
|
|
assert sorted(r_list) == expected
|
|
assert sorted(r_set) == expected
|
|
print(f"N={N}: correctness OK")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("=== zulip-0002: update_user_group group_ids_found list vs set benchmark ===")
|
|
print()
|
|
|
|
test_correctness(100)
|
|
test_correctness(1000)
|
|
print()
|
|
|
|
speedup_100 = run_test(100, reps=500)
|
|
speedup_1000 = run_test(1000, reps=100)
|
|
print()
|
|
|
|
PASS = True
|
|
if speedup_100 < 3.0:
|
|
print(f"FAIL N=100: speedup {speedup_100:.1f}x < 3x threshold")
|
|
PASS = False
|
|
if speedup_1000 < 3.0:
|
|
print(f"FAIL N=1000: speedup {speedup_1000:.1f}x < 3x threshold")
|
|
PASS = False
|
|
|
|
if PASS:
|
|
print("PASS")
|
|
else:
|
|
raise SystemExit(1)
|