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 char
s) and doing another std::mismatch
over the remaining char
s.
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
.
long
is not necessarily the same size of a pointer. There's a standard type to store pointer differences:ptrdiff_t
. \$\endgroup\$