[1/*] Generic string function optimization: Add skeleton

Hi,

As i mentioned improving generic string functions this is my second
attempt. As lot of functions will be optimized in same way this uses
generic code flow. Functions will vary just by expression to check and
how interpret return value.

Performance gains of using this are from loop unrolling and better
header that doesn't have to check start byte-by-byte.

Unrolling migth be excessive but its better to tune it in skeleton than
try manually and risk introducing errors.

This implementation would probably be faster than assembly on other
architectures as this will beat it unless you used hardware specific
instruction or gcc messes up compilation and generates suboptimal code.

Comments?

	* string/common.h: New file.
	* string/skeleton.h: Likewise.

---
 string/common.h   |  35 +++++++++++++
 string/skeleton.h | 145 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 180 insertions(+)
 create mode 100644 string/common.h
 create mode 100644 string/skeleton.h

--

On Fri, 29 May 2015, Ondřej Bílka wrote:

> On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> > On Thu, 28 May 2015, Ondřej Bílka wrote:
> > 
> > > Both comments are correct. We should do it generically and surround
> > > these functions with ifdef to supply arch-specific versions. 
> > 
> > #if, not #ifdef, please, for all architecture choices in these functions.  
> > The sysdeps/generic version of the header architectures can use to change 
> > the default choices should have detailed comments on the default 
> > definitions of all the relevant macros to explain their semantics.
> > 
> For what purpose? Its pointless except that you would need to have
> additional header say precommon.h, then undef and redefine macro when
> you want change.

The general principle is that macro uses should be typo-proof.  That means 
avoiding #ifdef, #ifndef and #undef where possible.

The principle of documenting macro semantics applies even if there's a 
good reason typo-proof conventions are problematic in a particular case.  
There should *never* be any sort of architecture hook without clear 
documentation of the semantics of the hook (written from the perspective 
of an architecture maintainer wanting to know how to set the hook for 
their architecture, not from the perspective of the person writing the 
code using the hook).  I always advise writing documentation early in the 
process of developing a patch - the documentation is as important as the 
rest of the code.

> And it doesn't help to catch any errors. If you misspell define then you
> will get error with duplicate definition.

If the code does

#ifdef MACRO

or

#ifndef MACRO

then if an architecture does

#define MCARO

(with or without #undef) that will silently be ignored.

If, instead, the code does

#if MACRO

and there's a sysdeps/generic header that defines MACRO one way, if an 
architecture overrides that header with one that misspells the name, a 
-Wundef warning will be immediately visible (though we still need to fix 
the -Wundef warnings in the testsuite and remove the -Wno-error=undef).

On Fri, May 29, 2015 at 10:42:17AM +0000, Joseph Myers wrote:
> On Fri, 29 May 2015, Ondřej Bílka wrote:
> 
> > On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> > > On Thu, 28 May 2015, Ondřej Bílka wrote:
> > > 
> > > > Both comments are correct. We should do it generically and surround
> > > > these functions with ifdef to supply arch-specific versions. 
> > > 
> > > #if, not #ifdef, please, for all architecture choices in these functions.  
> > > The sysdeps/generic version of the header architectures can use to change 
> > > the default choices should have detailed comments on the default 
> > > definitions of all the relevant macros to explain their semantics.
> > > 
> > For what purpose? Its pointless except that you would need to have
> > additional header say precommon.h, then undef and redefine macro when
> > you want change.
> 
> The general principle is that macro uses should be typo-proof.  That means 
> avoiding #ifdef, #ifndef and #undef where possible.
> 
> The principle of documenting macro semantics applies even if there's a 
> good reason typo-proof conventions are problematic in a particular case.  
> There should *never* be any sort of architecture hook without clear 
> documentation of the semantics of the hook (written from the perspective 
> of an architecture maintainer wanting to know how to set the hook for 
> their architecture, not from the perspective of the person writing the 
> code using the hook).  I always advise writing documentation early in the 
> process of developing a patch - the documentation is as important as the 
> rest of the code.
> 
> > And it doesn't help to catch any errors. If you misspell define then you
> > will get error with duplicate definition.
> 
> If the code does
> 
> #ifdef MACRO
> 
> or
> 
> #ifndef MACRO
> 
> then if an architecture does
> 
> #define MCARO
> 
> (with or without #undef) that will silently be ignored.
> 
> If, instead, the code does
> 
> #if MACRO
> 
> and there's a sysdeps/generic header that defines MACRO one way, if an 
> architecture overrides that header with one that misspells the name, a 
> -Wundef warning will be immediately visible (though we still need to fix 
> the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> 
Joseph, read previous mail before writing. Your suggestion is pointless.

For a code

#ifndef CUSTOM_FOO
int foo()
{
}
#endif

If architecture does
#define CUTSOM_FOO
int foo()
{
}

Then it gets error with redefinition of foo.

On Fri, 29 May 2015, Ondřej Bílka wrote:

> > If, instead, the code does
> > 
> > #if MACRO
> > 
> > and there's a sysdeps/generic header that defines MACRO one way, if an 
> > architecture overrides that header with one that misspells the name, a 
> > -Wundef warning will be immediately visible (though we still need to fix 
> > the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> > 
> Joseph, read previous mail before writing. Your suggestion is pointless.

Which previous mail?  As far as I can tell, your last patch posting adding 
common.h is <https://sourceware.org/ml/libc-alpha/2015-05/msg00751.html>, 
which has a range of within-function #ifdefs (some completely untested, 
e.g. "#  ifdef NEED BITWISE", and all completely undocumented).  Anyway, 
when we have conventions in glibc (such as preferring #if to #ifdef) you 
should follow them unless there is a strong justification for doing 
otherwise (presented in every patch submission).  Likewise, even early 
patches should follow normal glibc formatting conventions.

Throwing out a series of untested, undocumented patches is not a helpful 
way of proposing changes to glibc.  I strongly recommend, in any 
complicated case such as this, that:

(a) each patch submission is self-contained - has the full self-contained 
write-up of the patch itself with the rationale for the patch and all the 
choices made, that would go in the commit message, followed by the 
description of changes from the previous version, rather than requiring a 
trail of previous messages to be followed to get the full rationale; and

(b) the documentation is more important than the code (write first for 
humans to read, only then for computers to execute); documenting the 
interfaces (such as FAST_CLZ and NEED_BITWISE) should be a very early step 
before any patches are sent to the list, not an afterthought, and the same 
applies to each internal function and macro in the code, even those that 
are not interfaces for architectures to reimplement.

> For a code
> 
> #ifndef CUSTOM_FOO
> int foo()
> {
> }
> #endif
> 
> If architecture does
> #define CUTSOM_FOO
> int foo()
> {
> }
> 
> Then it gets error with redefinition of foo.

Or you could avoid making readers think about whether the #ifndef is OK in 
a particular case by simply following normal glibc practices and have a 
sysdeps/generic/string-foo.h header that has a default definition with a 
careful comment explaining the semantics, and then architectures can have 
their own version to replace it as needed; no macros needed at all.

On Fri, May 29, 2015 at 11:38:51AM +0000, Joseph Myers wrote:
> On Fri, 29 May 2015, Ondřej Bílka wrote:
> 
> > > If, instead, the code does
> > > 
> > > #if MACRO
> > > 
> > > and there's a sysdeps/generic header that defines MACRO one way, if an 
> > > architecture overrides that header with one that misspells the name, a 
> > > -Wundef warning will be immediately visible (though we still need to fix 
> > > the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> > > 
> > Joseph, read previous mail before writing. Your suggestion is pointless.
> 
> Which previous mail?  As far as I can tell, your last patch posting adding 
> common.h is <https://sourceware.org/ml/libc-alpha/2015-05/msg00751.html>,

This one. I already explained that for using if you would need
additional header to be able to undefine macros.

https://sourceware.org/ml/libc-alpha/2015-05/msg00812.html


> 
> (a) each patch submission is self-contained - has the full self-contained 
> write-up of the patch itself with the rationale for the patch and all the 
> choices made, that would go in the commit message, followed by the 
> description of changes from the previous version, rather than requiring a 
> trail of previous messages to be followed to get the full rationale; and
>
Almost nobody does that for good reason, see that most v2 on lists are
shorter than previous. You should write mostly what changed. Sure, I
could copy-paste three pages from original mail with rationale but most
readers would skip it as its duplicate and would skip changes made into
it.

I could make recapitulation once per while but for incremental
improvements its best to keep just increments.
 
> (b) the documentation is more important than the code (write first for 
> humans to read, only then for computers to execute); documenting the 
> interfaces (such as FAST_CLZ and NEED_BITWISE) should be a very early step 
> before any patches are sent to the list, not an afterthought, and the same 
> applies to each internal function and macro in the code, even those that 
> are not interfaces for architectures to reimplement.
> 
Thats not completely true as purpose of this is get every bit of
performance before you need to go into assembly. It depends how
technical my interface will become, with strcmp I found that I need
handle another primitive. As documentation its better to have good
overview than overly verbose one. Some macros there are just there for
optimizer to try both branches and select better one.


> > For a code
> > 
> > #ifndef CUSTOM_FOO
> > int foo()
> > {
> > }
> > #endif
> > 
> > If architecture does
> > #define CUTSOM_FOO
> > int foo()
> > {
> > }
> > 
> > Then it gets error with redefinition of foo.
> 
> Or you could avoid making readers think about whether the #ifndef is OK in 
> a particular case by simply following normal glibc practices and have a 
> sysdeps/generic/string-foo.h header that has a default definition with a 
> careful comment explaining the semantics, and then architectures can have 
> their own version to replace it as needed; no macros needed at all.
> 
First its too typo-prone. Architecture maintainer would create
string_foo.h file and never notice that it was silently ignored.


Then why didn't you said that directly? That saves time instead
suggesting if when you mean separate file. Thats correct as there are
several variants and you need to run benchmark to select correct one.