The problem gets more complicated every time

a lot of computation using their own memory space

No problem.

Nobody else cares what a thread does with data that isn't shared (and even if it's shared, it only matters if at least one thread writes to the area).

the result of the computation needs to be stored back into a very large array in memory.

So basically, 4 threads do some lengthy operation and output 4 result values once. When they are available (presumably you block on an event?) you read them. No problem.

Acutally, you don't even need atomicity for that to work reliably. Since you must synchronize with a semaphore or an event or a cond var anyway, that's already more than good enough.

random locations and can partially overlap (it depends from what the user do)

Problem. This isn't so much a threading or atomicity thing, however. It's a correctness thing.

If you add those results to some "random ranges" and these ranges overlap, you will add two results instead of one, atomic or not. If that is not allowable (or even desirable) then your code will not work correctly.

Ok, so far I've wrote this (destination and addvalue are float*):

            float oldval, newval;
            do {
                oldval=*destination;
                newval=oldval+*addvalue;
            } while (!std::atomic_compare_exchange_strong(destination,&oldval,newval));

But it doesn't compile (C2665: 'std::atomic_compare_exchange_strong' : none of the 32 overloads could convert all the argument types). Any idea what I should do ?

Compare and exchange is bit-wise compare so it will also only work on integers here.. but you can cast it (as the compare when storing can still be bitwise). You can write it prettier and safer perhaps but this should work:

            float oldval, newval;
            do {
                oldval=*destination;
                newval=oldval+*addvalue;
            } while (!std::atomic_compare_exchange_strong((uint32_t*)destination,(uint32_t*)&oldval,*(uint32*)(&newval)));

But actually to be honest I would not do it exactly like that even if it happens to work...

Do all read/writes on the memory that needs to be atomic in integers, and use memcpy to write the 4 bytes to a float that is added, and then memcpy it back.

@samoth: I actually have something like 1000 threads (only 4 of thoses are running at the same time, matching the real CPU cores - I'm chaining them using QThreadPool).

So I end up with a thousand blocks of results that can add anytime to the final (large) array.

I could wait for all the threads to finish computation, and store the results from theses threads in a single thread, but then I would loose time (1 thread storing results being slower than 4 threads storing results).

1, 2 or 3 results being added at the same place is a wanted behaviour (the results adding each other to the final array even if they overlap). I'm dealing with audio data (PCM), think of the threads as special audio effects being added to the long audio array.

@SeanMiddleditch: see the answer above (audio processing). However you're right about the time took by atomic functions, I'll have to bench that...

I actually have something like 1000 threads

If 4 out of 1,000 threads are running, why create 1,000 in the first place? Create a work queue and have 4 threads pull tasks (each task having one big block of private data, and outputting one value to another queue) from the queue. Pull one value at a time from the results queue (in the main thread) and apply them, one at a time.

Creating 1,000 threads takes very non-neglegible CPU time and address space and memory (think stack reserve / commit), even when threads are not running (if they are all running, you have a lot of context switches on top). These CPU cycles and this memory are better spent elsewhere.

1 thread storing results being slower than 4 threads storing results

Yes, no, maybe. It depends. One thread adding some float value to memory will almost certainly be limited by memory bandwidth, not by arithmetic.

4 threads will be limited by memory bandwidth, too.

However, 4 threads modifying the same location (or a close-by location in the same cache line, or a multiple of cacheline-size times associativity) will incur false sharing, which greatly impacts performance. Also, atomic operations, which are necessary to make this work reliably, are orders of magnitude slower than normal writes.