2
\$\begingroup\$

I am trying to check if a string is a palindrome in cython. Here is the code I am using:

cpdef bint check_palindrome(
    str word,
):
    cdef:
        int N = len(word)
        int i

    for i in range(N // 2 + 1):
        if word[i] != word[N-i-1]:
            return 0

    return 1

How can I make it more efficient? I suspect that the len() function is not cythonic, however I am more concerned about the check if word[i] != word[N-i-1] which gets repeated in a loop. How could it be improved? I would be checking a large number of very long (10000+ character-long) strings.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Seems pretty optimal to me unless you want to try to vectorize. What's the concern about the if word[i] != word[N-i-1] check specifically? \$\endgroup\$
    – ggorlen
    Commented Jun 7 at 19:03
  • \$\begingroup\$ When I run the script through cython -a <filename>.pyx, that line is bright yellow-colored, which indicates it might be more efficient if done using a C-based alternative. \$\endgroup\$
    – John
    Commented Jun 7 at 20:07
  • \$\begingroup\$ I don't know anything about cython, but if word[i] != word[N-i-1] looks about as fast as you can get in C (barring vectorization), just offsets into an array (string). \$\endgroup\$
    – ggorlen
    Commented Jun 7 at 20:21
  • 1
    \$\begingroup\$ This innocently-looking code hides a lot. Are your strings ASCII (or other single-byte) encoding, or do you need to support multi-bytes encoding (UTF-8, UTF-16, ...)? How is it called from python later? \$\endgroup\$
    – STerliakov
    Commented Jun 9 at 0:08
  • 1
    \$\begingroup\$ The strings are digits only, e.g. "12345" for False and "12321" for True. \$\endgroup\$
    – John
    Commented Jun 10 at 15:00

1 Answer 1

4
\$\begingroup\$

already fast

The word[i] != word[N - i - 1] test looks Just Fine, you won't go much faster than that in any language. (Though I do wish you would name it lowercase n.)

I assume the len(word) operation happens in \$O(1)\$ constant time.

Please ensure that word is a (readonly) byte array when it's passed in, so it is compact and we needn't worry about unicode details.

BLAS

You might take it out of the hands of cython, and let numpy worry about reversing bytes and worry about comparisons. If you want to take advantage of vectorized instructions, "make it numpy's problem!" is the lowest effort path to accomplishing that.

Notice that conversion to bytes, or conversion to a numpy array, will be a \$O(N)\$ linear operation. So the possible speedups are pretty meager. What could be winning is if you get to translate to a new representation once and then re-use that datastructure many times. Also, you might be using pyarrow's Parquet file format to map a file into memory. In that case it might happen that you never even fault the middle page, upon finding a mismatch in pages near the beginning.

alignment

The OP code is simple enough that it gives an -O3 C compiler an opportunity to use vector instructions for fetching and comparisons. We might see better code generated if the compiler can easily prove some convenient alignment. Rely on godbolt and your stopwatch to verify that any proposed edit actually does some good.

We might even wish to have a variable number of bytes in the middle, to ensure that the end has a nice alignment.

cache friendly

You didn't mention what sort of distribution your mismatches follow, nor whether you typically see a 1% or a 99% palindrome rate. In the 99% case, there's little to be done, since you necessarily have to examine each and every byte. But in the 1% case, we care about where we detect a mismatch.

If there's typically a mismatch near {front, back}, then OP code is already optimal. If for many of the False results we can find a mismatch near the middle, then focus on that. (Even if front vs middle is similar frequencies, still focus on middle.)

We can test from the middle outward just as easily as the current testing from the ends inward. But if the mismatch is very near the middle, then we can win after dragging one cache line in from L3 or main memory, instead of two.

Cache lines are smallish. Virtual memory pages are bigger than a kilobyte. As mentioned above, demand faulting from e.g. Parquet could let you declare "not a palindrome!" without even having the bulk of the string loaded into RAM.

N threads

Actually, in the 99% case you could burn more cores. Divide the string into sub-segments that are delegated to individual threads. We can do the OP comparison in each thread. Or we can choose to optimistically compute hash of input segment in just one direction, and do a quick comparison of segment hashes to verify that yes, it is a palindrome.

Given that you have a large number of input strings, so the metric of interest is throughput rather than latency, there's probably little reason to adopt such an approach. Better to parallelize across input strings, assigning each one to a particular thread.

input distribution

It might be the case that non-palindromes often start with particular prefixes. Compute hashes of such prefixes and store them in a dict, along with offset of probable mismatch. Use that as a "fast path" for quickly demonstrating that the input is definitely not a palindrome.

Or, almost the same thing, use a probabilistic datastructure like a Bloom filter to quickly identify such inputs.

\$\endgroup\$
1
  • \$\begingroup\$ In Python, how do I go about converting an int to a readonly byte array? Is there anything more efficient than x = 12321; list(str(x).encode("UTF-8"))? The second operation alone takes as much time as my test for palindromicity. \$\endgroup\$
    – John
    Commented Jun 19 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.