Re: memmem speedup

[Ralf Wildenhues]

Hi Eric,

* Eric Blake wrote on Sun, Jan 06, 2008 at 02:23:33AM CET:
> 
> I'd appreciate any reviews before checking it in.

Here's a rough glance at it.  FWIW, the diff is not very readable
(there was a patch to diffutils out there for --more-readable).

> +/* We use the Two-Way string matching algorithm, which guarantees
> +   linear complexity with constant space.  Additionally, for long
> +   needles, we also use a bad character shift table similar to the
> +   Boyer-Moore algorithm to acheive sub-linear performance.

s/acheive/achieve/  (2 instances in the code)

> +/* Peform a critical factorization of NEEDLE, of length NEEDLE_LEN.

s/Peform/Perform/

> +static void *
> +two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
> +                   const unsigned char *needle, size_t needle_len)
> +{
[...]
> +
> +  /* Perform the search.  Each iteration compares the right half
> +     first.  */
> +  if (memcmp (needle, needle + period, suffix) == 0)
> +    {

In order to test the code in both blocks following this test, you may
want to also test with a periodic needle in test-memmem.c:

  {
    const char input[] = "ABC ABCDAB ABCDABCDABDE";
    const char *result = memmem (input, strlen (input), "ABCDABCD", 8);
    ASSERT (result == input + 11);
  }

This still won't give you full code coverage (but for the other corner
cases I'd probably need to go and read the description of the
algorithm ;-)

[...]
> diff --git a/tests/test-memmem.c b/tests/test-memmem.c
> index 976f293..e900e1c 100644
> --- a/tests/test-memmem.c
> +++ b/tests/test-memmem.c
> @@ -152,5 +152,32 @@ main (int argc, char *argv[])
>        free (haystack);
>    }
>  
> +  /* Check that a some long needles not present in a haystack can be

s/a some //

> +     handled with sublinear speed.  */

Nice work, BTW!

Cheers,
Ralf