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

[Junio C Hamano <gitster@pobox.com>]

Jeff King <peff@peff.net> 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 <peff@peff.net>
> ---
> 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.