# Calculating primes: Could this be any faster?

I've ported a prime-number calculation program from primes.pyx to C++ for benchmark purpose.

Since I wrote it in C++, I thought that my program would be faster than the original. However, mine took 25.8 ms at the fastest, while the original took only 1.45 ms on the same machine. I tested 10 times each, but got similar results (25.8~51.7ms vs 1.45~1.47ms). But, why?

Here's my code:

#include <iostream>
#include <vector>
#include <chrono>
using namespace std;

vector<int> primes(size_t nb_primes)
{
int n;
vector<int> p;
p.reserve(nb_primes);

n = 2;
while (p.size() < nb_primes)
{
bool other = true;
for (size_t i = 0; i < p.size(); i++)
{
if (n % p[i] == 0)
{
other = false;
break;
}
}
if (other)
p.push_back(n);
n += 1;
}
return p;
}

int main()
{
auto start = std::chrono::high_resolution_clock::now();

vector<int> p = primes(1000);
//for (auto i : p)
//    cout << i << ' ';

auto finish = std::chrono::high_resolution_clock::now();

std::chrono::duration<double> elapsed = finish - start;
std::cout << "Elapsed Time: " << elapsed.count() << " s\n";
}


These algorithms are exactly the same, I believe.
Please don't limit the check up to sqrt(n), to achieve a sieve of Eratosthenes.
I need to compare with the original.

One thing I'm worried is the for ... else statement in the original.
I borrowed the idea to use the other flag from Username: haccks.
If you can apply another for ... else method, please go ahead.

My Windows 10 machine (i5) spec:
Clock Frequency: 1.60GHz 1.80GHz
Memory: 8.00GB

I wrote the original version on Anaconda Prompt/Python 3.8.
I write the C++ version on Visual Studio 2019.

• What compiler optimisation options are you using? It completes in 1ms for me with g++ -O3. Jun 12 '20 at 16:49
• You tagged this benchmarking, but how did you benchmark it? What optimizers on what system?
– Mast
Jun 12 '20 at 18:13
• @gmath I see! Thanks to you, I've just got Elapsed Time: 0.0014516 s! Please make it an answer; so I will accept it. Firstly, I was running in Debug Mode (sorry). Changing to Release Mode made it 2~7ms. Then, I set Favor Size Or Speed as Favor fast code (/Ot). It made 1.45ms! Thank you sooo much! Jun 12 '20 at 18:36

There are some optimizations that can make your code better, even with compiler optimizations turned on:

Pre-allocate the vector and treat it like an array.

Use a variable to keep track of the length.

Putting these together, I found about a 10% increase in speed:

vector<int> primes(size_t nb_primes)
{
vector<int> p(nb_primes,2);
int n = 2;
size_t len_p = 0;
while (len_p < nb_primes)
{
bool other = true;
for (size_t i = 0; i < len_p; i++)
{
if (n % p[i] == 0)
{
other = false;
break;
}
}
if (other)
p[len_p++] = n;
n += 1;
}
return p;
}

• You're right, you improved 11.0% on average. In addition, your version is closer to the original since you introduced the variable len_p. vector<int> p(nb_primes,2); was new to me. It seems it's called Expression List. I'll learn these techniques. Thank you so much! / Primes by me / # of Tests: 100 / Average: 0.00141529 / Minimum: 0.0012612 / Maximum: 0.0023088 / Median: 0.0013155 / Primes by tinstaafl / # of Tests: 100 / Average: 0.00127456 / Minimum: 0.0012637 / Maximum: 0.0016251 / Median: 0.0012686 Jun 13 '20 at 14:23

The code is not the cause of the slow down

Since I wrote it in C++, I thought that my program would be faster than the original. However, mine took 25.8 ms at the fastest, while the original took only 1.45 ms on the same machine.

I get about 1ms when compiling with g++ -O3. So the code is achieves your goal of performing (at least as) well as the .pyx code, it must be your compilation options. C++ compilers often do not turn on optimisations by default. When bench-marking code ensure that you are compiling your code with optimisations on.

As you mention there are optimisations that can be applied to the code, such as using sqrt(n), which you won't use because you "need to compare with the original". Your code seems to be already as optimised as the .pyx, so any further optimisations may impair the comparison. You could avoid using using namespace std;, however, which is not usually recommended as using an entire name space can result in name collisions.

• This does not provide insight about the code in the question. And it does little to improve microbenchmarking skills or know-how. Jun 13 '20 at 5:52
• @greybeard Perhaps, but it is correct answer to the question asked (Why is my C++ code slower than '.pyx'). And the OP specifically asked not to optimise the algorithm past the .pyx code. Arguably this is the wrong site to ask the question, but the OP didn't know that till I answered. Jun 13 '20 at 6:00
• I was the only one to make the observation that the code wasn't the problem. Jun 13 '20 at 6:07
• That link mentions that short answers are fine, but using namespace std; is not recommended I guess. Jun 13 '20 at 6:47
• @IanHacker It isn't always possible to avoid the XY problem, e.g asking for code optimisation when code isn't the cause; the recommendation is to give enough information to find the real problem (meta.stackexchange.com/questions/66377/what-is-the-xy-problem). In this case you gave a complete working example together with your expected and actual result. Answering this question was fairly easy, so I think this is a relatively good question. Jun 13 '20 at 15:28