[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] Significant performance improvements to locate, struct order
From: |
Eric Blake |
Subject: |
Re: [PATCH] Significant performance improvements to locate, struct order optimizations |
Date: |
Wed, 16 May 2018 09:36:30 -0500 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 |
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