Re: Question about concurrent access to array

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 13-02-14 22:39 , john@peppermind.com wrote:
> I'd like like several tasks to share an unpacked array of a definite
> discriminant record type.
> 
> 1.) Is this possible?

Yes.

> 2.) Do I need any kind of synchronization if I can guarantee that
> every task can only write and read to a different area (different
> range of indices) in the array?

See section 9.10 in the RM. The crucial part is this:

"If two different objects, including nonoverlapping parts of the same
object, are independently addressable, they can be manipulated
concurrently by two different tasks without synchronization."

For arrays, independent addressability can be specified with the aspect
Independent_Components; see RM C.6, 6.8/3 and 6.9/3.

This is new in Ada 2012. For earlier Ada versions, I don't know how to
specify independent addressability of array components, but the Ada 2005
RM says in 9.10 that components are "normally" independently
addressable, unless packing or Component_Size is specified. To be safe,
I would make sure that the size of an array component is a multiple of
the machine word size, perhaps by adding padding components.

> Performance matters a lot in this case, which is why I would prefer
> not to use a protected object or any other synchronization mechanism.
> I can't imagine how a problem could occur if every task only accesses
> his own part of the array, but perhaps there is still one?

The computation could go wrong if the program for some reason uses
memory accesses that are wider than one array component. For example, if
the array components are 16 bits (unlikely in this case), and are
aligned to 16 bits, a task that updates a given component might still
use 32-bit accesses and could therefore interfere with concurrent
updates of the adjacent component. I'm not sure if Ada standards before
2012 really forbade such interference.

From the performance point of view, if you intend to gain performance by
running tasks in parallel on several cores, you should probably ensure
(by padding) that an array component fits exactly in one or more cache
lines. Alternatively, if a cache line holds more than one component,
then the tasks updating those components should run in the same core if
possible. The goal is to avoid "false sharing" that makes the cores
compete for ownership of cache lines.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .