0
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Are there any characteristics of blockNum that we need to be aware of? Occurs sequentially with no gaps? Essentially random on each call? Only in a specific range? \$\endgroup\$ – Glenn Rogers Jul 30 '12 at 6:19
  • \$\begingroup\$ blockNum will always be less than 0xFFFFFF. Yes, it is pretty much random on each call. \$\endgroup\$ – hetelek Jul 30 '12 at 6:29
  • \$\begingroup\$ I don't think any of your hand optimizations are actually providing you with a benefit. This kind of macro optimization is ultimately self defeating and usually leads to slower code as you confuse the compiler optimizer which is a million times better than you at optimizations. \$\endgroup\$ – Martin York Jul 30 '12 at 7:54
  • \$\begingroup\$ After my analysis (see below). This code is contributing to 0.0001% of the execution time. Any time spent trying to optimize this is a complete and utter waste of time. Write it as clearly as possible without regard for optimization. Anything you do will have ZERO affect on the run time. \$\endgroup\$ – Martin York Jul 30 '12 at 8:07
  • 1
    \$\begingroup\$ There are at least 2 bugs in your code (initializing byte to value that is too large for the type and accessing the step array out of bounds). Fix those bugs first. \$\endgroup\$ – Jan Hudec Jul 30 '12 at 8:37
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ It also calls other methods 300,000 times. I'm just saying that's how much it takes off of the whole process, as there are many other functions being called, not just this one. \$\endgroup\$ – hetelek Jul 30 '12 at 7:56
  • 1
    \$\begingroup\$ @hetelek: I understand this. It is your other functions that are taking the time not this one. Making this return 0 just means you execute another path through the other code that is less expensive. This code is not causing any significant cost. \$\endgroup\$ – Martin York Jul 30 '12 at 7:58
  • \$\begingroup\$ Would it help if I posted all the functions? \$\endgroup\$ – hetelek Jul 30 '12 at 8:13
  • 2
    \$\begingroup\$ It would probably help you a lot to learn to use the profiling tools provided by MS. They will point you at any bottlenecks that need optimizations. The most affective optimizations are done at the algorithm level not at the micro what instruction should I use level. \$\endgroup\$ – Martin York Jul 30 '12 at 8:18
  • 1
    \$\begingroup\$ And the other broken thing: Initializing BYTE to 0x723A, which is too large for the type. \$\endgroup\$ – Jan Hudec Jul 30 '12 at 8:35
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the repsonse, but I cannot do that. If (blockNum < 0x70E4) is true, than it return 'num + step[1]', so 'num' must be calculated before. \$\endgroup\$ – hetelek Jul 30 '12 at 7:13
  • 2
    \$\begingroup\$ @hetelek But num is guaranteed to be 0 in that situation. For any two ints, x, y, if x < y, x / y = 0. Like 3/5, or 100/101. For all z, 0 * z = 0, thus, if the condition is true, num = 0. \$\endgroup\$ – Corbin Jul 30 '12 at 7:18

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.