Re: [PATCH] limit_list: avoid quadratic behavior from still_interesting

2015-04-17 Thread Junio C Hamano
Jeff King writes: > The implementation is fairly straightforward. Whenever we do > the linear search, we cache the interesting commit we find, > and next time check it before doing another linear search. > If that commit is removed from the list or becomes > UNINTERESTING itself, then we fall bac

[PATCH] limit_list: avoid quadratic behavior from still_interesting

2015-04-17 Thread Jeff King
When we are limiting a rev-list traversal due to UNINTERESTING refs, we have to walk down the tips (both interesting and uninteresting) to find where they intersect. We keep a queue of commits to examine, pop commits off the queue one by one, and potentially add their parents. The size of the queu