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

Re: merge-base: update the clean-up postprocessing

From
Junio C Hamano <junkio@cox.net>
Date
Jul 5, 2006, 23:20 UTC
Message-ID
<7v4pxvbpw0.fsf@assigned-by-dhcp.cox.net>
In-Reply-To
<Pine.LNX.4.63.0607050946390.29667@wbgn013.biozentrum.uni-wuerzburg.de>
Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
Show 9 quoted lines
> On Tue, 4 Jul 2006, Junio C Hamano wrote:
>
>> This is "for concepts" only -- it still seems to have bugs
>> somewhere to break other tests, although it passes your new
>> tests.
>
> Doesn't this introduce a nasty O(n*m) performance (where m is the 
> number of merge bases, and n the number of traversed commits)? I think 
> possibly many commits are traversed multiple times.

In practice m is small and the recomputation of bases between bases does not require the minimalization so O(m^2). I've given the numbers from a small real world example on the fixed code.

Previous: Johannes SchindelinNext: Junio C Hamano
Message 4 of 8 in “Additional merge-base tests (revised)”
  1. Additional merge-base tests (revised)A Large Angry SCM, Jul 5, 2006
  2. merge-base: update the clean-up postprocessingJunio C Hamano, Jul 5, 2006
  3. Johannes SchindelinJul 5, 2006
  4. Junio C HamanoJul 5, 2006
  5. Junio C HamanoJul 5, 2006
  6. Junio C HamanoJul 5, 2006
  7. Junio C HamanoJul 11, 2006
  8. Johannes SchindelinJul 11, 2006

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.