On Mar 2, 2004, at 1:15 PM, Ben Schroeder wrote:

> Hi Avi,
>
> Thanks, that fixes it!  We're down to only a few seconds.
>
> We were exploring some more, and it looks like there are simply many, 
> many paths through our version history tree, due possibly to whatever 
> number of merges we had done (not the majority of the updates, but 
> still several).  If I understand your fix correctly, the sorter now 
> doesn't go down paths that it has already seen, making the search much 
> smaller.

Well, close - what the algorithm is interested in is more or less the 
shortest path to each node (it's related to Dijkstra's algorithm but 
has some additional constraints).  So it only prunes a branch if it's 
already seen that node on a path the same length as or shorter than the 
current one.  I'm pretty sure it was just a dumb oversight that it 
didn't do this before (that's the problem with TDD - the tests were 
green and I had other things to do so I moved on :).