How can I optimize this for speed? (C++)

Question

Here is my method:

// can change
DWORD step[2] = { 0xAC, 0x723A };
packageType = 1;

DWORD computeLevel(DWORD blockNum)
{
    DWORD num = (blockNum / 0x70E4) * step[1];
    if (blockNum < 0x70E4)
        return num + step[0];
    return (1 << packageType) + num;
}

I am trying to optimize this for speed, as it gets called about 300,000 times and one little operation could add alot of time on. If I change the blockStep to just constant values, this makes it much, much faster. The problem is, is that they can change so I cannot make it const. Also, if I just have it return a straight up 0, no comparisons, it saves my code around 1 minute, 30 seconds, so this function is really slowing me down.

Also, it would be nice if this function could also be enhanced. I already tried by best, but it would be great if it can get better.

DWORD computeLevel0(DWORD blockNum)
{
    WORD quotient1 = (blockNum / 0xAA);
    BYTE quotient2 = (blockNum / 0x70E4);
    DWORD num = quotient1 * 0xAC;

    // optimizations (0 comparison)

    WORD mult1 = quotient1;
    mult1 |= mult1 >> 8;
    mult1 |= mult1 >> 4;
    mult1 |= mult1 >> 2;
    mult1 |= mult1 >> 1;
    mult1 &= 1;

    BYTE mult2 = quotient2;
    mult2 |= mult2 >> 4;
    mult2 |= mult2 >> 2;
    mult2 |= mult2 >> 1;
    mult2 &= 1;

    num += ((quotient2 + 1) << packageType) * mult1;
    num += (((1 << packageType)) * mult2) * mult1;

    return num;
}

Answer 1

The best optimization you can do is write code that works.

It makes it infinitely faster:

BYTE step[2] = { 0xAC, 0x723A };

    DWORD num = (blockNum / 0x70E4) * step[2];
                                //    ^^^^^^^   Broken. Undefined behavior.
                                //              The rest of the code is invalid.

Second I don't believe your numbers:

1 minute, 30 seconds for 300,000 calls.

That's an awfully slow machine. 90 seconds for 300,000 calls or 3,333 calls a second. Even unoptimized this code runs (300,000) in less then 1/100 of a second on my machine when fully optimized it is closer to 1/1000 of a second.

So it is not this code that is causing you to slow down. But the result of this code may be affecting the call path inside your application and causing other more costly code to be executed.

Since this code takes 1/1000 of a second of the 90 second total. It is contributing to 0.0001% of the execution time. This is so insignificant that you should not even be trying to optimize this part of the code.

My test code:

#include <iostream>
#include <time.h>
#include <vector>
#include <algorithm>

int step[2] = { 0xAC, 0x723A };
int packageType = 1;

int computeLevel(int blockNum)
{
    int num = (blockNum / 0x70E4) * step[1]; // changed.
    if (blockNum < 0x70E4)
        return num + step[0];                // changed
    return (1 << packageType) + num;
}


// Add this to pre-vent the code being optimized to zero.
int result = 0;
int check  = 0;
int doComputeLevel(int blockNum)
{
    result += computeLevel(blockNum);
    ++check;
}


int main()
{
    // Set up random test data
    std::vector<int>    data;
    data.reserve(300010);
    for(int loop = 0;loop < 300000;++loop)
    {   
        data.push_back(rand());
    }   

    // Run the test
    clock_t t = clock();
    std::for_each(data.begin(), data.end(), doComputeLevel);
    clock_t e = clock();

    // print the results;
    std::cout << (e-t) << std::endl;
    std::cout << (e-t)*1.0/CLOCKS_PER_SEC << std::endl;
    std::cout << data.size() << " : " << check << " : " << result << std::endl;
}

> g++ -O3 t.cpp
> ./a.out
1812                           TICKS
0.001812                       TIME in seconds
300000 : 300000 : 62755196     iterations : check of iterations : result

Answer 2

I'll expand on this later when I get a chance, but something immediately jumps out at me:

DWORD num = (blockNum / 0x70E4) * step[2];
if (blockNum < 0x70E4)

You could rearrange this and potentially save a few operations:

DWORD computeLevel(DWORD blockNum)
{

    if (blockNum < 0x70E4) {
        //if blockNum < 0x70e4, (blockNum / 0x70e4) == 0, thus num == 0.
        return step[1];
    }

    DWORD num = (blockNum / 0x70E4) * step[2];

    return (1 << packageType) + num;

}

Depending on compiler optimization, how the CPU pipelines, and what the bytecode generated is, this might not make a difference, but it's worth a try. Also, if that branch isn't taken very often, this isn't going to make a significant difference.