[Top][All Lists]

[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,

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]