Menu
Search

Forums

Forum Index

Jump to page: 1 2
Thread overview
Is core.internal.atomic.atomicFetchAdd implementation really lock free?
Nov 30, 2022
mw
Nov 30, 2022
Vladimir Panteleev
Nov 30, 2022
H. S. Teoh
Nov 30, 2022
rikki cattermole
Nov 30, 2022
H. S. Teoh
Nov 30, 2022
claptrap
Nov 30, 2022
rikki cattermole
Nov 30, 2022
Iain Buclaw
Dec 03, 2022
claptrap
Dec 03, 2022
max haughton
Dec 03, 2022
claptrap
Dec 03, 2022
max haughton
Dec 03, 2022
claptrap
Dec 04, 2022
max haughton
Dec 04, 2022
rikki cattermole
Dec 04, 2022
claptrap
Dec 04, 2022
max haughton
Dec 05, 2022
claptrap
Dec 05, 2022
max haughton
Dec 05, 2022
Johan
November 30, 2022
Gravatar of mwPosted by mwReply
mw
Gravatar of mw


Reply

According to the doc:

https://dlang.org/library/core/atomic/atomic_fetch_add.html

Atomically adds mod to the value referenced by val and returns the value val held previously. This operation is both lock-free and atomic.

However, when I check its final implementation, I saw

https://github.com/dlang/dmd/blob/master/druntime/src/core/internal/atomic.d#L275

lock; xadd[%0], %1;

Is this really lock free?

If not, can we use cas to implement it, e.g pseudo code:

int atomicFetchAdd(int * pAddr, int nIncr ) {

 while (true) {
  int ncur = atomicLoad(pAddr);
  if (cas( pAddr, ncur, ncur + nIncr )
    return ncur ;
 }

}
November 30, 2022
Gravatar of Vladimir PanteleevPosted by Vladimir Panteleev
in reply to mw		Reply
Vladimir Panteleev
Gravatar of Vladimir Panteleev
Posted in reply to mw


Reply

(Disclaimer: I have not studied lock-free programming so I might be wrong.)

On Wednesday, 30 November 2022 at 00:04:22 UTC, mw wrote:

> 
lock; xadd[%0], %1;

Is this really lock free?

lock here refers not to some mutex (which is what "lock free" generally means), but to the processor cache line:

https://stackoverflow.com/questions/8891067/what-does-the-lock-instruction-mean-in-x86-assembly

>

If not, can we use cas to implement it, e.g pseudo code:

int atomicFetchAdd(int * pAddr, int nIncr ) {

 while (true) {
  int ncur = atomicLoad(pAddr);
  if (cas( pAddr, ncur, ncur + nIncr )
    return ncur ;
 }

}

CMPXCHG, used to implement CAS on x86, needs LOCK as well:

https://stackoverflow.com/questions/27837731/is-x86-cmpxchg-atomic-if-so-why-does-it-need-lock

November 29, 2022
Gravatar of H. S. TeohPosted by H. S. Teoh
in reply to mw		Reply
H. S. Teoh
Gravatar of H. S. Teoh
Posted in reply to mw


Reply
On Wed, Nov 30, 2022 at 12:04:22AM +0000, mw via Digitalmars-d wrote:
> According to the doc:
> 
> https://dlang.org/library/core/atomic/atomic_fetch_add.html
> 
> Atomically adds mod to the value referenced by val and returns the value val held previously. This operation is both lock-free and atomic.
[...]

Hmm, that's weird that the docs would say that.  I've always been under
the impression that core.atomic ops use locks to achieve atomicity.


T

-- 
Which is worse: ignorance or apathy? Who knows? Who cares? -- Erich Schubert
November 30, 2022
Gravatar of rikki cattermolePosted by rikki cattermole
in reply to H. S. Teoh		Reply
rikki cattermole
Gravatar of rikki cattermole
Posted in reply to H. S. Teoh


Reply
On 30/11/2022 1:12 PM, H. S. Teoh wrote:
> Hmm, that's weird that the docs would say that.  I've always been under
> the impression that core.atomic ops use locks to achieve atomicity.

No its correct.

As long as the hardware supports atomic operations, it'll use those instructions. It does have a fallback to use a mutex if need be though, which might be where you got that idea from.
November 29, 2022
Gravatar of H. S. TeohPosted by H. S. Teoh
in reply to rikki cattermole		Reply
H. S. Teoh
Gravatar of H. S. Teoh
Posted in reply to rikki cattermole


Reply
On Wed, Nov 30, 2022 at 01:16:00PM +1300, rikki cattermole via Digitalmars-d wrote:
> On 30/11/2022 1:12 PM, H. S. Teoh wrote:
> > Hmm, that's weird that the docs would say that.  I've always been under the impression that core.atomic ops use locks to achieve atomicity.
> 
> No its correct.
> 
> As long as the hardware supports atomic operations, it'll use those instructions. It does have a fallback to use a mutex if need be though, which might be where you got that idea from.

Ah, I see. Thanks!


T

-- 
It is not the employer who pays the wages. Employers only handle the money. It is the customer who pays the wages. -- Henry Ford
November 30, 2022
Gravatar of claptrapPosted by claptrap
in reply to rikki cattermole		Reply
claptrap
Gravatar of claptrap
Posted in reply to rikki cattermole


Reply
On Wednesday, 30 November 2022 at 00:16:00 UTC, rikki cattermole wrote:
> On 30/11/2022 1:12 PM, H. S. Teoh wrote:
>> Hmm, that's weird that the docs would say that.  I've always been under
>> the impression that core.atomic ops use locks to achieve atomicity.
>
> No its correct.
>
> As long as the hardware supports atomic operations, it'll use those instructions. It does have a fallback to use a mutex if need be though, which might be where you got that idea from.

It really shouldn't do that IMO. People expect atomic ops to be lock-free, it should be compile error if it cant be so.
November 30, 2022
Gravatar of rikki cattermolePosted by rikki cattermole
in reply to claptrap		Reply
rikki cattermole
Gravatar of rikki cattermole
Posted in reply to claptrap


Reply
On 30/11/2022 1:35 PM, claptrap wrote:
> On Wednesday, 30 November 2022 at 00:16:00 UTC, rikki cattermole wrote:
>> On 30/11/2022 1:12 PM, H. S. Teoh wrote:
>>> Hmm, that's weird that the docs would say that.  I've always been under
>>> the impression that core.atomic ops use locks to achieve atomicity.
>>
>> No its correct.
>>
>> As long as the hardware supports atomic operations, it'll use those instructions. It does have a fallback to use a mutex if need be though, which might be where you got that idea from.
> 
> It really shouldn't do that IMO. People expect atomic ops to be lock-free, it should be compile error if it cant be so.

It does.

Its really only GDC that supports it with its wide range of esoteric targets.

But generally speaking if druntime works on a CPU it probably has atomics.
November 30, 2022
Gravatar of Iain BuclawPosted by Iain Buclaw
in reply to claptrap		Reply
Iain Buclaw
Gravatar of Iain Buclaw
Posted in reply to claptrap


Reply

On Wednesday, 30 November 2022 at 00:35:55 UTC, claptrap wrote:

>

On Wednesday, 30 November 2022 at 00:16:00 UTC, rikki cattermole wrote:

>

On 30/11/2022 1:12 PM, H. S. Teoh wrote:

>

Hmm, that's weird that the docs would say that. I've always been under
the impression that core.atomic ops use locks to achieve atomicity.

No its correct.

As long as the hardware supports atomic operations, it'll use those instructions. It does have a fallback to use a mutex if need be though, which might be where you got that idea from.

It really shouldn't do that IMO. People expect atomic ops to be lock-free, it should be compile error if it cant be so.

C++'s std::atomic has followed this precedent too of using a mutex if all else fails.

Really, you'd have to be pretty explicit in forcing GDC built-in atomics to be disabled at configure-time - there's an atomic library right there in GCC's tree if a given target does not have native support.

December 03, 2022
Gravatar of max haughtonPosted by max haughton
in reply to claptrap		Reply
max haughton
Gravatar of max haughton
Posted in reply to claptrap


Reply
On Wednesday, 30 November 2022 at 00:35:55 UTC, claptrap wrote:
> On Wednesday, 30 November 2022 at 00:16:00 UTC, rikki cattermole wrote:
>> On 30/11/2022 1:12 PM, H. S. Teoh wrote:
>>> Hmm, that's weird that the docs would say that.  I've always been under
>>> the impression that core.atomic ops use locks to achieve atomicity.
>>
>> No its correct.
>>
>> As long as the hardware supports atomic operations, it'll use those instructions. It does have a fallback to use a mutex if need be though, which might be where you got that idea from.
>
> It really shouldn't do that IMO. People expect atomic ops to be lock-free, it should be compile error if it cant be so.

I expect atomic ops to provide correct memory consistency, and preferably be atomic where the platform allows it.
December 03, 2022
Gravatar of claptrapPosted by claptrap
in reply to max haughton		Reply
claptrap
Gravatar of claptrap
Posted in reply to max haughton


Reply
On Saturday, 3 December 2022 at 03:42:01 UTC, max haughton wrote:
> On Wednesday, 30 November 2022 at 00:35:55 UTC, claptrap wrote:
>> On Wednesday, 30 November 2022 at 00:16:00 UTC, rikki cattermole wrote:
>>> On 30/11/2022 1:12 PM, H. S. Teoh wrote:
>>>> Hmm, that's weird that the docs would say that.  I've always been under
>>>> the impression that core.atomic ops use locks to achieve atomicity.
>>>
>>> No its correct.
>>>
>>> As long as the hardware supports atomic operations, it'll use those instructions. It does have a fallback to use a mutex if need be though, which might be where you got that idea from.
>>
>> It really shouldn't do that IMO. People expect atomic ops to be lock-free, it should be compile error if it cant be so.
>
> I expect atomic ops to provide correct memory consistency, and preferably be atomic where the platform allows it.

I am really hoping that "preferably atomic" was just a poor choice or words.

I guess regarding the other issues I still think of atomic ops in terms of what the cpu does, so a high level wrapper around them that takes a lock is the complete antithesis to what is actually desired.

I mean the whole point of atomic ops is to be able to avoid using locks.

And if you look at the phobos docs...

"Atomically adds mod to the value referenced by val and returns the value val held previously. This operation is both lock-free and atomic."

https://dlang.org/library/core/atomic/atomic_fetch_add.html
« First   ‹ Prev
1 2
Next ›   Last »