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

Re: git-diff-tree -M performance regression in 'next'

From
Junio C Hamano <junkio@cox.net>
Date
Mar 13, 2006, 01:22 UTC
Message-ID
<7vhd63w33n.fsf@assigned-by-dhcp.cox.net>
In-Reply-To
<Pine.LNX.4.64.0603121700410.3618@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> writes:
> Umm. Why do you rehash at all?
>
> Just take the size of the "src" file as the initial hash size.

The code uses close to 16-bit hash and I had 65k flat array as a hashtable. That one was what you commented as "4-times as many page misses".

Interestingly enough, that kind of flat array representation seems to be too sparse and gives very bad performance behaviour.

The improvement I mentioned in the message you are replying to is the result of making it into smaller (starting at (1<<9) or something like that) linear-overflowing hash.

The latter suggestion I need to think about it a bit more.
Previous: Linus TorvaldsNext: Linus Torvalds
Message 8 of 17 in “git-diff-tree -M performance regression in 'next'”
  1. Fredrik KuivinenMar 11, 2006
  2. Junio C HamanoMar 12, 2006
  3. Junio C HamanoMar 12, 2006
  4. Linus TorvaldsMar 12, 2006
  5. Junio C HamanoMar 12, 2006
  6. Junio C HamanoMar 13, 2006
  7. Linus TorvaldsMar 13, 2006
  8. Junio C HamanoMar 13, 2006
  9. Linus TorvaldsMar 13, 2006
  10. Linus TorvaldsMar 13, 2006
  11. Linus TorvaldsMar 13, 2006
  12. Linus TorvaldsMar 13, 2006
  13. Linus TorvaldsMar 13, 2006
  14. Junio C HamanoMar 13, 2006
  15. Junio C HamanoMar 14, 2006
  16. Linus TorvaldsMar 14, 2006
  17. Junio C HamanoMar 14, 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.