Help understanding C program

[Jjoshua2]

So I know c# and java and c++ isn't that different. The following program is meant to solve the postage stamp problem. If you have three stamps and D denominations what should the denominations be so you can make any change from 1 to as high as possible. One thing I was wanting to do is see if I could extend this as to four stamps and D denominations. g_nLevels = D. I found out the weird stuff in the do loop is duff's device to copy memory. I tried to convert it to using memcpy to see the speed difference, but I couldn't get it to not reference bad memory.

#include <iostream>

using std::cout; 

long g_buf[1024]; 
int g_arrValues[25]; 
int g_arrBest[25]; 
int g_nLevels; 
int g_nBest; 

void Step(int nLevel) 
{
    int nVal = g_arrValues[nLevel++]; 

    if(nLevel == g_nLevels) 
    {
        while(g_buf[nVal++] != 0); 

        if(nVal > g_nBest) 
        {
            for(int i = 0; i < nLevel; i++) 
                g_arrBest[i] = g_arrValues[i];
            g_nBest = nVal;
        }
    }
    else 
    {
        do 
        {
            ++g_buf[nVal++];

            long* pFrom = g_buf; 
            long* pTo = g_buf + nVal;
            int nCount = (nVal + 7) / 8; 

            switch (nVal & 7) 
            {
            case 0: 
                do 
                {
                    *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
            case 7: *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
            case 6: *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
            case 5: *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
            case 4: *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
            case 3: *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
            case 2: *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
            case 1: *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 
                }
                while(--nCount > 0); 
            }

            g_arrValues[nLevel] = nVal;

            Step(nLevel);

            pFrom = g_buf + nVal * 2 - 1;
            pTo = g_buf + nVal * 3 - 1;
            nCount = (nVal + 7) / 8;

            switch (nVal & 7) 
            {
            case 0: 
                do 
                {
                    *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
            case 7: *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
            case 6: *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
            case 5: *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
            case 4: *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
            case 3: *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
            case 2: *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
            case 1: *pTo-- -= short(*pFrom--) << 8; *pTo-- -= short(*pFrom--) << 8; 
                }
                while(--nCount > 0); 
            }
        }
        while(--g_buf[nVal-1] != 0); 
    }
}

int main(int argc, char* argv[]) 
{
    g_nBest = 0;
    g_arrValues[0] = 1;
    g_buf[0] = 0x00000001;
    g_buf[1] = 0x00000100;
    g_buf[2] = 0x00010000;
    g_nLevels = 9;

    Step(0);

    cout << "Max sum: " << g_nBest - 1 <<'\n';

    for (int i = 0; i < g_nLevels; ++i) 
        cout << g_arrBest[i] << ' ';

    cout << '\n';

    return 0; 
}

 

[Neverm1nd]

Why don't you post the code with memcpy which doesn't work?

 

[Jjoshua2]

Sure. I modified it myself and I've never done it before so I must have done it wrong. I was just trying to change the two duff's devices to memcpy. It compiles, but gets shutdown when it tries to reference memory it shouldn't.

void Step(int nLevel) 
{
    int nVal = g_arrValues[nLevel++]; 

    if(nLevel == g_nLevels) 
    {
        while(g_buf[nVal++] != 0); 

        if(nVal > g_nBest) 
        {
            for(int i = 0; i < nLevel; i++) 
                g_arrBest[i] = g_arrValues[i];
            g_nBest = nVal;
        }
    }
    else 
    {
        do 
        {
            ++g_buf[nVal++];

            long* pFrom = g_buf; 
            long* pTo = g_buf + nVal;
            //int nCount = (nVal + 7) / 8; 
          
	    memcpy(pFrom, pTo, nVal); //or nCount? neither works
						
            g_arrValues[nLevel] = nVal;

            Step(nLevel);

            pFrom = g_buf + nVal * 2 - 1;
            pTo = g_buf + nVal * 3 - 1;
            //nCount = (nVal + 7) / 8;
           
	    memcpy(pFrom, pTo, nVal);
        }
        while(--g_buf[nVal-1] != 0); 
    }
}

 

[Neverm1nd]

After fixing your compiler error, it runs fine for me (VS2005). But the code you posted doesn't compile. Are you sure this is what you've tested? Also, what compiler & platform?

 

[Jjoshua2]

After fixing your compiler error, it runs fine for me (VS2005). But the code you posted doesn't compile. Are you sure this is what you've tested? Also, what compiler & platform?

Yah the second nCount should be commented (i fixed it) out as well for no compiler error. I have VS2008 Win vista x64, but it is working for me now. I remember now when it crashes is if I only replace one of the duff's devices with the memcpy. But even when I replace both it gives the wrong answer. It should give the same answer as with the duffs, which is:
Max sum: 121 Time: 7 seconds
1 3 8 9 14 32 36 51 53

 

[Gamingphreek]

This is your second post that looks suspiciously like homework and you make no mention of it being such. You need to be upfront with us right now.

 

[Jjoshua2]

This is your second post that looks suspiciously like homework and you make no mention of it being such. You need to be upfront with us right now.

I got this code from http://aliakseis.livejournal.com/2791.html It was written for a programming contest around 2001, which was to solve only the 3 throw darts problem. I want to incorporate ideas from it into my program, but it is blazingly faster than mine. But its seems to just be copying memory around almost.

 

[Gamingphreek]

Well the switch statement is likely going to be assembled to a jump table which will slow your execution time down.

To be quite honest, I'm not sure why a switch statement is used to begin with since all the conditions are fall through.

Additionally, while VS2008 is an excellent IDE, the MS compiler, in my experience leaves something to be desired when compared with the gcc and Intel compilers.

Furthermore, I see no reason to use any of the C++ functions. Doing this in raw C may yield additional performance.

What do you mean by "it crashes". Does it segfault?

-Kevin

 

[Jjoshua2]

Thanks! My goal is more to understand how it works so I can use its speedy concepts in my own program or two extend this program to cover other cases than to make this as fast as possible. I don't know how to compile it w/gcc or Intel or in C and I it being a bit faster won't really help me unless I can get it to work on something besides the 3 stamp/dart throws problem, since I want a general purpose solver. Case 3 has already been solved very high with many hundreds of CPU years.

I guess its a segfault. It says Unhandled exception at 0x00fe1180 in Stamp.exe: 0xC0000005: Access violation writing location 0x00fe7000.

 

[Venix]

Well the switch statement is likely going to be assembled to a jump table which will slow your execution time down.

To be quite honest, I'm not sure why a switch statement is used to begin with since all the conditions are fall through.

It's a modification of Duff's device, as the OP stated.

Additionally, while VS2008 is an excellent IDE, the MS compiler, in my experience leaves something to be desired when compared with the gcc and Intel compilers.

Absolutely false, as was proven the last time you made this ridiculous claim. What does it have to do with this thread, anyway? Let's stick to the topic, please.

Furthermore, I see no reason to use any of the C++ functions. Doing this in raw C may yield additional performance.

What do you mean by "it crashes". Does it segfault?

What is a "C++ function" and how is using it going to degrade performance? For that matter, where is he even using any functions except to print some data to the console?

The modified program isn't working correctly for several reasons. One is that the source and destination parameters to memcpy are swapped. Another is that the Duff's device isn't just copying memory, it's also bit shifting the source and copying nVal * 2 elements, so it can't just be replaced with memcpy (really memmove, since the source overlaps the destination).

You could just remove the Duff's device completely and replace it with a normal loop or a call to std::transform. Depending on the compiler and target architecture, Duff's device may be faster, the same, or even slower than a regular loop. It's certainly more confusing than the alternatives.

 

[Jjoshua2]

Thanks! So could you explain what *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; does and why it appears twice in each case? It appears to be doing many different things at once, and I'm not entirely sure of the order of operations. Stepping through it didn't help too much for my understanding.

 

[Gamingphreek]

It's a modification of Duff's device, as the OP stated.

Ok - I don't understand why HE used a switch statement. Better?

Absolutely false, as was proven the last time you made this ridiculous claim. What does it have to do with this thread, anyway? Let's stick to the topic, please.

Neither of those claims disprove my point.

The tests clearly show that the Intel compiler has a large advantage. Additionally, GCC and MSVC are close; however, if you don't limit yourself to just the -Ox switches, it is very possible to optimize your code further.

As for the Firefox testing - sure, profile guided optimization isn't provided. Use a code profiler (ie: gprof) and look at the code and optimize as you see fit. Furthermore, if he is really concerned about the values in registers, supply the appropriate switches to force the values he wants to be stored in registers (Function parameters for instance)

What is a "C++ function" and how is using it going to degrade performance? For that matter, where is he even using any functions except to print some data to the console?

Never said he was using C++ methods. Using the C++ libraries and using 'cout' instead of a raw system 'write' or a 'printf()'is more costly.

As you said though, the results are different because of bit-shifting and the flip flopped parameters.

-Kevin (Gamingphreek)

 

[Venix]

Thanks! So could you explain what *pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; does and why it appears twice in each case? It appears to be doing many different things at once, and I'm not entirely sure of the order of operations. Stepping through it didn't help too much for my understanding.

The source is cast to short, left shifted by 8 bits (which multiplies by 256), and then added to whatever was already in the destination. I can't explain much else at the moment because I've really only glanced at the code. Due to the lack of comments and poor variable naming it would take a little time to decipher it.

Ok - I don't understand why HE used a switch statement. Better?

The link I posted earlier explains it clearly. Tom Duff's original e-mail about the discovery is also interesting.

Furthermore, if he is really concerned about the values in registers, supply the appropriate switches to force the values he wants to be stored in registers (Function parameters for instance)

You don't understand what register allocation is. But again, this is neither the time nor place for compiler jihad.

Never said he was using C++ methods. Using the C++ libraries and using 'cout' instead of a raw system 'write' or a 'printf()'is more costly.

Are you suggesting that the console I/O that runs one time after the calculation is complete is a critical path? This is simply terrible advice, and premature optimization to the extreme.

It also relies on the faulty assumption that iostreams are necessarily slower than stdio. Benchmarks demonstrate that some implementations can be as fast or faster.

 

[Jjoshua2]

But what about the ++ operators? You never mentioned that? And does this happen twice because that sentence is repeated?

 

[Venix]

Oh, sorry. ++ just increments the pointers so they point to the next element in the source and destination arrays.

*dst++ += *src++ dereferences the values at src and dst, adds them together, stores the result in dst, and then makes the dst and src pointers point to the next element in their respective arrays. It's a common idiom in C, but I can imagine that it's fairly confusing for someone coming from a higher level language.

If you aren't familiar with pointers, you may want to search for a tutorial or pick up a book on C or C++.

 

[degibson]

Oh, sorry. ++ just increments the pointers so they point to the next element in the source and destination arrays.

++ on a pointer is a poor man's iterator. ++ always takes into account the size of the things you're ++ing.

 

[Jjoshua2]

I understood Venix. But I don't know what it means "takes into account the size of the things you're ++ing". Why does the size matter if your just adding one?

 

[zebano]

Because ++ on an array of UINT8 and on an array of UINT32 is going to change the pointer by different amounts based on sizeof(yourdatatype).

 

[Cogman]

It should be noted that ++ pretty much directly translates (ignoring post and preincrement) to
thing = thing + 1;
or
thing += 1;

as for post and pre increment. The difference is this.

int i = ++j;
int i = j++;

in the first, i gets the value j, in the second, i gets the value of j + 1. So basically if the ++ is before the thing it means "Add 1, then evaluate the rest of the expression) where as if it is after it means "evaluate the expression then add one to the variable".

 

[iCyborg]

I think he's confused with pointers, because for them p++ (and p=p+1) translates to taking p's memory address as a number and adding sizeof(T) to it (assuming p is a T*). I intentionaly wrote this out in words because p += sizeof(T) means something else... It's a convenience thing to have p point to a next element of type T in arrays.

 

[Jjoshua2]

Ok thanks I get it now. So do the statements like "*pTo-- -= short(*pFrom--) << 8" execute twice since they are in each case twice with a semicolon? Im thinking you can pretend there is a return there in between? But then wouldn't you need {} since there are two statements?