9
\$\begingroup\$

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);
}
\$\endgroup\$
  • 10
    \$\begingroup\$ C++? This looks more like C. \$\endgroup\$ – Jamal Sep 12 '15 at 1:30
  • \$\begingroup\$ You might get a truncation warning on a 64bit platform. long is not necessarily the same size of a pointer. There's a standard type to store pointer differences: ptrdiff_t. \$\endgroup\$ – glampert Sep 12 '15 at 2:17
  • \$\begingroup\$ @jamal Added C tag to the question. Target environment is C++ so I wanted to have available the option to use C++ resource such as library funciotns if it improved performance. \$\endgroup\$ – Pep Sep 12 '15 at 10:34
  • \$\begingroup\$ @glampert In the 10x faster version just posted I changed the types to long long int to support larger pointer differences, thanks for the remark. \$\endgroup\$ – Pep Sep 12 '15 at 10:36
  • \$\begingroup\$ If you don't need to support older CPUs take a look at how to get your compiler to output SSE2/SSE3 or even AVX instructions \$\endgroup\$ – user45891 Sep 12 '15 at 10:58
7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ The issue with this solution is that, although it looks a lot more C++y, for my data set it seems to run about 10 times slower that the C solution in my update than traverses the char arrays at "long long int" speed. I admit thought that I do not follow you comment about <algorithm> to improve this further because I'm a noob in modern C++ (I've not coded in C++ since the 90's). Also string "b" is a suffix of "a" (that's why we know it is shorter) so with a char[] approach, it gets initialized with a mere pointer assignment b = (a + suffix_dist) \$\endgroup\$ – Pep Sep 12 '15 at 22:30
  • \$\begingroup\$ @Pep updated my answer. Can you show us your benchmark in order to analyse your 10x claim? \$\endgroup\$ – TemplateRex Sep 13 '15 at 13:22
  • \$\begingroup\$ @TemplateTex The question origined when solving a HR challenge: hackerrank.com/challenges/string-similarity (I am using HR to practice/recall C/C++ skills). The code that can be used for benchmark is this (changing the called len_common_preffix in each submission): pastebin.com/QDnYYqbQ For example: Testcase #5, runs in 0.05 seconds with long long int len_common_preffix, runs in 1.06 seconds witn your len_common_prefix_10x and runs in 1.58 seconds with your len_common_preffix_base. Other comparable (not timed out) testcases are (0.00/1.61/1.16) or (0.02/1.69/1.86). \$\endgroup\$ – Pep Sep 13 '15 at 15:56
  • \$\begingroup\$ Just noticed that your strlens assertions and a calculation had a big impact in performance because the strings a very long. Since that len(a) > len(b) is an invariant, and len(b) is known at the upper layer, I removed the assertions and passed len(b) as a parameter so that the funcitions are comparable (pastebin.com/msaPtA0E) and ran the HR testcases again. The outcome was that the C algorithm was about twice faster than your C++ len_common_prefix_10x and your len_common_prefix_10x was some 5/6 times faster than your C++ len_common_prefix_base. \$\endgroup\$ – Pep Sep 13 '15 at 20:58
  • \$\begingroup\$ @Pep assert() is compiled away in Release mode, so are you sure that your benchmark code is representative and actually compiled in Release mode? E.g. in Debug mode, the C++ Standard Library might also do bound-checking and other overhead. \$\endgroup\$ – TemplateRex Sep 13 '15 at 21:31
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ This depends on platform specific details, e.g. whether char is signed or unsigned \$\endgroup\$ – TemplateRex Sep 13 '15 at 11:24
  • \$\begingroup\$ Endianness is another issue you have to deal with \$\endgroup\$ – TemplateRex Sep 13 '15 at 11:43
  • \$\begingroup\$ Thank you for the remarks. The "if ( q == stop )" s is not required because len(b) < len(a) so it is guaranteed than when *q ==0 then *p !=0 for sure, so the while loop will always exit with (*p == *q) even when *q==0. \$\endgroup\$ – Pep Sep 13 '15 at 12:13
  • \$\begingroup\$ @Pep, the only exception to that is when the two strings are equal. In that case, you need that additional check. \$\endgroup\$ – R Sahu Sep 13 '15 at 23:36
  • \$\begingroup\$ @RSahu They cannot be equal, because one is known the be strictly longer than the other by at least one char. \$\endgroup\$ – Pep Sep 14 '15 at 0:18

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.