git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: Generalised bisection

From
EWEaldwulf Wuffinga <ealdwulf@googlemail.com>
Date
Mar 16, 2009, 22:08 UTC
Message-ID
<efe2b6d70903161508i19c16f6bm7f695452748a06a1@mail.gmail.com>
In-Reply-To
<d9c1caea0903160329v3c1a1600m9913eafa00cc2f37@mail.gmail.com>
On Mon, Mar 16, 2009 at 10:29 AM, Steven Tweed <orthochronous@gmail.com> wrote:
Show 12 quoted lines
> I had a look over the weekend, and got a bit sidetracked on one of
> your assumptions. You seem to be assuming that the bug is such that
> observing a single positive observation of the symptom at a position i
> in the linear history _does not_ completely rule out that the guilty
> commit occurs after that point. I would have thought the generally
> more applicable assumption is that, given that generally you don't
> have a bug ridden system where more than one bug causes the same
> symptom _within the history of interest_, that a single observation of
> the symptom does totally rule out the bug after that point (whilst
> intermittency clearly not having observed the bug before that point
> doesn't completely rule out the guilty commit being earlier, although
> it should increase the liklihood estimate of the bug being later).

I must have been unclear somewhere, because I do indeed assume that a single observation of the symptom rules out the origin of the bug being later than that observation.

 If you have a play with the software in manual mode, you can see that its
behaviour reflects this  - it starts out doing something like an
ordinary binary search, albeit skewed towards older revisions (it
seems to go for
a roughly 1:2 division, rather than the usual 1:1). Then once it has got to the
point where a deterministic search would end, it hammers away at the parent(s)
of the newest revision where the fault was observed, until it is satisfied that
it cannot be found there. All this just emerges from the generic least-entropy
algorithm; I didn't know what it would do until I got it running.
> I wonder what your thoughts are on this? (I started formulating a
> model over the weekend, but work is a bit hectic so I may not get to
> write it up in LaTeX very quickly.)

It will be interesting to see whether your model turns out to be different from mine. I'm only doing this in my spare time, so I'm in no hurry.

Ealdwulf
Previous: Ealdwulf WuffingaNext: Ealdwulf Wuffinga
Message 21 of 25 in “Generalised bisection”
  1. Ealdwulf WuffingaMar 9, 2009
  2. Christian CouderMar 10, 2009
  3. Ealdwulf WuffingaMar 11, 2009
  4. John TapsellMar 11, 2009
  5. Johannes SchindelinMar 11, 2009
  6. John TapsellMar 11, 2009
  7. Johannes SchindelinMar 11, 2009
  8. John TapsellMar 11, 2009
  9. Ealdwulf WuffingaMar 11, 2009
  10. Ealdwulf WuffingaMar 11, 2009
  11. John TapsellMar 12, 2009
  12. Johannes SchindelinMar 12, 2009
  13. Steven TweedMar 12, 2009
  14. Ealdwulf WuffingaMar 13, 2009
  15. Ealdwulf WuffingaMar 13, 2009
  16. Steven TweedMar 13, 2009
  17. Ealdwulf WuffingaMar 15, 2009
  18. Steven TweedMar 16, 2009
  19. John TapsellMar 16, 2009
  20. Ealdwulf WuffingaMar 16, 2009
  21. Ealdwulf WuffingaMar 16, 2009
  22. Ealdwulf WuffingaMar 13, 2009
  23. Johannes SchindelinMar 13, 2009
  24. John TapsellMar 13, 2009
  25. Johannes SchindelinMar 13, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.