odd behavior on simple program (factorials)

[lancekimbrough]

I'm trying to get a grasp of TBB, so I started out by writing a simple program to calculate the factorial of i, from i=0 to n. I've been working with the GNU MP (bignum) library, so I decided to use it as well to handle the large factorials. I'm really just looking to get a simple program to behave properly...but I'm having some difficulties with it. When I run the following code (printing out the "i" in the parallel loop), I get some very strange results....

[cpp]#include 
#include 
#include 
#include 
#include "tbb/task_scheduler_init.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"


using namespace tbb;
using namespace std;


class factorial {
public:
	void operator()( const blocked_range& range ) const {
		// mpz object to store factorial
		mpz_class fact_result;

		for( double i=range.begin(); i<=range.end(); i++ ) {
			// perform factorial on i
			mpz_fac_ui(fact_result.get_mpz_t(), i);   
			cout << i << "n";
		}
	}
};


// define function ParallelFactorial
void ParallelFactorial(int n) {
	// new factorial object called fact
	factorial fact;  
	parallel_for( blocked_range(0, n, 1000 ), fact );
}


int main() {
	task_scheduler_init init;

	// Max number to apply factorial
	int b=5000; 
	
	clock_t start = clock();  // start clock for parallel test
	ParallelFactorial(b);     // apply parallelfactorial up to b
	clock_t end = clock();    // find end time for parallel test
	double time_elapsed = double(end-start)/CLOCKS_PER_SEC;  // calculate elapsed time in parallel
	cout << "time to run in parallel: " << time_elapsed <<"n";
	

	/*-----------------------------begin serial test-------------------------------------*/

	clock_t start_serial = clock();  // start clock for serial test
	mpz_class fact_result_serial;    // mpz object for storing serial factorial
	
	for (int i=0; i<=b; i++ ){
		mpz_fac_ui(fact_result_serial.get_mpz_t(), i);  // perform factorial on i
		//cout << i <<"n";
		}
	clock_t end_serial = clock();   // find end time for serial test
	double time_elapsed_serial = double(end_serial-start_serial)/CLOCKS_PER_SEC;  // calc elapsed time in serial
	
	
	cout << "time to run in serial: " << time_elapsed_serial <<"n";
	
	double time_speedup=time_elapsed_serial/time_elapsed;
	cout << "time speedup: " << time_speedup;
	 
	return 0;
}
[/cpp]

When I run this particular code (with b=5000), my return is

.....

4680
4994
4681
4682
4995
4996
4997
4998
4999
5000
4683
4684
4685
4686
4687
time to run in parallel: 1.22
time to run in serial: 1.12
time speedup: 0.918033

Why is the progression of i so erratic? I'm guessing it has something to do with the multiple threads....am I missing something more fundamental here? I'm not sure what else to try? I appreciate any help.

Regards,

Lance

[RafSchietekat · Accepted solution]

"Why is the progression of i so erratic?" TBB recursively divides the range to find parallelism, like you'll see visually in the tachyon example. BTW, you include the end() of a blocked_range in the loop, which you shouldn't (neither in STL nor in TBB), but I'll leave it at that.

[Dmitry_Vyukov]

Quoting - lance.kimbrough

Why is the progression of i so erratic?

What progression do you expect? And what is wrong with this progression?

[lancekimbrough]

Well, I guess there really is nothing wrong with it, lol. I suppose I've been working in "serial" mode for so long that I didn't expect to see the "i" jumping around, but with multiple threads, it makes perfect sense. And Raf, I appreciate you letting me know not to include the end() of the blocked_range in the loop. I've never worked with the STL or any template library before, so I'm learning as I go. I still have much to learn :) Thanks again for the input!

Best Regards,

Lance