Palindromes and string slicing. Performance

Question

There are a lot of ways to check if string is a palindrome. Plenty of them listed here

This question is not about "how" but rather about performance.

I was assuing that is_palindrome should be twice faster than is_palindrome0 because it does len/2 iterations in the worst case.

However, in reality, is_palindrome takes more than 30 seconds to check all the strings while is_palindrome0 gets the job done in less than half of a second!

Test-case

def is_palindrome(s):
    for i in range(len(s) // 2):
        if s[i] != s[len(s)-i-1]:
            return 0
    return 1

def is_palindrome0(s):
    if s == s[::-1]:
        return 1
    else:
        return 0

N = 500
L = 99999

sss = '101' * L

import time

start = time.time()
print(sum([1 for i in range(N) if is_palindrome0(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')

start = time.time()
print(sum([1 for i in range(N) if is_palindrome(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')

Output

Any ideas why string slicing is so crazy fast? How to debug further?

Apologies if I missed answered question with in-depth performance comparison.

UPDATE. Taking into account Frank's comment.

def is_palindrome(s):
    l = len(s)
    for i in range(l // 2):
        if s[i] != s[l-i-1]:
            return 0
    return 1

def is_palindrome0(s):
    if s == s[::-1]:
        return 1
    else:
        return 0

N = 500
L = 99999

sss = '101' * L

import time

start = time.time()
print(sum([1 for i in range(N) if is_palindrome0(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')

start = time.time()
print(sum([1 for i in range(N) if is_palindrome(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')

A bit faster but still around 50x times slower.

It's somewhat a problem of scripting languages where library functions are optimized, the result could look completely different for a compiled language. — maraca
– maraca, Commented May 3 at 1:18
Try again, but put len(s) into a variable rather than getting its value everytime through the loop. You'll get some speed up but I don't know how much. — Frank Yellin
– Frank Yellin, Commented May 3 at 1:28
@maraca this makes sense but 50x times faster still looks too good. — Slimboy Fat
– Slimboy Fat, Commented May 3 at 1:34
you could use True/False instead of 1/0 and then you can reduce code in is_palindrome0 to one line return s == s[::-1] — furas
– furas, Commented May 3 at 1:35

Sahan Randika · Accepted Answer · 2025-05-03 01:41:23Z

is_palindrome0 (the fast one)

s[::-1] uses C-level optimizations under the hood (it's implemented in highly efficient C code in CPython). String comparisons (==) are also optimized for short-circuiting; they stop early if a mismatch is found. The entire operation is happening in compiled code with no explicit Python loops.

is_palindrome (the slow one):

This is pure Python, interpreted line by line. Each index access like s[i] and s[len(s) - i - 1] is an individual bytecode operation. Python for loops and indexing are orders of magnitude slower than equivalent operations in C.

The main performance killer here is actually in the line is_palindrome(sss+sss[i:]). For each iteration, in ur code:

U create a new string via concatenation (sss+sss[i:])
This new string is ~200,000 characters long
Then ur function iterates through half of it

Kelly Bundy · Accepted Answer · 2025-05-03 15:14:34Z

4

First of all, not really what you're asking for, but typically Python function are supposed to return True and False (which are automatically turned into 1 and 0 if used in arithmetic). Your code would look more Pythonic as:

def is_palindrome(s):
    length = len(s)
    return all(s[i] == s[length - i - 1] for i in range(length // 2))

def is_palindrome0(s):
    return s == s[::-1]

As to the actual cause of the slowdown, Python is an interpreted language. The first piece of code is nothing but the interpreter running a loop. For length // 2 times, you have to access two list element (which involves type checking, bounds checking) and compare them. For the second code, you call an internal that reverses a string and another internal that compares two strings. It's all done below.

This is just to say that time isn't necessary intuitive when you're dealing with interpreted languages. It's not the string slicing is fast, but that it's a lot faster than that many loops (or even half that many loops) through in the interpreter.

edited May 3 at 15:14

Kelly Bundy

28k7 gold badges34 silver badges76 bronze badges

answered May 3 at 1:36

Frank Yellin

11.6k1 gold badge15 silver badges27 bronze badges

4 Comments

Slimboy Fat May 3 at 1:41

Frank, can you recommend any profilers to dive deeper and check where the time is spent on a lower level?

Kelly Bundy May 3 at 15:09

I suggest s[i] == s[~i]. And if you're trying to be fast, as your variable length suggests, then using all like that is counterproductive.

Frank Yellin May 3 at 17:44

You're right that s[~i] is a bit faster. I should have mentioned that. It bothers me a little bit that writing the code the "Pythonic" way with all is a tad bit slower. Didn't 3.12 or 3.13 inline comprehensions?

Kelly Bundy May 3 at 18:24

I think they only inlined comprehensions, not generator expressions. And I think that the inlining only saves a little constant time per comprehension. That's not what I meant. I meant your extra time per element, since you're passing your bools from the generator iterator to all for evaluation. See this.

Collectives™ on Stack Overflow

Palindromes and string slicing. Performance

2 Answers 2

Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related