C++ Question

[Clete2]

Well, I'm writing a program that I wish to display its status when it is taking longer than usual. I'm doing a loop that is doing hundreds of repetitions per second. In the loop, I currently have this line:

Code: Select all

			if(tries % 10000000 == 0){
			     cout << "Current tries: " << tries << "\r";
			}

The problem is: Wouldn't this be doing a couple MORE hundred calculations per second in order to find out if fries % ... == 0? How can I just do a simple counter to update the status each second without doing hundreds of calculations to see if time(0) has incremented?

[tarpman]

Without getting into threading, I doubt it.

[Clete2]

Without getting into threading, I doubt it.

I hear threading is complicated.. I haven't gotten quite that far yet.

I assume I'm right in saying that computing `tries % 10000000 == 0` is severly slowing down my process? I wish I could just make it do it once a second.. on some sort of timer.

If I do `time(0) % 10 == 0` then it prints out a bunch of tries for a second every ten seconds. So that isn't my solution...

[barophobia]

mod
branch if equal

That is alot of calculations!

Pipeline stalling is not a problem because branch prediction is usually going to be right.

Stop worrying about it.

you can be cute and do something like

Code: Select all

for( i=0; i < 10; i++)
{
  for( tries=0; tries < 100000000; tries++)
  {
    do stuff
  }
  cout << "blah blah blah\r";
}

[Phenax]

Threading is actually pretty easy, and efficient w/pthreads. Should only be like 5-10 lines of code to launch a new thread for it, at the most.

[codergeek42]

Maybe boost::timer would help with this?

[tarpman]

Maybe boost::timer would help with this?

Eek! Boost zombies! BEGONE!!

[Clete2]

mod
branch if equal

That is alot of calculations!

Pipeline stalling is not a problem because branch prediction is usually going to be right.

Stop worrying about it.

you can be cute and do something like

Code: Select all

for( i=0; i < 10; i++)
{
  for( tries=0; tries < 100000000; tries++)
  {
    do stuff
  }
  cout << "blah blah blah\r";
}

Well, here is the current block. That's not exactly what I need..

Code: Select all

	for(int i = 0; i < repetitions; i++){

		int tries = 0; // Keeping a running tab on the number of tries in the individual test.
		do{ // Using do...while so the loop will execute at least once
			findPhrase = kitty.giveString(); // Getting a string that has the number of letters that the user wants
			tries++;

			//if(tries % 10000000 == 0){
			//	cout << "Current tries: " << tries << "\r";
			//}

		}while(findPhrase != realPhrase); // If findPhrase is not equal to givenPhrase, then keep going

		if(tries > maximumTries){ // These two if statements keep track of the minimum number of tries and the maximum number of tries
			maximumTries = tries;
		}
		if(i == 0){
			minimumTries = tries;
		}else if(tries < minimumTries){
			minimumTries = tries;
		}

		totalTries += tries;

		cout << "It took " << setw(realPhrase.length() * 2) << tries << " tries to find the letters " << realPhrase << "." << endl;	 // We move the column over the length of the string * 2 so that it's all in a nice row.

	}

I will look into boost::timer later. I had a flu shot today and I feel extremely sick.

[bunder]

Moved from Off the Wall to Portage & Programming.

[Clete2]

Moved from Off the Wall to Portage & Programming.

Sorry.... I forgot that it's Portage & Programming

[barophobia]

That if mod equal is not a significant amount of code in that loop. Most of it is taken up in generating the string and string matching.

Here is the threading approach

start statusthread
loop do your thing update tries
stop statusthread

statusthread:
sleep x seconds
copy the #tries
print your copy of #tries

Notice I did not lock the #tries variables so it might change in the middle of your copy operation! This is fine since it is a counter and it doesn't change that much, even in the rare occasion where change does matter so what. Locking will add even more overhead which you don't want.

The context switching with threading might be even more overhead but hey what do i know.

[timeBandit]

Optimize only when and where it makes sense to optimize. It's quite possible the contribution of your counter check (tries % 100000000) to the loop time is dwarfed by the time spent in the real work of the loop (kitty.giveString() and so on). Absent profiling data to prove otherwise, fretting over the performance of that check would be teaching a pig to sing (wastes your time and annoys the pig).

That said, since you're not looking for precise update intervals, just an "I'm not dead" progress signal, do this:

Code: Select all

if ((tries & 0x3FFFFFF) == 0) {
  cout << "Current tries: " << tries << "\r";
}

The compiler can emit a simple set of shift and mask instructions for that, which will be crazy-fast compared to a full-blown modulus by a non-power-of-two divisor.

(Why 0x3FFFFFF? It's the largest integer not greater than 100000000 (your original interval) whose binary representation is a contiguous run of 1 bits. Add or remove bits to double/halve the notification interval. )

[Edit: got distracted between "Preview" and "Submit," I see barophobia agrees.... ]

[barophobia]

Code: Select all

if ((tries & 0x3FFFFFF) == 0) {
  cout << "Current tries: " << tries << "\r";
}

]

Oops forgot about the bitshift/and operation tricks.

Ok now to make the problem more complicated than is needed because I am a geek and that is what geeks do.

On a smp machine threading will save you time but it is a sad waste of a core. This is assuming that you have something that keeps your cache from going stale like a snooping cache. Just make sure that there is nearly no synchronization between the two cores.

But seriously I don't get why people micro-optimize at this level, it is just silly.

[Akkara]

Adding some ideas to the mix:

Keep a sentinel. Fast (just one 'if') and works for any N not just powers of 2:

Code: Select all

next_update = N;
do{
         findPhrase = kitty.giveString();
         tries++;
         if(tries >= next_update) {
            cout << "Current tries: " << tries << "\r";
            next_update = tries + N;
         }
}while(findPhrase != realPhrase);

Roll the update with the exit condition. Testing two low-probability events simultaneously is better than one at a time.

Code: Select all

next_update = N;
do{
         do{
                  findPhrase = kitty.giveString();
                  tries++;
         }while((tries < next_update) && (findPhrase != realPhrase));
         cout << "Current tries: " << tries << "\r";
         next_update = tries + N;
}while(findPhrase != realPhrase);

A decent optimizing compiler should be able to generate only one conditional test for the inner loop above (I didn't check whether gcc does so currently). If it is really critical I've sometimes seen the conditional coded arithmetically, ((tries - next_update) & (findPhrase - realPhrase)) != 0 but this is not recommended unless extensive profiling shows it to be the hotspot and the compiler is otherwise braindead.

And what the posters above said, most likely it doesn't matter to microoptimize such a loop. Still a interesting question however, and the knowledge gained from simple things like this does carry forward and will be there at the ready for when it really does matter.

[mv]

Oops forgot about the bitshift/and operation tricks.

You also do not have to remember them: It should be sufficient to replace your number by a power of two - since this is a constant, any reasonable compiler will translate the mod into the corresponding and-operation if the processor can really do this faster.

[mv]

Roll the update with the exit condition. Testing two low-probability events simultaneously is better than one at a time.

Why? (Note that there is an && not an ||). On assembler level it translates into two tests anyway. At least the "straightforward" translation into assembler of the above code examples is identical (except that the second example has even an additional test in the outer loop).

[Akkara]

It should be sufficient to replace your number by a power of two - since this is a constant, any reasonable compiler will translate the mod into the corresponding and-operation if the processor can really do this faster

Actually, it is more than just a mask, as seen with:

Code: Select all

echo "int main(int ac,char **av) { return ac % 16; }" | cc -x c -S -O2  - -o - | sed -n '/^main/,/ret/p'

Then try changing the int to unsigned. That generates the expected mask. (Another interesting tidbit: -Os generates a idiv for the integer case.)

The reason for that behavior, is way back when, someone had the brilliant idea that negative numbers modulo a positive divisor should return negative answers -- contrary to every mathematics text ever written. In (some) fairness however, this was sort-of forced because of the way integer division was defined to chop toward zero regardless of the sign of operands: integer a / b == sign(a) * sign(b) * floor(abs(a) / abs(b))


[rant on]
So totally logical patterns get broken. For example, let's say you're counting down from 1000 mod 10. What do you get? 1000, 999, 998, 997, ... becomes 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, and so on. That pattern of 9,8,7,6,5,4,3,2,1,0 repeats -- until you get to 0, then it goes, 2, 1, 0, -1, -2, -3, ..., -9, 0, -1, -2, ... So what would have been an easy invariant - once initialized, the modulo counter is independent of the loop variable - isn't because of the special behavior around 0 requires the loop counter to be taken into consideration. Of course few programmers in the heat of writing are actually consciously thinking of such things and what happens is you get either code that fortuitously happens to work regardless since numbers are usually positive, or else a subtle bug.

Even the motivating idea of division truncating toward 0 is suspect. Let's say you want to round to nearest. Countless times I've seen code that adds 1/2 of what you're dividing by: z = (x + y/2) / y. Works, doesn't it? Well, yes, if x and y are positive. But what is -9/10, rounded. Should be -1. But (-9 + 10/2)/10, truncated, is (-9 + 5)/10 = -4/10, truncated, = 0, which is wrong. For correct operation, one needs to add either +y/2 or -y/2 depending on the sign of x. Which puts a conditional in what should have been a purely arithmetic statement. Or else, easier, one uses unsigned and handles the sign themselves, manually.

[aside]: I've often also seen attempts to "round" floats to ints with code like float x; ... int i = x + 0.5;, which also doesn't work for the case of negative x for similar reasons. (Instead, use lrint for rounded float -> int conversion.)

I avoid division and modulus like the plague for these reasons. The few times I can't avoid it, my code is littered with conditionals to test and deal with cases such as these introduced by less-than-mathematical definitions.
[/rant]

On assembler level it translates into two tests anyway.

A quick test...

Code: Select all

echo "int main(int ac,char **av) { return ac < 5 && av != 0; }" | cc -x c -S -O2  - -o - | sed -n '/^main/,/ret/p'

...suggests that it generates only one branch. The reason is that, even though && has early-stop semantics, since there are no side-effects in the 2nd expression, there's no harm in evaluating it.

This, however, needs early-stop, since there's no guarantee that ac[1] and ac[2] can be referenced if the first part isn't true:

Code: Select all

echo "int main(int ac,char **av) { return ac > 2 && av[1] != av[2]; }" | cc -x c -S -O2  - -o - | sed -n '/^main/,/ret/p'

Edit: adjusted the c-code expressions to be slightly more real-worldish (doesn't change any of the results).

[mv]

The reason for that behavior, is way back when, someone had the brilliant idea that negative numbers modulo a positive divisor should return negative answers

I was not aware that the standard declares mod by mathematical nonsense which is even harder to calculate. Last time I checked, this was implemented properly (but I admit that my last check is many many years ago). Usually, I don't have this problem since I don't use signed numbers - in most cases they are useless. One just has to get the habit to use e.g. the appropriate types for loop counters instead of the stupid "int". Of course, in the above case the proper solution would be also to give tries the correct (unsigned) type.

In (some) fairness however, this was sort-of forced because of the way integer division was defined to chop toward zero regardless of the sign of operands: integer a / b == sign(a) * sign(b) * floor(abs(a) / abs(b))

I don't see the connection with the mod-sillyness: Implementation of division (be it on assembler or sub-assembler level) needs probably case distinctions anyway - so on the same level one could calculate a correct mod in the corresponding case.

...suggests that it generates only one branch.

Thanks, now I understand what you mean. So the generated code is not what one would obtain by a "straightforward" translation of the C code: Statistically, it appears to be cheaper to do a test in vain than to have a branch (even although branch prediction might be correct). After thinking about it, this sounds reasonable.

[Akkara]

I was not aware that the standard declares mod by mathematical nonsense which is even harder to calculate.

I incorrectly used the word "standard" in my previous post, which is too strong a word to describe the situation.

To clarify:

C doesn't completely prescribe what happens when negative operands are divided using integer division. The intent is to allow the compiler to use the undelying hardware instruction wherever possible.

What C *does* require, is, if q = y / x and r = x % y,
-> that x == q * y + r, for all x, y and y != 0
-> and that 0 <= q < y when x, y positive

Both of these makes sense. The first requires that the quotient times the divisor, plus the remainder, must always be equal to the dividend. The second, that the remainder is less than the divisor, at least for positive arguments. Together, they remove a degree of freedom: If division is defined in a particular way, modulus is forced, namely, x % y == x - y * (x / y). Likewise if modulus is defined then division is forced.

The unfortunate defacto-standard of integer division, from back in the days of fortran, is to divide the magnitude of the operands, and then adjust the sign afterwards. This results in the classic "round-toward-zero" behavior, illustrated here dividing by 3:

Code: Select all

x:           9  8  7  6  5  4  3  2  1   0  -1 -2 -3 -4 -5 -6 -7 ...
q = x/3:     3  2  2  2  1  1  1  0  0   0   0  0 -1 -1 -1 -2 -2 ...

There's already a hint that there's something strange going on: notice that each quotient appears 3 times - except for 0, which appears 5 times!

The problem becomes evident when we enforce the remainder + product of quotient and divisor" rule. This rule forces the mod to be what it is:

Code: Select all

x:           9  8  7  6  5  4  3  2  1   0  -1 -2 -3 -4 -5 -6 -7 ...
q = x/3:     3  2  2  2  1  1  1  0  0   0   0  0 -1 -1 -1 -2 -2 ...
3 * y:       9  6  6  6  3  3  3  0  0   0   0  0 -3 -3 -3 -6 -6 ...
r = x - 3*q  0  2  1  0  2  1  0  2  1   0  -1 -2  0 -1 -2  0 -1 ...

If we want modulus to always return positive remainders when the divisor is positive, like mathematics texts says, it would require negatives to be handled differently in division:

Code: Select all

x:           9  8  7  6  5  4  3  2  1   0  -1 -2 -3 -4 -5 -6 -7 ...
x % 3:       0  2  1  0  2  1  0  2  1   0   2  1  0  2  1  0  2
x - x%3:     9  6  6  6  3  3  3  0  0   0  -3 -3 -3 -6 -6 -6 -9
q            3  2  2  2  1  1  1  0  0   0  -1 -1 -1 -2 -2 -2 -3

Notice that each quotient now appears 3 times. The remainder cycle progresses cyclically with no interruption. 0 is no longer a special point where strange things happen. And properly rounded x/y can always be had with (x + y/2)/y.

This integer division is floor( (double)x / y )

Unfortunately, human nature (as well as a massive code-base) generally supports the old definition. When casually asked, "what is the best answer to integer -7 / 3", I think that most people will answer "-2", and not "-3". Unfortunately, the cycle of work to implement division like previously done, followed by work complicating one's code to get around the parts that don't work (or worst - coding in oblivion of the issues and introducing subtle bugs) continues.

(But interestingly, the Haskel language does define integer division and modulus as advocated here.)

[mv]

It is clear that the cause is that the C standard defines % to be the reminder (of the division) and not as the mod. But this is the stupidity IMHO, because in most application a mod is required and not a reminder (actually, in the moment, I cannot think of even one application where the reminder might be useful). Anyway, we will not be able to change the standard now...