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

Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes

From
DLDavide Libenzi <davidel@xmailserver.org>
Date
Oct 16, 2006, 16:24 UTC
Message-ID
<Pine.LNX.4.64.0610160920250.7697@alien.or.mcafeemobile.com>
In-Reply-To
<Pine.LNX.4.64.0610160838200.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
Show 15 quoted lines
> 
> Davide? I'm quoting the whole report, because I suspect you don't follow 
> the git lists, and this is all original libxdiff code.
> 
> Jim: the annotation failure _may_ just be due to a "valid" diff change 
> (there is not always a unique correct answer for a diff, and so two 
> different diff algorithms can validly give two different answers, which 
> will also mean that git-annotate/blame would give different explanations). 
> 
> But it could certainly also be that you just broke the diffs entirely, so 
> I would like to wait for Davide to comment on your diff before Junio 
> should apply it. 
> 
> Others may be intimately familiar with the diff algorithms too, of course. 
> It just scares me personally ;)

The test is fine as is. Only really bad hash collisions can show O(M*N). Can I have the two sample files to test?

- Davide
Previous: Linus TorvaldsNext: Jakub Narebski
Message 26 of 27 in “git-diff-tree inordinately (O(M*N)) slow on files with many changes”
  1. Jim MeyeringOct 16, 2006
  2. Linus TorvaldsOct 16, 2006
  3. Linus TorvaldsOct 16, 2006
  4. Jim MeyeringOct 16, 2006
  5. Davide LibenziOct 16, 2006
  6. Jim MeyeringOct 16, 2006
  7. Davide LibenziOct 16, 2006
  8. Jim MeyeringOct 16, 2006
  9. Davide LibenziOct 16, 2006
  10. Linus TorvaldsOct 16, 2006
  11. Linus TorvaldsOct 16, 2006
  12. Davide LibenziOct 16, 2006
  13. Davide LibenziOct 16, 2006
  14. Linus TorvaldsOct 16, 2006
  15. Davide LibenziOct 16, 2006
  16. Jakub NarebskiOct 16, 2006
  17. Junio C HamanoOct 16, 2006
  18. Linus TorvaldsOct 16, 2006
  19. Davide LibenziOct 16, 2006
  20. Jim MeyeringOct 16, 2006
  21. Davide LibenziOct 16, 2006
  22. Jim MeyeringOct 16, 2006
  23. Linus TorvaldsOct 16, 2006
  24. Davide LibenziOct 16, 2006
  25. Linus TorvaldsOct 16, 2006
  26. Davide LibenziOct 16, 2006
  27. Jakub NarebskiOct 16, 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.