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