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

Re: git-rev-list: "--bisect" flag

From
Jon Seymour <jon.seymour@gmail.com>
Date
Jun 20, 2005, 14:37 UTC
Message-ID
<2cfc40320506200737113caa9f@mail.gmail.com>
In-Reply-To
<2cfc403205062003292db2b457@mail.gmail.com>
Show 6 quoted lines
> I am exploring another variation of the idea which is even simpler.
> Experimentally it seems quite similar to your average case
> performance, but doesn't yet approach your low std deviations.
> However, I think I know why that is, so I will, after a few games of
> pool and a similar number of beers, have another crack at it.
>

Ok, just for information, I have a linear bisection algorithm which results in a bug-blatt algorithm with the following characteristics on the Linux 2.6 kernel:

AVERAGE 13.64589235 MEDIAN 13 MAX 28 MIN 9 STDEV 2.171923221

These results were derived by running the algorithm over the full 2118 commits of the current Linux 2.6 source.

I'll document what this algorithm is and what its flaws are.
The algorithm is as follows:

Consider the graph as a closed network of pipes with N reservoirs of 1 unit of volume. Rotate this graph so the head is at the top. Now, pour N units of liquid into the top of the network of pipes. The liquid percolates through the network of pipes and ends up in the reservoirs. The selected bisection point is the node that saw as close to N/2 units of liquid as any other node.

Now, why isn't this as good (in terms of average and stdev) as Linus' algorithm? The flaw with this algorithm is that some liquid from peer nodes reaches the lower half of the network before the liquid that went through the selected node. As a result, the selected node is elevated "above" the ideal bisection point, by a factor that I believe would be sufficient to explain the higher average and also the greater standard deviation.

Still, my algorithm is very simple and very linear, so it's very good a start.

As it happens, I believe I have (re-?)discovered a precise way to discover the bisection points in O(n). I am in the midst of implementing that now.

jon.
Previous: Jon Seymour
Message 19 of 19 in “git-rev-list: "--bisect" flag”
  1. Linus TorvaldsJun 18, 2005
  2. Jon SeymourJun 19, 2005
  3. Jan HarkesJun 19, 2005
  4. Jon SeymourJun 19, 2005
  5. Linus TorvaldsJun 19, 2005
  6. Linus TorvaldsJun 19, 2005
  7. David LangJun 19, 2005
  8. Linus TorvaldsJun 19, 2005
  9. Jon SeymourJun 19, 2005
  10. Jon SeymourJun 19, 2005
  11. Linus TorvaldsJun 19, 2005
  12. Ingo MolnarJun 19, 2005
  13. Linus TorvaldsJun 19, 2005
  14. Jon SeymourJun 19, 2005
  15. Linus TorvaldsJun 20, 2005
  16. Jon SeymourJun 20, 2005
  17. Jon SeymourJun 20, 2005
  18. Jon SeymourJun 20, 2005
  19. Jon SeymourJun 20, 2005

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.