Re: [PATCH] Significant performance improvements to locate, struct order optimizations

[Eric Blake]

On 05/16/2018 02:35 AM, Bernhard Voelker wrote:
> >     1. By default, I replaced the strstr implementation with the
> >        fast_strstr implementation by Raphael Javaux (BSD 3-Clause,
> >        https://github.com/RaphaelJ/fast_strstr).

Which states:

"Its worst case complexity (O(n × m) where n is the length of the string 
and m the length of the searched sub-string) is the same as the naive 
brute-force algorithm but it mostly runs with a linear complexity (O(n)) 
on most strings."

However, gnulib's strstr() implementation has a worst-case complexity of 
O(n+m) (linear, not quadratic).  Thus, fast_strstr() is NOT always 
faster, given pathological input.

There may be ways to speed up gnulib's strstr().  gnulib was the first 
widely-available linear implementation of strstr() that I'm aware of (at 
the time I contributed it, I could not find any other open source 
implementation that was linear) - but that does not mean it is the 
fastest.  At one point, gnulib's version was imported to glibc (as 
linear is better than quadratic for large string searches, although the 
startup penalties are noticeable on small strings); later, glibc added 
heuristics to further speed up their implementation to dynamically 
switch between algorithms to avoid the penalties on small strings while 
still remaining linear on large strings.  I'm not sure if all of the 
subsequent glibc improvements have been ported back to gnulib.  gnulib 
already rejects libc strstr() that are quadratic (which I suspect is 
still the case with MacOS) - but that becomes a topic for gnulib to 
decide if we should also be replacing libc strstr() when we can prove 
that our implementation is faster, without forcing the replacement (and 
risking speed penalties) on other systems.

> First of all, performance improvements should *never* be done in
> one patch,

Make that: s/performance/multiple performance/

But yes, a good rule of thumb is that you should always have each patch 
do one thing only, rather than cramming multiple actions into a single 
patch.  You want to make the reviewer's life easier, even if a series of 
well-divided patches adds up to more cumulative changes (due to churn on 
some lines) than a single patch that combines all the changes at once.

--
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org