jelmer/dulwich — pull request #217 by damz (2014-08-19 16:56:56+00:00)
Title: ProtocolGraphWalker._is_satisfied should not travel all the paths.

We just found out that the way `ProtocolGraphWalker._is_satisfied` is currently implemented in very inefficient, and that would be the understatement of the year.

The implementation travels all the paths in the commit graph that lead from the want to one have.

It is usually not a problem, but we have a relatively small repository (less than 400 commits), with an arguably weird history of cross-merges, that has `2.1e22` paths between its HEAD commit and its root commit.

A really good start is to maintain the set of already known nodes (i.e. nodes that are either pending or already visited).