C++: Random Pieces

[invisal]

I have recently started to write my own tiny little electronic-book. This e-book is not about teaching C++ from ground up, but it is a collection of C++ pieces that I have learnt during these past few years that I want to share with everyone. I call this e-book "C++: Random Pieces". It is still incomplete.

I decide to post my first draft, hoping to get constructive feedback and to bring meaningful discussion.

[B]NOTE:[/B] My English is very poor. If you find any grammatically mistake or you have better way of explain the point, please do not hesitate to correct. [B]NOTE:[/B]If you have any trick or useful information related to C++, do not hesitate to share. [B]NOTE:[/B]My programming knowledge is limited, if I have made any mistake, please spare my ignorance.

There will be around 20 to 25 C++ pieces that will be included in this e-book. I have finished the first 4 pieces so far. Firstly, I will post the first two pieces here.

[invisal]

1st Piece: Reduce the Calculation

Computer is well-known of its ability to calculate arithmetic operation in an instant. Because it performs so fast that make some people think it will make no difference to do extra calculation. Keep that in mind that it still does spend minor time in each calculation; and those minor times will eventually build up and will make a huge difference in performance speed. The first piece of today is to simplify the mathematical expression and to reduce unnecessary calculation.

For example: k = (168 * m) / 2; This can be reduced to: k = 84 * m; Most of trigonometry functions take radian value while some people are more familiar with degree than radian. So, function to make conversion from degree to radian is very useful. Because this function might use often throughout the program, it is good idea to reduce its calculation.

double Degree2Radian(double _degree)
{
     return (_degree * PI) / 180;
}

This can be reduced to:

double Degree2Radian(double _degree)
{
     return _degree * 0.0174532925;
}

Even a little bit more complicated calculation can be reduced.

For example: k = (a + b + c) / (b + c); Reduce to: k = a /(b + c) + 1; For example: k = a * b + a * c + a * d; Reduce to: k = (b + c + d)*a;

[invisal]

2nd Piece : Everything Is Not the Same
[INDENT]Not every arithmetic operation takes same time to compute. Some might take longer and some might take shorter to compute. Subtraction and addition operator perform faster than multiplication, and multiplication performs faster than division.

Each computer instruction requires certain number of clock cycles. The less clock cycles it requires, the less time it will performs. So, if the problem can be solved in addition or subtraction, then use them instead of multiplication and division.

For example: k *= 2;

We can use addition instead of multiplication by: k += k;

Remember that not every multiplication problem can be beneficially replaced by addition.

For example: k = m + m + m + m + m +m + m + m + m + m;

We shouldn’t use addition instead multiplication because 9 addition calculation take longer than a single multiplication calculation. For this problem, multiplication should be used. k = m * 10;

[/INDENT]

[tux4life]

1st Piece: Reduce the Calculation

For example: k = (168 * m) / 2; This can be reduced to: k = 84 * m;

Uh? You meant: k = 84 * m / 2;

2nd Piece : Everything Is Not the Same

For example: k *= 2; We can use addition instead of multiplication by: k += k;

AFAIK, k <<= 1; is the most efficient way to do a multiplication by two.

[invisal]

Uh? You meant: k = 84 * m / 2;

I think (168 * m) / 2 = 84 * m

AFAIK, k <<= 1; is the most efficient way to do a multiplication by two.

Shift left is slightly slower than addition operator in modern processor.

[Narue]

>If you find any grammatically mistake or you have better
>way of explain the point, please do not hesitate to correct.
Which amounts to rewriting your prose, I'm afraid. It's very clearly written by someone with grammar habits from another language, and those habits are hard to break with a few quick corrections. A dedicated editor with strong English writing skills would be better.

>If you have any trick or useful information related to C++, do not hesitate to share.
I have tons of them, but random collections are rarely useful. Do you have any specific direction you want to take things? What's the target audience?

>1st Piece: Reduce the Calculation
Simplifying expressions, good. Simplifying at the cost of readability, not so good. 180 is pushing it for magic numbers, and 0.0174532925 is outside the realm of good taste. You should make use of manifest constants in your examples to promote good practice.

>2nd Piece : Everything Is Not the Same
Here's another piece of advice: Don't sweat the small stuff. In the majority of cases, arithmetic won't make up the lion's share of your processing time, and a decrease in readability for dubious enhancements is rarely a win. I cringe every time I see someone do something silly like convert k *= 2 to K <<= 1 or K += k and expect huge performance improvements when their code is I/O bound in the first place. :icon_rolleyes:

[gashtio]

It's always nice to see people posting tutorials, but I have to disagree with both pieces you posted.

You need not do any of these things, because that's the compiler's job - making the machine code optimal. Precalculating constants and rearranging expressions in weird ways only makes code hard to read and follow. You should write code that is easy to maintain and leave optimizations to the compiler - it usually does a better job than you would anyway :).

Here are some codes and the pertinent parts of the disassembly using MSVC 2008 and /O2 for optimization:

#include <cstdio>
#define _USE_MATH_DEFINES
#include <cmath>

double DegToRad( const double& lfDeg )
{
	return lfDeg * (M_PI / 180.0);
}

int main()
{
	double lfDeg = 0.0;

	scanf( "%lf", &lfDeg );
	double lfRad = DegToRad( lfDeg );

	printf( "%lf\n", cos( lfRad ) );

	return 0;
}

double lfRad = DegToRad( lfDeg );
00BF1023  fld         qword ptr [esp+40h]				// push lfDeg on top of the FPU stack
00BF1027  fmul        qword ptr [__real@3f91df46a2529d39 (0BF2110h)] 	// multiply top of FPU stack with 0.017453... (0x3f91df46a2529d39 in memory)

The compiler premultiplied M_PI / 180.0 and inlined the function without even hinting.

...
int a, b, c, d;
scanf( "%d %d %d %d", &a, &b, &c, &d );

int res = a * b + a * c + a * d;

printf( "%d\n", res );
...

00CC1022  mov         ecx,dword ptr [esp+14h] 	// load b into ecx
00CC1026  mov         edx,dword ptr [esp+18h] 	// load c into edx
00CC102A  add         ecx,edx 			// store b+c into ecx

	int res = a * b + a * c + a * d;

	printf( "%d\n", res );
00CC102C  add         ecx,dword ptr [esp+1Ch] 	// add d to the sum of b+c into ecx
00CC1030  imul        ecx,dword ptr [esp+20h] 	// multiply b+c+d by a

Optimized for add s by grouping all the possible addends since imul is more expensive.

int k, t, s;
scanf( "%d %d", &k, &t );
k *= 2;
t *= 32; // random power of 2
s = k + k + k + k + k + k + k + k + k + k + k; // 11 * k
printf( "%d %d %d\n", k, t, s );

k *= 2;
00281018  mov         ecx,dword ptr [esp+0Ch]	// load k into ecx
	t *= 32; // random power of 2
0028101C  mov         eax,dword ptr [esp+10h] 	// load t into eax
00281020  add         ecx,ecx 			// double k ( k *= 2 )
	s = k + k + k + k + k + k + k + k + k + k + k; // 11 * k
00281022  mov         edx,ecx 			// load the doubled value of k into d
00281024  imul        edx,edx,0Bh 		// load the product of the doubled k and 11 (0Bh) into edx
	printf( "%d %d %d\n", k, t, s );
00281027  push        edx  			// this is for the printf, unrelated
00281028  shl         eax,5 			// use a shift to multiply t by 32

The k *= 2 is made into an add for better performance;
the t *= 32 is made into a left shift;
the 11 additions of k has been reduced to a single multiplication.

So there you go, have some faith in the compiler, it does a lot of things for you.

[Nick Evan]

I have to agree with the things said above: a lot of optimization will result in poorly readable and hard-to-maintain code.
However , I think that learning these things can be useful, especially when you're writing C(++) for (older) micro-controllers which have limited resources. It also gives you a better insight in how compilers and processors work, which is a good thing.
But above all: it's fun to tweak around with bit and bytes, even when it has no other purpose then for hobby and amusement. So keep 'em coming.
you might also like this thread, which has some useful, and some "less useful" snippets in it :)

[invisal]

Don't sweat the small stuff. In the majority of cases, arithmetic won't make up the lion's share of your processing time, and a decrease in readability for dubious enhancements is rarely a win.

I totally agree with your point; however, I just feel that it is fun to know it, and it might be useful in some rare cases.

What's the target audience?

Beginner to Intermediate C++ programmer.

You need not do any of these things, because that's the compiler's job - making the machine code optimal.

Not every compiler is as smart as Visual Studio C++.

int main()
{
	int a = 7;
	int m = 0;
	
	m = a + a + a + a + a + a + a;

	return 0;
}

GCC compiler produce

movl	$7, -4(%ebp)
	movl	$0, -8(%ebp)
	movl	-4(%ebp), %eax
	addl	-4(%ebp), %eax
	addl	-4(%ebp), %eax
	addl	-4(%ebp), %eax
	addl	-4(%ebp), %eax
	addl	-4(%ebp), %eax
	addl	-4(%ebp), %eax

#include <cstdio>
#define _USE_MATH_DEFINES
#include <cmath>

double DegToRad( const double& lfDeg )
{
	return lfDeg * (M_PI / 180.0);
}

int main()
{
	double lfDeg = 0.0;

	scanf( "%lf", &lfDeg );
	double lfRad = DegToRad( lfDeg );

	printf( "%lf\n", cos( lfRad ) );

	return 0;
}

GCC compiler produce:

__Z8DegToRadRKd:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %eax
	fldl	(%eax)
	fldl	LC0
	fmulp	%st, %st(1)
	popl	%ebp
	ret
....
....
main:
....
....
	movl	%eax, (%esp)
	call	__Z8DegToRadRKd
	fstpl	-16(%ebp)
....
....

[invisal]

But above all: it's fun to tweak around with bit and bytes, even when it has no other purpose then for hobby and amusement. So keep 'em coming.)

It's always nice to see people posting tutorials,)

Thank you guy for encouraging me.

Which amounts to rewriting your prose, I'm afraid. It's very clearly written by someone with grammar habits from another language, and those habits are hard to break with a few quick corrections. A dedicated editor with strong English writing skills would be better.

I will try to sharpen my English writing skills. The main thing that I concern is whether my English is understandable or not.

[Nick Evan]

What optimization-level are you using for GCC?

[invisal]

Shame, I was using level 0 optimization-level. With level 3 optimization-level, GCC compiler choose a very optimal way.

Still, we can't rely everything on compiler; personally, I still think we as a human know better way to optimize than compiler.

For example: m = (a + b + c) / (b + c) GCC compiler (level 3 optimization) produces

movl	-8(%ebp), %edx
	movl	-12(%ebp), %eax
	movl	-4(%ebp), %ecx
	addl	%edx, %eax
	addl	%ecx, %eax
	addl	%ecx, %edx
	movl	%edx, %ecx
	cltd
	idivl	%ecx

But the compiler is not smart enough to change: m = (a + b + c) / (b + c) to m = a/(b + c) + 1; so that we can produce:

movl	-8(%ebp), %eax
	movl	-4(%ebp), %edx
	addl	%eax, %edx
	movl	-12(%ebp), %eax
	movl	%edx, %ecx
	cltd
	idivl	%ecx
	incl	%eax

[invisal]

4th Piece: Logical Operator

We are going to do little experiment on Logical Operator. First we will define two functions that will be used throughout the experiment.

bool func1()
{
    std::cout << "Function 1 is called.\n";
    return true;
}

bool func2()
{
    std::cout << "Function 2 is called.\n";
    return false;
}

Experiment 1:

int main()
{
    if (func2() || func1());
    return 0;
}

Output:
Function 2 is called.
Function 1 is called.

Experiment 2:

int main()
{
    if (func1() || func2());
    return 0;
}

Output:
Function 1 is called.

In second experiment, function 2 is not called because if the first condition is true regardless of what second condition is, the whole condition will be true. So, if you use OR logical operator, it is best to put condition which is more likely to be TRUE first rather than to put condition which is more likely to be FALSE first.

Experiment 3:

int main()
{
    if (func1() && func2());
    return 0;
}

Output:
Function 2 is called.
Function 1 is called.

Experiment 4:

int main()
{
    if (func2() && func1());
    return 0;
}

Output:
Function 2 is called.

Logically, if the first condition is false regardless of what second condition is, the whole condition will be false. So, if you use AND logical operator, it is best to put condition which is more likely to be FALSE first rather than to put condition which is more likely to be TRUE first.

(I skip 3rd piece, because I still want to revise it one more time)

[Narue]

>I still think we as a human know better way to optimize than compiler.
I recall an experiment not too long ago where a modern C compiler did a better job optimizing into assembly than assembly programmers writing directly in assembly.

The conclusion was twofold:

1. Don't presume that a human is better at optimization than a compiler unless that human is unusually skilled and attentive (it took an expert assembly programmer and more effort than he normally expended on optimization to beat the compiler).
2. Trying to optimize manually is more likely to confuse the compiler and result in worse machine code than writing simply and letting the compiler optimize for you.

[invisal]

I recall an experiment not too long ago where a modern C compiler did a better job optimizing into assembly than assembly programmers writing directly in assembly.

It is a little bit irrelevant to my point. What I am trying to say is that C compiler is more likely to produce better optimized machine code when optimize the well-optimized C code than when optimize unoptimized C code.

[tux4life]

The main thing that I concern is whether my English is understandable or not.

Your English is understandable.

[Narue]

>C compiler is more likely to produce better optimized machine
>code when optimize the well-optimized C code than when optimize unoptimized C code.
That's not necessarily the case. Please read the second conclusion about how "well-optimized C code" can confuse the optimizer and produce worse results.

[invisal]

That's not necessarily the case. Please read the second conclusion about how "well-optimized C code" can confuse the optimizer and produce worse results.

I cannot totally agree with you or totally disagree with you because there is no clear definition of "well-optimized C code".

In conclusion (like what Narue has concluded that it was twofold):

• Compiler optimize our code based on rules that are written by very skilled programmer. It probably can optimize better than ton of programmers here.
• However, human is more flexible and can sometimes optimize beyond the compiler written rules such as changing to more efficient
  algorithm. Furthermore, we, programmers, know our own program more than what compiler could see.

Next time when I try to deliver these two items, I will make sure to include these messages to the readers, and I will mark these two items as "a unnecessary thing to know, but fun just to know"

I have not received feedback of my 4th item. I will take it as an acceptable item and resume to my next item shortly.

[invisal]

5th Piece : Ordering Your Condition

When dealing with multiple else if conditions, it is good practice to check the least expensive condition and condition which has high chance of being FALSE first.

For example:

John wrote a simple online chat server. User can send message to each other by using command SEND and admin users have special ability to send message to every online user by using command SENDALL . However, the message must not excess 200 characters long.

if (strcmp(cmd,"SEND") == 0) {
        // ....
        // ....
        // ....
    } else if (strcmp(cmd,"SENDALL") == 0) {
        if (strlen(msg) > 200) {
            // message is too long
        } else if (user.access == ACCESS_ADMIN) {
            // you do not have privilege to use this command
        } else {
            // send to everyone.
        }
    }

The code works fine. Then, John questioned himself whether it is best to check user.access == ACCESS_ADMIN first or to check strlen(msg) > 200 first. Firstly, user.access == ACCESS_ADMIN is the least expensive condition. Secondly, there are more regular users than admin users, chance that regular users attempt to use SENDALL command is high. So, chance of user.access == ACCESS_ADMIN being false is relatively high.

Hence, user.access == ACCESS_ADMIN should be checked first.

} else if (strcmp(cmd,"SENDALL") == 0) {
        if (user.access == ACCESS_ADMIN) {
            // you do not have privilege to use this command
        } else if (strlen(msg) > 200) {
            // message is too long
        } else {
            // send to everyone.
        }
    }