graph.heads() does O(N^2) access to the graph
Bug #165307 reported by
Robert Collins
| Affects | Status | Importance | Assigned to | Milestone | |
|---|---|---|---|---|---|
| Bazaar |
Confirmed
|
Medium
|
Unassigned | ||
| Breezy |
Triaged
|
Medium
|
Unassigned | ||
Bug Description
Graph.heads() repeatedly walks the same region of the graph many times
when cancelling searches. This is very slow when graph access is
anything other than trivially cheap. Specifically this affects merge and
merge commits on packs, so I'm tagging it packs.
affects bzr
tag packs
--
GPG key available at: <http://
| Changed in bzr: | |
| importance: | Undecided → Medium |
| status: | New → Confirmed |
| Changed in bzr: | |
| status: | Confirmed → Fix Released |
Revision history for this message
| John A Meinel (jameinel) wrote | #1 |
| Changed in bzr: | |
| status: | Fix Released → Confirmed |
| tags: | added: check-for-breezy |
| tags: | removed: check-for-breezy |
| Changed in brz: | |
| status: | New → Triaged |
| importance: | Undecided → Medium |
| tags: | added: performance |
To post a comment you must log in.
I don't think this is actually fixed. KnownGraph.heads() is better than N^2, but does so at a cost of loading the whole graph. Graph.heads() is still O(N^2) I believe.
And there are still a fair number of places that use Graph and Graph.heads() rather than KG.