Leetcode 14. Longest Common Prefix beats only ~50% of C++ solutions

Question

The task is to find the longest common prefix. While I had no trouble to find the solution, I'm interested in the statistics of my code:

Runtime: 7 ms, faster than 56.36% of C++ online submissions for Longest Common Prefix.
Memory Usage: 9.3 MB, less than 54.46% of C++ online submissions for Longest Common Prefix.

Although these statistics are taken to be with a grain of salt:

08/06/2022 12:06 Accepted 8 ms 9.1 MB cpp
08/06/2022 12:06 Accepted 6 ms 9.3 MB cpp
08/06/2022 12:00 Accepted 7 ms 9.3 MB cpp

So appareantly my code can be optimized in 1 or 2 ways. How can I make it faster? And how can I make it more memory efficient? By what I see, I only allocate memory once, for the storage of the string I need to return. Granted, if the first string happens to be gargantually big and the other prefixes are small, this could be an issue and reserving only the size of the minimum length string would improve this. So maybe let's focus a bit more on the performance site.

Try it on godbolt!

#include <iostream>
#include <vector>

std::string f(std::vector<std::string>& strs){
    std::string common = "";
    common.reserve(strs[0].size());
    for( std::size_t i = 0; i < strs[0].size(); ++i ){        
        for( auto const& str : strs ){            
            if( str.size() < i || str[i] != strs[0][i] ){
                return common;
            }
        }
        common += strs[0][i];
    }
    return common;
}

int main(){
    std::vector<std::string> list = {"hh", "hhho", "hhh"};
    std::cout << f(list) << "\n";
}

Answer 1

Precalculate the size of the shortest string

In the inner loop you are checking str.size() < i. Consider that the longest common prefix cannot be longer than the shortest string. I would first try to calculate the size of the shortest string, as this avoids the size check in the inner loop of the actual algorithm:

std::string f(std::vector<std::string>& strs){
    std::size_t min_size = SIZE_MAX;

    for (auto& str: strs)
        min_size = std::min(min_size, str.size());

    for(std::size_t i = 0; i < min_size; ++i)
        for (auto& str: strs)       
            if(str[i] != strs[0][i])
                return str.substr(0, i);

    return strs[0];
}

Memory access pattern

The algorithm is quite simple, and I strongly suspect the bottleneck is how fast it can read the strings from memory. If you have a large number of strings which don't fit into the CPU cache, then the order in which you check things against each other might matter a lot. RAM access latency can be quite high, but this latency can be hidden by the CPU by looking at your memory access patterns, and prefetching memory based on that pattern. Contemporary CPUs can handle code reading and writing to a few areas in RAM simultaneously, but if for example you are comparing 100 strings, it will not be able to track that, and thus will either not prefetch (bad) or prefetch the wrong things (even worse).

So it might be interesting to check only two strings against each other at a time, as that is much more likely to keep the prefetcher happy:

std::string f(std::vector<std::string>& strs){
    std::size_t min_size = SIZE_MAX;

    for (auto& str: strs) {
        min_size = std::min(min_size, str.size());

        for (std::size_t i = 0; i < min_size; ++i)
            if(str[i] != strs[0][i]) {
                min_size = i;
                break;
            }
        }

        if (min_size == 0)
            break;
    }

    return strs[0].substr(0, min_size);
}

However, this strategy might work slower than your solution if everything already fit into the cache.

You could probably find an even better solution that does something in-between the two strategies: consider checking the first cache line worth of bytes from each string against each other, then the next cache line worth of bytes if necessary, and so on.

Avoid checking a given string against itself

Both in your code and in my code above, the inner loop will check all strings against the first string. But that includes checking the first string against itself, which is unnecessary.

Check multiple characters in one go

You are checking individual characters against each other, but on contemporary computers, the CPU typically has registers that are 64 bits wide, and can thus hold 8 characters. There are even vector registers that are larger; with AVX512 you can have 64 characters in one register! For long strings, this might allow you to speed up the algorithm substantially.

Say you compare 8 characters at a time, stored in uint64_ts. Then if two of those uint64_ts are equal, you know that all 8 characters are the same, and you can skip to the next set of 8 characters. But if they are not equal, you can still quickly find which of the 8 characters was the first that is not equal by XORing both uint64_ts together, and using std::countl_zero() (since C++20) or ffs() on the result.

Answer 2

Improve cache usage

I agree with G. Sliepen that changing the order of iterating over strings may improve execution time.

Consider the variant of the classic example as an illustration.

void incrementByRow(vector<vector<int>> &v) {   
  for (auto i = 0; i < v.size(); ++i) {
    for (auto j = 0; j < v[0].size(); ++j)
      ++v[i][j];        
  }
}

void incrementByColumn(vector<vector<int>> &v) {
  for (auto j = 0; j < v[0].size(); ++j) {
    for (auto i = 0; i < v.size(); ++i)
       ++v[i][j];
  }
}

On each iteration of the inner loop in incrementByColumn, we access a different vector which needs to be, probably partially, loaded to the data cache. When cache space is exhausted, an unused vector has to be popped for another to be loaded, merely to let us change a value of only one element. Execution time degrades significantly as matrix dimensions grow.

The worst case scenario, when almost all strings have long common prefix, clearly resembles the example. But to be precise, reliable benchmark results are needed.

On leetcode problems

Coding challenge solution may be a throw-away code, unless it is presented at interview where, normally, exact execution time does not matter. To make leetcode solutions faster, I use "dirty" hacks like reusing input data (when problem statement does not prohibit) and memory leaks.

string longestCommonPrefix(vector<string>& strs) {
    int len = strs[0].size();
    for (int i = 1; i < strs.size(); ++i) {
        len = min(len, (int)strs[i].size());

        for (int j = 0; j < len; ++j) {
            if (strs[0][j] != strs[i][j]) {
                len = j;
                break;
            }
        }

        if (len == 0)
            return {};
    }

    strs[0].resize(len);
    return move(strs[0]);
}

For example, instead of creating a new string, I reuse the input data, which theoretically should improve execution time. On the first run, I got Runtime: 0 ms, faster than 100.00% but the runtime varied up to Runtime: 12 ms, faster than 19.62% for consecutive submissions of the same solution. After solving more than 300 leetcode problems, I do not consider leetcode timers as a reliable source of efficiency estimates. I find them meaningful only when my solution is obviously slow, and the problem has large input size. This problem has small input size.

Since any dirty code goes, and timers float unpredictably, it is hard to reason about code performance and quality here, on stackexchange. For more solutions, I would refer to the problem discussion and check the code samples from the time distribution histogram at leetcode.