core.stdc.stdatomic

[Richard (Rikki) Andrew Cattermole]

On 15/11/2023 7:13 AM, Walter Bright wrote:
> Correct multithreaded code is about doing things in the correct 
> sequence, it is not about timing. If synchronization code is dependent 
> on instruction timing, it is inevitably going to fail because too many 
> things affect timing.

You have mostly caught on to the problems here that I have experienced. 
About the only people who can write lock-free concurrent data structures 
reliably work with kernels and yes kernels do have them. As a subject 
matter they are only about 20 years old (30 for some key theory). Which 
is very young for data structures.



To quote Andrei about its significance:

If you believe that's a fundamental enough question to award a prize to 
the answerer, so did others. In 2003, Maurice Herlihy was awarded the 
Edsger W. Dijkstra Prize in Distributed Computing for his seminal 1991 
paper "Wait-Free Synchronization" (see 
http://www.podc.org/dijkstra/2003.html, which includes a link to the 
paper, too). In his tour-de-force paper, Herlihy proves which primitives 
are good and which are bad for building lock-free data structures. That 
brought some seemingly hot hardware architectures to instant 
obsolescence, while clarifying what synchronization primitives should be 
implemented in future hardware.

https://drdobbs.com/lock-free-data-structures/184401865



So it is timing based, you have set points which act as synchronization 
events and then everything after it must work exactly the same on each 
core. This is VERY HARD!

I got grey hair because of dmd using inline assembly, because function 
calls do not result in "exact" timings after those synchronization 
points! But it was possible with ldc with a lot of work, just not dmd.



I'm not the only one who has gone down this path:

https://github.com/MartinNowak/lock-free

https://github.com/mw66/liblfdsd

https://github.com/nin-jin/go.d



 > As a path forward for DMD:
 >
 >  1. implement core.stdc.stdatomic in terms of core.atomic and/or
 >     core.internal.atomic
 >
 >  2. eventually add intrinsics to dmd to replace them

Almost. Everything that is in core.stdc.stdatomic should have similar 
codegen to the C compiler, if it doesn't that is a bug, this is what 
gives it the value desired, the guarantee that it will line up.

So my proposal is almost the same but applies to all compilers:

1. Implement functions that wrap core.internal.atomic iff those function 
implementations are intrinsics, equivalent to an intrinsic or uses locking.
2. Implement intrinsics in core.interal.atomic and then implement the 
corresponding wrapper function for stdatomic.