From: Jeff King <peff@peff.net>
Date: Mon, 14 Jul 2014 05:53:54 +0000 (-0400)
Subject: paint_down_to_common: use prio_queue
X-Git-Tag: v2.1.0-rc0~3^2~1
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/73f43f220f0276012de50c84413fd61bf6aa307b?ds=inline;hp=73f43f220f0276012de50c84413fd61bf6aa307b

paint_down_to_common: use prio_queue

When we are traversing to find merge bases, we keep our
usual commit_list of commits to process, sorted by their
commit timestamp. As we add each parent to the list, we have
to spend "O(width of history)" to do the insertion, where
the width of history is the number of simultaneous lines of
development.

If we instead use a heap-based priority queue, we can do
these insertions in "O(log width)" time. This provides minor
speedups to merge-base calculations (timings in linux.git,
warm cache, best-of-five):

[before]
$ git merge-base HEAD v2.6.12
real    0m3.251s
user    0m3.148s
sys     0m0.104s

[after]
$ git merge-base HEAD v2.6.12
real    0m3.234s
user    0m3.108s
sys     0m0.128s

That's only an 0.5% speedup, but it does help protect us
against pathological cases.

While we are munging the "interesting" function, we also
take the opportunity to give it a more descriptive name, and
convert the return value to an int (we returned the first
interesting commit, but nobody ever looked at it).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---