From: Junio C Hamano <gitster@pobox.com>
Date: Tue, 11 Oct 2016 21:26:30 GMT
Subject: Re: [PATCH] upload-pack: use priority queue in reachable() check
Message-ID: <xmqqshs27f21.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <20161011212016.hnw4dl473puhyax7@sigill.intra.peff.net>

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.