Calculating angles and distances

Question

I am running a simulation with 250 interacting agents and have a few functions that are called over and over again. Even with precomputing all distances between agents before the N² (250x250) interaction loop, my simulation is still very slow. Are there any C++ optimization tricks that I could use to speed these up?

This is the most-used function in my simulation. It calculates the distance² between two agents in a continuous space. I have a feeling there isn't much that can be done to further optimize this, but you guys have surprised me with some tricks before:

double tGame::calcDistanceSquared(double fromX, double fromY, double toX, double toY)
{
    double diffX = fromX - toX;
    double diffY = fromY - toY;

    return ( diffX * diffX ) + ( diffY * diffY );
}

Here's another expensive function in my simulation. It calculates the angle from one agent to another agent relative to the 'from' agent's heading. As you can see, I already did a little precomputing with the atan2() function (and that DOES speed things up a bit, despite what I've read in other posts).

double tGame::calcAngle(double fromX, double fromY, double fromAngle, double toX, double toY)
{
    double Ux = 0.0, Uy = 0.0, Vx = 0.0, Vy = 0.0;

    Ux = (toX - fromX);
    Uy = (toY - fromY);

    Vx = cosLookup[(int)fromAngle];
    Vy = sinLookup[(int)fromAngle];

    int firstTerm = (int)((Ux * Vy) - (Uy * Vx));
    int secondTerm = (int)((Ux * Vx) + (Uy * Vy));

    if (fabs(firstTerm) < 1000 && fabs(secondTerm) < 1000)
    {
        return atan2Lookup[firstTerm + 1000][secondTerm + 1000];
    }

    else
    {
        return atan2(firstTerm, secondTerm) * 180.0 / cPI;
    }
}

Finally, here's the monster function that uses the calcDistanceSquared() function so much. This is run every simulation time step, and there's 2,000 time steps per simulation (and MANY simulations). The most expensive part is the calcDistanceSquared() in the N² loop.

void tGame::recalcPredAndPreyDistTable(double preyX[], double preyY[], bool preyDead[],
                                       double predX, double predY,
                                       double predDists[250], double preyDists[250][250])
{
    for (int i = 0; i < 250; ++i)
    {
        if (!preyDead[i])
        {
            predDists[i] = calcDistanceSquared(predX, predY, preyX[i], preyY[i]);
            preyDists[i][i] = 0.0;

            for (int j = i + 1; j < 250; ++j)
            {
                if (!preyDead[j])
                {
                    preyDists[i][j] = preyDists[j][i] = calcDistanceSquared(preyX[i], preyY[i], preyX[j], preyY[j]);
                }
            }
        }
    }
}

Answer 1

It looks good to me. I would change

    if (!preyDead[i])
    {

To

    if (preyDead[i])
            continue;

Just so its less nested. Same with preyDead[j]. But everything looks fine to me. A tip I once saw on SO is, if your list order doesn't matter you can sort the preyDead so all the dead would be at the beginning or end and that will help branch prediction. However thats assuming its not really expensive to sort it and that its a very erratic bool and it isnt true/false 90% of the time already.

Thats a uber optimize that may not help, it shouldn't be done less you really really want to

Answer 2

I don't believe you will not get maximum benefits from code changes, but see my answer here:
Optimization Coding Practices

One issue that is screaming out is why are you making so many iterations?
For example, do all the positions need to be recalculated?

Can you cache the calculations?
You only need to perform the calculations if something moves. You can quickly detect if something moves by comparing the coordinates (don't need to calculate distances here).

Another observation is that you are currently polling, that is, looping until something moves. You may want to change your paradigm to event driven: when something changes, it sends out a message or notification. With the Event Driven paradigm, your reduce a lot of computation for things that don't change.

Answer 3

It is being said that compilers can vectorize stuff better if there are no ifs in loops. So, in that spirit, try to remove the if from the inner loop of recalcPredAndPreyDistTable() to see if it does not vectorize better and thus generate better code and thus is not a performance win despite the recomputation of distances between the dead prey.

Second thought, if you have a compiler that supports OpenMP, try to parallelize the outer loop, like this:

#pragma omp parallel for
  for (int i = 0; i < 250; ++i)
    {

Answer 4

Almost certainly whatever you try to achieve with "fromAngle" and atan2, can be accomplished with pure vector math.

Re-arrange the matrix (with extra level of indirection in other parts of the code) so that the prayDead[i]==true are in the beginning of the array (and prayDead[i]==false) are at the end.

It does not only reduce branch prediction, but decreases from N*N to (N-n)*(N-n).

Also it may not be optimal to try to reduce the operations from N*N to N*N/2 by computing an upper triangle. It's better to make a simple loop that the compiler can parallelize (that's 4x gain compared to max 2x gain from reducing the symmetry.)

Further, it's often better to split 256x256 operations to 32x32 x 8x8 operations or so. Then each block will benefit from the array being in cache -- however in this case it may again be beneficial to permute upper triangle blocks:

a b c <-- here the diagonal blocks (a,d,f) are calculated as usual
B d e     but B,C,E can be calculated by rotating the results of (b,c,e)
C E f

Answer 5

If this is possible - try to rewrite methods header like this. Once I get valuable speed-up. This is because you have no need to copy arrays, you can give to your method only addresses.

void tGame::recalcPredAndPreyDistTable(double &preyX[], double &preyY[], bool &preyDead[],
                                           double predX, double predY,
                                           double &predDists[250], double &preyDists[250][250])

EDIT: will this work?

void tGame::recalcPredAndPreyDistTable(double *preyX, double *preyY, bool *preyDead,
                                           double predX, double predY,
                                           double *predDists, double **preyDists)