Help with code optimization

Question

I've written a little particle system for my 2d-application. Here is raining code:

// HPP -----------------------------------
struct Data
{
    float x, y, x_speed, y_speed;
    int timeout;
    Data();
};        
std::vector<Data> mData;
bool mFirstTime;
void processDrops(float windPower, int i);

// CPP -----------------------------------
Data::Data()
    : x(rand()%ScreenResolutionX), y(0)
    , x_speed(0), y_speed(0), timeout(rand()%130)
{ }

void Rain::processDrops(float windPower, int i)
{
    int posX = rand() % mWindowWidth;

    mData[i].x = posX;

    mData[i].x_speed = WindPower*0.1; // WindPower is float
    mData[i].y_speed = Gravity*0.1;   // Gravity is 9.8 * 19.2

    // If that is first time, process drops randomly with window height
    if (mFirstTime)
    {
        mData[i].timeout = 0;
        mData[i].y = rand() % mWindowHeight;
    }
    else
    {
        mData[i].timeout = rand() % 130;
        mData[i].y = 0;
    }
}

void update(float windPower, float elapsed)
{
    // If this is first time - create array with new Data structure objects
    if (mFirstTime)
    {
        for (int i=0; i < mMaxObjects; ++i)
        {
            mData.push_back(Data());
            processDrops(windPower, i);
        }
        mFirstTime = false;
    }

    for (int i=0; i < mMaxObjects; i++)
    {
        // Sleep until uptime > 0 (To make drops fall with randomly timeout)
        if (mData[i].timeout > 0)
        {
            mData[i].timeout--;
        }
        else
        {
            // Find new x/y positions
            mData[i].x += mData[i].x_speed * elapsed;
            mData[i].y += mData[i].y_speed * elapsed;

            // Find new speeds
            mData[i].x_speed += windPower * elapsed;
            mData[i].y_speed += Gravity * elapsed;

            // Drawing here ...

            // If drop has been falled out of the screen
            if (mData[i].y > mWindowHeight) processDrops(windPower, i);
        }
    }
}

So the main idea is: I have some structure which consist of drop position, speed. I have a function for processing drops at some index in the vector-array. Now if that's first time of running I'm making array with max size and process it in cycle.

But this code works slower that all another I have. Please, help me to optimize it.

I tried to replace all int with uint16_t but I think it doesn't matter.

Answer 1

Replacing int with uint16_t shouldn't do any difference (it'll take less memory, but shouldn't affect running time on most machines).

The shown code already seems pretty fast (it's doing only what it's needed to do, and there are no particular mistakes), I don't see how you could optimize it further (at most you could remove the check on mFirstTime, but that should make no difference).

If it's slow it's because of something else. Maybe you've got too many drops, or the rest of your code is so slow that update gets called little times per second.
I'd suggest you to profile your program and see where most time is spent.

---

EDIT:
one thing that could speed up such algorithm, especially if your system hasn't got an FPU (! That's not the case of a personal computer...), would be to replace your floating point values with integers.

Just multiply the elapsed variable (and your constants, like those 0.1) by 1000 so that they will represent milliseconds, and use only integers everywhere.

Answer 2

Few points:

1. Physics is incorrect: wind power should be changed as speed makes closed to wind speed, also for simplicity I would assume that initial value of x_speed is the speed of the wind.
2. You don't take care the fraction with the wind at all, so drops getting faster and faster. but that depends on your want to model.
3. I would simply assume that drop fails in constant speed in constant direction because this is really what happens very fast.

Also you can optimize all this very simply as you don't need to solve motion equation using integration as it can be solved quite simply directly as:

x(t):= x_0 + wind_speed * t
y(t):= y_0 - fall_speed * t

This is the case of stable fall when the gravity force is equal to friction.

x(t):= x_0 + wind_speed * t;
y(t):= y_0 - 0.5 * g * t^2;

If you want to model drops that fall faster and faster.

Answer 3

Few things to consider:

In your processDrops function, you pass in windPower but use some sort of class member or global called WindPower, is that a typo? If the value of Gravity does not change, then save the calculation (i.e. mult by 0.1) and use that directly.

In your update function, rather than calculating windPower * elapsed and Gravity * elapsed for every iteration, calculate and save that before the loop, then add. Also, re-organise the loop, there is no need to do the speed calculation and render if the drop is out of the screen, do the check first, and if the drop is still in the screen, then update the speed and render!

Interestingly, you never check to see if the drop is out of the screen interms of it's x co-ordinate, you check the height, but not the width, you could save yourself some calculations and rendering time if you did this check as well!

Answer 4

In loop introduce reference Data& current = mData[i] and use it instead of mData[i]. And use this reference instead of index also in procesDrops.

BTW I think that consulting mFirstTime in processDrops serves no purpose because it will never be true. Hmm, I missed processDrops in initialization loop. Never mind this.

Answer 5

This looks pretty fast to me already. You could get some tiny speedup by removing the "firsttime" code and putting it in it's own functions to call once rather that testing every calls.

You are doing the same calculation on lots of similar data so maybe you could look into using SSE intrinsics to process several items at once. You'l likely have to rearrange your data structure for that though to be a structure of vectors rather than a vector od structures like now. I doubt it would help too much though. How many items are in your vector anyway?

Answer 6

It looks like maybe all your time goes into ... Drawing Here.
It's easy enough to find out for sure where the time is going.