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

Re: in_merge_bases() is too expensive for recent "pu" update

From
Junio C Hamano <gitster@pobox.com>
Date
Aug 23, 2012, 18:08 UTC
Message-ID
<7vd32h4h1t.fsf@alter.siamese.dyndns.org>
In-Reply-To
<878vd5k7uu.fsf@thomas.inf.ethz.ch>
Thomas Rast <trast@student.ethz.ch> writes:
> At the very least it should be possible to change in_merge_bases() to
> not do any of the post-filtering; perhaps like the patch below.

I do not recall the details but the post-filtering was added after the initial naive version without it that was posted to the list did not work correctly in corner cases. I wouldn't doubt that N*(N-1) loop can be optimized to something with log(N), but I offhand find it hard to believe "to not do any" could be correct without seeing more detailed analysis.

Previous: Thomas RastNext: Junio C Hamano
Message 3 of 16 in “in_merge_bases() is too expensive for recent "pu" update”
  1. Nguyen Thai Ngoc DuyAug 23, 2012
  2. Thomas RastAug 23, 2012
  3. Junio C HamanoAug 23, 2012
  4. Junio C HamanoAug 23, 2012
  5. Junio C HamanoAug 23, 2012
  6. Thomas RastAug 24, 2012
  7. Junio C HamanoAug 24, 2012
  8. Thomas RastAug 24, 2012
  9. Jeff KingAug 24, 2012
  10. Junio C HamanoAug 24, 2012
  11. Junio C HamanoAug 24, 2012
  12. Nguyen Thai Ngoc DuyAug 24, 2012
  13. Nguyen Thai Ngoc DuyAug 24, 2012
  14. Junio C HamanoAug 28, 2012
  15. Thomas RastAug 28, 2012
  16. Junio C HamanoAug 28, 2012

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.