`str.rfind()` slower than `str.find()` on macOS

Why is str.rfind() 14x slower than str.find() on macOS? That doesn’t even make sense.

from timeit import timeit

print(timeit("string.find('/')", setup="string = 'a' * 1000"))
print(timeit("string.rfind('/')", setup="string = 'a' * 1000"))
wannes@Stefans-iMac cpython % main/python.exe find_str.py 
0.04677163400265272
0.6524513209988072

Specs:

Processor 3.6 GHz Quad-Core Intel Core i7
Graphics Radeon Pro 560 4 GB
Memory 16 GB 2400 MHz DDR4
macOS 13.6.7 (22G720)

Because there are some fast existing library for forward search, but not enough for backward search.

memrchr() is glibc function. not available on macOS.

1 Like

Thanks, that explains everything. Should I mention this on my pull request?

I don’t know what is your pull request. But maybe yes.

Hm, on my machine[1] it’s more like a 3-4x slowdown for that example, although it gets up to 15x if I increase the size of the string 10x.

I wonder if the 3-4x slowdown is due to the difference in algorithm and the 15x slowdown is more specific to architecture or something else.


  1. Macbook Pro, 2.4 GHz 8-Core Intel Core i9 ↩︎

It is almost faster to reverse the string and do find:

from timeit import timeit

print(timeit("string[::-1].find('/')", setup="string = 'a' * 1000"))
0.8221996217034757

print(timeit("string.find('/')", setup="string = 'a' * 1000"))
0.12581167742609978

print(timeit("string.rfind('/')", setup="string = 'a' * 1000"))
0.5199544378556311

That doesn’t look like “almost faster” to me :joy:

2 Likes

Maybe it something like when you access memory the caching assumes that it is very likely you will access higher addresses.
Sane for page faulting in the OS.

But rfind wants to access lower addresses, which the chips do not optimise? I could be completely wrong, this is a wild guess.