Is QtConcurrent suitable for this concurrent/parallel algorithm?

JonB

I feel like testing my new laptop's speed/core threading... :)

My test will be calculating whether an input number is prime or not. The size of the number will be "large", so Eratosthenes Sieve would cost too much space. Instead I will run trial division. So the initial, single-threaded algorithm will be:

long dividend = ...;  // the number to test for primality
long limit = sqrt(test);
for (long divisor = 2; divisor <= limit; divisor++)
    if (dividend % divisor == 0)
        return false;
return  true;

Now the question is to how to split the task "optimally" for concurrent execution across available threads/cores.

If I naively just set this off with some QtConcurrent method and a function/lambda which just returns the dividend % divisor == 0 result for each number in range 2..limit I presume there will be some overhead for initiating/terminating each thread which has only done a simple dividing and that will be far from optimal. Right?

If I were to do this myself with threads/cores I would go for something like:

int threads = available_threads();  // maybe 8?
for (int thread = 0; thread < threads; thread++)
{
    threadObj = createThread();
    threadObj->run(threadFunc, 2 + thread, limit, threads);
}
if (any_thread_returns_false())
    return false;
return true;

bool threadFunc(long start, long limit, long step)
{
    for (long divisor = start; divisor <= limit; divisor += step)
        if (dividend % divisor == 0) 
            return false;
    return  true;
}

This partitions the range into available_threads() separate ranges via steps, so each created thread tests each of these sub-ranges, no further thread creation/destruction over the initial creation of threads.

Obviously I then need (a) some mechanism of knowing when all threads have run their own loops to completion and never found a divisor for the dividend (so tested number is indeed prime) and (b) a way of a thread returning or signalling immediately when it has found a divisor (tested number is composite) so that main code can then immediately terminate the other threads and return false.

Among all the QtConcurrent methods for filtering/mapping/reducing I have not figured whether/how this algorithmic behaviour could be executed as stated? (Btw, any solution which creates a list of all the numbers from 2 to limit and then filters/reduces them takes too much space by definition; and anything which creates more total threads ever greater than available_threads() is presumed to be "slow" because of thread creation overhead.)

For the avoidance of doubt: I am interested in Qt methods to test performance. If there is, say, a std library function which tells you whether a number is prime even by using the host's threads for you, that is not what I am looking for :)

JonB

Thinking aloud about my own post. Funny how typing it all in makes you think down a logical route... :)

I was thinking/hoping in terms of calling a QtConcurrent method for each division to test and having it just do the dividend % divisor == 0 for one pair of numbers. But as I said that will presumably incur too much overhead. If I want to use QtConcurrent: I know (I think) that I only want available_threads() number of threads created, so I could use it to create those with threadFunc(long start, long limit, long step) as the function to run. I am then using QtConcurrent to handle the early or final termination code of all threads (the "outer" loop) rather than at the "do one division" (the "inner" loop). (Looks like QtConcurrent::run() in Run With Promise mode?)

Is this the (only/right) way to use QtConcurrent for my proposed algorithm?

IgKh

I'd probably use a filter-reduce operation on a custom iterator class (to not actually allocate a list of all numbers 2..sqrt(n)) - https://doc.qt.io/qt-6/qtconcurrentfilter.html#concurrent-filter-reduce

Also - I know you didn't ask for alternative algorithms, but for the benefit of anyone reading the thread later that might be interested, the most efficient way to test primality of truly large numbers is the Rabin-Miller test

JonB

@IgKh said in Is QtConcurrent suitable for this concurrent/parallel algorithm?:

I'd probably use a filter-reduce operation on a custom iterator class (to not actually allocate a list of all numbers 2..sqrt(n)) - https://doc.qt.io/qt-6/qtconcurrentfilter.html#concurrent-filter-reduce

Yes, I did wonder whether a "lazy-generator" of the numbers might be usable for the QtConcurrent methods. I might try this as a timing test against my proposed approach outlined earlier.

the most efficient way to test primality of truly large numbers is the Rabin-Miller test

I had a read through this. I am aware there are other algorithms which perform better than trial division. But, if I understand correctly, it (a) only tells me whether a number is probably prime, (b) relies (at least in some variants) on a still unproven Riemann hypothesis and (c) does not give me factors if it decides a number is composite. I am uncomfortable about all of these! Of course, I do realise my intended range of 64-bit numbers is trivially small and doubtless the assumptions do hold in this domain, but I still don't like the idea of a mathematical solution which says a 3 sided shape is "probably" a triangle... ;-)

IgKh

@JonB said in Is QtConcurrent suitable for this concurrent/parallel algorithm?:

But, if I understand correctly, it (a) only tells me whether a number is probably prime, (b) relies (at least in some variants) on a still unproven Riemann hypothesis and (c) does not give me factors if it decides a number is composite.

We are going a little off-topic, but this is close to the area of my professional capacity so why not! Rabin-Miller is indeed probabilistic, but the error probability can be arbitrarily bounded by running more iterations of the test, driving the chance of mistake to being negligible. This is similar in concept to other probabilistic data structure and algorithms, like bloom filters. The Riemann hypothesis thing is not actually relied on if you accept non-determinism, so the matter of assumptions holding is not pertinent to the size of the numbers.

It's true that RM is just a test, it doesn't help to factorize integers - at least not directly. It is however very important in cryptography, since many cryptosystems rely on generating very large random prime numbers. And by very large I mean things like 2,048 or 4,096 bits. A loop of drawing a random number from a range and then testing it for primality is the best we have in practice, so a fast (even if only, say, 99.9999% accurate) test is extremely useful.

JonB

@IgKh
I read a whole book just on the Riemann Hypothesis a few years ago. I can honestly say it was the most boring book I have ever read ;-)

JKSH

Back to using Qt Concurrent for your algorithm:

@JonB said in Is QtConcurrent suitable for this concurrent/parallel algorithm?:

Among all the QtConcurrent methods for filtering/mapping/reducing I have not figured whether/how this algorithmic behaviour could be executed as stated? (Btw, any solution which creates a list of all the numbers from 2 to limit and then filters/reduces them takes too much space by definition

Instead of a list of all numbers to test, generate a list of ranges ("arithmetic progressions" in maths parlance) to test:

struct Range {
    long start;
    long limit;
    long step;
};

Then, apply QtConcurrent::map() to your QList<Range>. This is the idiomatic way^ to express your algorithm above (both are equivalent).

BTW, it's pointless/wasteful to test even divisors (except 2). Just check if your number is divisible by 2 before starting any threads, and then let your threads only test odd divisors. This halves the maximum number of divisors that they need to test.

Obviously I then need (a) some mechanism of knowing when all threads have run their own loops to completion and never found a divisor for the dividend (so tested number is indeed prime) and (b) a way of a thread returning or signalling immediately when it has found a divisor (tested number is composite)

QFutureWatcher is your friend.

so that main code can then immediately terminate the other threads and return false.

Once an instance of your threadFunc() starts running, it normally can't be terminated before completion (in contrast, QThread offers a terminate() function). So, you'll need to add some kind of escape hatch, like a global Boolean flag that your for-loops check before performing a division. I'm not sure how much overhead this adds -- benchmark and see.

@JonB said in Is QtConcurrent suitable for this concurrent/parallel algorithm?:

(Looks like QtConcurrent::run() in Run With Promise mode?)

Is this the (only/right) way to use QtConcurrent for my proposed algorithm?

As you've seen above, Run, Map, and Filter are all viable. I'd imagine that the global Boolean flag has equal or lower overhead than cancelling a Run via a QPromise. However, the latter is more "self-contained" so you could run your prime-check algorithm on multiple dividends simultaneously.

^ P.S. To be extra idiomatic, you could use map-reduce instead of map, where the reduce function checks the results of all your threads and makes the final declaration of "Prime" or "Not Prime". But I think this is over-engineering. Plus, it doesn't fit nicely with the requirement to terminate computation early once a factor is found.

JonB

@JKSH said in Is QtConcurrent suitable for this concurrent/parallel algorithm?:

Then, apply QtConcurrent::map() to your QList<Range>. This is the idiomatic way^ to express your algorithm above.

We shall see. For now I am creating QtConcurrent::run()s for each available core, per my approach earlier, passing in parameters to each one for what "range" to test. No map/filter/reduce, no ranges as ranges. When that's working/timed, I might compare against the list approach. What we are all agreeing, apparently, is not to do the naïve "create a thread for each test division (not with a loop to test a bunch of them)", and let QtConcurrent figure out threads & pool for it. Which to me is the "logical" way a noob might approach it, but I assume grossly slow.

QFutureWatcher is your friend.

Ah, OK.

Once an instance of your threadFunc() starts running, it normally can't be terminated before completion (in contrast, QThread offers a terminate() function). So, you'll need to add some kind of escape hatch, like a global Boolean flag that your for-loops check

Ah, OK again. Yes, surprises me if basic QThread does allow forceful terminate.

BTW, it's pointless/wasteful to test even divisors (except 2). Just check if your number is divisible by 2 before starting any threads, and then let your threads only test odd divisors. This halves the maximum number of divisors that they need to test.

Of course, already in code but not shown earlier.

SimonSchroeder

Well, maybe a small side quest: The easiest method to make the algorithm parallel might be using OpenMP:

long dividend = ...;  // the number to test for primality
long limit = sqrt(test);
bool isPrime = false;
#pragma omp parallel for shared(limit,dividend,divisor,isPrime)
for (long divisor = 2; divisor <= limit; divisor++)
    if (dividend % divisor == 0)
        isPrime = true;
return  isPrime;

You have to turn on OpenMP (something like -fopenmp) to make it run in parallel. OpenMP automatically scales with the number of cores and you can even choose a scheduling algorithm and chunk size to optimize it further. Quick testing can be done by setting OpenMP environment variables to change the defaults.

The equivalent in Qt is actually QtConcurrent. QtConcurrent::run doesn't really help because most of the work is still on your shoulders, but map-and-reduce is perfect for this. QtConcurrent actually starts a thread pool and does not oversubscribe your CPU cores (even with QtConcurrent::run). It is also not constantly starting new threads, but reuses threads from the thread pool. You can do similar things with QThread if you just start the event loop for each worker thread and push "tasks" by using QMetaObject::invokeMethod.

You might have noticed that for the OpenMP example I did not include early termination (yet). IIRC with OpenMP this is a little bit more complicated and you might have to write continue to run empty loops for "early terminations". Usually (independent of OpenMP), it is sufficient to have a boolean variable accessible to all threads and let one thread toggle it if it finds a solution. It does not have to be atomic. For early termination you probably don't care if termination is immediate or slightly delayed (until the cores have synched up). At least, you don't have to pay for the overhead of an atomic in every single loop iteration.

If you are looking for a fast solution, you can get some inspiration from Dave Plummer's Prime Drag Race. Dave Plummer is a retired Microsoft engineer on YouTube. In the Prime Drag Race people competed/compete with different programming languages to write the fastest program.

JonB

@SimonSchroeder
[Before we start: you might like to change what you have written either to swap the true/falses or change isPrime to isComposite :) ]

The underlying issue here I am trying to examine is: the simplest way to write the algorithm is just to have a single loop running from 2 to limit, just as you have here. And have each division check done in some thread. Theoretically with 4 threads you get 4 times the speed. However, I presume that --- even if we allow the pre-creation of the 4 threads and re-use --- there is some overhead for running the division on a thread: something for setting up/starting off the division code and something for finishing/returning the result. Right? And that may be considerable, even larger than, the time taken to execute a single division in its body.

That indicates to me that I need to write an algorithm which partitions the domain into 4 quarters and just gets each of 4 threads to do a loop over its 1/4th of the numbers, to minimize the thread start/end overheads.

Now, it may be that your #pragma omp parallel for shared(limit,dividend,divisor,isPrime) does just that. I don't know because you have not said how it works. That would be a good start. But I am guessing that, even if it does so, it naively partitions the range into the lowest first quarter of numbers, the middle two quarters and the highest quarter, e.g. first quarter would run from 2 to 2 + limit / 4. This would be fine if the body were, say, counting the number of iterations in each thread's quarter of the range. Each quarter does just the same amount of work as every other.

But that is not true for prime test by trial division. When a number is going to be prime each quarter must run through all its range till they all fail, fine. But when a number is going to be composite we are going to find a factor and stop (all threads). The problem is that a target composite dividend is going to be much more likely to have a factor in the first quarter (3, 5, 7, 11, ...) than in a higher quarter. Let's say a dividend is going to have 11 as its lowest factor. We will have to wait for the lowest quarter range to perform 4 iterations before it meets 11 and we can terminate that and the other threads. Over a large range of numbers, the algorithm --- at least when it examines a composite dividend --- will degenerate into sequential/single-threaded performance.

My intention is to partition the domain into quarters a different way:

Thread 1: 3, 11, 19, ...
Thread 2: 5, 13, 21, ...
Thread 3: 7, 15, 23, ...
Thread 4: 9, 17, 25, ...

This spreads out the lower numbers, which are going to be the most common factors, fairly equally between the threads. It will be more common to find a (low) factor early in one of the threads.

Now, I don't know, but does your #pragma omp parallel for shared(limit,dividend,divisor,isPrime) do that, or can it be made to do that? Because without guidance it would have no reason to do so, rather than just divide it into sequential quarters?

And when you do have a (pre-created) thread to use on a core: just what is the "overhead" to, say, start, run and complete a piece of target code in it? I don't know how/what the processor or the code has to do when asked to execute a small piece of code in a thread?