Fastest C++ code to get common prefix length

Question

In a C++ program, I have the following function to find the length of the longest common prefix between to char arrays a and b. String b is guaranteed to be shorter than string a.

Is there a faster char array comparison code (for example, with some library function)? I wish to optimize this code for speed.

long len_common_prefix(char a[], char b[]) {  
    char* p = a;
    char* q = b;
    while ((*p == *q) && (*q)) {
        p++;
        q++;
    };
    return p-a;
}

I've found the following code to be about 10 times faster that the original one I gave. Is there an even faster alternative?

long long int len_common_prefix(char a[], char b[]) {  
    long long int* p = (long long int*)a;
    long long int* q = (long long int*)b;
    int ratio = sizeof(long long int) / sizeof(char);
    while (*p == *q) {
        p++;
        q++;
    }
    long long int long_long_diff = p-(long long int*)a;
    char* p2 = (char*)p;
    char* q2 = (char*)q;
    while (*p2 == *q2) {
        p2++;
        q2++;
    }
    return long_long_diff * ratio + (p2 - (char*)p);
}

Answer 1

The C++ way would be to call std::mismatch and be done with it

#include <algorithm>    // mismatch
#include <cassert>      // assert
#include <cstddef>      // ptrdiff_t
#include <cstring>      // strlen
#include <iostream>     // cout
#include <iterator>     // distance

std::ptrdiff_t len_common_prefix_base(char const a[], char const b[])
{
    assert(std::strlen(b) <= std::strlen(a));
    return std::distance(b, std::mismatch(b, b + std::strlen(b), a).first);
}

If you absolutely have to improve on the base line performance, you can rewrite your second solution as two successive calls to std::mismatch. First, by reinterpreting the char* as long long int* and calling std::mismatch at the block level. Secondly, after finding the first char in the first mismatching block (which could be the final partial block containing the remaining chars) and doing another std::mismatch over the remaining chars.

std::ptrdiff_t len_common_prefix_10x(char const a[], char const b[]) 
{
    assert(std::strlen(b) <= std::strlen(a));
    using block_type = long long int;

    auto p = reinterpret_cast<block_type const*>(a);
    auto q = reinterpret_cast<block_type const*>(b);

    auto const n = std::strlen(b);
    auto const num_blocks = n / sizeof(block_type);

    auto block_mismatch = std::mismatch(q, q + num_blocks, p);
    auto b2 = reinterpret_cast<char const*>(block_mismatch.first);
    auto a2 = reinterpret_cast<char const*>(block_mismatch.second);

    return std::distance(b, std::mismatch(b2, b + n, a2).first);
}

int main()
{
    char const a[] = "hello world is a trivial exercise";
    char const b[] = "hello world is a trivial example";

    std::cout << len_common_prefix_base(a, b) << '\n';
    std::cout << len_common_prefix_10x(a, b) << '\n';
}

Live Example that prints 27 (the same as your two implementations).

What you are doing with your pointer cast to long int is very fragile, at the very least it's implementation-defined at possibly undefined behavior (for which no warning is required, and that includes the case that your code runs 10x faster on your system but crashes after you turn on compiler optimizations or port it to another system).

Some issues that you have to be very careful about when doing pointer casting:

• alignment, if your char[] is part of a struct, you need to be sure it is aligned at 8-byte boundaries to avoid unaligned memory access from your long long int pointers.
• endianness, you need to make sure that the bytes within a long long int are in the same order as the char[] array

I'd like to see a reproducible benchmark before being able to comment on whether a 10x improvement is really possible on std::mismatch.

Answer 2

I understand that the reason for your post is to find a method that will be faster than the one you already have.

However, the posted code has the potential to access memory that is beyond the valid limits.

For the sake of making a point, let's say that on your platform, sizeof(long long int) is 8. Your input strings are "philosophy" and "phil".

Given that, evaluating *q will end up accessing memory past the terminating null character of "phil". In theory, that is cause for undefined behavior.

Here's my updated version of your function to make sure that you always access memory within the valid limits.

long long int len_common_prefix(char a[], char b[]) {  

   // Take advantage of the guarantee that b is shorter than a
   char* cp = b;
   while ( *cp ) ++cp;

   long long int* p = (long long int*)a;
   long long int* q = (long long int*)b;
   int ratio = sizeof(long long int) / sizeof(char);
   size_t max = (cp - b)/ratio;
   long long int* stop = q+max;

    while ((*p == *q) && (q != stop) ) {
        p++;
        q++;
    }

    long_long_diff = p-(long long int*)a;
    char* p2 = (char*)p;
    char* q2 = (char*)q;

    if ( q == stop )
    {
       // Make sure not to go beyond the valid limit
       while ((*p2 == *q2) && *q2 ) {
          p2++;
          q2++;
       }
    }
    else
    {
       // There is no need to worry about valid limit here.
       // The comparison will fail before we can go beyond the valid limit.
       while (*p2 == *q2) {
          p2++;
          q2++;
       }
    }

    return long_long_diff * ratio + (p2 - (char*)p);
}