How Java manages the multithread access to elements of arrays?

One possible you may be running in to is threads thrashing over cache lines. If different threads rapidly write to locations in the same cache line (for instance, close in the same array), then the hardware has a high communication overhead ensuring that the data remains consistent.

 I wonder if Java still locks up yS, even that each batch isn't trying to access the same elements as others.

There is no automatic synchronization or locking in Java. You have to explicitly code that.

I wonder also if my problem is related to the overhead due to context switching..

Context switches do have overhead. If all your threads work on the same task, which is CPU-intensive, then your number of threads should equal to number of available processor cores.

If there were pointers, I could have new arrays of just the desired elements withsimple pointer operations and without reallocating anything.

All objects in Java are passed by reference (for example when you pass them to a method). And basically all references are pointers (with a difference that you can not dereference them). So no objects are copied in Java, except when explicitly requested by your code.

That being said, you should be aware of another thing: If you are adding a lot of elements to Collections (Lists, HashMaps, etc..) than this Collections need to grow. Internally all Collections use arrays to store elements, and when elements are added the arrays need to be resized. As there is no way to resize an array in Java, there needs to be created a new array and all references to old objects copied to a new array. Or if you use primitive types all data needs to be copied. So, when creating Collections you should size them to appropriate size so that they wouldn't need to be resized.

You may also like to read How many threads should I use in my Java program?

Based on what you've mentioned so far, I would try the following things

1. Compare results between the serial and the parallel version for increasing sizes for your arrays. Difference in performance may indeed be insignificant for your problem size and may only show itself once the size gets bigger i.e. size of the arrays

2. Give each runnable its own copy of the array. In light of performance, the way the array is laid out in memory and how you access them can gave a effect on performance. Even though you may have a 2D array, its going to be laid out as a concurrent list of arrays serially in memory. Hence, if you share this array between runnables, it may become inefficient for some of them.