git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: "Manuel Bärenz" <manuel@enigmage.de>
To: "Ævar Arnfjörð Bjarmason" <avarab@gmail.com>
Cc: git@vger.kernel.org, Han-Wen Nienhuys <hanwen@google.com>
Subject: Re: Feature request: Exponential search in git bisect
Date: Sun, 1 Nov 2020 21:30:13 +0100	[thread overview]
Message-ID: <58ba4fcd-50ff-1d1a-fe11-1ee59ad1c533@enigmage.de> (raw)
In-Reply-To: <87wnzbhntw.fsf@evledraar.gmail.com>


> Let's suppose we have a repository with 700 linear commits:
>     
>     set -e
>     
>     cd /tmp
>     rm -rf /tmp/test-repo
>     mkdir /tmp/test-repo
>     cd /tmp/test-repo
>     git init
>     
>     for i in $(seq 1 700)
>     do
>         touch $i
>         git add $i
>         git commit -m"add $i"
>     done
>
> Then let's bisect it from the root:
>     
>     git bisect start HEAD HEAD~699
>
> And let's further suppose that the feature wasn't introduced until
> commit 650, and it's broken since 653.
>
> With the bisect method of finding this we're going to start our session
> with these commits:
>
>     [bef4b96adf5f082b1103c170eb6a41d1526fa919] add 350 => good
>     [d271fdb29129dbba723d3eac1035b58b6dc6f583] add 525 => good
>     [b0c9b7da646334a6c7eadb333b5ae77ec35388b3] add 612 => good
>     [2a78858d04cc5542e176dd8f68fa2660b8b48ab3] add 656 => bad (or skip)
>
> Whereas with this proposed exponential search it'll be commits #:
>     
>     2
>     4
>     8
>     16
>     32
>     64
>     128
>     256
>     512
>
> So we're going to test 8 commits before we get past the mid-point that
> bisect now starts with. Of course that may be more efficient, but if the
> regression is in some random place I don't see why we wouldn't test the
> middle instead of weighing things towards the start of the history. If
> the relevant commit is an early one like #50 bisect is still faster.
That's true. If the feature was broken n commits ago, and exponential
search has to be useful, then the feature must not have been introduced
later than a*n commits ago, where a is the exponent.
> With the disclaimer that I may be missing something, I'm just plowing
> ahead:
>
> I don't see the usefulness of this proposed exponential search, but I
> definitely *do* see the usefulness of a "bisect undo", and I've been
> bitten many times by the lack of that myself. We should definitely have
> that.
What exactly would you undo? If an older commit has been marked as
"bad", should e.g. a later "good" marker undo the earlier "bad" marker?
I don't know how this helps because the bigger problem is that if I tend
to mark old commits as good rather than skip, I will more likely
accidentally mark a bad commit as good, and I don't see how I could undo
that.
> And as Christian pointed out in [1] it seems you're (understandably, it
> can be confusing) conflating skip and "good" in your example.
Yes, knowingly, unfortunately. Or to put it more precise: I cannot write
a script that is good enough to really detect a good old commit reliably.
>  So to
> re-state the problem you have, if I were to use "skip" in the above
> example bisect for me will do:
>     
>     [bef4b96adf5f082b1103c170eb6a41d1526fa919] add 350 => skip
>     [15c181442dcbd785bf2b28cfddcf1932aaa71c42] add 351 => skip
>     [c985feffa2c92b2d3d9804a43b215e26c7275549] add 374 => skip
>     [effa691ec5dc2d80c0b070c4d8ac9fa70cbfea9f] add 168 => skip
>     [212a5ee3ff55834196661d0632f584098e9f6fb2] add 369 => skip
>     [2ca67a4500c9f3cd489b9e529d41eb99252dc8f6] add 179 => skip
>     [4067ee067e2298e1b104f4ff9aab15f4e815e101] add 337 => skip
>     [...]
>
> If only there was a way to be on 350 and say "skip everything up to this
> point", so I implemented it!:
>
>     [bef4b96adf5f082b1103c170eb6a41d1526fa919] add 350 => skip-to-here
>     [15c181442dcbd785bf2b28cfddcf1932aaa71c42] add 351 => skip
>     [6f7b5ca1dcc21c28af658a172136e503d7a2d0ea] add 420
>     [...]
>
> etc. now we're not jumping around in 1..350:
>
>     $ git config alias.bisect-skip-to-here
>     !f() { good=$(git for-each-ref refs/bisect/good* --format="%(objectname)"); git bisect skip $good..HEAD; }; f
>
> Great eh? Not really, because I've just discovered a really tedious and
> expensive (I created 350 "skip" refs) of re-inventing what I could do if
> I just did "good" on commit 350[2] :)

I'm not entirely sure whether I understand yet. If you mark a whole
range of commits untestable, then yes. But how do you know whether the
whole range can be skipped? Maybe the feature was really introduced in
300, 320 broke it and 350 just broke it because of a typo?

Maybe another possible, simpler feature would be a different
(configurable?) skip algorithm. It could move exponentially as well.
(I'm not sure how useful that would be, though.)


  reply	other threads:[~2020-11-01 20:30 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-10-09 12:56 Feature request: Exponential search in git bisect Manuel Bärenz
2020-10-10  9:22 ` Christian Couder
2020-10-10  9:46   ` Christian Couder
2020-10-25 17:15   ` Philip Oakley
2020-10-26 18:13     ` Junio C Hamano
2020-10-26 20:59       ` Philip Oakley
2020-11-01 20:17     ` Manuel Bärenz
2020-10-27 12:10 ` Ævar Arnfjörð Bjarmason
2020-11-01 20:30   ` Manuel Bärenz [this message]
2020-11-02 10:36     ` Ævar Arnfjörð Bjarmason

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=58ba4fcd-50ff-1d1a-fe11-1ee59ad1c533@enigmage.de \
    --to=manuel@enigmage.de \
    --cc=avarab@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=hanwen@google.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).