Optimizing performance of string comparison function (particularly interested in redundancies)

Question

I've been working on the below function which compares two input strings and returns a similarity score. I've managed to tweak it down to a level of performance I'm pretty happy with, but I'm relatively new to C++ and wondering how I might push it further! In particular if there's any way to cut down on redundancies.

My code works in the following manner:

1. Decomposes each string into a vector of bigrams (e.g. "John Smith" becomes Jo oh hn n S Sm mi it th) and creates a union of elements from both.
2. For each element in the union, count the frequency at which it occurs in each of the constituent vectors and store the frequency values in a new pair of vectors.
3. Return the score as the dot product of both frequency vectors over the geometric mean of their inner products.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

double similarity(std::string string1, std::string string2) {
    std::vector<std::pair<char, char>> s1, s2, sunion;
    size_t l1 = string1.size() - 1;
    s1.reserve(l1);
    for (int i = 0; i < l1; i += 1){
        s1.push_back(std::pair<char, char>(string1.at(i), string1.at(i+1)));
    }
    size_t l2 = string2.size() - 1;
    sunion.reserve(l1+l2);
    sunion = s1;
    s2.reserve(l2);
    for (int i = 0; i < l2; i += 1){
        s2.push_back(std::pair<char, char>(string2.at(i), string2.at(i+1)));
        sunion.push_back(std::pair<char, char>(string2.at(i), string2.at(i+1)));
    }

    std::sort(sunion.begin(), sunion.end());
    sunion.erase(std::unique(sunion.begin(), sunion.end()), sunion.end());

    size_t lu = sunion.size();
    std::vector<int> f1, f2;
    f1.reserve(lu);
    f2.reserve(lu);
    for (int i = 0; i < lu; i += 1){
        std::pair<char, char> bi = sunion[i];
        f1.push_back(std::count(s1.begin(), s1.end(), bi));
        f2.push_back(std::count(s2.begin(), s2.end(), bi));
    }

    double jacc = std::inner_product(f1.begin(), f1.end(), f2.begin(), 0.0)
    / std::sqrt(std::inner_product(f1.begin(), f1.end(), f1.begin(), 0.0)
    * std::inner_product(f2.begin(), f2.end(), f2.begin(), 0.0));
    
    return jacc;
}

Answer 1

Most of the time is spent in std::count and the std::sort + std::unique, in that order.

This algorithm to compute a histogram (which is what the loop with std::counts in it is doing) is not efficient, it requires S passes over the vector of bigrams where S is the number of unique bigrams, but a histogram like that could be computed in one pass, and without requiring to compute the unique bigrams first. Switching to a different algorithm takes out both of the big ticket items together.

An alternative histogram algorithm that makes only one pass is, at a high level, "for each item, increment histogram[item]". The items here are bigrams, and they could come directly from the input string, saving on the cost of explicitly creating vectors of bigrams, which became a significant time waster when the histogram algorithm was changed.

The histograms could be std::array<uint32_t, 256 * 256> (which will cost a lot of unused size for typical string) or some kind of sparse map (eg unordered map) indexed by a pair if you prefer. For the array, a pair of chars needs to be turned into an index, which is no big deal but be aware that char is often signed and the index shouldn't be negative. They could be converted to unsigned char, or masked with & 0xFF. The array would contain many zeroes, which wouldn't be good to pass to the inner_product functions. That wouldn't be wrong, but it force those functions to waste time on multiplying lots of zeroes together. To avoid that, the same vectors f1 and f2 could be created. I changed them to std::vector<int64_t> because I had some overflow problems with the giant strings that I used for benchmarking.

For example:

std::array<uint32_t, 256 * 256> c1 = {};
std::array<uint32_t, 256 * 256> c2 = {};
for (size_t i = 0; i < l1; i++)
{
    c1[(string1[i] & 0xFF) + (string1[i + 1] & 0xFF) * 256]++;
}
for (size_t i = 0; i < l2; i++)
{
    c2[(string2[i] & 0xFF) + (string2[i + 1] & 0xFF) * 256]++;
}

std::vector<int64_t> f1, f2;
for (size_t i = 0; i < 256 * 256; i++)
{
    if (c1[i] | c2[i])
    {
        f1.push_back(c1[i]);
        f2.push_back(c2[i]);
    }
}

On my PC, with the big 100000000-character strings I generated, that took the time taken from about 17.5 second down to 0.15 seconds, a decent improvement. Of course, the improvement won't be so big in all cases, in fact for small strings this approach may be worse due to the need to iterate through 65536-element arrays.

Pushing even further

Computing histograms quickly is difficult, and what I just showed is just the most basic algorithm that isn't slow, it's not the state of the art of computing histograms. The focus is usually on counting bytes, so other results do not necessarily translate to this problem with pairs of characters, but this should still suffer from the issue that plagues the basic histogram algorithm: incrementing the same element of the histogram (which can happen by chance) in quick succession does not pipeline well (and may result in memory dependence mis-speculation and rollback) because the increments depend on each other. Powturbo Histogram uses some techniques to avoid that problem, as do unusual new techniques that abuse VGF2P8AFFINEQB. There is not a lot of information in that twitter post, but I invented a histogram calculation algorithm that uses VGF2P8AFFINEQB as well, and it wouldn't work in this case: it's good for 7-bit ASCII, still decent for bytes, but anything larger than that would be bad, a pair of chars is far out of reach. Some of the techniques used in Powturbo Histogram may be worth trying.