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

Re: [PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops

From
Linus Torvalds <torvalds@linux-foundation.org>
Date
Oct 26, 2007, 23:36 UTC
Message-ID
<alpine.LFD.0.999.0710261633090.30120@woody.linux-foundation.org>
In-Reply-To
<7vy7dpv4ls.fsf@gitster.siamese.dyndns.org>
On Fri, 26 Oct 2007, Junio C Hamano wrote:
> 
> So for a broken pair, the actual value of rename_used does not really 
> matter.  We only care about it not going down to zero.

Correct. The rename_used count really is immaterial *except* for the magic distinction between zero ("it's a rename, no original source file left") and non-zero ("it's a copy, original source file remains").

Which is why the new counter is so fundamentally simple: by decrementing it for each rename we encounter, we automatically get that behaviour of "only the last user turns into a 'rename' if the source file really went away" that we want.

The old code did it all with some really expensive loops over the remaining renames.

		Linus
Previous: Junio C HamanoNext: Linus Torvalds
Message 9 of 18 in “Cleaned-up rename detection patch-series”
  1. 0/6 Cleaned-up rename detection patch-seriesLinus Torvalds, Oct 25, 2007
  2. 1/6 Add 'diffcore.h' to LIB_HLinus Torvalds, Oct 25, 2007
  3. 2/6 Split out "exact content match" phase of rename detectionLinus Torvalds, Oct 25, 2007
  4. 3/6 Ref-count the filespecs used by diffcoreLinus Torvalds, Oct 25, 2007
  5. 4/6 copy vs rename detection: avoid unnecessary O(n*m) loopsLinus Torvalds, Oct 25, 2007
  6. Junio C HamanoOct 26, 2007
  7. Linus TorvaldsOct 26, 2007
  8. Junio C HamanoOct 26, 2007
  9. Linus TorvaldsOct 26, 2007
  10. 5/6 Do linear-time/space rename logic for exact renamesLinus Torvalds, Oct 25, 2007
  11. Daniel BarkalowOct 25, 2007
  12. Jeff KingOct 25, 2007
  13. Daniel BarkalowOct 25, 2007
  14. Linus TorvaldsOct 25, 2007
  15. Daniel BarkalowOct 25, 2007
  16. 6/6 Do exact rename detection regardless of rename limitsLinus Torvalds, Oct 25, 2007
  17. Linus TorvaldsOct 25, 2007
  18. Jeff KingOct 25, 2007

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.