Re: [PATCH] upload-pack: use priority queue in reachable() check

Jeff King [off-list ref] writes:

Like a lot of old commit-traversal code, this keeps a
commit_list in commit-date order, and and inserts parents
into the list. This means each insertion is potentially
linear, and the whole thing is quadratic (though the exact
runtime depends on the relationship between the commit dates
and the parent topology).

These days we have a priority queue, which can do the same
thing with a much better worst-case time.

Signed-off-by: Jeff King <redacted>
---
This was inspired by a real-world case where several instances of
upload-pack were chewing minutes of CPU, and backtraces in each instance
pointed to this function.  Unfortunately, I only saw the server side of
these requests. I pulled the contents of have_obj and want_obj out of
the process via gdb, but I wasn't able to reproduce the slow fetch.

So I'm not 100% sure that this fixes it, but the problem hasn't happened
again. And it certainly seems like it couldn't _hurt_ to optimize this.

This does look good and looks like a quite straight-forward change.

Will queue; thanks.