Better calibration of str.find aka FASTSEARCH

[dg-pb]

Feature or enhancement

Proposal:

Details in discourse link.
Exact methodology will be laid out in PR docstrings.

Has this already been discussed elsewhere?

I have already discussed this feature proposal on Discourse

Links to previous discussion of this feature:

https://discuss.python.org/t/optimize-str-find-aka-fastsearch/54483/2

Linked PRs

• gh-119702: New dynamic algorithm selection for string search (+ rfind alignment) #120025

[dg-pb]

Ok, let's do that. I have decided to put all in 1 PR. After a bit of refactoring and simplifying, it does seem manageable.

Things that I have done (for you to prepare mentally :)):

1. Split _prepare of two-way into 2. One part is used by new dynamic algorithm, then it passes it forward to two-way so that it does not need to do the work again
2. Merged 2 big loops of two-way into 1.
3. Eliminated nested loops of two-way.
4. Counting is now part of _two_way in the same way as default_find does it. Thus removed two_way_count and two_way_find does both (same as default_find).
5. Did 2 level logging. Added one more level to not print any outputs with input strings. (Sometimes it is useful to see what algorithm is doing for long inputs, but screen gets flooded). Also logged period and gap.
6. Added special case for n == m to use memcmp. Tried to cover a bit more with it, but complexity was not worth it for few more special cases, so left it at only for 1.
7. Finally, added horspool_find function, which is now the main function.

[dg-pb]

It is not as bad as it sounds and I am happy to revert any changes that are not crucial for my implementation to work.

I am encountering a strange situation, where adding 1 extra variable performance decreases by 100%. It feels like hitting some sort of threshold. Just addition of a simple counter variable sometimes causes enormous changes in performance.

Have you ever encountered anything like that?

[sweeneyde]

Have you ever encountered anything like that?

I'm not sure off the top of my head; it could be a compiler running out of registers or it could be random fluctuations in binary layout.

[dg-pb]

Latest results. I have extended the table to cover more space.

Average improvement - 105%, meaning on average current approach takes twice as long to run.

Note, max alpha for green is at 200%, while max alpha for red is at 100%.

Results

Here, hardcoded boundaries of current approach can be clearly seen:
a) The square on the upper left is where default is running. Then, performance decrease can clearly be seen after this step. It has seemingly been kicking in two-way too early.
b) step change on the bottom, where adaptive_find kicks in when m > n / 3. It also seems to be kicking in too early.

Current approach does not have such steps. Instead it has 1 function horspool_find, which effectively combines bloom from default_find and bad character table from two_way_find.

It works well, because bad character table initialization is quick (compared to bloom) so initialization does not experience any significant penalty compared to default_find.

Then, it dynamically switches to two-way if it detects that it can run faster.

However, this data-set doesn't seem to ever switch to it as improved default (now horspool) handles many more cases linearly.

[dg-pb]

Just to correct myself. It is not that current rules are kicking in "too early".

Those boundaries are visible, because new "horspool_find" is able to handle some cases more efficiently than "default_find" and "two_way" find.

So where there was a step change before, now it is 1 algorithm handling the whole space.