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

Junio C Hamano schrieb:

Junio C Hamano [off-list ref] writes:

quoted

René Scharfe [off-list ref] writes:
...

quoted

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