Re: first bisection step takes quite a while

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 22, 2025, 02:15 UTC
Message-ID: <xmqqldty912l.fsf@gitster.g>
In-Reply-To: <CAP8UFD0xsZWDnH9kLJ4eWfzq4nvAm+qMHcdbZSf0d4-yPG9+5g@mail.gmail.com>

Christian Couder <christian.couder@gmail.com> writes:

Show 23 quoted lines

> On Fri, Feb 21, 2025 at 9:24 PM Christian Couder
> <christian.couder@gmail.com> wrote:
>>
>> On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:
>
>> > >>  * 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.