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

Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules

From
Junio C Hamano <gitster@pobox.com>
Date
Sep 12, 2011, 23:33 UTC
Message-ID
<7vsjo11gl9.fsf@alter.siamese.dyndns.org>
In-Reply-To
<20110912224934.GA28994@sigill.intra.peff.net>
Jeff King <peff@peff.net> writes:
Show 5 quoted lines
> To be honest, the whole submodule recursion thing seems a bit confusing
> to me....
> So since we must accept that we can't necessarily get every intermediate
> step, I wonder if we are simply better off diffing the "before" and
> "after" state of a particular ref, rather than traversing.
Yes, exactly my thought.

It would be far cheaper to look at a single final tree and enumerate all the submodules, which would give you pessimistically the maximum set that could possibly be relevant, than running millions of pairwise diff trees.

By the way, I think the submodule traversal won't hurt the correctness of the primary traversal because that happens _after_ we fetch the object stream.

The submodule traversal _may_ be getting an incorrect result, though, for the same reason.

Previous: Jeff KingNext: Jens Lehmann
Message 9 of 17 in “fetch: avoid quadratic loop checking for updated submodules”
  1. fetch: avoid quadratic loop checking for updated submodulesJeff King, Sep 12, 2011
  2. Junio C HamanoSep 12, 2011
  3. Jens LehmannSep 13, 2011
  4. Jens LehmannSep 14, 2011
  5. Junio C HamanoSep 12, 2011
  6. Jeff KingSep 12, 2011
  7. Junio C HamanoSep 12, 2011
  8. Jeff KingSep 12, 2011
  9. Junio C HamanoSep 12, 2011
  10. Jens LehmannSep 13, 2011
  11. Jeff KingSep 13, 2011
  12. Marc BranchaudSep 14, 2011
  13. Jens LehmannSep 14, 2011
  14. Jeff KingSep 14, 2011
  15. Christian CouderSep 13, 2011
  16. Jeff KingSep 13, 2011
  17. Junio C HamanoSep 13, 2011

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.