two-way for `str.rfind`

[dg-pb]

Feature or enhancement

Proposal:

After closing with: #120025 (comment)

I appreciate that str.rfind is much less frequently used than str.find. But as can be seen it the PR above, it is fairly easy to make two_way bi-directional to handle both. I concluded that for standard track Horspool algorithm the cost of bi-directional logic is best avoided - those methods are fairly short and simple. However, two-way is a plausible candidate I think. Having separate functions for both direction would mean very large code duplications and I think paying a small perf cost to keep single logic for both might be a fairly good deal.

I think it would be good to do it - single string search is one of the most important low level algorithms - having this space clean and complete is I think a good thing -- it would give peace of mind for developers and predictable behaviour for users, and library developers who make heavy use of string search, allowing to derive new algorithms that work in both directions without performance surprises when running in reverse.

There is a workaround of course:

idx = str[::-1].find(sub[::-1])
if idx != -1:
    idx = len(str) - len(sub) - idx

However, for small problem sizes this is a non-trivial overhead + double memory.

So, what are the thoughts of others?
Is adapting two-way search to serve str.rfind (eliminating its O(n^2) worst case) desirable/worthwhile?

cc @methane @rhettinger @serhiy-storchaka @vstinner

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

[picnixz]

I'm sorry but this issue is unclear to me.

I think it would be good to do it - single string search is one of the most important low level algorithms - having this space clean and complete is I think a good thing -- it would give peace of mind for developers and predictable behaviour for users, and library developers who make heavy use of string search, allowing to derive new algorithms that work in both directions without performance surprises when running in reverse.

What do you mean by "space clean"? do you mean the code? if this is the case, it's not enough. Otherwise we would have already run linters on the entire source. Also, I don't think this is an argument for changing the code of something that worked and wasn't the issue.

However, for small problem sizes this is a non-trivial overhead + double memory.

I'm not sure I understand. If the problem's size is small it's negligible. And if the problem has limited memory, I don't think doubling the size of a string is really the bottlneck. But that could be debatable. As for the "non-trivial overhead", what's really the overhead? it's again an implementation detail that barely anyone would be aware of unless they experimentally saw "oh rfind() runs muchs slower sometimes!". For real use-cases I doubt it matters.

---

So please, could you answer the following questions:

• what are you real use cases? is there any codebase that would really benefit from that change?
• what is the exact change you want to make: is it the same as the PR you closed but only limited to one of its part?
• hypothetically, what would be the changes you want to make and what would be their costs and benefits? how are they expressed?

[dg-pb]

What do you mean by "space clean"?

By this I meant polishing/completing optimal complexity profile of the single-pattern string search by synchronising forward and reverse search by adapting missing things to reverse search that are present in forward search.

I'm not sure I understand.
These are separate:
a) non-trivial overhead for small problem sizes
b) double memory (matters for large problem sizes)

• what are you real use cases? is there any codebase that would really benefit from that change?

To me personally, use cases are various utilities that have rev argument and make use of str.find/str.rfind. I have a branch in these which does the above reversal hack when rev=2, but I would rather not have it in the long run.

• what is the exact change you want to make: is it the same as the PR you closed but only limited to one of its part?

It is as stated in the headline: two-way path for reverse search. I can offer my experience and thoughts, which is that bi-directional logic could be a good way for it, but if there are better ways to do it, I don't mind.

• what would be the changes you want to make and what would be their costs and benefits? how are they expressed?

In case of bi-directional logic it is part of the PR I linked.

Benefits - No O(n^2) case on reverse string search - forward and reverse searches are in sync.

Costs - a bit of additional complexity.

However, it is quite small compared to the amount of extra code if we had 2 two-way functions - 1 for forward and 1 for reverse.

Performance penalty was very small.
And I think it can be eliminated by exploiting branch predictions.
In either case, two-way can generally be considered as a secondary branch which doesn't kick in that often -- from what I have seen, performance penalty (if any) would be acceptable.

[picnixz]

To me personally, use cases are various utilities that have rev argument and make use of str.find/str.rfind. I have a branch in these which does the above reversal hack when rev=2, but I would rather not have it in the long run.

This still does not answer the question about data. When I said "real use cases" I meant also "projects that do NOT know about the slowliness". I never thought rfind() was really slow. How are real projects affected in practice by that? I'm sorry but I see little benefits in rewriting an algorithm to solely optimize worst case complexity (for regular and resonable use cases, is there any difference?).

Also, while the worst case is quadratic, in pratice, is it the bottleneck? I used rfind() most of the time for strings that are relatively short (at most few characters) in strings that could be large, and even in a loop, the surrounding code is usually the bottleneck, not rfind() itself. If I want strings much faster I would not use Python directly.

What I lack are examples that would really see an improvement. Namely, today I do s.rfind(t) and it takes X time but with two-way I can get it in X/2 time. That would help in determining whether changing the code is relevant. Remember, Python is not meant to be the fastest. We can try to make it fast but it is still preferrable to make as little changes as possible when we can.

---

How complex would the patch be? and would it affect PGO/and how? when you say "complexity", this is about code complexity right? I would rather have duplicated functions instead to avoid lots of if/else branches needed because that, or intricate arithmetic.

[dg-pb]

I see little benefits in rewriting an algorithm

It is rather adapting existing well tested algorithm from forward search to reverse search.

How complex would the patch be?

It is nothing more than storing dir=1/-1 with few extra variables. So that the same loop iterates in whichever direction is needed. It is branchless and as I said performance difference is minimal. Thinking now, I would test how it would work with branches instead - as direction is constant throughout the routine I suspect branch prediction would result to speed as if there were no branches.

Main function and preparation routines would need to be extended. But I have those - this has been written for a long time now - all tests pass, all works.

What I lack are examples that would really see an improvement.

Go to referenced PR. Most of benefit in rfind benchmark results table is from this specific adaptation. 2-3x faster on average for the test suite with several different structures with quite a few permutations on haystack/needle size. I have inherited most of test cases from when two-way was initially written.

[dg-pb]

I would rather have duplicated functions instead to avoid lots of if/else branches needed because that, or intricate arithmetic.

Would be interested to hear what others think. This is one of 2 main questions. First one being: "do we want to do this at all?".

It is roughly extra 300 LOC. With bi-directional logic code size pretty much stays constant. However, I think the biggest benefit is not having to keep 2 algorithms in sync.

[picnixz]

Go to referenced PR. Most of benefit in rfind benchmark results table is from this specific adaptation. 2-3x faster on average for the test suite with several different structures with quite a few permutations on haystack/needle size. I have inherited most of test cases from when two-way was initially written.

This kind of answer should be included in the issue. I should not ne forced to navigate through issues or PRs to see such justifications. I also find the tables hard to read but maybe it's because it's late

---

More generally, I think such questions should be asked on DPO first. You will reach a larger audience that could also have other ideas.