Can someone explain to me the performance difference of using pointers vs indices for accessing an array?

Question

So I am learning C and to get practice I do some "LeetCode" challenges. For a palindrome checker I have tried two approaches, one using indices and one using pointers.

• Where does the large performance difference come from?

And as a follow up question:

• What method is usually preferred and for what reasons?

For reference here are the code blocks.

Pointers:

bool isPalindrome(char *s) {

    size_t length = strlen(s);
    char *left = s;
    char *right = s + length - 1;

    while (left < right) {
        
        while (left < right && !isalnum(*left))
            ++left;
        
        if (left == right)
            return true;

        while (right > left && !isalnum(*right))
            --right;

        if (right == left)
            return true;
        
        if (tolower(*left) != tolower(*right))
            return false;

        ++left;
        --right;
    }

    return true;
}

Indices:

bool isPalindrome(char *s) {

    size_t length = strlen(s);
    size_t left = 0;
    size_t right = length - 1;

    while (left < right) {
        
        while (left < right && !isalnum(s[left]))
            ++left;
        
        if (s[left] == '\0')
            return true;

        while (right > left && !isalnum(s[right]))
            --right;

        if (right == 0)
            return true;
        
        if (tolower(s[left]) != tolower(s[right]))
            return false;

        ++left;
        --right;
    }

    return true;
}

Answer 1

Where does the large performance difference come from?

There are many potential reasons for a performance difference, but it would be helpful to understand how you compile the code, how you measure performance and with what input. Here are a few hints:

• the 2 functions posted do not implement the same semantics: in the pointer version, you exit the loop if (left == right) whereas the equivalent test in the index version is if (s[left] == '\0') which is not true in most cases where if (left == right) is true. If the functions behave differently, no surprise they perform differently.

• did you enable optimisations? without optimisations, s[left] may generate more code than *left, but with optimisations enabled, most compilers will generate code with similar performance, either converting the index approach to a pointer approach, or using addressing modes that use multiple registers, with or without scaling, without a penalty.

What method is usually preferred and for what reasons?

Both methods are equivalent if implemented properly, and compile to equivalent performance with modern compilers.

Here are reasons to use pointers:

• Using pointers may be more appropriate if local rules encourage it
• Pointers are quite specific to C (and C++), it makes the code more familiar to die hard C programmers in their 60s

Reasons to use index variables with type size_t:

• using indices is more general, works in most languages and probably more idiomatic in C++ language (for .
• code is more readable for programmers from various backgrounds
• code is easier to port to other languages.

Before you focus on performance, focus on correctness!

• both functions have undefined behavior on the empty string, a trivial palindrome.
• you have multiple redundant tests.
• the macros isalnum() and tolower() from <ctype.h> are only defined for a restricted range of int values: all values of type unsigned char and the special negative value EOF expands to. Passing negative char values has undefined behavior on platforms where type char is signed by default. You should use a cast to (unsigned char).

Here are modified versions:

bool isPalindrome_idx(const char *s) {
    size_t len = strlen(s);
    if (len > 1) {
        size_t left = 0;
        size_t right = len - 1;
        while (left < right) {
            while (!isalnum((unsigned char)s[left])) {
                if (++left >= right)
                    return true;
            }
            while (!isalnum((unsigned char)s[right])) {
                if (left >= --right)
                    return true;
            }
            if (tolower((unsigned char)s[left]) != tolower((unsigned char)s[right])) {
                return false;
            } else {
                left++;
                right--;
            }
        }
    }
    return true;
}

bool isPalindrome_ptr(const char *s) {
    size_t len = strlen(s);
    if (len > 1) {
        const char *left = s;
        const char *right = s + len - 1;
        while (left < right) {
            while (!isalnum((unsigned char)*left)) {
                if (++left >= right)
                    return true;
            }
            while (!isalnum((unsigned char)*right)) {
                if (left >= --right)
                    return true;
            }
            if (tolower((unsigned char)*left) != tolower((unsigned char)*right)) {
                return false;
            } else {
                left++;
                right--;
            }
        }
    }
    return true;
}

Answer 2

Change if (right == 0) in the indexed example to if (right == left), to make them the same. Then their performance should be very similar.