graph.heads() does O(N^2) access to the graph

Bug #165307 reported by Robert Collins
Affects Status Importance Assigned to Milestone

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: <>.

Martin Pool (mbp)
Changed in bzr:
importance: Undecided → Medium
status: New → Confirmed
Vincent Ladeuil (vila)
Changed in bzr:
status: Confirmed → Fix Released
Revision history for this message
John A Meinel (jameinel) wrote :

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.

Changed in bzr:
status: Fix Released → Confirmed
Jelmer Vernooij (jelmer)
tags: added: check-for-breezy
Jelmer Vernooij (jelmer)
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.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.