10
\$\begingroup\$

this post is sort of a continuation of my answer on the following question: Fast Algorithm to Factorize All Numbers Up to a Given Number. As this post explains - We need to factorize all the numbers up to a large N.

At first I gave a python solution which was pretty slow (since - you know, python), than I decided to write it in C++. I am not that good with C++ and I would like to have a code review about that answer:

#include <math.h>
#include <unistd.h>
#include <list>
#include <vector>
#include <ctime>
#include <thread>
#include <iostream>
#include <atomic>

#ifndef MAX
#define MAX 200000000
#define TIME 10
#endif


std::atomic<bool> exit_thread_flag{false};

void timer(int *i_ptr) {
    for (int i = 1; !exit_thread_flag; i++) {
        sleep(TIME);
        if (exit_thread_flag) {
            break;
        }
        std::cout << "i = " << *i_ptr << std::endl;
        std::cout << "Time elapsed since start: " 
                  << i * TIME 
                  << " Seconds" << std::endl;
    }
}

int main(int argc, char const *argv[])
{
    int i, upper_bound, j;
    std::time_t start_time;
    std::thread timer_thread;
    std::vector< std::list< int > > factors;

    std::cout << "Initiallizating" << std::endl;
    start_time = std::time(nullptr);
    timer_thread = std::thread(timer, &i);
    factors.resize(MAX);
    std::cout << "Initiallization took " 
              << std::time(nullptr) - start_time 
              << " Seconds" << std::endl;

    std::cout << "Starting calculation" << std::endl;
    start_time = std::time(nullptr);
    upper_bound = sqrt(MAX) + 1;
    for (i = 2; i < upper_bound; ++i)
    {
        if (factors[i].empty())
        {
            for (j = i * 2; j < MAX; j += i)
            {
                factors[j].push_back(i);
            }
        }
    }
    std::cout << "Calculation took " 
              << std::time(nullptr) - start_time 
              << " Seconds" << std::endl;

    // Closing timer thread
    exit_thread_flag = true;

    std::cout << "Validating results" << std::endl;
    for (i = 2; i < 20; ++i)
    {
        std::cout << i << ": ";
        if (factors[i].empty()) {
            std::cout << "Is prime";
        } else {
            for (int v : factors[i]) {
                std::cout << v << ", ";
            }
        }
        std::cout << std::endl;
    }
    
    timer_thread.join();
    return 0;
}

I would especially like a review about my usage of threads (I am afraid it might slow down the code). The performance are reaching 6619 which is the 855th (out of 1662 primes up to 14140 ~ square root of 200000000) in 1.386111 hours, if you find any way to make it faster I will be amazing! A more semantic review is also very welcome (Like #include order?).

Just for fun and a point of reference if you are trying to run the code yourself:

Progression Graph

Where X is time and Y is the prime reached (i). The orange tradeline is y = 13 * 1.00124982852632 ^ x. The graph is exponential since indeed the inner loop time is getting shorter.

The orange tradeline says I will reach 14107 (The highest prime before the square root) at x ≈ 5595.842803197861 seconds which is 1.554 hours!

\$\endgroup\$

2 Answers 2

8
\$\begingroup\$

Timing

The timer thread is unnecessary and an inaccurate way to measure time.

I do now know about this system_clock, system calls might slow down the process (maybe the context switch even more though)

Querying the time costs a bit of time, even if it does not involve an actual system call - which it really may not, there are lots of clever tricks for example clock_gettime uses vDSO on modern Linux and reads from a shared memory location and QueryPerformanceCounter reads the TSC on typical Windows systems, there is no transition into and out of kernel mode. It's never a lot of time relative to what this program is doing, the overhead of getting the time is only an issue when timing very short spans of time. Even if getting the time costs a milisecond (which would be unacceptable and considered a bug in the implementation), it would still be OK for this program.

Performance

Storing the factors in explicit linked lists is a major performance problem, and unlike usual, using vectors wouldn't be great either. There is an alternative: store only one factor of a number. That still gives a complete factorization for any number, because if a number N has a factor factors[N], then you can divide N by that factor and look up a factor of the new (smaller) number and so on, until 1 is reached.

That way the inner loop of the sieve only does a bunch of stores into a vector, nothing heavy-weight like dynamically allocating nodes of a linked list, and the memory usage does not get out hand.

As a convention, I'll use that the lowest factor of a prime is the prime itself. That is the mathematical definition, and it makes iterating over the implicit factor lists easy.

Other

Defining MAX by macro definition and putting local variable declarations at the top of the function are very C things to do. Even C has moved away from "all locals at the top". As general guidelines, I recommend using const variables instead of defines, and limiting local variables with the smallest possible scope. That does not repeatedly incur a cost for "making a variable" because that's not how that happens, any fixed space a function needs is allocated all at once at function entry. Besides, most local variables spend their entire lifetime in registers.

Avoid #include <unistd.h> if possible/reasonable, it does not exist on all platforms.

Pick a brace style and stick to it. There were "same line"-braces and "next line"-braces. There are various opinions on which should be used, but at least they shouldn't be mixed.

In total, the code might come out like this:

#include <iostream>
#include <vector>
#include <math.h>
#include <chrono>

int main() {
    const int MAX = 200000000;
    std::vector<int> factors;

    std::cout << "Initiallizating" << std::endl;
    auto start_time = std::chrono::steady_clock::now();
    factors.resize(MAX);
    std::cout << "Initiallization took "
        << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start_time).count()
        << " ms" << std::endl;

    std::cout << "Starting calculation" << std::endl;
    start_time = std::chrono::steady_clock::now();
    int upper_bound = sqrt(MAX) + 1;
    for (int i = 2; i < upper_bound; ++i) {
        if (factors[i] == 0) {
            for (int j = i; j < MAX; j += i) {
                factors[j] = i;
            }
        }
    }
    std::cout << "Calculation took "
        << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start_time).count()
        << " ms" << std::endl;

    std::cout << "Validating results" << std::endl;
    for (int i = 2; i < 20; ++i) {
        std::cout << i << ": ";
        if (factors[i] == i) {
            std::cout << "Is prime";
        }
        else {
            for (int N = i; N > 1; N /= factors[N]) {
                std::cout << factors[N] << ", ";
            }
        }
        std::cout << std::endl;
    }

    return 0;
}

On my PC the sieving takes about 2.5 seconds now. Ideone is a bit slower but the program is fast enough to run there too.

\$\endgroup\$
3
  • \$\begingroup\$ Wow, 2.5 seconds! What is the time complexity for querying here? Before it was O(1) and now it is O(log q)? Thanks for the great answer :) \$\endgroup\$
    – Yonlif
    Jul 10, 2020 at 12:06
  • \$\begingroup\$ @Yonlif the complexity for enumerating the factors of a number would the same as before (each step is still constant time, and the number of factors for a number hasn't changed). The complexity of "getting a list of factors" may have changed, depending on what you're willing to count as a list \$\endgroup\$
    – user555045
    Jul 10, 2020 at 12:14
  • \$\begingroup\$ Oh correct since the previous items was in a linked list and now getting the next item is still O(1) \$\endgroup\$
    – Yonlif
    Jul 10, 2020 at 12:15
5
\$\begingroup\$

The code does just a tad more then a standard sieve. Of course the inner loop of the sieve starts with i*i whereas your code starts with i*2; still we can expect that it should scale nicely with \$O(n \log \log n)\$ time complexity. Considering that a sieve over 200000000 completes in a matter of seconds, the difference must come from the work the sieve does not.

This tad more is that while sieve crosses out the compound numbers, you push_back them to the lists. And this is a performance killer.

You push back every factor of every integer. The number of push_backs performed grows approximately as \$N\log{N}\$ (the Dirichlet estimate). I expect that the factors lists amasses about 4G entries; as each entry (having an int value and two pointers) is of 24 byte (on a 64-bit system), the total memory consumed is about 90 GB (how much exactly we don't know; you are at the mercy of the standard library implementors). This is by itself a very impressive number. What's worse, elements of these lists are scattered all over the place, and the code accesses them pretty much randomly, in a very cache-unfriendly manner. In other words, most of the time is spent thrashing the cache.

To be honest, I don't know how to speed up your code. I have some ideas based on the entirely different approaches, by I don't expect an order of magnitude improvements. Factorizing is hard.


I don't understand why do you want a timer thread. It is perfectly OK to query std::chrono::system_clock::now(); before the processing, and at any moment you want to know how much time elapsed.


Validating results section is very sloppy. A visual inspection of a few primes is far from enough. You should take a small, yet representative (say, 10000 strong), set of numbers, compute their factors the hard way, and compare the results.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for all of your points. I did not know about the Dirichlet estimate, these numbers are quite insane, 90GB - the numbers add up but how my computer did not crush? The program did got killed that might be the reason... I actually had a strong suspicion about the cache but I didn't want to bring it up since it is more of a SO question, do you think disabling it will be better? I do now know about this system_clock, system calls might slow down the process (maybe the context switch even more though). I will do a better "Validating results", thanks. Lastly should I consider C implementation? \$\endgroup\$
    – Yonlif
    Jul 10, 2020 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.