2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @BCdotWEB ups yes completely agree \$\endgroup\$ – formerlyknownas_463035818 Jul 22 '16 at 15:49
  • 1
    \$\begingroup\$ You could probably give a try and ask for advice on math.stackexchange.com . Looking for minimum values between two variables sounds like derivative to me (i.e. a calculus problem). If f(x) is your first vector and g(x) is your second vector, you want to get the minimum value of h(x) = (f(x)-g(x))^2). I'm not sure, but maybe you can get away with just calculating the derivative h'(x) . That would go from O(n^2) to O(1). \$\endgroup\$ – ChatterOne Jul 22 '16 at 21:03
  • \$\begingroup\$ @ChatterOne Actually I already asked a question related to this problem on math.stackexchange. A better algorithm uses convolution via FFT. However, for now I wanted to see how far I can get with my current approach (mainly because there is some legacy code and I have to be very careful in changing the algorithm). \$\endgroup\$ – formerlyknownas_463035818 Aug 8 '16 at 8:35
2
\$\begingroup\$

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\$

\$\endgroup\$
  • \$\begingroup\$ thanks for the suggestions I might accept this once i tried it out, but I will be on holidays for the next two weeks :) \$\endgroup\$ – formerlyknownas_463035818 Jul 22 '16 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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