Find offset that minimizes squared difference between two vectors of different size

Question

I am working on a project where the hotspot is some code that is supposed to find an offset, such that the squared differences between a reference vector and a given vector becomes minimal. The core function is this:

#include <vector>
#include <map>
typedef std::vector<double> vect_d

double sqDiffSum(const vect_d& ref, const vect_d& x,int offset){
    size_t scale = ref.size() / x.size(); // ref.size() is always n*x.size()
    double sum = 0;
    int counter = 0;
    for (size_t i=0;i<x.size();i++){
        for (size_t j=0;j<scale;j++){
            int bin = i*scale + j - offset;
            if (bin >= 0 && bin < (int)ref.size()){
                double diff = ref[bin] - x[i];
                sum += diff * diff;
                counter++;
            }
        }
    }
    return sum / counter;
}

This is called from some minimization routine, that (for now) I dont want to change. It varies the offset to get the minimum sqDiffSum. I know that I could probably do the task faster by using a FFT, but for now I want to see how much I can get out of the current approach. I could already make it faster (roughly x2.5) by adding some memoization:

double callSqDiffSum(const vect_d& ref, const vect_d& x,int offset,bool firstCall){
    static std::map<int,double> memo;
    if (firstCall){ memo.clear(); }
    else {
        std::map<int,double>::iterator found = memo.find(offset);
        if (found != memo.end()){
            return found->second;
        }
    }    
    double result = sqDiffSum(ref,x,offset);
    memo[offset] = result;
    return result;
}

However, it is still too slow. There are several points that in principle I could optimize, but for each I have my doubts whether it will bring any benefit:

• The reference vector ref is actually always the same, thus I could avoid passing it around at all.

• The size of the vectors is always the same, so actually there is no need for std::vector, but if possible I would like to avoid c-style arrays and I dont expect too much improvement by not using vectors here.

• The innermost loop has some branching, that could be avoided

Is there anything that comes to your mind to make this more efficient? Is my assumption that the above points are not really worth to change wrong?

Please note that this is pre-C++11.

Answer 1

Without changing the algorithm, the only things I can see by having a look at the assembly of sqDiffSum:

• read x[i] only once in the outer loop (i.e const double x_i = x[i] and then use x_i instead). You'll get a small win by not having to fetch it whenever you enter the if.
• compute once i * scale - offset in the outer loop because this invariant. But latest gcc and clang seem smart enough to figure this out themselves.

Also, you might want to test std::unordered_map.

edit: whenever bin >= ref.size(), you know that it will be for all the next j. Maybe you even replace j by bin running (before morning coffee) when \$offset >= i \cdot scale\$ and \$\frac{i \cdot ref\_size}{x\_size} + offset < ref\_size\$