21
\$\begingroup\$

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?

\$\endgroup\$
  • 11
    \$\begingroup\$ C is not "supposed" to be quick, C does not add too much extra abstraction to your compiled code, so it allows you to write code that can be quick. Writing code in C does not make it "quick" by some magic trick. \$\endgroup\$ – Tommy Andersen Dec 1 '15 at 7:43
  • 4
    \$\begingroup\$ @TommyA I actually disagree with that claim. C keeps things minimal and doesn't add a lot of overhead that other languages do add, contributing to its speed. You'll find on average that most programs written in C will beat programs written in "higher-level" languages. \$\endgroup\$ – syb0rg Dec 1 '15 at 16:03
  • \$\begingroup\$ @syb0rg: I would argue that they faster because they leave out the needed code to make them correct and safe. Its easy to make code fast if you leave out all the checks to make sure it worked (and your tests always work). \$\endgroup\$ – Martin York Dec 1 '15 at 16:33
  • \$\begingroup\$ Are you looking for performance improvements too or just a code review? \$\endgroup\$ – edmz Dec 1 '15 at 18:48
  • 2
    \$\begingroup\$ Just so it's said...unless something has changed recently, I'm pretty sure a compiler is technically allowed to optimize out your loop entirely and/or move it out from between the clock() calls, since the loop has no real effect. (As far as C is concerned, execution time is not observable behavior.) \$\endgroup\$ – cHao Dec 1 '15 at 23:28

10 Answers 10

25
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ For many compilers and target platforms, the use of pointers is faster than using array indices. While it may be useful for a C beginner to use array indexing instead, it may come with a performance penalty, which seems counter to the intent with this question. \$\endgroup\$ – Edward Dec 1 '15 at 3:06
  • \$\begingroup\$ @Edward Very much agreed, I was noting that the question was tagged beginner and made the suggestion that he could transition to that. I'll make an edit to clarify. \$\endgroup\$ – syb0rg Dec 1 '15 at 3:07
  • \$\begingroup\$ If text is a const pointer, doesn't that mean it can't be incremented? \$\endgroup\$ – Sam McCreery Dec 1 '15 at 9:10
  • 1
    \$\begingroup\$ @JPhi1618 Assuming your compiler understands what that means, #pragma once is preferred. However, it isn't part of the standard and therefore not guaranteed to be supported by all compilers, hence my recommendation for include guards. \$\endgroup\$ – syb0rg Dec 1 '15 at 14:18
  • 2
    \$\begingroup\$ @faraza The main difference between the for's and the while's is a matter of pragmatics: we usually use for when there is a known number of iterations, and use while constructs when the number of iterations in not known in advance. \$\endgroup\$ – syb0rg Dec 24 '15 at 5:23
20
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ In performance point of view, your solution is taking more time. OP's solution takes 0.017 in my machine. While your solution takes 0.026 \$\endgroup\$ – niyasc Dec 1 '15 at 9:36
  • 4
    \$\begingroup\$ In my view, going from pointers to indices is actually less idiomatic C, and relies more on the compiler optimisations to keep performance. \$\endgroup\$ – Reinstate Monica Dec 1 '15 at 12:13
  • 1
    \$\begingroup\$ @Angew I've learned a long time ago that readability/understandability beats performance every time. In my head, I had to read over the OP's loop many times before I could argue to myself that it was correct. Maybe it had to do with the odd positions of the ++ and -- rather than the pointers themselves, I don't know. All I know is that I could visualize the indexed version much easier than the pointer version. \$\endgroup\$ – JS1 Dec 1 '15 at 18:09
  • \$\begingroup\$ @niyasc With what compiler and optimization level? On my compiler it was the same. (gcc with and without optimizations) \$\endgroup\$ – JS1 Dec 1 '15 at 18:16
  • 2
    \$\begingroup\$ @Angew And I don't mean to say that bubblesort is better than quicksort. Just that for the same algorithm, writing it in a clearer way is better, because a lot of bugs can arise from writing unclear/tricky code, and bugs are a lot worse than small performance degradations. \$\endgroup\$ – JS1 Dec 1 '15 at 18:26
13
\$\begingroup\$

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 ü.

\$\endgroup\$
  • 1
    \$\begingroup\$ Handling UTF-8 strings correctly is actually significantly harder, because iterating backward through the characters in a string is nontrivial in UTF-8 (requires a lookahead). I'd hesitate to even call it the same problem. \$\endgroup\$ – Mario Carneiro Dec 1 '15 at 14:37
  • 2
    \$\begingroup\$ Yes, this program doesn't handle UTF-8 strings. But for a beginner programmer, I wouldn't expect it as it is much more elaborate to implement. Still, a good note to make; +1. \$\endgroup\$ – syb0rg Dec 1 '15 at 16:11
  • \$\begingroup\$ If you speak about unicode and whole characters, remember that a single codepoint can be more or less than one whole character! \$\endgroup\$ – Deduplicator Dec 2 '15 at 14:33
10
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Quite promptly after, I wrote an alternative palindrome_l that takes length as an argument. Well-written answer. \$\endgroup\$ – Sam McCreery Dec 2 '15 at 0:47
4
\$\begingroup\$

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");
    }
}
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ I would avoid the use of "metal" keywords like register. These days the optimizer can take care of this for you, as you suggested. They are meant as a suggestion to the compiler, but they're more likely to be misleading to the developer. Nice analysis, though! \$\endgroup\$ – phord Dec 2 '15 at 13:54
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Good job on your first answer. \$\endgroup\$ – SirPython Dec 1 '15 at 23:11
  • \$\begingroup\$ Good point about the stack overhead. But replacing text with a global in the original code runs even faster on my test. \$\endgroup\$ – phord Dec 2 '15 at 14:03
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I did mention that, but my recommendation was to remove it overall. I also don't think adding another variable is necessary, but it does add a tiny bit of readability I suppose. \$\endgroup\$ – syb0rg Dec 1 '15 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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