perf: replace O(N) two-phase BFS in find_merge_base with simultaneous bidirectional BFS
The old algorithm walked ALL ancestors of commit A before touching B, making merge-base search O(total_history). Branches with nearby LCAs — the common case for feature branches — paid the full cost of the entire commit graph.
Replace with simultaneous bidirectional BFS: expand both frontiers one step at a time, stop the moment any commit appears in both seen_a and seen_b. Cost is now O(distance_to_LCA), which for a typical feature branch with one day of commits is ~2 reads instead of thousands.
TDD: added test_bidirectional_terminates_early (monkeypatches read_commit to count calls; asserts ≤10 reads for a 100-commit chain where LCA is 1 hop away) and test_deep_chain_diamond (50-commit chain, 5-commit diverging branches).
sha256:81cb9a6b5afb09ea2e450246c04a23c69826f1c567d1d13825eca72b8cf84b41
sha
sha256:817b8d7e334126e09be06ac0963104c6cd8ed2dcb89c46cfe31a9a977834d5f9
snapshot
← Older
Oldest on task/bidirectional-merge-base-bfs
All commits
Newer →
Latest on task/bidirectional-merge-base-bfs
0 comments
To add a comment, use the Muse CLI:
muse hub commit comment sha256:81cb9a6b5afb09ea2e450246c04a23c69826f1c567d1d13825eca72b8cf84b41 --body "your comment"
No comments yet. Be the first to start the discussion.