Junio C Hamano schrieb:
> Junio C Hamano <gitster@xxxxxxxxx> writes:
>
>> René Scharfe <rene.scharfe@xxxxxxxxxxxxxx> writes:
>> ...
>>> In any case, there is also memmem(), which uses the same fast algorithm
>>> as strstr() in recent glibc versions. Like this?
>> Thanks; it would be nice to bench this change.
>
> With memmem() patch applied on top of [1-4/4], the same test as described
> in the commit log message of [4/4] which was:
>
> $ STRING='Ensure that the real time constraints are schedulable.'
> $ git log -S"$STRING" HEAD -- kernel/sched.c >/dev/null
>
> (Before the patch, best of 5 runs)
> 5.59user 0.15system 0:05.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+39956minor)pagefaults 0swaps
>
> (After the patch, best of 5 runs)
> 3.04user 0.17system 0:03.23elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+49697minor)pagefaults 0swaps
>
> The file "kernel/sched.c" has roughly 900 changes applied to it, and over
> its lifetime, it has grown from 5kB to 9kB in size. I'd expect a larger
> file may see a bigger performance boost.
>
> (With memmem() patch, best of 5 runs)
> 2.46user 0.15system 0:02.62elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+49698minor)pagefaults 0swaps
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.
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.
Hmm, gnulib (http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=summary)
contains all parts ready for copy & paste, licensed under the GPL 2 or
up. That won't cause problems with the libgit2 relicensing effort, as
memmem() won't end up in there, right?
For the record, here the raw timings used to make the table above (best
of five):
Fedora 10:
8.10user 0.05system 0:08.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+31943minor)pagefaults 0swaps
2.38user 0.06system 0:02.45elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+41294minor)pagefaults 0swaps
1.19user 0.05system 0:01.25elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+39274minor)pagefaults 0swaps
1.10user 0.05system 0:01.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+31796minor)pagefaults 0swaps
Ubuntu 8.10:
8.08user 0.05system 0:08.14elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+29579minor)pagefaults 0swaps
2.35user 0.07system 0:02.43elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+40437minor)pagefaults 0swaps
1.23user 0.08system 0:01.31elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+41097minor)pagefaults 0swaps
1.46user 0.05system 0:01.51elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+30533minor)pagefaults 0swaps
Windows:
real 0m9.236s
user 0m0.000s
sys 0m0.000s
real 0m2.995s
user 0m0.000s
sys 0m0.000s
real 0m2.917s
user 0m0.000s
sys 0m0.015s
real 0m8.455s
user 0m0.000s
sys 0m0.000s
--
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
