On 02/24/2011 12:18 PM, Jim Meyering wrote: >>> Here's what I've just pushed: >> >> Thank you for handling this so promptly. Would it be possible to also >> credit Mike Stump as original bug reporter? > > +++ b/ChangeLog > @@ -14,7 +14,9 @@ > * lib/str-two-way.h (two_way_short_needle): Correct off-by-one error > in period calculation. > (two_way_long_needle): Likewise. > - Reported by Ralf Wildenhues, with the short needle and haystack. > + The original problem was reported by Mike Stump in > + http://thread.gmane.org/gmane.comp.sysutils.autoconf.bugs/7834 > + Ralf Wildenhues provided the short needle and haystack. > * tests/test-strstr.c: Add Ralf's test case to trigger the bug. > Add a more involved test to trigger the bug in two_way_long_needle.
I'm more and more convinced that while this fixes the bug, it is a speed regression - it causes more comparisons to be made than strictly necessary. It's too late for me tonight, but I'll be reverting the str-two-way.h part of this patch, as well as the bug in the earlier patch where my mistaken "optimization" could result in mis-handling particular needles. The str-two-way algorithm only works if the critical factorization is found prior to the period of the needle, not equal to the period of the needle. Conversely, I also think that scanning right-to-left instead of left-to-right may offer some speedups, but that will be a separate patch, and only after I run more extensive testing. -- Eric Blake [email protected] +1-801-349-2682 Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
