[PATCH] Optimize generic strtok(_r) function.

[Carlos O'Donell]

On 3/12/20 11:30 AM, Joseph Yoo wrote:
> The current generic strtok_r implementation calls strspn to find the
> beginning of the token and strcspn to find the end. Within each of these
> call stacks is a redundant 256-byte look-up table used to compare chars
> of S with DELIM. This patched version, for the most part, manually
> inlines them + adds other (commented) optimizations. Still, strtok(_r)
> benefits from existing str(c)spn vector implementations. So, any
> sub-arch with a __str(c)spn_(vx/sse42/etc) should also have a
> __strtok_r_(vx/sse42/etc) to call them explicitly. I've done so for those
> affected: x86_64, powerpc64/power8, s390(x), and i386/686.
> I've tested on my own x86_64 machine, but I'd like help with the
> others (there seem to be different conventions in how versioning
> is done, and I'm acquainted with at least none of them). 

Thanks for posting this!

Before we go much further I just wanted to check if you have copyright
assignment with the FSF and to make sure we start that process if you don't.
Assignment will allow us to review patches quickly and with minimal friction.

The contribution checklist is here:
https://sourceware.org/glibc/wiki/Contribution%20checklist

> I CC-ed Adhemerval Zanella because I was working under their
> branch, generic-strings, and also just noticed that this goes
> against their goal of promoting portability. Meaning, it seems it would
> be preferred to keep str(c)spn in this function. So, another solution
> could be to 'externally' inline the two calls (strspn+strcspn),
> allowing an optimizing compiler to prevent re-allocation. With 
> optimization flags set at O[s,2-3] (tested in x86_64 gcc 9.2) the compiler 
> does so. However, the instructions to zero the table, 
> search through delim, and set the table still repeat. So, manual inlining 
> seems to be 'optimal,' but I understand that it would mean more work in
> terms of having to write more architecture-specific implementations.

Correct, and at an architectural review level the direction you are
proposing here goes against what we've been doing over the past couple
of years to centralize the implementations. I'll let Adhemerval comment
more.

Without looking too deeply at your changes, what kinds of performance
improvements do you see? 

> I hope this patch/email/Changelog format is somewhat correct!

You don't need ChangeLog's anymore :-)

-- 
Cheers,
Carlos.