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

From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date: Mar 1, 2009, 10:53 UTC
Message-ID: <49AA693B.5060108@lsrfire.ath.cx>
In-Reply-To: <7viqmtaec4.fsf@gitster.siamese.dyndns.org>

Junio C Hamano schrieb:

Show 16 quoted lines

> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
> 
>> 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.

Show 11 quoted lines

>> 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é