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\$
8
  • 10
    \$\begingroup\$ C++? This looks more like C. \$\endgroup\$
    – Jamal
    Sep 12, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 10:58

2 Answers 2

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\$
7
  • 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, 2015 at 22:30
  • \$\begingroup\$ @Pep updated my answer. Can you show us your benchmark in order to analyse your 10x claim? \$\endgroup\$ Sep 13, 2015 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, 2015 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, 2015 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\$ Sep 13, 2015 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\$
6
  • \$\begingroup\$ This depends on platform specific details, e.g. whether char is signed or unsigned \$\endgroup\$ Sep 13, 2015 at 11:24
  • \$\begingroup\$ Endianness is another issue you have to deal with \$\endgroup\$ Sep 13, 2015 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, 2015 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, 2015 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, 2015 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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