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

Re: [PATCH 07/10] bisect: automatically sort sha1_array if needed when looking it up

From
Christian Couder <chriscool@tuxfamily.org>
Date
May 10, 2009, 04:44 UTC
Message-ID
<200905100644.14786.chriscool@tuxfamily.org>
In-Reply-To
<m3ljp6me9v.fsf@localhost.localdomain>
Le samedi 9 mai 2009, Jakub Narebski a écrit :
Show 9 quoted lines
> Christian Couder <chriscool@tuxfamily.org> writes:
> > This makes sha1_array easier to use, so later patches will be simpler.
>
> Hmmm... sort on lookup array. I wonder if it would be worth
> librarizing, and if there is any smart optimization for that (like
> e.g. heap for fast access to smallest value and fast insertion, using
> insertion sort for almost sorted array, etc.).
>
> BTW. does it become unsorted anywhere?

No, it doesn't. We first read all the "refs/bisect/good-*" and "refs/bisect/skip-*" and put them in some "struct sha1_array". Then later we may lookup sha1 there from 2 different functions: "check_merge_bases" first and then "filter_skipped".

This patch optimizes by not sorting before we lookup, so if we don't lookup anything, we pay no sorting price.

Best regards, Christian.

Previous: Jakub NarebskiNext: Christian Couder
Message 10 of 14 in “bisect: port git bisect merge base checking to C”
  1. 00/10 bisect: port git bisect merge base checking to CChristian Couder, May 9, 2009
  2. 01/10 bisect: use "sha1_array" to store skipped revisionsChristian Couder, May 9, 2009
  3. 02/10 bisect: implement "rev_argv_push" to fill an argv with revsChristian Couder, May 9, 2009
  4. 03/10 bisect: store good revisions in a "sha1_array"Christian Couder, May 9, 2009
  5. 04/10 bisect: use new "struct argv_array" to prepare argv for "setup_revisions"Christian Couder, May 9, 2009
  6. 05/10 bisect: remove too much function nestingChristian Couder, May 9, 2009
  7. 06/10 bisect: make skipped array functions more genericChristian Couder, May 9, 2009
  8. 07/10 bisect: automatically sort sha1_array if needed when looking it upChristian Couder, May 9, 2009
  9. Jakub NarebskiMay 9, 2009
  10. Christian CouderMay 10, 2009
  11. 08/10 bisect: implement the "check_merge_bases" functionChristian Couder, May 9, 2009
  12. 09/10 bisect: add "check_good_are_ancestors_of_bad" functionChristian Couder, May 9, 2009
  13. 10/10 bisect: make "git bisect" use new "--next-all" bisect-helper functionChristian Couder, May 9, 2009
  14. Junio C HamanoMay 11, 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.