Re: first bisection step takes quite a while

Christian Couder [off-list ref] writes:

On Fri, Feb 21, 2025 at 9:24 PM Christian Couder
[off-list ref] wrote:

quoted

On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano [off-list ref] wrote:

quoted

quoted

quoted

quoted

 * The "this is good enough" logic currently allows us to be within
   0.1% of the real halfway point.  Until the candidate set becomes
   small enough, we could loosen the criteria to allow larger, say
   3%, slack.  This code is written but not enabled (with "0 &&").

The above follows the same reasoning why we chose "division by 1024"
in the first place.  The illustration patch postulates that we could
be way more aggressive than 0.1% while the set is large by dividing
64, without wanting to loosen the criteria near the end of the
bisection session when the remaining set is reasonably small like
1000 commits.  So we cannot rely on integer division truncating.

The code you posted above uses 10000 as the threshold, not 1000:

10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)

Also if "division by 1024" means within 0.1% of the real halfway
point, then division by 64 means 0.1 * 1024 / 64 = 1.6 % not 3%.

Heh, I suck at arithmetic (but that is why I have you guys around
for correction ;-).

The current code makes sure that we do not punt with an inexact
result below nr for which nr/1024 is truncated away.  The overly
loose cutoff that uses nr/64 needs to stop kicking in way before
that happens to make sure we do not affect correctness with the
change to optimize, and that is the only reason why 10000 was
arbitrary chosen.  The threashold could have been set at 5000, or
100000.

Exact numbers do not matter as much as the real issue, i.e.,
limiting the possible damage to correctness from the change near the
end of a bisect session.

Thanks.