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 = true;
#pragma omp parallel for shared(limit,dividend,divisor,isPrime)
for (long divisor = 2; divisor <= limit; divisor++)
    if (dividend % divisor == 0)
        isPrime = false;
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?

SimonSchroeder

It's been about 15 years since I have used OpenMP (which means I might be a little fuzzy on the details). Some things might have changed since then (maybe less restrictions).

Here is a quick start to OpenMP:

#pragma omp starts new OpenMP directives
#pragma omp parallel starts a new parallel section. This might contain parallel for loops or individual tasks to be run in parallel.
#pragma omp for declares a for loop to be executed in parallel. parallel and for can be combined into a single #pragma. (Beware of nested parallel sections!)
The end of the loop effectively has to be constant. vector.size() is not the best idea here; instead copy the vector's size to a variable and use that as an upper bound (which is not a problem in this specific example of primes).
Variables can be private, i.e. every thread has it's own copy of the variable (uninitialized!), firstprivate, i.e. still private, but the original value before the threads started is copied in, lastprivate (I don't remember), or shared. Shared variables is the same variable (without synchronization) for all threads.

The defaults can be changed by environment variables (e.g. OMP_NUM_THREADS to restrict the number of threads per parallel section) or by calling omp_...() functions. One such thing is the schedule (env var OMP_SCHEDULE): It determines how the loop is split up! It basically boils down (with additional variations) to a static and a dynamic schedule: With the static schedule it is predetermined which parts of the loop are run by which thread and with a dynamic schedule some limited form of work stealing can happen. However, dynamic schedules need additional synchronization to distribute the work. Associated with the schedule is the chunk size: It determines how many loop iterations each work packet does. This is to avoid cache problems when memory access is involved. So, you might have a chunk size of 8. With a static schedule it is still predetermined which chunks each thread gets, but with the dynamic schedule we have work packets of 8 iterations that are some sort of first come first serve (or maybe at first like the static schedule and once a thread has used up its assigned work packets it starts stealing from other threads).

You might get lucky with a schedule(static,1), but in general a chunk size of 1 is not a good idea. Would you be open to a chunk size of 8? Still a lot better if all threads work on the first couple of numbers first. Alternatively, you might try something like this:

#pragma omp parallel shared(limit,dividend,divisor,isPrime)
for(long divisor = omp_get_thread_num(); divisor <= limit; divisor += omp_num_threads())
   ...

Notice that I did not include for in the #pragma omp: I just let every thread run the same loop, but change the start with omp_get_thread_num() (the index of the current thread, starting from 0 -> adapt to start at 2). Unfortunately, omp_get_thread_num() and omp_num_threads() sound quite similar.

BTW, for potentially better performance there is also an unroll directive for the pragma.

There are official cheat sheets for OpenMP: https://www.openmp.org/resources/refguides/

JKSH

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

@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.... When that's working/timed, I might compare against the list approach.

To clarify: What I described does EXACTLY the same thing as your multiple QtConcurrent::run() calls, so I'd expect the timing to be the same.

It was to show you how to use QtConcurrent::mapped() to run the algorithm that you described (my apologies, my previous post erroneously said map() instead of mapped()). The main difference is that you end up with a single QFuture instead of one QFuture per thread:

struct Range {
    long start;
    long limit;
    long step;
};
bool threadFunc(const Range &range)
{
    for (long divisor = range.start; divisor <= range.limit; divisor += range.step)
        if (dividend % divisor == 0) 
            return false;
    return  true;
}

// ### Set up and run your threads
int threads = available_threads();  // maybe 8?
QList<Range> ranges;
for (int thread = 0; thread < threads; thread++)
    ranges << Range{2+thread, limit, threads}; // Or `Range{3+thread, limit, 2*threads};` if you've already tested for evenness earlier

QFuture<bool> future = QtConcurrent::mapped(ranges, threadFunc);


// ### Set up your results monitor
auto watcher = new QFutureWatcher<bool>(someParent);
QObject::connect(watcher, &QFutureWatcher<bool>::resultReadyAt, qApp, [watcher](int index)
{
    if (!watcher->resultAt(index))
        qDebug() << "Thread" << index << "found a factor";
});
watcher->setFuture(future);

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.

Indeed. I haven't benchmarked, but I'd expect the cost of setting up a thread to be comparable to the cost of doing a single division in that thread.

Once an instance of your threadFunc() starts running, it normally can't be terminated before completion (in contrast, QThread offers a terminate() function)...

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

Thread termination is a foot-gun. It's safe here because you're only reading integers and writing Booleans.

JonB

@JKSH
Hi @JKSH. I managed to find some time to try your algorithm.

After some required changes to it, and making it do the same loop as my existing code using QtConcurrent::run() (e.g. each range should start from 3 + thread * 2), I agree timings came out similar. I would probably make an effort to reduce overhead space/time on having to create all these list elements by using an iterator-function or the new QRangeModel if I used mapped() but didn't bother to rewrite to test that.

Since the sort of number I am testing initially is a 64-bit 18446744073709551557UL, which I know to be prime, it is fortunate we only have to examine up to its square root, else the pre-created lists would need to be really large :)

What I did find interesting while doing is: applying equally whether I use mapped() or run(), the overhead of checking in each thread's loop for whether any other thread has found a factor:

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

    for (unsigned long divisor = start; divisor <= limit && !finish_threads.load(std::memory_order_relaxed); divisor += step)
        if (dividend % divisor == 0)
        {
            finish_threads.store(true, std::memory_order_relaxed);
            return false;
        }
    return true;

Just the test of the atomic boolean each time round the loop, done as efficiently as I know how, seems to about double the total elapsed time (for a prime number). I had not expected that to be as high a cost as the division (early in my past I wrote for 6502 processor where you had to write division as a loop yourself, I guess it's more efficient these days ;) ) It's an (interesting) shame to discover that the code required to "short-circuit" testing every factor once a factor is found anywhere (required for early-discovered composites) costs as much as all the division tests and hence doubles the time if the target number turns out to be prime. So if you want the fastest time when a number turns out to be prime don't even try to terminate early if it is not!

JKSH

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

I would probably make an effort to reduce overhead space/time on having to create all these list elements by using an iterator-function or the new QRangeModel if I used mapped() but didn't bother to rewrite to test that.

Since the sort of number I am testing initially is a 64-bit 18446744073709551557UL, which I know to be prime, it is fortunate we only have to examine up to its square root, else the pre-created lists would need to be really large :)

?? The size of the list equals available_threads(). Which shouldn't be a really large number on your laptop.

It's an (interesting) shame to discover that the code required to "short-circuit" testing every factor once a factor is found anywhere (required for early-discovered composites) costs as much as all the division tests and hence doubles the time if the target number turns out to be prime. So if you want the fastest time when a number turns out to be prime don't even try to terminate early if it is not!

I wonder if you'll get a noticeable improvement if you use a non-atomic bool? Since the value always starts as false and the only value that could possibly be written is true, there's no benefit in guarding against race conditions.

(early in my past I wrote for 6502 processor where you had to write division as a loop yourself, I guess it's more efficient these days ;) )

Fun!

JonB

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

?? The size of the list equals available_threads(). Which shouldn't be a really large number on your laptop.

I am so sorry. I got it fixated in my mind that using mapped() we were going to create actual lists of the numbers in each range, hence all my stuff about large numbers of elements. Of course this code now approaches it in just the same way as my run()s, the list is just one element, not as many as are in the range, per thread.

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

I wonder if you'll get a noticeable improvement if you use a non-atomic bool? Since the value always starts as false and the only value that could possibly be written is true, there's no benefit in guarding against race conditions.

I took that code straight from an AI, and haven't even bothered to look into it :) That's what it said I wanted for simplest/fastest for "set in one thread, test in others" I didn't even look it up, I thought it was implying this is non-mutex. If you are not convinced I will certainly retest tomorrow with, say, a plain bool and see if that is where it is taking all its time. In which case we will discuss that... :)

JonB

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

I wonder if you'll get a noticeable improvement if you use a non-atomic bool? Since the value always starts as false and the only value that could possibly be written is true, there's no benefit in guarding against race conditions.

Well indeed! Changing from std::atomic<bool> to just plain bool halved the time to run the algorithm/loop so that it is just the same as if the test were not there. So now I have some questions... :)

I got std::atomic<bool> from my friend ChatGPT, who is never wrong. He said I could/should use std::memory_order_relaxed. Reading up on that now:

Atomic operations tagged memory_order_relaxed are not synchronization operations; they do not impose an order among concurrent memory accesses. They only guarantee atomicity and modification order consistency.

Typical use for relaxed memory ordering is incrementing counters, such as the reference counters of std::shared_ptr, since this only requires atomicity, but not ordering or synchronization

So that part is something to do with the ordering of operations in different threads, which I do not need here. But what is the underlying behaviour of std::atomic<bool> with store() and load()? Does a plain std::atomic<bool> flag; flag = true; // or if (flag) ... behave any differently than using store()/load()? Ignoring this "memory order" stuff, which seems to be to do with ordering multiple accesses, is the terrible speed because atomic does some kind of "mutex" under the hood, not just a single/fast instruction to access it?

What exactly do I have to do/protect against concurrent access when? In the olden days, where "multitasking" meant a single CPU swapping between threads of execution, I had to think about something like the processor swapping in between each individual instruction, but I think not when right in the middle of executing a single instruction.

Now presumably a different thread can execute any time, even when the other thread is in mid-instruction? Why do I care anyway when I have, say, a bool or even int variable which I set in one thread and test in another? Those are (presumably) set in a single instruction, the reader just sees it either as it was before or afterwards but not in some inconsistent "mid-instruction" state? And here I don't care if a test in the loop sees a change from another thread this time round or next time round. I also don't think it matters if two threads simultaneously find their own factors and both set the variable to true (though I agree that might matter in an incrementing counter case)? Even if the shared variable (still one writer many readers) were a pointer wouldn't a statement which assigned a new value, ptr = new_value;, be a single instruction so a reader executing "during" that would still see the value either as before or after that statement, not half way through writing into the 4/8 bytes comprising the pointer?

Finally, while I am here: what exactly has to be done at runtime when you ask a thread to execute some code (function/lambda)? I assume there are two overheads. One is from initial construction of a thread/QThread. If you destroy and recreate you would pay this every time. But presumably with a thread pool like I am using it re-uses previously created threads? The second must be whatever has to be done to "start" or "run" the thread with its code, like QThread::start() or run() (say you have subclassed QThread::run() so it does not do any event loop via exec()). What has to be done/how much overhead is there to just get an (existing) thread to start executing some code? This is pretty significant if the code just does something really small and simple like a single division and then exits. Which is why I make each thread do a range of tests instead of one at a time, even though that complicates my algorithm.

SimonSchroeder

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

Ignoring this "memory order" stuff, which seems to be to do with ordering multiple accesses, is the terrible speed because atomic does some kind of "mutex" under the hood, not just a single/fast instruction to access it?

Usually, the mutex is implemented through atomics (and not the other way around). And an atomic is just a single instruction (and it is fast for what it does). However, what might need to happen is synchronization between L1 caches of different cores. This is slow. Though, it's not necessarily the bytes of actual data that is exchanged between the caches, but just the information if something has changed (and only after that the actual data is also sent).

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

What exactly do I have to do/protect against concurrent access when?

You definitely have to protect against read-modify-write. The easiest example for this is a counter (or more specific in the context of threads a semaphore). Between reading and writing another thread might have already read and written the same variable. This easily messes up counters if they are not atomic (that's why shared_ptr uses an atomic counter internally). There is even an A/B problem with two variables and two threads; each reading from one variable and writing the other. There is something strange going on here with an instruction ordering that might result in a totally unexpected state (at least on x86). C++26 now also introduced hazard pointers that allow multiple readers, but only a single writer (while nobody else is reading).

In your specific case the write does not depend on the previous value and therefore does not have to be atomic. The only thing that might happen without an atomic is that other threads are not immediately informed when a change happens. They might just run a few additional cycles of the loop. You might also just check the atomic boolean variable every 10 loop cycles to get more speed. I am not entirely sure if there is anything about the boolean variable (if it is not atomic) that requires it to be committed to memory eventually (and not just stay a register-only variable). You could mark it as volatile, but that would require to fetch it from memory (or cache) on every single access. That also slows it down.

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

Finally, while I am here: what exactly has to be done at runtime when you ask a thread to execute some code (function/lambda)?

From my easiest understand if the thread does not have any code to run anymore, it is terminated. So, there needs to be explicit code somewhere that sleeps the thread to wait for further work. Usually, you'll have something like a task queue–either for a single worker thread or for a thread pool. You cannot just run code in another thread without doing additional work (either it's your own code or it is some library code). With QThread the easiest way is to just use the default run() method which will call exec(). Then, you can add individual work items to that thread's event loop through QMetaObject::invokeMethod(). Otherwise your QThread has to implement it's own method how others can communicate to run some specific function (with arguments). But, that would require that you have a task queue (definitely thread-safe!) where you can store functions to be executed and the worker thread has to get new items from the queue. If nothing is there, it needs to sleep. And either it is woken up when something is put into the queue, or the thread has to wake up repeatedly and poll the task queue. This gets more complicated if you want a thread pool instead. Effectively, you'd be reimplementing either the event loop of QThread or the thread pool of QtConcurrent::run(). Just use those instead if you are already using Qt for threading. For a one-off thread there is also QThread::start() (as you have mentioned), but it needs boiler plate code to clean up after itself (or you just use my small wrapper library for QThread: https://github.com/SimonSchroeder/QtThreadHelper ; it is just a single header, but it shows a lot of different corner case you might not have thought about, yet).

JonB

@SimonSchroeder
Hi Simon, thanks for your answer. there is a lot to digest here!

The variable is a "global" variable, I was expecting that to actually read/write the location not use a register but I see what you mean about the code might hold it only in a register at least for some time. FWIW, I have marked it volatile and see no speed difference. Yes I had thought about only checking an atomic every so often through the loop for speed now that I know atomic is so slow.

In your specific case the write does not depend on the previous value and therefore does not have to be atomic.

Indeed. My situation is many threads (if multiple factors) may set the variable and many threads need to test the variable to exit. While this is by no means the only algorithm using threads and variables it is one of the most common and simple. I shall be requerying ChatGPT on why it wanted me to use an atomic and what the speed consequences are.

From my easiest understand if the thread does not have any code to run anymore, it is terminated. So, there needs to be explicit code somewhere that sleeps the thread to wait for further work.

Otherwise your QThread has to implement it's own method how others can communicate to run some specific function (with arguments).

This quite changes my understanding/guessing of how threads, and Qt's thread pool, work. I had thought/assumed that, at the OS level, you could initially create a thread that was totally empty/idle and get a "handle" back from it. Then whenever you liked you could have a function/some code and just tell the idle thread to execute that; and when it finished that code it would return to be quite empty/idle, ready for re-use. Now you are saying that, effectively, you must have some code for the thread always to be executing right from that start, and for "re-use" you must have explicit code in it constantly "waiting" for a "message" which it interprets for setting off some execution, after which it returns to its "waiting loop". All of which probably does not exist for the underlying OS thread but is provided at the lowest level by QThread.

It also means that where I read

QThreads begin executing in run(). By default, run() starts the event loop by calling exec() and runs a Qt event loop inside the thread.

Another way to make code run in a separate thread, is to subclass QThread and reimplement run().
In that example, the thread will exit after the run function has returned. There will not be any event loop running in the thread unless you call exec().

I interpreted "if you don't call exec() there will be no event loop" as meaning a thread (QThread) does not have any code/loop running if you don't call exec(). You are saying a QThread always has (or should have) a function-execution-request-queue, just it won't have specifically a Qt event loop if no exec(). You cannot actually completely separate the creation of a thread from what code it will execute, that has to be specified at creation time not later on. And QThreadPool is to do with marshalling how many of these QThreads are doing work at the same time and sending them "messages" for when to do the next job which they themselves are sitting in a loop waiting for, not for re-using an "idle" thread to do a totally new job somehow.

JonB

@SimonSchroeder
Hmm, further complications. I went back to ChatGPT and carefully phrased what we are trying to do/asking about, where we think this case of a boolean and the way it is set/read means we do not need atomicity and can just use, say, a volatile shared variable. The gist of its answer is:

In this situation std::atomic<bool> is required if you want the program to be correct according to the C++ memory model.

The important distinction is between what the hardware happens to do and what C++ guarantees.

In C++, a non-atomic object cannot safely be accessed concurrently this way. That's a data race, and a data race means undefined behaviour.

It doesn't matter that:
[...]

volatile does not fix it. volatile is about observable memory accesses, primarily for things such as memory-mapped hardware; it isn't a thread-synchronisation mechanism.

and concludes:

But atomicity is still required for the read/write relationship.

So the short answer is:

Yes, atomic<bool> is required for a correct C++ program here. No, volatile bool is not a valid replacement. But you absolutely don't need to pay for an atomic load on every iteration — checking it periodically is a very reasonable optimisation for your algorithm.

(It having suggested only calling done.load(std::memory_order_relaxed) once every so many iterations round the loop, just as you & I talked about. I have implemented that for every 256 iterations in each thread and that gives me acceptably similar timing now.)

So I take that it while my non-atomic implementation may appear to work, or may work fine on my particular machine/architecture, it is at least theoretically not allowed ("Undefined Behaviour") under C++ at least.

In a certain sense this is "reassuring"/"simple": instead of having to ponder whether a given "shared" variable and what we do with it (flag, counter, whatever) determines whether I need atomic or not, it seems I just need to use atomic whenever I have cross-thread read/writes.