Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #145970 > unrolled thread

Example uses for read-modify-write operations?

Back to article view | Back to comp.lang.c

Contents

  Example uses for read-modify-write operations? Philipp Klaus Krause <pkk@spth.de> - 2019-09-04 11:20 +0200
    Re: Example uses for read-modify-write operations? Clifford Heath <no.spam@please.net> - 2019-09-04 20:44 +1000
      Re: Example uses for read-modify-write operations? Philipp Klaus Krause <pkk@spth.de> - 2019-09-04 13:26 +0200
        Re: Example uses for read-modify-write operations? Clifford Heath <no.spam@please.net> - 2019-09-04 22:13 +1000
          Re: Example uses for read-modify-write operations? Philipp Klaus Krause <pkk@spth.de> - 2019-09-04 14:33 +0200
        Re: Example uses for read-modify-write operations? already5chosen@yahoo.com - 2019-09-04 05:14 -0700
          Re: Example uses for read-modify-write operations? Philipp Klaus Krause <pkk@spth.de> - 2019-09-04 14:35 +0200
          Re: Example uses for read-modify-write operations? mark.bluemel@gmail.com - 2019-09-04 08:24 -0700
            Re: Example uses for read-modify-write operations? already5chosen@yahoo.com - 2019-09-04 08:37 -0700
            Re: Example uses for read-modify-write operations? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-09-04 17:10 +0100
    Re: Example uses for read-modify-write operations? Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-04 14:28 +0200

#145970 — Example uses for read-modify-write operations?

While I saw fetch-and-add mentioned a few times as useful, though not as
powerful as compare-and-swap, hardware and software tend to provide more
atomic read-modify-write operations.

Typically (e.g. in C), there are

fetch-and-add
fetch-and-subtract
fetch-and-bitwise-or
fetch-and-bitwise-xor
fetch-and-bitwise-and
fetch-and-increment
fetch-and-decrement

That return the previous value before modification. There also are the
operators that work as read-modify-write (++, --, +=, -=, <<=, >>=, *=,
/*, %=, &=, |=, ^=) on atomics that instead return the new value.

Could someone please point me to examples of algorithms that use these?

Philipp

P.S.: I already tried to post this 4 hours ago, but it didn't show up
yet. Sorry if this results in a double post.

[toc] | [next] | [standalone]

#145975

On 4/9/19 7:20 pm, Philipp Klaus Krause wrote:
> While I saw fetch-and-add mentioned a few times as useful, though not as
> powerful as compare-and-swap, hardware and software tend to provide more
> atomic read-modify-write operations.
> 
> Typically (e.g. in C), there are
> 
> fetch-and-add
> fetch-and-subtract
> fetch-and-bitwise-or
> fetch-and-bitwise-xor
> fetch-and-bitwise-and
> fetch-and-increment
> fetch-and-decrement
> 
> That return the previous value before modification. There also are the
> operators that work as read-modify-write (++, --, +=, -=, <<=, >>=, *=,
> /*, %=, &=, |=, ^=) on atomics that instead return the new value.
> 
> Could someone please point me to examples of algorithms that use these?

If the instructions are truly atomic (bus-locked, excluding intervention 
by DMA as well as other CPU cores and their caches) they can be used to 
implement the full spectrum of lock-free parallelisation primitives.

I know this because I've done it :)

[toc] | [prev] | [next] | [standalone]

#145979

Am 04.09.19 um 12:44 schrieb Clifford Heath:
> On 4/9/19 7:20 pm, Philipp Klaus Krause wrote:
>> While I saw fetch-and-add mentioned a few times as useful, though not as
>> powerful as compare-and-swap, hardware and software tend to provide more
>> atomic read-modify-write operations.
>>
>> Typically (e.g. in C), there are
>>
>> fetch-and-add
>> fetch-and-subtract
>> fetch-and-bitwise-or
>> fetch-and-bitwise-xor
>> fetch-and-bitwise-and
>> fetch-and-increment
>> fetch-and-decrement
>>
>> That return the previous value before modification. There also are the
>> operators that work as read-modify-write (++, --, +=, -=, <<=, >>=, *=,
>> /*, %=, &=, |=, ^=) on atomics that instead return the new value.
>>
>> Could someone please point me to examples of algorithms that use these?
> 
> If the instructions are truly atomic (bus-locked, excluding intervention
> by DMA as well as other CPU cores and their caches) they can be used to
> implement the full spectrum of lock-free parallelisation primitives.
> 
> I know this because I've done it :)
> 

According to Herlihy, "Wait-Free Synchronization" (1991), the RMW
operations are stricly less powerful than compare-and-swap.
However, I am mostly interested in algorithms, where the RMW operations
come up naturally.

Philipp

[toc] | [prev] | [next] | [standalone]

#145980

On 4/9/19 9:26 pm, Philipp Klaus Krause wrote:
> Am 04.09.19 um 12:44 schrieb Clifford Heath:
>> On 4/9/19 7:20 pm, Philipp Klaus Krause wrote:
>>> While I saw fetch-and-add mentioned a few times as useful, though not as
>>> powerful as compare-and-swap, hardware and software tend to provide more
>>> atomic read-modify-write operations.
>>>
>>> Typically (e.g. in C), there are
>>>
>>> fetch-and-add
>>> fetch-and-subtract
>>> fetch-and-bitwise-or
>>> fetch-and-bitwise-xor
>>> fetch-and-bitwise-and
>>> fetch-and-increment
>>> fetch-and-decrement
>>>
>>> That return the previous value before modification. There also are the
>>> operators that work as read-modify-write (++, --, +=, -=, <<=, >>=, *=,
>>> /*, %=, &=, |=, ^=) on atomics that instead return the new value.
>>>
>>> Could someone please point me to examples of algorithms that use these?
>>
>> If the instructions are truly atomic (bus-locked, excluding intervention
>> by DMA as well as other CPU cores and their caches) they can be used to
>> implement the full spectrum of lock-free parallelisation primitives.
>>
>> I know this because I've done it :)
>>
> 
> According to Herlihy, "Wait-Free Synchronization" (1991), the RMW
> operations are stricly less powerful than compare-and-swap.
> However, I am mostly interested in algorithms, where the RMW operations
> come up naturally.

Perhaps so, but anything that allows you to do a mutex allows you to 
build everything else. Less efficiently, it's true (I used C&S) but still.

[toc] | [prev] | [next] | [standalone]

#145984

Am 04.09.19 um 14:13 schrieb Clifford Heath:
> 
> Perhaps so, but anything that allows you to do a mutex allows you to
> build everything else. Less efficiently, it's true (I used C&S) but still.

Though the mutex you get from fetch-and-add has a limit on the number of
threads waiting on it before it breaks (the maximum value of the
underlying data type), but I don't see that as a big restriction.

On the other hand, with a mutex, the things you build are no longer
wait-free (and Herlihy requires this property).

From the C perspective: You can build a lockless atomic (i.e. one that
can be used safely from signal handlers) easily with CAS, but not with a
mutex (unless there are certain restrictions on signal handlers beyond
what the C standard states).

Philipp

[toc] | [prev] | [next] | [standalone]

#145981

On Wednesday, September 4, 2019 at 2:26:21 PM UTC+3, Philipp Klaus Krause wrote:
> Am 04.09.19 um 12:44 schrieb Clifford Heath:
> > On 4/9/19 7:20 pm, Philipp Klaus Krause wrote:
> >> While I saw fetch-and-add mentioned a few times as useful, though not as
> >> powerful as compare-and-swap, hardware and software tend to provide more
> >> atomic read-modify-write operations.
> >>
> >> Typically (e.g. in C), there are
> >>
> >> fetch-and-add
> >> fetch-and-subtract
> >> fetch-and-bitwise-or
> >> fetch-and-bitwise-xor
> >> fetch-and-bitwise-and
> >> fetch-and-increment
> >> fetch-and-decrement
> >>
> >> That return the previous value before modification. There also are the
> >> operators that work as read-modify-write (++, --, +=, -=, <<=, >>=, *=,
> >> /*, %=, &=, |=, ^=) on atomics that instead return the new value.
> >>
> >> Could someone please point me to examples of algorithms that use these?
> > 
> > If the instructions are truly atomic (bus-locked, excluding intervention
> > by DMA as well as other CPU cores and their caches) they can be used to
> > implement the full spectrum of lock-free parallelisation primitives.
> > 
> > I know this because I've done it :)
> > 
> 
> According to Herlihy, "Wait-Free Synchronization" (1991), the RMW
> operations are stricly less powerful than compare-and-swap.
> However, I am mostly interested in algorithms, where the RMW operations
> come up naturally.
> 
> Philipp

I use it for simple parallel scheduler.
Imagine N jobs or "work items" that can be done independently in arbitrary order. Then there is a pool of M working threads. You have a variable CNT that points to the next unassigned work items in the list. A main thread initializes a CNT, fires working threads and waits for their completion. Each working thread runs in a loop. At the beginning of the loop it does idx=Fetch-and-Add(CNT). If idx >= N then working thread exits otherwise it processes work item # idx and continues to the beginning of the loop. That's about all. Apart of multiple details.

[toc] | [prev] | [next] | [standalone]

#145985

Am 04.09.19 um 14:14 schrieb already5chosen@yahoo.com:
> 
> I use it for simple parallel scheduler.
> Imagine N jobs or "work items" that can be done independently in arbitrary order. Then there is a pool of M working threads. You have a variable CNT that points to the next unassigned work items in the list. A main thread initializes a CNT, fires working threads and waits for their completion. Each working thread runs in a loop. At the beginning of the loop it does idx=Fetch-and-Add(CNT). If idx >= N then working thread exits otherwise it processes work item # idx and continues to the beginning of the loop. That's about all. Apart of multiple details.
> 

Thanks for giving a real-world example use of fetch-and-add.
From what I've read, fetch-and-add ist the most widely used of the RMW
operations.
Are there algorithms where one of the others occurs naturally (excluding
obvious rewrites of algorithms to use fetch-and-subtract intead of
fetch-and-add)?

Philipp

[toc] | [prev] | [next] | [standalone]

#145990

On Wednesday, 4 September 2019 13:14:40 UTC+1, already...@yahoo.com  wrote:
> On Wednesday, September 4, 2019 at 2:26:21 PM UTC+3, Philipp Klaus Krause wrote:
> > Am 04.09.19 um 12:44 schrieb Clifford Heath:
> > > On 4/9/19 7:20 pm, Philipp Klaus Krause wrote:
> > >> While I saw fetch-and-add mentioned a few times as useful, though not as
> > >> powerful as compare-and-swap, hardware and software tend to provide more
> > >> atomic read-modify-write operations.
> > >>
> > >> Typically (e.g. in C), there are
> > >>
> > >> fetch-and-add
> > >> fetch-and-subtract
> > >> fetch-and-bitwise-or
> > >> fetch-and-bitwise-xor
> > >> fetch-and-bitwise-and
> > >> fetch-and-increment
> > >> fetch-and-decrement
> > >>
> > >> That return the previous value before modification. There also are the
> > >> operators that work as read-modify-write (++, --, +=, -=, <<=, >>=, *=,
> > >> /*, %=, &=, |=, ^=) on atomics that instead return the new value.
> > >>
> > >> Could someone please point me to examples of algorithms that use these?
> > > 
> > > If the instructions are truly atomic (bus-locked, excluding intervention
> > > by DMA as well as other CPU cores and their caches) they can be used to
> > > implement the full spectrum of lock-free parallelisation primitives.
> > > 
> > > I know this because I've done it :)
> > > 
> > 
> > According to Herlihy, "Wait-Free Synchronization" (1991), the RMW
> > operations are stricly less powerful than compare-and-swap.
> > However, I am mostly interested in algorithms, where the RMW operations
> > come up naturally.
> > 
> > Philipp
> 
> ... You have a variable CNT ...

I learnt a long time ago not to call a variable CNT. It makes discussing
it awkward.

[toc] | [prev] | [next] | [standalone]

#145992

On Wednesday, September 4, 2019 at 6:24:31 PM UTC+3, mark....@gmail.com wrote:
> On Wednesday, 4 September 2019 13:14:40 UTC+1, already...@yahoo.com  wrote:
> > On Wednesday, September 4, 2019 at 2:26:21 PM UTC+3, Philipp Klaus Krause wrote:
> > > Am 04.09.19 um 12:44 schrieb Clifford Heath:
> > > > On 4/9/19 7:20 pm, Philipp Klaus Krause wrote:
> > > >> While I saw fetch-and-add mentioned a few times as useful, though not as
> > > >> powerful as compare-and-swap, hardware and software tend to provide more
> > > >> atomic read-modify-write operations.
> > > >>
> > > >> Typically (e.g. in C), there are
> > > >>
> > > >> fetch-and-add
> > > >> fetch-and-subtract
> > > >> fetch-and-bitwise-or
> > > >> fetch-and-bitwise-xor
> > > >> fetch-and-bitwise-and
> > > >> fetch-and-increment
> > > >> fetch-and-decrement
> > > >>
> > > >> That return the previous value before modification. There also are the
> > > >> operators that work as read-modify-write (++, --, +=, -=, <<=, >>=, *=,
> > > >> /*, %=, &=, |=, ^=) on atomics that instead return the new value.
> > > >>
> > > >> Could someone please point me to examples of algorithms that use these?
> > > > 
> > > > If the instructions are truly atomic (bus-locked, excluding intervention
> > > > by DMA as well as other CPU cores and their caches) they can be used to
> > > > implement the full spectrum of lock-free parallelisation primitives.
> > > > 
> > > > I know this because I've done it :)
> > > > 
> > > 
> > > According to Herlihy, "Wait-Free Synchronization" (1991), the RMW
> > > operations are stricly less powerful than compare-and-swap.
> > > However, I am mostly interested in algorithms, where the RMW operations
> > > come up naturally.
> > > 
> > > Philipp
> > 
> > ... You have a variable CNT ...
> 
> I learnt a long time ago not to call a variable CNT. It makes discussing
> it awkward.

There are advantages in not being a native English speaker and not having many native English speakers around.
It took me like 10 seconds to even understand what you are talking about.

BTW, by chance the variable is not named CNT in the real code. There it's a field in the structure (a.k.a. class) and it's name is m_runElementI.

[toc] | [prev] | [next] | [standalone]

#145993

mark.bluemel@gmail.com writes:
> On Wednesday, 4 September 2019 13:14:40 UTC+1, already...@yahoo.com  wrote:
<cut>
>> ... You have a variable CNT ...
>
> I learnt a long time ago not to call a variable CNT. It makes discussing
> it awkward.

Yes, and it needs extra care when writing code fragments live in front
of a class.  Even "count" should probably be avoided.  I found this out
the hard way, though the ID I was writing was "func".

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#145983

Am 04.09.2019 um 11:20 schrieb Philipp Klaus Krause:
> While I saw fetch-and-add mentioned a few times as useful, though not as
> powerful as compare-and-swap, hardware and software tend to provide more
> atomic read-modify-write operations.
> Typically (e.g. in C), there are
> fetch-and-add
> fetch-and-subtract
> fetch-and-bitwise-or
> fetch-and-bitwise-xor
> fetch-and-bitwise-and
> fetch-and-increment
> fetch-and-decrement

These instuctions like LOCK XADD on x86 can't alway replace LOCK CMPXCHG
always. With LOCK XADD f.e. you could write a simple mutex. The locking
occurs in a way that you have a counter which is incremented atomically
by this instruction and the value before this increment is evaluated
after; if it is zero, the thread has gained the lock, if it is higher
than zero, the thread will be one of the threads waiting for the lock.
And if a thread relinquishes the lock it does LOCK XADD with -1 and if
the value before is higher than 1, it awakens one of the threads waiting
to get ownership of the lock.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web