0

I'm having some speed issues with my c++ program. A similar python project is 5x as fast, and that doesn't seem right. Can anyone tell me if I've done a grave mistake?

#include <iostream>

void prime(int limit) {
    std::cout << 2 << std::endl;
    bool isPrime;
    for (int i = 3; i < limit; i = i + 2) {
        isPrime = true; 
        for (int j = 2; j < i; j = j +1) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime){
            std::cout << i << std::endl;
        }
    }
}

int main()
{
    int limit = 100000;
    prime(limit);
}

The compared python code is the following;

import time
def prime(limit):
    start_time = time.time()
    print(2)
    for i in range(3, limit, 2):
        is_prime = True
        for j in  range(2, i):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            print(i)
    print("\nThe program used {} seconds to compute all the primes below {}.".format(round(time.time() - start_time, 2), limit))


prime(1000000)
Anders Haarberg Eriksen
  • 11
  • 2
  • 3
    Are you compiling with optimisations enabled? Hard to compare with python without seeing the python code. – john Dec 23 '20 at 14:07
  • 1
    Also I imagine the time taken for the above code (and the python code) would be dominated by the time taken to perform the console I/O. I could easily imagine python being faster at that. – john Dec 23 '20 at 14:08
  • 1
    questions about performance must include more details than usual. What compiler did you use with what flags? How did you measure? What are the results of your measurement? – 463035818_is_not_an_ai Dec 23 '20 at 14:12
  • 1
    To add to what others have stated, you are timing output routines like `std::cout`. You are supposed to be timing only the algorithm, not how fast the console interprets output. In addition, you should actually change your code to put in the proper calls to the timer functions, so that you have better control of what is being timed. – PaulMcKenzie Dec 23 '20 at 14:15

3 Answers3

1

Problem:

  1. You are calling the I/O functions many times.
  2. You're checking unnecesary numbers.

Solution:

  1. Minimize the calling to the I/O functions by using a std::string and concatenating the numbers you're going to print.
  2. Check the number 2 and the odd numbers until sqrt(i).

Full code:

I compiled this code with mingw64 without optimizations and ran it on Windows. It took 622ms.

#include <iostream>
#include <string>
#include <cmath>

void prime(int limit)
{
    std::string toPrint;
    toPrint += std::to_string(2) + "\n";
    bool isPrime;
    for(int i = 3; i < limit; i = i + 2){
        isPrime = true;
        if(i % 2 == 0){
            isPrime = false;
        }
        else{
            for(int j = 3; j <= sqrt(i); j+= 2){
                if(i % j == 0){
                    isPrime = false;
                    break;
                }
            }
        }
        if(isPrime){
            toPrint += std::to_string(i) + "\n";
        }
    }
    std::cout << toPrint;
}

int main()
{
    int limit = 100000;
    prime(limit);
}
Gary Strivin'
  • 908
  • 7
  • 20
0

I recommend the following edits to make your algorithm faster and it is language independent.

#include <iostream>
#include <cmath>

void prime(int limit) {
    std::cout << 2 << std::endl;
    bool isPrime;
    for (int i = 3; i < limit; i = i + 2) {
        isPrime = true;
        if(i % 2 == 0)
            isPrime = false;

        for (int j = 3; j <= sqrt(i); j += 2) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime){
            std::cout << i << std::endl;
        }
    }
}

int main()
{
    int limit = 100000;
    prime(limit);
}
Fatemeh Karimi
  • 914
  • 2
  • 16
  • 23
  • This is more of a comment than an answer. We don't know if the code shown by the OP is actually slower than Python. – PaulMcKenzie Dec 23 '20 at 14:22
0

The std::cout calls will make it slower e.g.:

void prime(int limit) {
    std::stringstream test;
    test << 2 << std::endl;
    bool isPrime;
    for (int i = 3; i < limit; i = i + 2) {
        isPrime = true;
        for (int j = 2; j < i; ++j) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            test << i << '\n';
        }
    }
    std::cout << test.str();
}

with main:

int main(int32_t argc, sp::char8** const argv)
{
    auto t0 = std::chrono::high_resolution_clock::now();
    int limit = 100000;
    prime(limit);
    std::cout << std::endl;
    auto t1 = std::chrono::high_resolution_clock::now();

    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0);
    std::cout << "time taken : " << ms.count() << " ms. " << std::endl;

    return 1;
}

On MSVC release /02 optimizations

time taken : 1337 ms.

vs yours:

time taken : 5959 ms.

0RR
  • 1,538
  • 10
  • 21
  • 1
    You are still timing stream operations. Unless the algorithm's main purpose is to stream output, then all of those calls to `test <<` should be removed. – PaulMcKenzie Dec 23 '20 at 14:26
  • 2
    @PaulMcKenzie sure, but let's face it, his python program timing will including outputting to the screen – 0RR Dec 23 '20 at 14:28
  • How does this differ in performance vs using [`std::ios::sync_with_stdio(false);`](https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio) and directly writing to `std::cout`? – clcto Dec 23 '20 at 14:35
  • @clcto still slow https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull – 0RR Dec 23 '20 at 14:43