git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Junio C Hamano <gitster@pobox.com>
To: "SZEDER Gábor" <szeder.dev@gmail.com>
Cc: git@vger.kernel.org
Subject: Re: [PATCH v2] bisect: loosen halfway() check for a large number of commits
Date: Thu, 12 Nov 2020 10:23:13 -0800	[thread overview]
Message-ID: <xmqqft5ejuy6.fsf@gitster.c.googlers.com> (raw)
In-Reply-To: <20201112161938.20494-1-szeder.dev@gmail.com> ("SZEDER Gábor"'s message of "Thu, 12 Nov 2020 17:19:38 +0100")

SZEDER Gábor <szeder.dev@gmail.com> writes:

> So let's loosen the check in the halfway() helper to consider commits
> within about 0.1% of the exact halfway point as halfway as well, and
> rename the function to approx_halfway() accordingly.  This will allow
> us to return early on a bigger good-bad range, even when there is no
> commit exactly at the halfway point, thereby reducing the runtime of
> the first command above considerably, from ~15s to 4.901s.

The optimization presented with this change would probably offer
more merge commits to be tested than a single-parent commit than the
original algorithm, simply because merges are inspected first before
single-parent commits so have better chance to be picked as "good
enough" among commits with similar goodness.

  Side note: This is merely an observation---I do not know if it is
  a good thing, a bad thing, or a neutral thing, but it would likely
  affect the end-user experience.

The optimization presented here gives probably more than enough
improvement, but it just occured to me when writing the entry to
explain the topic in the What's cooking report:

     "git bisect start/next" in a large span of history spends a lot of
     time trying to come up with exactly the half-way point; this can be
     optimized by stopping when we see a commit that is close enough to
     the half-way point.

The realization is that the optimization naturally will be affected
by the order the commits are visited.  If a commit that is close
enough to the half-way point happens to be visited earlier, it would
help terminate our search early.  And do_find_bisection() search
counts all merge commits before any commit on the linear ancestry
chain can be counted to optimize counting of commits on the linear
ancestry chain, which are expected to exist more than merge commits.

By sorting the "list" to somehow encourage commits near the half-way
appear early on it, we may raise the likelyhood that we'd find
good-enough commit early and terminate, no?  Perhaps sort by the
(absolute) distance between the committer timestamp of individual
commit and its median value, or something?

Thanks.

      reply	other threads:[~2020-11-12 18:23 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-10-22 10:38 [PATCH] bisect: loosen halfway() check for a large number of commits SZEDER Gábor
2020-10-22 10:40 ` SZEDER Gábor
2020-10-22 17:18 ` Junio C Hamano
2020-10-24  7:41   ` Christian Couder
2020-10-25 18:01     ` SZEDER Gábor
2020-11-12 16:19 ` [PATCH v2] " SZEDER Gábor
2020-11-12 18:23   ` Junio C Hamano [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=xmqqft5ejuy6.fsf@gitster.c.googlers.com \
    --to=gitster@pobox.com \
    --cc=git@vger.kernel.org \
    --cc=szeder.dev@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).