How to make C++ running efficient?

[alvinw]

HI, all,

I have a block of following C++ code to run,

vector<double> st(25000,0);

for(int n=0;n<st.size();n++)
for(int i=0;i<p.size();i++)
if(n-i>0 && n-i<a.size()) st[n]+=p[i]*a[n-i];

where a is a double vector of the same size as st, p is a double vector of size 2500.

I found that this block takes considerable running time. Do you have any good idea to improve this block running efficiency?
Thanks in advance.

[jonnin]

a cheap first pass at it.

const int st_size = st.size(); //lets not call a function every iteration!
const int p_size = p.size();
const int a_size = a.size();
register int i; //try to help the compiler make a smart decision

for(int n=0;n<st_size;n++)
for(i=0;i<p_size;i++)
{
const int nmi = n-i; //this is used a lot
if(nmi>0 && nmi<a_size)
st[n]+= p[i]*a[nmi];
}

[jonnin]

Additional thoughts -- dont use double if you dont NEED double.
Re-arranging the code carefully to access memory sequentially instead of random will reduce page faults (can consume considerable effort)

Re-arranging the code to only have one loop will help free up registers and resources. Nontrivial coding effort.

If you really, really need a boost drop the vector and use an array and manage the size yourself. There is some overhead in the vector class that can be cleared up at the cost of a nice object.

[jonnin]

Finally, I am almost certain you can lose the conditional(busted pipeline, many bad things) AND code the for loops in a way that reduces the "do nothing" iterations and only loops over valid indexes (that do work). This should cut out a lot of wasted time and should not be a difficult fix! A better algorithm is always the first step toward speed.

[alvinw]

Thanks a lot. I will see what I can do with these points.
The vector and double type cannot be saved since this is a block in a class where they already exisit there.

[Danny]

Another point: you probably can replace the double with int, execute the loop on a vector of int, and then copy the result to a vector of double. I see nothing that warrants the use of double anyway.

Another, perhaps the most curcial point: turn your compiler's optimization switches on. Modern compilers are very good at optimizing loops, so perhaps you won't need to work very hard...
Finally, I disagree with jonnin with respect to the register declaration. I doubt that Visual C++ (even in its older versions) heeds this hint since the register keyword, like auto, is completely transparent -- the compiler ignores it because it usually knows best which variables are the best candidates for being stored in the CPU's registers.

[jonnin]

I havent had much luck with register to be sure. But I stick it in anyway as part of self documentation (hey reader, this is gonna be used a lot and might be a spot to somehow optimize).

You can't see the incoming data (p and a) -- how can you know that double/floating type isnt necessary? I dont see that -- it looks for all the world like a matrix multiply to me.

[Danny]

I guess you're right with respect to the double/float. Anyway, since I didn't see any positive evidence warranting the usage of a floating point datatype, I didn't exclude this option...
As for register: I think I can agree with you. It doesn't matter to the compiler anyway, so at least the keyword documents that this variable is used frequently. I never use register and inline in my code, btw.

[jonnin]

I *have* to use inline -- we have the cheap visual .net and it does not support optimization (the release is set to only inline marked functions and cannot be changed.)

[Danny]

duh! why can't it optimize the code?

[jonnin]

The cheap version has hardcoded the optimizer settings to "only functions labeled inline" among other dumb settings. I didnt see this when we bought it and now im stuck for a while -- I thought the cheap version lost the profiler and some less useful things.