Why are these calculations so slow to be performed?

[AlTech]

So I wanted to make a stress test and I did. I made it calculate Pythagoras 1.1 million times.

 

And I set it up so that it counts how long It takes to calculate this.

 

Why is it taking ,a quad core i5, 110 Seconds to finish it?

 

This seems so slow.......

[Doh007]

because it has to do it 1.1 million times

[AlTech]

Just now, Doh007 said:

because it has to do it 1.1 million times

But a CPU should be able to output at least 800 Million calculations per second if it is 800Mhz........... This is 3.2GHz so theoretically it should be able to do this in less than a second..............

[Doh007]

Just now, AluminiumTech said:

But a CPU should be able to output at least 800 Million calculations per second if it is 800Mhz........... This is 3.2GHz so theoretically it should be able to do this in less than a second..............

actually it can theoretically do more than that due to it assigning several instructions per clock, but assuming that what you're talking about is a^2+b^2=c^2, it will have to do many operations on each "pythagoras".

[AlTech]

Just now, Doh007 said:

actually it can theoretically do more than that due to it assigning several instructions per clock, but assuming that what you're talking about is a^2+b^2=c^2, it will have to do many operations on each "pythagoras".

.......... If I use random numbers each time, will it affect the speed?

[_JohnB330ci]

Just now, AluminiumTech said:

.......... If I use random numbers each time, will it affect the speed?

Each Pythagoras runthrough is more than 1 calculation, and choosing a random number is even more. 

[ThinkWithPortals]

8 minutes ago, AluminiumTech said:

But a CPU should be able to output at least 800 Million calculations per second if it is 800Mhz........... This is 3.2GHz so theoretically it should be able to do this in less than a second..............

Calculating Pythagoras' Theorum even once takes far, far more than one calculation.

And yes, choosing random numbers should slow it down even more.

[Doh007]

7 minutes ago, AluminiumTech said:

.......... If I use random numbers each time, will it affect the speed?

to some degree, but also consider that it might not be able to fully utilize all 4 cores of your CPU.

[AlTech]

2 minutes ago, Doh007 said:

to some degree, but also consider that it might not be able to fully utilize all 4 cores of your CPU.

I know it's only using 1 core .

[Nineshadow]

Are you by any chance printing the results each iteration?

Because something like this :

#include <iostream>
#include <fstream>
#include <random>
#include <chrono>
float a, b, c;
int main()
{
	std::random_device rd;
	std::mt19937 mt(rd());
	std::uniform_real_distribution<double> dist(0.0, 1999999973.0);
	std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
	for (int i = 0; i < 1100000; ++i)
	{
		a = dist(mt), b = dist(mt);
		c = a*a + b*b;
	}
	std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
	std::cout << "Time : " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << std::endl;
	std::cin.get();
    return 0;
}

Takes me around ~750000 microseconds. But going with random numbers each time isn't exactly a great way of doing it, since results can vary a lot.

[AlTech]

1 minute ago, Nineshadow said:

Are you by any chance printing the results each iteration?

Because something like this :

#include <iostream>
#include <fstream>
#include <random>
#include <chrono>
float a, b, c;
int main()
{
	std::random_device rd;
	std::mt19937 mt(rd());
	std::uniform_real_distribution<double> dist(0.0, 1999999973.0);
	std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
	for (int i = 0; i < 1100000; ++i)
	{
		a = dist(mt), b = dist(mt);
		c = a*a + b*b;
	}
	std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
	std::cout << "Time : " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << std::endl;
	std::cin.get();
    return 0;
}

Takes me around ~750000 microseconds. But going with random numbers each time isn't exactly a great way of doing it, since results can vary a lot.

I'm doing it in C#, And I'm square rooting it at the end just like Pythagoras is done in real life.........

[Nineshadow]

10 minutes ago, AluminiumTech said:

I'm doing it in C#, And I'm square rooting it at the end just like Pythagoras is done in real life.........

Whops, silly mistake.

Anyway, I've made a dataset of randomly generated real numbers in a uniform distribution between 0 and 1999999973 and it takes around 60000 microseconds for the calculations to be done.

#include <iostream>
#include <fstream>
#include <random>
#include <chrono>
std::ifstream in("database.in");
float a[1100000], b[1100000], c;
int main()
{
	std::cout << "Loading dataset...\n";
	for (int i = 0; i < 1100000; ++i)
	{
		in >> a[i] >> b[i];
	}
	std::cout << "Done loading dataset\n";
	std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
	for (int i = 0; i < 1100000; ++i)
	{
		c = sqrt(a[i]*a[i] + b[i]*b[i]);
	}
	std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
	std::cout << "Time for calculations : " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << std::endl;
	std::cin.get();
    return 0;
}

 

[AlTech]

2 minutes ago, Nineshadow said:

Whops, silly mistake.

Anyway, I've made a dataset of randomly generated real numbers in a uniform distribution between 0 and 1999999973 and it takes around 60000 microseconds for the calculations to be done.

#include <iostream>
#include <fstream>
#include <random>
#include <chrono>
std::ifstream in("database.in");
float a[1100000], b[1100000], c;
int main()
{
	std::cout << "Loading dataset...\n";
	for (int i = 0; i < 1100000; ++i)
	{
		in >> a[i] >> b[i];
	}
	std::cout << "Done loading dataset\n";
	std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
	for (int i = 0; i < 1100000; ++i)
	{
		c = sqrt(a[i]*a[i] + b[i]*b[i]);
	}
	std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
	std::cout << "Time for calculations : " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << std::endl;
	std::cin.get();
    return 0;
}

 

You're using C++ though......

[Nineshadow]

1 minute ago, AluminiumTech said:

You're using C++ though......

It shouldn't make much of a difference tbh.

Are you by any chance printing the numbers in each iteration of the loop? That would explain why it takes you so long.

[Nineshadow]

Jeez, another rookie mistake. I was compiling my program in Debug mode.

 

Release version takes around ~600 nanoseconds.

[AlTech]

3 minutes ago, Nineshadow said:

It shouldn't make much of a difference tbh.

Are you by any chance printing the numbers in each iteration of the loop? That would explain why it takes you so long.

............................

 

That was embarrassing................. After I fixed it, it took 3 seconds to do 2 million calculations....

[Nineshadow]

4 minutes ago, AluminiumTech said:

............................

 

That was embarrassing................. After I fixed it, it took 3 seconds to do 2 million calculations....

Told you.

[mathijs727]

 

6 hours ago, Nineshadow said:

Jeez, another rookie mistake. I was compiling my program in Debug mode.

 

Release version takes around ~600 nanoseconds.

600ns is way too short (1800 cycles at 3GHz).

 

Seems like something else is going on:

In release mode the whole calculation will get optimized away because the result (variable c) is disgarded.

Make an additional array "c" and store the results there, that should hopefully get rid of the compiler optimization.

[Unimportant]

2 hours ago, mathijs727 said:

Make an additional array "c" and store the results there, that should hopefully get rid of the compiler optimization.

Or just make the result variable volatile.

[Nineshadow]

2 hours ago, mathijs727 said:

 

600ns is way too short (1800 cycles at 3GHz).

 

Seems like something else is going on:

In release mode the whole calculation will get optimized away because the result (variable c) is disgarded.

Make an additional array "c" and store the results there, that should hopefully get rid of the compiler optimization.

I was thinking about something about those lines but didn't go further with since I had to go into town.

But yup, that's the reason.

It's around 3000 microseconds now.

[Unimportant]

sqrt(a[i]*a[i] + b[i]*b[i]);

 might be too complex for the compiler to vectorize. Try performing 

a*a + b*b in their own loop and store the results to another array before taking the square root. 

[Nineshadow]

1 hour ago, Unimportant said:

sqrt(a[i]*a[i] + b[i]*b[i]);

 might be too complex for the compiler to vectorize. Try performing 

a*a + b*b in their own loop and store the results to another array before taking the square root. 

I was kinda wondering if that could happen and I tested it out. And as I expected, nope, it's actually slower. Compilers are really smart these days.

[mariushm]

Replace that sqrt  with one of the alternative square root functions that gives you enough precision for your needs but is much faster than the default one : http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

 

You should try to use at least Intel Threading Building Blocks to parallelize your code to run on all cores: https://software.intel.com/en-us/node/506045

 

 

 

 

[mathijs727]

3 hours ago, mariushm said:

Replace that sqrt  with one of the alternative square root functions that gives you enough precision for your needs but is much faster than the default one : http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

 

You should try to use at least Intel Threading Building Blocks to parallelize your code to run on all cores: https://software.intel.com/en-us/node/506045

 

 

 

 

Why use Intel Threading Blocks?

Easiest way to parallize this code is to use OpenMP.

That requires you to add the line "#pragma omp parallel for" before the for loop.

Thats it, if you now compile it with OpenMP flag it is magically parallel.

 

NOTE: only do this if the result variable C is an array

[mariushm]

Intel TBB was the first thing that came to mind. I guess OpenMP could be just as good for this particular case or you could just code your own thread pool with a bunch of threads that basically do only that square root and return the result.

Both have issues, it's enough to search for openmp vs tbb and you'll find plenty of answers.