Junio C Hamano schrieb:
> René Scharfe <rene.scharfe@xxxxxxxxxxxxxx> 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.
>> 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é
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
