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
Linus Torvalds <torvalds@osdl.org>
Date
Oct 16, 2006, 16:57 UTC
Message-ID
<Pine.LNX.4.64.0610160956360.3962@g5.osdl.org>
In-Reply-To
<Pine.LNX.4.64.0610160932100.7697@alien.or.mcafeemobile.com>
On Mon, 16 Oct 2006, Davide Libenzi wrote:
Show 5 quoted lines
>
> I think the xdl_hashbits() picks up the hash table size "almost" 
> correctly. I think we're looking at some bad hash *collisions* (not 
> records with same hash value, that'd be stopped by the mlim check). 
> Send me the files and I'll take a look ...
Davide, they were mentioned in the original report:
	http://meyering.net/code/git-perf/configure.gz
	http://meyering.net/code/git-perf/configure-curr.gz
I'd take a look myself, but I need to run..
		Linus
Previous: Davide LibenziNext: Davide Libenzi
Message 25 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.