This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Machine maintainer veto.


On Fri, 3 Jul 2015, David Miller wrote:

> From: Rich Felker <dalias@libc.org>
> Date: Fri, 3 Jul 2015 12:54:38 -0400
> 
> > BTW, another specific issue I expect to come up again and again is
> > performance, particularly situations where a machine maintainer
> > wants a "fast" implementation of some function that's fast in the
> > cases they care about but O(n²) whereas the generic implementation
> > is O(n) or O(n*log(n)). I would say this is a situation where
> > allowing the bad-big-O implementation should require consensus at
> > the project level rather than machine maintainer veto
> > discretion. The right solution in general is almost sure to be
> > something like the introsort solution (self-measurement to fall back
> > to generic code for cases where worst-case performance is imminent)
> > which is more work for the machine-specific code contributor or
> > machine maintainer but better for the project.
> 
> I don't think the project as a whole gets to dictate what is the best
> performance selection or set of tradeoffs for CPU X in all possible
> scenerios.
> 
> Port specific performance tradeoffs exist (f.e.: people who use CPU X
> do _NOT_ care about case Y of string function Z so we don't have to
> optimize it well), and you cannot enfore tree wide rules in this area.

I think that's only valid for constant factors, not for cases such as 
quadratic strstr implementations.  The exponent should be considered part 
of the architecture-independent, OS-independent GNU API for glibc, and so 
increased exponents should be unacceptable in any machine-specific 
implementation (and grounds for removal of such an implementation as a 
security regression - strstr can be used with untrusted inputs - if such 
an O(n^2) implementation gets in where the machine-independent 
implementation is O(n), and the machine maintainer doesn't fix it 
promptly).

The strstr case is also a case involving cooperation between GNU projects 
- gnulib has a test that strstr works in linear time, building a 
replacement implementation if libc's strstr is quadratic, and if gnulib 
considers a glibc function buggy that's a problem that needs to be worked 
out in collaboration between the projects.

-- 
Joseph S. Myers
joseph@codesourcery.com

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]