Speed surprises in reimplementing the .find() string method

March 1, 2008

In yesterday's entry, I mentioned that I was surprised by the relative performances of my three reimplementations of the .find() string method.

The src[i:].startswith(sub) version was the slowest, and why is obvious in hindsight: it's summed up clearly in the first bit, where we create a big new string (src[i:]) on every iteration of the loop. No wonder it's slow; creating big strings is slow in general, because you both churn object memory and copy a lot of data around.

Now it's easy to see why the brute force src[i:i+len(sub)] == sub is much faster; with it, we are only creating a relatively small new string every iteration around the loop, especially with my rather small sub string.

The real surprise to me is that the src.startswith(sub, i) version is not the fastest, and not by a small margin (it's generally more than twice as slow as the fastest version). By all rights it should be by far the winner, since it requires no object creation or data copying and should boil down to just a memcmp(). I don't know what the Python runtime is doing, but clearly something is dropping the ball.

The really interesting part of this for me is that I started with the the one-argument startswith() version; I added the brute force version only out of a sense of completeness, because it was the most C-like approach, and I expected it to be the slowest.

Comments on this page:

From at 2008-12-30 17:23:08:

The slowness of ".startswith()" comes from Python's method call overhead. First is the getattr(s, "startswith") and then is the call(f, ()). While [] and == have special optimizations.

--Andrew Dalke

From at 2009-07-07 11:40:10:

Any slowness from getattr(src, "startswith") could be dealt with by doing "sw = src.startswith" and then using "sw" to do "sw(sub, i)".

-- Jeff Kaufman
Written on 01 March 2008.
« An illustration of the speed advantage of Python builtins
How ZFS's version of RAID-5 can be better than normal RAID-5 »

Page tools: View Source, View Normal, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Sat Mar 1 23:31:31 2008
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.