Re: bug in autoconf-2.64

[Eric Blake]

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   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature