Converting from List<Object> to Array with threads

Question

I have a large (>500.000) list of Objects and I want to convert it to a multidimensional array. Until now I am doing this using a for loop, but after some measurements I identified that this is a bottleneck for my program.

I am considering to make the conversion in parallel using a thread pool executor. The logic is that if I have N threads I will separate the initial data to N chunks. Each thread will 'convert' the Object values and insert them to the 'shared' array. Since I know the exact position of each item, I can ensure that 2 threads will never try to write to the same array position.

Is this a good way to go? Are there any considerations?

Are there any Libraries implementing such functionality? (Note: I am not asking for the libraries their-self, since this would be of topic. I just want to know, if there is something similar, meaning that I am in the good track)

Note 1: I know that creating thread is 'time-consuming' also, but to find for what amount_of_data / number_of_thread, parallel conversion is more optimal than serial is another issue.

Answer 1

For me it seems pretty straightforward - as you say, you can divide the work beforehand to N chunks, each thread will pick up and process their assigned elements and put to pre-determined place in the array - threads effectively won't read/write same data.

Two things though:

• You should preallocate all the arrays accessed by multiple threads before hand to avoid race conditions.
• There's a potential visibility problem - shared data is sometimes cached thread-locally in the CPU registers, their changes doesn't have to be immediatelly propagated to the main memory. The risk here is that once all the changes are done in "worker" threads, these changes may not be visible (present in the main memory) for the thread which uses the produced multidimensional array. There are several possible ways how to handle it for this case, but arguably the simplest is to use java.util.concurrent.atomic.AtomicReferenceArray instead of simple array - this will solve the visibility problems without having to reason hard about what's going on.