Palindromes in C

Question

The function tests whether or not the provided string is a palindrome, and the main function just times how quick it is (after all, C's supposed to be quick, right?).

header.h

bool palindrome(char *text);

main.c

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>
#include "header.h"

int main() {
    clock_t start;
    start = clock();

    int j;
    for(j = 0; j < 1000000; j++) {
        palindrome("racecar");
    }

    printf("%.10f", (double) (clock() - start) / CLOCKS_PER_SEC);
    return 0;
}

bool palindrome(char *text) {
    char *right = text + strlen(text);
    while(text < --right) {
        if(*text++ != *right) {
            return false;
        }
    }
    return true;
}

Output is about 0.016.

Is this as fast as it gets?

Answer 1

A few notes:

• Put some include guards in your header.

• Name your header something more unique and appropriate.

• Always declare what parameters your function takes in, even if nothing.

  int main(void)
  

  You might wonder why we have to do this. Imagine we have the function foo() declared as such:

  int foo()
  

  In C, this is known as an identifier list and means that it "can take any number of parameters of unknown types". We can actually pass values to the function even though we don't mean to or intend to. If the caller calls the function giving it some argument, the behavior is undefined. The stack could become corrupted for example, because the called function expects a different layout when it gains control.

  Using identifier lists in function parameters is deprecated. It is much better to do something like:

  int foo(void)
  

  In C, this is known as a parameter type list and defines that the function takes zero arguments (and also communicates that when reading it) - like with all cases where the function is declared using a parameter type list, which is called a prototype. If the caller calls the function and gives it some argument, that is an error and the compiler spits out an appropriate error.

  The second way of declaring a function has plenty of benefits. One of course is that amount and types of parameters are checked. Another difference is that because the compiler knows the parameter types, it can apply implicit conversions of the arguments to the type of the parameters. If no parameter type list is present, that can't be done, and arguments are converted to promoted types (that is called the default argument promotion). char will become int, for example, while float will become double.

• I'm not sure I'd have the timing implemented in as part of your code, instead I'd use the bash command time as such to time it (please note that this output has no relation to your program and it is just an example):

  $ time ./a.out
  real    0m0.007s
  user    0m0.004s
  sys     0m0.005s
  

• Notice that you can collapse your palindrome() function from the while() loop into a for loop:

  bool palindrome(char *text) 
  {
      for(char *right = text + strlen(text) - 1; text < right; text++, right--) 
      {
          if(*text != *right) 
          {
              return false;
          }
      }
      return true;
  }
  

  You could also transition from pointer usage to array usage as @JS1 has in his code example, something I would probably recommend as a beginner. Note that if you do transition to arrays, this may come with a small performance hit (depending on compiler optimizations).

• You don't need the return 0; at the end of main, per the C standard.

Answer 2

Simplification

I found that the multiple pointer solution you used was a bit hard to read and verify for correctness (although the function was correct). I would use array syntax and indices instead, like this:

bool palindrome(const char *text)
{
    for (int left=0, right=strlen(text)-1; left < right; left++, right--) {
        if (text[left] != text[right])
            return false;
    }
    return true;
}

const keyword

If you notice in my code above, I used const on the function argument. As a beginner C programmer, just be aware that const exists and means that the argument will not be modified.

For this particular function, there is no speed benefit to using const. In other functions, it may be possible for the compiler to improve optimizations based on its knowledge that a variable will not change value. I feel the largest benefit of const is to improve the understanding of your program by distinguishing which variables are mutable and which are immutable. In java, you have whole immutable types such as String. In C, you use const to denote an immutable variable instead.

Print a newline

Your output doesn't include a newline, and when I ran your program it messed up my shell prompt.

Answer 3

Be aware that your palindrome function only works on strings where the characters are encoded as 1 byte per character. If you receive a multibyte encoded string in an encoding where characters are not always the same width, this method will not work.

e.g. If you had a UTF-32 string and some type utf32_char* that worked on whole characters, your same method would work as your two cursors traverse the string character-by-character.

However, a UTF-8 string being iterated across by two char*s would result in you examining a multi-byte codepoint in mid-character.

The nonsense word 'düd' appears to be a palindrome, but its UTF-8 encoding is

0x64 0xC3 0xBC 0x64

Where the 0xC3 0xBC is the UTF-8 sequence for the single code point ü.

Answer 4

Here are some observations and suggestions that may help you improve your code. In all, it's not bad at all for a first effort.

Eliminate the header

For a small program like this, it can all easily be in a single file. Unlike Java, C does not force you into proliferating bunches of files for every program. The declaration can either be in main.c or even simpler, just place the definition for palindrome above that for main and you won't need any forward declaration.

Use const where practical

The argument to palidrome is a pointer to text which is not altered within the function. To show that to any calling program, the declaration should instead be like this:

bool palindrome(const char *text) 

Think of the user

If this code is ever used elsewhere, you will want to both reintroduce a header file (but give it a decent name!) and also document how the code will handle certain kinds of input. Right now, it will crash if handed a NULL pointer.

Omit return 0

Since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.

Answer 5

palindrome is not a good name. It does not tell the user what it does. I suggest simply isPalindrome or, if you prefer, is_palindrome.

Answer 6

Regarding the performance of your loop:

Note that you're actually scanning the string twice (once for strlen). If you can avoid that, or explicitly scan it yourself, you may be able to eke out a bit more performance. For example, an API change that accepts the length in the function makes it the caller's responsibility: they may use strlen (which is no net loss) but if they already have the strlen you'll see your loop is a lot faster - especially if you pass it larger palindromes.

Nice catch, by the way, in passing the worst-case example to it. If you passed something like 'alphabet', it would bail out on the first character.

For performance, pointers are native to C while arrays can sometimes be optimized to the same level as C - depends on your compiler and optimizer. You'll probably see unexpectedly different results using the Visual Studio C compiler and gcc.

With respect to comparisons against other languages, one of the things to note is that several languages do a lot of stuff explicitly to make strings more efficient -- masking out characters can be relatively expensive (compared to comparisons of the word-size for the chip). There are languages that do more than C to handle strings implicitly, and they might actually outperform C on this particular test.

Your actual question seemed to be whether the performance can be improved; for me, that would take some experimentation. So I don't have a short answer for that part.

Answer 7

I don't mind the ++ and -- in the loop in palindrome, but I'd find it slightly more readable to move those operations on the same line:

bool palindrome(char *text) {
    char *right = text + strlen(text) - 1;
    while (text < right) {
        if (*text++ != *right--) {
            return false;
        }
    }
    return true;
}

In this version it's easier to see that the pointers are moved in sync.

Another thing that puts me off is that the main method just runs palindrome in a loop for the same input string. It would be more interesting if:

• It verified if the result is correct
• It used multiple palindrome and non-palindrome examples
• It used longer examples, for example itusedlongerexamplesforexampleelpmaxerofselpmaxeregnoldesuti

Alternatively, it would be user-friendly if I could run the method against command line arguments, for example:

int main(int argc, char ** argv) {
    int j;
    for (j = 1; j < argc; j++) {
        printf("%s -> %s\n", argv[j], palindrome(argv[j]) ? "yes" : "no");
    }
}

Answer 8

You asked whether it can go faster. Interesting question. Sometimes you have to play around with it, and the obvious tweaks are not always the best ones.

The first thing I tested was compiler optimization. The difference between "gcc" and "gcc -O3" was huge:

A billion iterations:

• Short string (3 chars), yours: 5.45 sec
• Short string (3 chars), mine: 2.77 sec
• Medium string (racecar), yours: 9.45 sec
• Medium string (racecar), mine: 4.30 sec
• Long string (52 chars), yours: 66.94 sec
• Long string (52 chars), mine: 18.14 sec

Optimized with gcc -O3:

• Short string (3 chars), yours: 2.47 sec
• Short string (3 chars), mine: 0.000001 sec
• Medium string (racecar), yours: 3.04 sec
• Medium string (racecar), mine: 2.42 sec
• Long string (52 chars), yours: 16.28 sec
• Long string (52 chars), mine: 12.45 sec

You can see the optimizer drastically narrowed the gap! In general, if you write clean code and let the compiler do its work, you'll get pretty good numbers without the need to spend a lot of effort optimizing. Still, some optimization is possible.

I tested with a short string to emphasize function call overhead and algorithm setup; a medium string for the typical case; and a very long string (the alphabet forward and backward) to test the tight loop within the function.

Here is my tweaked version of palindrome:

bool palindrome(register char *text, int len) {
    register char *right = text + len - 1;
    while (text < right && *text == *right) {
        text++;
        right--;
    }
    return (text >= right);
}

As others have suggested, lifting the strlen out of the loop and just passing in the length yielded about a 15% speedup for me.

The register keyword tells the compiler to use a CPU register if possible instead of a memory variable. It roughly doubled the speed in the un-optimized case, but had no effect with optimization, probably because the compiler is already doing that anyway. Register will only help if you have very few variables (in this case two).

On the surface it looks equivalent: the same number of tests, the same number of variables. But it runs significantly faster.

I played with a lot of variations, but the goal was to eliminate as many tests as possible. Most of my "clever innovations" proved to slow it down, but one yielded surprising results: I found that the compare and increment construction *text++ == *right-- ran significantly slower than separating the increment and placing it in the loop body. I suspect this is because it gave the compiler more flexibility to optimize things. This seems to be the largest source of improvement outside of the register keyword, at least for very long palindromes. Short strings saw very little improvement. Again, write clear code and let the compiler do the work. But definitely experiment!

I am not sure why the short (3 char) string test takes almost no time with my version. Perhaps the optimizer is clever enough to pre-compute everything and optimize the entire test loop away. That is always a problem in this sort of simple loop test: you may not be testing what you think you are testing, and the compiler may toss large chunks of your code. It can be tricky to force it to do unnecessary work for the sake of generating a benchmark.

It would be fun to try this on a really long palindrome!

Answer 9

Disclaimer: this isn't a code review. In fact, this is worse than what the OP wrote. However, it is faster per the OP's request.

Write a macro

I wrote a macro version of this (see below). The ({...}) is a GCC extension called a statement expression, but if you're not using GCC you can modify the variable ret and access it afterwards.

Usually macros are faster because they don't need a new stack frame, however I think GCC might still make a stack frame for statement expressions (maybe someone else can weigh in here). Also, the sizeof will get evaluated at compile time which is one less thing for the program to do at runtime.

Output from my code:

0.0900000000
0.0800000000
0.1000000000
0.0900000000
0.0800000000
0.1000000000

Output from your code

0.1600000000
0.1500000000
0.1500000000
0.1500000000
0.1700000000
0.1900000000

Here is the version of your code I ran:

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

bool pal(char * text);

int main() {
    clock_t start, stop;
    start = clock();
    for(int j = 0; j < 10000000; j++) {
        pal("racecar");
    }
    stop = clock();
    printf("%.10f\n", (double) (stop - start) / CLOCKS_PER_SEC);
    return 0;
}

bool pal(char *text) {
    char *right = text + strlen(text);
    while(text < --right) {
        if(*text++ != *right) {
            return false;
        }
    }
    return true;
}

And here is what I wrote:

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

#define pal(STRING)                         \
  ({bool ret = true;                        \
  char * left = STRING;                     \
  char * right = left + sizeof(STRING) - 2; \
  while(right > left){                      \
    if(*right != *left){                    \
      ret = false;                          \
      break;                                \
    }                                       \
    --right;                                \
    ++left;                                 \
  } ret;})

int main() {
    clock_t start, stop;
    start = clock();
    for(int j = 0; j < 10000000; j++) {
        pal("racecar");
    }
    stop = clock();
    printf("%.10f\n", (double) (stop - start) / CLOCKS_PER_SEC);
    return 0;
}

Answer 10

Of the many good suggestions here, none address the fact that you are benchmarking additional code in addition to the palindrome loop. Add a stop variable, and make sure that your start and stop variables are directly enveloping the loop:

int main() {
    clock_t start;
    clock_t stop;
    int j;

    start = clock();

    for(j = 0; j < 1000000; j++) {
        palindrome("racecar");
    }

    stop = clock();

    printf("%.10f", (double) (stop - start) / CLOCKS_PER_SEC);
    return 0;
}