On 12/18/18 11:01 AM, Wilco Dijkstra wrote:
> This patch significantly improves performance of memmem using a novel
> modified Horspool algorithm. Needles up to size 256 use a bad-character
> table indexed by hashed pairs of characters to quickly skip past mismatches.
> Long needles use a self-adapting filtering step to avoid comparing the whole
> needle repeatedly.
>
> By limiting the needle length to 256, the shift table only requires 8 bits
> per entry, lowering preprocessing overhead and minimizing cache effects.
> This limit also implies worst-case performance is linear.
>
> Small needles up to size 2 use a dedicated linear search. Very long needles
> use the Two-Way algorithm (to avoid increasing stack size inlining is now disabled).
>
> The performance gain is 6.6 times on English text on AArch64 using random
> needles with average size 8 (this is even faster than the recently improved strstr
> algorithm, so I'll update that in the near future).
>
> The size-optimized memmem has also been rewritten from scratch to get a
> 2.7x performance gain.
>
> Tested against GLIBC testsuite and randomized tests.
>
> --
> +
> +#if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
> +
> +/* Small and efficient memmem implementation. */
I'd strike the word 'efficient' in this comment, as...
> +void *
> +memmem (const void *haystack, size_t hs_len, const void *needle, size_t ne_len)
> +{
> + const char *hs = haystack;
> + const char *ne = needle;
> +
> + if (ne_len == 0)
> + return (void *)hs;
> + int i;
> + int c = ne[0];
> + const char *end = hs + hs_len - ne_len;
> +
> + for ( ; hs <= end; hs++)
> + {
> + if (hs[0] != c)
> + continue;
> + for (i = ne_len-1; i != 0; i--)
No spacing around the operator?
> + if (hs[i] != ne[i])
> + break;
> + if (i == 0)
> + return (void *)hs;
...this is the naive quadratic implementation. But it does certainly
qualify as the algorithm to use for someone wanting a compilation as
small as possible, and who doesn't care about speed (most likely because
their needles are unlikely to be large enough to notice the effects of
quadratic slowdowns).
> +#else
>
> -#if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__)
> # define RETURN_TYPE void *
> # define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
> # include "str-two-way.h"
> -#endif
>
> +#define hash2(p) ((size_t)((p)[0]-((p)[-1]<<3)) % sizeof (shift))
> +
> +
> +/* Fast memmem algorithm with guaranteed linear-time performance.
> + Small needles up to size 2 use a dedicated linear search. Longer needles
Why is the super-small needle cutoff at 2, rather than 4 or 8 by taking
advantage of vectorized searching?
> + up to size 256 use a novel modified Horspool algorithm. It hashes pairs
> + of characters to quickly skip past mismatches.
> + By limiting the needle length to 256, the shift table can be reduced to 8
> + bits per entry, lowering preprocessing overhead and minimizing cache effects.
> + The limit also implies worst-case performance is linear. On long needles a
> + self-adapting filtering step is used to quickly determine mismatches.
> + Needles larger than 256 characters use the linear-time Two-Way algorithm. */
I can't promise that I tried to completely understand the algorithm, but
the approach makes sense.
> + /* Use Two-Way algorithm for very long needles. */
> + if (__builtin_expect (ne_len > 256, 0))
> + return two_way_long_needle (hs, hs_len, ne, ne_len);
>
> - /* Larger code size, but guaranteed linear performance. */
> + uint8_t shift[256];
> + size_t tmp, shift1;
> + size_t m1 = ne_len - 1;
> + size_t offset = 0;
>
> - /* Sanity check, otherwise the loop might search through the whole
> - memory. */
> - if (haystack_len < needle_len)
> - return NULL;
> + /* Initialize bad character shift hash table. */
> + memset (shift, 0, sizeof (shift));
I don't know if we have a preference for 'sizeof shift' rather than
'sizeof (shift)'.
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3266
Virtualization: qemu.org | libvirt.org