Suppose I have an int[] which may contain some zeroes, and 2 functions, one scans the array for zeroes but does not modify it, and the other modifies array elements but never introduces new zeroes (though it may write a 0 to an existing 0).  Is it thread-safe to run the two functions in parallel without any synchronization between them?

I.e., will the first function always see zeroes where there are zeroes, in spite of the 2nd function writing to the array simultaneously?  Are there any hardware situations where the 1st function may read a non-zero value if the 2nd function is simultaneously overwriting an existing zero with another zero?  Or a situation where the 1st function may read a zero if the 2nd function is simultaneously overwriting a non-zero value with another non-zero value?

Or am I playing with fire here?


T

-- 
Chance favours the prepared mind. -- Louis Pasteur

On Thursday, 18 June 2020 at 16:42:15 UTC, H. S. Teoh wrote:
> Suppose I have an int[] which may contain some zeroes, and 2 functions, one scans the array for zeroes but does not modify it, and the other modifies array elements but never introduces new zeroes (though it may write a 0 to an existing 0).  Is it thread-safe to run the two functions in parallel without any synchronization between them?
>
> I.e., will the first function always see zeroes where there are zeroes, in spite of the 2nd function writing to the array simultaneously?  Are there any hardware situations where the 1st function may read a non-zero value if the 2nd function is simultaneously overwriting an existing zero with another zero?  Or a situation where the 1st function may read a zero if the 2nd function is simultaneously overwriting a non-zero value with another non-zero value?
>
> Or am I playing with fire here?
>
>
> T

As long as reads and writes of `int` are atomic on the platform in question (which they probably are) you should be ok.

Personally, I would use core.atomic.atomic{Load,Store} just to be safe; they should optimize themselves away if they're not needed.

On 6/18/20 9:42 AM, H. S. Teoh wrote:

> Are
> there any hardware situations where the 1st function may read a non-zero
> value if the 2nd function is simultaneously overwriting an existing zero
> with another zero?

I've worked in high performance projects where exactly that was done. I am not aware of any hardware feature that would make that unsafe.

Ali

On 6/18/20 12:42 PM, H. S. Teoh wrote:
> Suppose I have an int[] which may contain some zeroes, and 2 functions,
> one scans the array for zeroes but does not modify it, and the other
> modifies array elements but never introduces new zeroes (though it may
> write a 0 to an existing 0).  Is it thread-safe to run the two functions
> in parallel without any synchronization between them?
> 
> I.e., will the first function always see zeroes where there are zeroes,
> in spite of the 2nd function writing to the array simultaneously?  Are
> there any hardware situations where the 1st function may read a non-zero
> value if the 2nd function is simultaneously overwriting an existing zero
> with another zero?  Or a situation where the 1st function may read a
> zero if the 2nd function is simultaneously overwriting a non-zero value
> with another non-zero value?

I think it's possible there's a problem if the reads are not atomic:

Let's say a value is 0xffff0000

Thread that is looking for 0s reads the lower half of the number -> 0x????0000

Context switches, thread 2 writes 0x0000ffff into that memory slot.

Back at the zero-scanning thread, it reads the second half -> 0x0000????

Combines with the first part, and now it sees a 0 where there isn't one.

I would agree with Paul -- make the reads/writes atomic.

-Steve

On Thursday, 18 June 2020 at 16:42:15 UTC, H. S. Teoh wrote:
> Suppose I have an int[] which may contain some zeroes, and 2 functions, one scans the array for zeroes but does not modify it, and the other modifies array elements but never introduces new zeroes (though it may write a 0 to an existing 0).  Is it thread-safe to run the two functions in parallel without any synchronization between them?
>
> I.e., will the first function always see zeroes where there are zeroes, in spite of the 2nd function writing to the array simultaneously?  Are there any hardware situations where the 1st function may read a non-zero value if the 2nd function is simultaneously overwriting an existing zero with another zero?  Or a situation where the 1st function may read a zero if the 2nd function is simultaneously overwriting a non-zero value with another non-zero value?
>
> Or am I playing with fire here?

If you're on x86 all reads and writes are atomic if they are naturally aligned. IE 16 bits on 2 byte boundry, 32 bits on 4 byte boundry, 64 bits on 64 bit boundry. (Dont think it applies to 128 bit regs)

Short version is you're fine as long as your ints are on 4 byte boundrys.

If you want unaligned atomicity you need a lock prefix.

On Thursday, 18 June 2020 at 16:42:15 UTC, H. S. Teoh wrote:
> Suppose I have an int[] which may contain some zeroes, and 2 functions, one scans the array for zeroes but does not modify it, and the other modifies array elements but never introduces new zeroes (though it may write a 0 to an existing 0).  Is it thread-safe to run the two functions in parallel without any synchronization between them?
>

Found the relevant doc

http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf

On Thursday, 18 June 2020 at 16:42:15 UTC, H. S. Teoh wrote:
> Suppose I have an int[] which may contain some zeroes, and 2 functions, one scans the array for zeroes but does not modify it, and the other modifies array elements but never introduces new zeroes (though it may write a 0 to an existing 0).  Is it thread-safe to run the two functions in parallel without any synchronization between them?
>
> I.e., will the first function always see zeroes where there are zeroes, in spite of the 2nd function writing to the array simultaneously?  Are there any hardware situations where the 1st function may read a non-zero value if the 2nd function is simultaneously overwriting an existing zero with another zero?  Or a situation where the 1st function may read a zero if the 2nd function is simultaneously overwriting a non-zero value with another non-zero value?
>
> Or am I playing with fire here?
>
>
> T

If there's no alignment hanky panky (e.g. struct packing), and you're on x86-64, you have your guarantee - as reading aligned words are atomic. If you want portability then there's no guarantee.

Steven's case could certainly happen if a value crosses a word boundary on a platform that doesn't guarantee atomic reads/writes.

I was confirming things and found this which was a fun little read: https://preshing.com/20130618/atomic-vs-non-atomic-operations/