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

From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date: Feb 28, 2009, 13:10 UTC
Message-ID: <49A937B8.1030205@lsrfire.ath.cx>
In-Reply-To: <7v8wnrgkjw.fsf@gitster.siamese.dyndns.org>

Junio C Hamano schrieb:

Show 29 quoted lines

> Junio C Hamano <gitster@pobox.com> writes:
> 
>> René Scharfe <rene.scharfe@lsrfire.ath.cx> 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