Derrick Stolee <stolee@xxxxxxxxx> writes: > The biggest reason for the 20 seconds is not just the number of > commits in the ahead/behind but how many commits are walked (including > common to both branches) before paint_down_to_common() breaks its > while loop due to queue_has_nonstale(). Hmm, queue_has_nonstale() looks to see if any element is not STALE (where the definition of STALE is "known to be a common ancestor") by potentially checking all elements in the queue. I wonder if we have an opportunity for a trivial optimization? When the caller knows that it dug one level and added the parents that are not stale, it does not have to ask queue_has_nonstale() if there is any non stale element, for example. What do you exactly mean by "not just the number of commits in the ahead/behind"? Aren't the number of these commits pretty much proportional to the number of commits we need to paint down to common ancestors? Is the latter a lot larger than the former (i.e. are we somehow not stopping when we _could_ notice that we can with better information)?
