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, 23:52 UTC
Message-ID
<Pine.LNX.4.64.0610161651010.7697@alien.or.mcafeemobile.com>
In-Reply-To
<Pine.LNX.4.64.0610161604360.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
Show 7 quoted lines
> That said, it unnecessarily calculates "BITS_IN_LONG - (b)" to shift with, 
> because it really shouldn't matter _which_ high bits you use for hashing, 
> so you might as well just use the "next" b bits, and have
> 
> 	#define XDL_ADDBITS(v,b)	((v) + ((v) >> (b)))
> 	#define XDL_MASKBITS(b)		((1UL << (b)) - 1)
> 	#define XDL_HASHLONG(v,b)	(XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))
Ok, I'm fine with this. And my Opteron agrees too:

real 0m0.283s user 0m0.267s sys 0m0.016s

- Davide
Previous: Linus TorvaldsNext: Jim Meyering
Message 19 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.