Repository navigation
bytes.find consistently hangs in a particular scenario #86138
Description
| BPO | 41972 |
|---|---|
| Nosy | @gvanrossum, @tim-one, @rhettinger, @gpshead, @cfbolz, @taleinat, @pmp-p, @ambv, @serhiy-storchaka, @MojoVampire, @ammaraskar, @corona10, @sweeneyde, @Zeturic |
| PRs | |
| Files | str in str on random words of a language with a Zipf distribution |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = <Date 2021-07-19.15:25:54.659>
created_at = <Date 2020-10-07.23:31:59.517>
labels = ['3.9', '3.10', 'performance']
title = 'bytes.find consistently hangs in a particular scenario'
updated_at = <Date 2021-07-19.15:25:54.658>
user = 'https://github.com/Zeturic'bugs.python.org fields:
activity = <Date 2021-07-19.15:25:54.658>
actor = 'lukasz.langa'
assignee = 'none'
closed = True
closed_date = <Date 2021-07-19.15:25:54.659>
closer = 'lukasz.langa'
components = []
creation = <Date 2020-10-07.23:31:59.517>
creator = 'Zeturic'
dependencies = []
files = ['49499', '49503', '49507', '49508', '49511', '49512', '49518', '49545', '49577', '49578', '49674', '49746']
hgrepos = []
issue_num = 41972
keywords = ['patch']
message_count = 77.0
messages = ['378197', '378209', '378210', '378221', '378222', '378225', '378229', '378233', '378260', '378263', '378301', '378329', '378372', '378420', '378423', '378470', '378472', '378534', '378537', '378541', '378543', '378556', '378576', '378578', '378579', '378582', '378583', '378584', '378585', '378590', '378600', '378635', '378652', '378736', '378737', '378739', '378742', '378750', '378751', '378753', '378793', '378828', '378834', '378836', '378842', '378843', '378844', '378847', '378916', '378917', '378920', '378922', '378923', '378924', '378979', '379388', '379391', '379422', '379494', '379822', '379825', '380473', '380474', '380476', '380477', '380487', '382905', '385169', '387717', '387790', '387791', '387792', '387813', '397277', '397787', '397788', '397805']
nosy_count = 14.0
nosy_names = ['gvanrossum', 'tim.peters', 'rhettinger', 'gregory.p.smith', 'Carl.Friedrich.Bolz', 'taleinat', 'pmpp', 'lukasz.langa', 'serhiy.storchaka', 'josh.r', 'ammar2', 'corona10', 'Dennis Sweeney', 'Zeturic']
pr_nums = ['22679', '22904', '24672', '27091']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue41972'
versions = ['Python 3.9', 'Python 3.10']
Activity
Zeturic commentedon Oct 7, 2020
Sorry for the vague title. I'm not sure how to succinctly describe this issue.
The following code:
Always hangs on the second call to find.
It might complete eventually, but I've left it running and never seen it do so. Because of the structure of data.bin, it should find the same position as the first call to find.
The first call to find completes and prints near instantly, which makes the pathological performance of the second (which is only searching for one b"\xff" more than the first) even more mystifying.
I attempted to upload the data.bin file I was working with as an attachment here, but it failed multiple times. I assume it's too large for an attachment; it's a 32MiB file consisting only of 00 bytes and FF bytes.
Since I couldn't attach it, I uploaded it to a gist. I hope that's okay.
https://gist.github.com/Zeturic/7d0480a94352968c1fe92aa62e8adeaf
I wasn't able to trigger the pathological runtime behavior with other sequences of bytes, which is why I uploaded it in the first place. For example, if it is randomly generated, it doesn't trigger it.
I've verified that this happens on multiple versions of CPython (as well as PyPy) and on multiple computers / operating systems.
MojoVampire commentedon Oct 8, 2020
Can reproduce on Alpine Linux, with CPython 3.8.2 (running under WSLv2), so it's not just you. CPU usage is high; seems like it must be stuck in an infinite loop.
tim-one commentedon Oct 8, 2020
Also reproduced on 64-bit Win10 with just-released 3.9.0.
Note that string search tries to incorporate a number of tricks (pieces of Boyer-Moore, Sunday, etc) to speed searches. The "skip tables" here are probably computing a 0 by mistake. The file here contains only 2 distinct byte values, and the relatively huge string to search for has only 1, so there's plenty of opportunity for those tricks to get confused ;-)
serhiy-storchaka commentedon Oct 8, 2020
What is the content of "data.bin"? How can we reproduce the issue?
68 remaining items
sweeneyde commentedon Nov 7, 2020
This feels reasonable to me -- I changed the cutoff to the more cautious
if (m >= 100 && n - m >= 5000), where the averages are very consistently faster by my measurements, and it seems that Tal confirms that, at least for them >= 100part. More tuning may be worth exploring later, but this seems pretty safe for now, and it should fix all of the truly catastrophic cases like in the original post.sweeneyde commentedon Dec 12, 2020
For convenience, attached is a quick and dirty Tkinter GUI that lets you step through the Crochemore/Perrin Algorithm on your choice of inputs, just for play/discovery.
A good illustration of the memory for periodic needles can be found by testing:
haystack="456,123,123,456,123,123,456"
needle="123,123,123,"
The GUI program does not implement the Boyer-Moore/Horspool/Sunday-style shift-table. In the current PR 22904, this table is used in exactly those situations where the GUI says "Matched 0, so jump ahead by 1".
sweeneyde commentedon Jan 17, 2021
PR 22904 now adds a text document explaining how the Two-Way algorithm works in much more detail.
I was looking at more benchmarking results, and I came to a couple of conclusions about cutoffs.
There's a consistent benefit to using the two-way algorithm whenever both strings are long enough and the needle is less than 20% the length of the haystack. If that percentage is higher, the preprocessing cost starts to dominate, and the Two-Way algorithm is slower than the status quo in average such cases. This doesn't change the fact that in cases like OP's original example, the Two-way algorithm can be thousands of times faster than the status quo, even though the needle is a significant percentage of the length of the haystack.
So to handle that, I tried an adaptive/introspective algorithm like Tim suggested: it counts the number of matched characters that don't lead to full matches, and once that total exceeds O(m), the Two-Way preprocessing cost will surely be worth it. The only way I could figure out how to not damage the speed of the usual small-string cases is to duplicate that code. See comparison.jpg for how much better the adaptive version is as opposed to always using two-way on this Zipf benchmark, while still guaranteeing O(m + n).
cfbolz commentedon Feb 26, 2021
Thanks for pointing that out Tim! Turns out PyPy had copied that mindlessly and I just fixed it.
(I'm also generally following along with this issue, I plan to implement the two-way algorithm for PyPy as well, once you all have decided on a heuristic. We are occasionally in a slightly easier situation, because for constant-enough needles we can have the JIT do the pre-work on the needle during code generation.)
sweeneyde commentedon Feb 27, 2021
Any chance PR 22904 can make it into 3.10 before the May 03 feature freeze? The text document in that PR has some notes on how the algorithm works, so that may be a good place to start reviewing if anyone is interested.
gvanrossum commentedon Feb 27, 2021
If Tim approves we might get it into alpha 6 which goes out Monday.
tim-one commentedon Feb 27, 2021
I'm very sorry for not keeping up with this - my health has been poor, and I just haven't been able to make enough time.
Last time I looked to a non-trivial depth, I was quite happy, and just quibbling about possible tradeoffs.
I can't honestly commit to doing better in the near future, so where does that leave us? I'd personally "risk it".
I just added Raymond to the nosy list, on the off chance he can make some "emergency time" to give a more informed yes/no. He's routinely sucked up weeks of my life with random review requests, so I figure turnabout is fair play ;-)
tim-one commentedon Feb 28, 2021
New changeset 73a85c4 by Dennis Sweeney in branch 'master':
bpo-41972: Use the two-way algorithm for string searching (GH-22904)
73a85c4
sweeneyde commentedon Jul 12, 2021
In "Fast String Searching" (1991), A. Hume and D. Sunday emphasize that most of the runtime of string-search algorithms occurs in a code path that skips over immediately-disqualified alignments. As such, that paper recommends extracting a hot "Horspool" code path and keeping it small. For that reason, I'm posting a PR which boils down that fast path to the following:
This uses two memory accesses, whereas the last implementation used three (the extra to get window[cut]). This requires the skip table to change slightly, since it is indexed by the last character in the current haystack window rather than one character later ("fast" versus "sd1" in the paper). The paper also recommends unrolling this loop 3x, but my benchmarks found no benefit to unrolling.
The PR also refactors some of the main fastsearch code into separate functions, and computes and then uses a similar gap/skip integer used already in the default implementation (Hume and Sunday call this "md2"). It retains a linear-time constant space worst-case with the Two-Way algorithm.
There are a bunch of benchmarks here, both on Zipf-distributed random strings and on a few c/rst/python/binary files in the cpython repo. They compare the current main branch to the PR:
Summary of those results:
On the Zipf strings:
* 83 cases slower (at most 1.59x slower)
* 654 cases faster (up to 4.49x faster)
* Geometric mean: 1.10x faster
On the "Real world" source files:
* 76 cases slower (at most 2.41x slower)
* 420 cases faster (up to 18.12x faster)
* Geometric mean: 1.33x faster
ambv commentedon Jul 19, 2021
I checked the original example in this issue and the newest change in #71278 makes the
data.find(base)case 8.2% faster compared tomainwhile thedata.find(longer)case is 10.8% faster.ambv commentedon Jul 19, 2021
New changeset d01dceb by Dennis Sweeney in branch 'main':
bpo-41972: Tweak fastsearch.h string search algorithms (GH-27091)
d01dceb
ambv commentedon Jul 19, 2021
Looks like this can be closed now, the original issue is fixed, the original patch is merged for 3.10, and the improved patch is merged for 3.11.
Thanks! ✨ 🍰 ✨