Repository navigation
bytes.find consistently hangs in a particular scenario #86138
Description
Activity
Zeturic commented
on Oct 7, 2020 ZeturicmannequinMannequinAuthorSorry for the vague title. I'm not sure how to succinctly describe this issue.
The following code:
with open("data.bin", "rb") as f: data = f.read() base = 15403807 * b'\xff' longer = base + b'\xff' print(data.find(base)) print(data.find(longer))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 commented
on Oct 8, 2020 MojoVampiremannequinMannequinCan 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.
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 ;-)
What is the content of "data.bin"? How can we reproduce the issue?
68 remaining items
Toward that end it would be fine to use "very high" cutoffs, and save tuning for later.
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.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".
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 commented
on Feb 26, 2021 cfbolzmannequinMannequinBTW, this initialization in the FASTSEARCH code appears to me to be a mistake:
skip = mlast - 1;
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.)
If Tim approves we might get it into alpha 6 which goes out Monday.
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 ;-)
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:
while (skip > 0 && window_last < haystack_end) { window_last += skip; skip = table[(*window_last) & 63]; }
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:
https://gist.github.com/sweeneyde/fc20ed5e72dc6b0f3b41c0abaf4ec3beSummary 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 fasterOn 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 fasterLooks 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! ✨ 🍰 ✨
str in stron random words of a language with a Zipf distributionNote: 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:
bugs.python.org fields: