C++ Performance Tips

•

What is DaniWeb IT Discussion Community?

You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 426,640 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 1,583 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.

Join our community!

Please support our C++ advertiser: Programming Forums

Thread Tools Display Modes

Views: 39491 | Replies: 41

Page 2 of 5

Last »

•

Join Date: Mar 2006

Location: Zagreb, Croatia

Posts: 18

Reputation: brahle is an unknown quantity at this point

Rep Power: 3

Solved Threads: 0

brahle

Offline

Newbie Poster

how to convert int to binary?

#11

Mar 3rd, 2006

the best way to do this is to use the bits. The code would be:

Help with Code Tags

(Toggle Plain Text)

inline string to_binary( const int &x ) {
  int t;
  string ret;
  if( x > 0 ) t = x; else t = -1 * x;
  for( int i = 0; i < 32; ++i ) 
    if( t & ( 1 << i ) ) ret.push_back( '1' ); else ret.push_back( '0' );
  reverse( ret.begin(), ret.end() );
  ret.erase( 0, ret.find( '1' ) );
  if( ret.size() == 0 ) return "0";
  if( x < 0 ) return '-' + ret;
  return ret;
}

Revenage is a dish best served cold.
50|2|2Y 4 |34|) 3|\|6|_|5|-|

•

Join Date: Nov 2005

Location: Canada

Posts: 236

Reputation: dwks will become famous soon enough

Rep Power: 4

Solved Threads: 21

dwks

Offline

Posting Whiz in Training

Re: C++ Performance Tips

#12

Mar 11th, 2006

Help with Code Tags

(Toggle Plain Text)

for( int i = 0; i < 32; ++i )

That's not very portable. Use something in <climits> or the C++ equivalent.

dwk

Seek and ye shall find.

"Only those who will risk going too far can possibly find out how far one can go."
-- TS Eliot.

"I have not failed. I've just found 10,000 ways that won't work."
-- Thomas Alva Edison

"The only real mistake is the one from which we learn nothing."
-- John Powell

•

Join Date: May 2006

Location: France, Normandy

Posts: 10

Reputation: SuperKoko is an unknown quantity at this point

Rep Power: 3

Solved Threads: 0

SuperKoko

Offline

Newbie Poster

Re: C++ Performance Tips

#13

Aug 8th, 2006

•

Originally Posted by bitforce

An easy way to swap 2 variables without using another variable:
Help with Code Tags

(Toggle Plain Text)
a=a+b;
b=a-b;
a=a-b;
a=a+b; b=a-b; a=a-b;

Easy way? I don't know, but sure it is inefficient (except if the optimizer is really good).

There *are* temporary variables if from an ISO standard point-of-view.

And, this algorithm can only be useful if (assuming an optimizer as good as Turbo C++ 1.0 optimizer or better, knowing that it is a very old compiler, with an obsolete optimizer):

Both a and b are in a register (otherwise, I don't know any architecture where the temporary would be avoided)
AND There is no builtin XCHG instruction at the assembly level (false for x86 and PowerPC)
AND The CPU lacks register (in that case, it is very probable that the CPU has a XCHG instruction).

And, in that case, you may, ocasionally (rarely) gain little performance... In all other cases, you just can pray that the optimizer will understand your bad code, and implement it in a correct way.
Most compilers I know produce bad code for that.

If you use a 25 years old compiler, with a very very bad optimizer, it might also be possible that this compiler lacks register variables...

In that case, the following code:

Help with Code Tags

(Toggle Plain Text)

a-=b;
b-=a;
a-=b;

Will produce something like (on x86-16, yep I can't imagine any such bad optimizer on x86-32):

Help with Code Tags

(Toggle Plain Text)

mov ax, [bp-8] ; timings on a k6-2 CPU (1)
sub ax, [bp-4]  ; 3
mov [bp-8],ax  ; 4 CPU cycles

mov ax,[bp-4]
sub ax,[bp-8]
mob [bp-4],ax

mov ax, [bp-8]
sub ax, [bp-4]
mov [bp-8],ax ;11.5 CPU cycle (i.e. the last one might be paired with the next instruction)

Note : If the optimizer is even more bad than what I described, the generated code might even be worst.
And, your code (which has temporaries), on the same compiler might be twice as slow...

The classical

Help with Code Tags

(Toggle Plain Text)

int c;
c=b;
b=a;
a=c;

Will produce something like:

Help with Code Tags

(Toggle Plain Text)

mov ax,[bp-4]
mov [bp-12],ax

mov ax,[bp-8]
mov [bp-4],ax

mov ax,[bp-12]
mov [bp-8],ax   ; 5.5 CPU cycles (on a K6-2 CPU)

Note : I don't think that the compiler can generate worst code, even if there is no optimizer.

So, my point is that your code is *always* a bad idea.
This algorithm might only be used in some very special contexts, only on weird architectures (I don't know any such architecture, but it probably exists or existed), and at assembly level only!

Please, read my posts (SuperKoko) on these two threads (of another forum):
http://www.codeguru.com/forum/showthread.php?t=386883
http://www.codeguru.com/forum/showthread.php?t=383191

Also, remember that std::swap can be assumed as being optimal on your architecture : The compiler is allowed to do specific optimizations on it.

•

Join Date: May 2006

Location: France, Normandy

Posts: 10

Reputation: SuperKoko is an unknown quantity at this point

Rep Power: 3

Solved Threads: 0

SuperKoko

Offline

Newbie Poster

Re: C++ Performance Tips

#14

Aug 9th, 2006

•

Originally Posted by BountyX

When you want to pass a constant variable, pass it by reference to save memory.

Example:
int example (const int value); // Uses more memory than
int example (const int &value); // this one

That's the opposite!

Using const references is a good idea for large objects (say, 16 bytes and more).
For very small objects (smaller than a pointer), if you're lucky, you'll not loose performance.
But it is quite probable that the compiler will generate more code, slower code, and use more stack memory (if the argument is not a lvalue).
And, moreover, it is very hard for the compiler to optimize the const-reference thing when the function is used across translation units boundaries (at least, for most compilers), because it must respect a calling convention, and can't know whether the function, internally, gets the address of the const reference.
In that case, the compiler can't replace such const-reference by a simple value.

Please read my posts on these two threads:
http://www.codeguru.com/forum/showthread.php?t=339608
http://www.codeguru.com/forum/showth...=392134&page=2

•

Join Date: May 2005

Location: India

Posts: 65

Reputation: vicky_dev is an unknown quantity at this point

Rep Power: 4

Solved Threads: 0

vicky_dev

Offline

Junior Poster in Training

A General Performance Tip - Arithmetic involving powers of 2

#15

Dec 15th, 2006

Multiplication, division and modulus operations on powers of 2 can be made much faster using bitwise operators.

1. Modulo
Finding the modulus is particularly expensive. This operation can be performed mush faster using the & operator, because
a % n == a & (n-1) where n is power of 2.

2. Division
Division by a power of 2 can done faster using the >> operator.
a / n == a >> m, where n = 2^m

3. Multiplication
This is similar to division, except, use left shift << operator
a * n == a <<m , n = 2^m

•

Join Date: Apr 2004

Posts: 3,638

Reputation: Dave Sinkula is a glorious beacon of light

Rep Power: 17

Solved Threads: 143

Dave Sinkula Dave Sinkula is offline

Offline

long time no c

Re: A General Performance Tip - Arithmetic involving powers of 2

#16

Dec 15th, 2006

•

Originally Posted by vicky_dev

Multiplication, division and modulus operations on powers of 2 can be made much faster using bitwise operators.

1. Modulo
Finding the modulus is particularly expensive. This operation can be performed mush faster using the & operator, because
a % n == a & (n-1) where n is power of 2.

2. Division
Division by a power of 2 can done faster using the >> operator.
a / n == a >> m, where n = 2^m

3. Multiplication
This is similar to division, except, use left shift << operator
a * n == a <<m , n = 2^m

Valid, albeit ancient, advice -- much like the XOR swap.

It's one of those things that language implementers knew about ages ago, and should be done by the compiler automagically (or it may take some optimization option).

Bottom line: don't do this unless your compiler sucks. Write code to multiply by 4 like this num*=4. Obfuscating it as num<<=2 will make your code look strangeto newbies, and it will look like a newbish hack to old timers (both making what you write a little suspect).

And don't forget that right-shifting signed values is implementation defined!

Last edited by Dave Sinkula : Dec 15th, 2006 at 8:54 pm.

High Plains Blogger #plains #lounge ## I, for one, welcome our new socialist overlords.

•

Join Date: Feb 2007

Location: Bangalore, India

Posts: 535

Reputation: thekashyap will become famous soon enough

Rep Power: 4

Solved Threads: 50

thekashyap thekashyap is offline

Offline

Posting Pro

Re: C++ Performance Tips

#17

Feb 21st, 2007

A few more I find useful...

1. Replace switch-case/if-else with array-indexing:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
switch ( queue ) {
case 0 :   letter = 'W';
   break;
case 1 :   letter = 'S';
   break;
case 2 :   letter = 'U';
   break;
}
//or maybe
if ( queue == 0 )
  letter = 'W';
else if ( queue == 1 )
  letter = 'S';
else
  letter = 'U';
//A quicker method is to simply use the value as an
//index into a character array, eg.
static char *classes="WSU";
letter = classes[queue];
switch ( queue ) {
case 0 :   letter = 'W';
   break;
case 1 :   letter = 'S';
   break;
case 2 :   letter = 'U';
   break;
}
//or maybe
if ( queue == 0 )
  letter = 'W';
else if ( queue == 1 )
  letter = 'S';
else
  letter = 'U';
//A quicker method is to simply use the value as an
//index into a character array, eg.
static char *classes="WSU";
letter = classes[queue];

•

Join Date: Feb 2007

Location: Bangalore, India

Posts: 535

Reputation: thekashyap will become famous soon enough

Rep Power: 4

Solved Threads: 50

thekashyap thekashyap is offline

Offline

Posting Pro

Re: C++ Performance Tips

#18

Feb 21st, 2007

2. I'm sure most ppl know this but writing as it's not already mentioned in this topic so far. Use unsigned int stored in registers for loop variables.
Reasons
1. unsigned int arithmatic is faster than signed int.
2. registers are registers ! They're simply faster than memory access.

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
for( register unsigned int loop_variable = 0; loop_variable <=100000; i++ )
{ /*do your stuff*/ }
 
for( register unsigned int loop_variable = 0; loop_variable <=100000; i++ )
{ /*do your stuff*/ }

•

Join Date: Feb 2007

Location: Bangalore, India

Posts: 535

Reputation: thekashyap will become famous soon enough

Rep Power: 4

Solved Threads: 50

thekashyap thekashyap is offline

Offline

Posting Pro

Re: C++ Performance Tips

#19

Feb 21st, 2007

3. Optimizing the breaking conditions in for loops. If you know that the loop variable's range is from 0 to some +ve number AND it doesn't matter which way you traverse while looping, you can optimize the loop like this:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
//original loop
for( int i = 0; i <= 30; i++ )
{/*do your stuff*/}
//optimized loop
for( int i = 30; i--; )
{/*do your stuff*/}
//original loop
for( int i = 0; i <= 30; i++ )
{/*do your stuff*/}
//optimized loop
for( int i = 30; i--; )
{/*do your stuff*/}

•

Join Date: Feb 2007

Location: Bangalore, India

Posts: 535

Reputation: thekashyap will become famous soon enough

Rep Power: 4

Solved Threads: 50

thekashyap thekashyap is offline

Offline

Posting Pro

Re: C++ Performance Tips

#20

Feb 21st, 2007

4, Optimizing very small loops using switch-case.
When you know that the range of loop variable's value is
pretty small avoid the loop altogether.

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
//unoptimized code
for( int i = some_small_positive_int; i--; )
{/*do your stuff with i*/}
 
//optimized based on the assumption that some_small_positive_int can only be from 1 to 7.
switch( i ) 
{ 
    case 7 : /*do your stuff with i*/ i++; 
    case 6 : /*do your stuff with i*/ i++; 
    case 5 : /*do your stuff with i*/ i++; 
    case 4 : /*do your stuff with i*/ i++; 
    case 3 : /*do your stuff with i*/ i++; 
    case 2 : /*do your stuff with i*/ i++; 
    case 1 : /*do your stuff with i*/ 
}
//unoptimized code
for( int i = some_small_positive_int; i--; )
{/*do your stuff with i*/}

//optimized based on the assumption that some_small_positive_int can only be from 1 to 7.
switch( i ) 
{ 
    case 7 : /*do your stuff with i*/ i++; 
    case 6 : /*do your stuff with i*/ i++; 
    case 5 : /*do your stuff with i*/ i++; 
    case 4 : /*do your stuff with i*/ i++; 
    case 3 : /*do your stuff with i*/ i++; 
    case 2 : /*do your stuff with i*/ i++; 
    case 1 : /*do your stuff with i*/ 
}