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

Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()

From
Junio C Hamano <gitster@pobox.com>
Date
Mar 1, 2009, 07:31 UTC
Message-ID
<7viqmtaec4.fsf@gitster.siamese.dyndns.org>
In-Reply-To
<49A937B8.1030205@lsrfire.ath.cx>
René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
Show 14 quoted lines
> I get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo,
> Windows Vista x64 using a different Linux repo with the same HEAD on
> NTFS and msysgit, numbers are the elapsed time in seconds, best of five
> runs):
>
>                            Ubuntu  Fedora  Windows
>    v1.6.2-rc2                8.14    8.16    9.236
>    v1.6.2-rc2+[1-4]          2.43    2.45    2.995
>    v1.6.2-rc2+[1-4]+memmem   1.31    1.25    2.917
>    v1.6.2-rc2+[1-3]+memmem   1.51    1.16    8.455
>
> Ubuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more
> efficient memmem() implementation.  On Windows, we use our own naive
> memmem() implementation.
Shoot, I was not being careful enough.
> So using memmem() is worthwhile.  And providing a better fall-back
> version in compat/ can speed up this particular case to the point where
> the fourth patch becomes moot.

Are these numbers telling me that with a good memmem() implementation, patch 4/4 is not just moot but actively detrimental?

With a long enough needle, it entirely is possible that scanning the whole image with sublinear string search algorithm would perform much better than the preprocessing patch 4/4 does which has to scan all the bytes in the common parts.

Previous: René ScharfeNext: René Scharfe
Message 18 of 23 in “Pickaxe search clean-up and optimization”
  1. 0/4 Pickaxe search clean-up and optimizationJunio C Hamano, Feb 26, 2009
  2. 1/4 diffcore-pickaxe: refactor diffcore_pickaxe()Junio C Hamano, Feb 26, 2009
  3. René ScharfeFeb 27, 2009
  4. 2/4 diffcore-pickaxe: micro-optimize has_match() functionJunio C Hamano, Feb 26, 2009
  5. 3/4 diffcore-pickaxe: further refactor count_match()Junio C Hamano, Feb 26, 2009
  6. Kjetil BarvikFeb 26, 2009
  7. René ScharfeFeb 28, 2009
  8. Junio C HamanoFeb 28, 2009
  9. Junio C HamanoFeb 28, 2009
  10. René ScharfeFeb 28, 2009
  11. Junio C HamanoFeb 28, 2009
  12. René ScharfeFeb 28, 2009
  13. import memmem() with linear complexity from GnulibRené Scharfe, Feb 28, 2009
  14. Mike HommeyFeb 28, 2009
  15. Jeff KingMar 1, 2009
  16. René ScharfeMar 1, 2009
  17. René ScharfeMar 1, 2009
  18. Junio C HamanoMar 1, 2009
  19. René ScharfeMar 1, 2009
  20. 4/4 diffcore-pickaxe: optimize by trimming common initial and trailing partsJunio C Hamano, Feb 26, 2009
  21. Junio C HamanoFeb 26, 2009
  22. 1/2 diffcore-pickaxe: use memmem()René Scharfe, Mar 2, 2009
  23. 2/2 optimize compat/ memmem()René Scharfe, Mar 2, 2009

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.