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

Junio C Hamano schrieb:

René Scharfe [off-list ref] writes:

quoted

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.

Correction: On Windows, we use the previous, quadratic, naive memmem()
implementation from glibc, not anything we came up with.

quoted

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.

Yes, patch 4 makes it go slower than using memmem() alone, in this test.

Here are a few more numbers, all measured on Windows.  The topmost four
times in the column "long" should be the same as in the Windows column
above, yet they are slightly bigger.  Some background process must've
decided to do some work.

  git log -S"$STRING" HEAD -- kernel/sched.c >/dev/null

  short: STRING='e'
  long:  STRING='Ensure that the real time constraints are schedulable.'

                                  short  long
  v1.6.2-rc2                      9.120  9.266
  v1.6.2-rc2+[1-4]                3.037  3.048
  v1.6.2-rc2+[1-4]+memmem         2.994  2.964
  v1.6.2-rc2+[1-3]+memmem         8.514  8.528
  v1.6.2-rc2+[1-4]+memmem+linear  1.939  1.759
  v1.6.2-rc2+[1-3]+memmem+linear  2.315  1.559

So patch 4 helps significantly with short needles, while it hurts a bit
with long needles.  Linear memmem() is faster than the quadratic one we
currently have in compat/ in all cases.

René