Fast semaphore

mvor...@gmail.com

unread,

Feb 5, 2019, 2:25:03 PM2/5/19

to

my blog entry about fast c++ semaphore implementation: http://blog.vorbrodt.me/?p=495

Chris M. Thomasson

unread,

Feb 5, 2019, 6:20:55 PM2/5/19

to

On 2/5/2019 11:24 AM, mvor...@gmail.com wrote:
> my blog entry about fast c++ semaphore implementation: http://blog.vorbrodt.me/?p=495
>

Thank you for your interest. The "fast_semaphore" algorithm has many
advantages over a traditional "slow_semaphore". Fwiw, Joe Seigh
developed this back on comp.programming.threads within one of my
discussions with him, many years ago. IIRC, around 2007. Damn, I am
getting older. The ability to skip a lot of calls into to the
"slow_semaphore" is very beneficial.

;^)

mvor...@gmail.com

unread,

Feb 5, 2019, 6:38:47 PM2/5/19

to

you're very welcome :) thank you for sharing it with me. could you maybe comment on my blog please and give us an explanation of how exactly it work, and why the specific values for memory model?

mvor...@gmail.com

unread,

Feb 5, 2019, 6:40:23 PM2/5/19

to

On Tuesday, February 5, 2019 at 6:20:55 PM UTC-5, Chris M. Thomasson wrote:

See here: https://www.reddit.com/r/cpp/comments/anhnw3/fast_semaphore/

Chris M. Thomasson

unread,

Feb 5, 2019, 7:01:36 PM2/5/19

to

Before I comment there, the fences in the fast_semaphore are exactly
what is needed. Period. We _cannot_ get rid if them. End of story. I
will provide more into later on today or tomorrow.

Chris M. Thomasson

unread,

Feb 5, 2019, 7:07:36 PM2/5/19

to

Actually, this is a good example. If we remove any of the fences, or
even weaken them, then the algorithm does _not_ work at all! The fences
enforce the acquire/release relationship between the wait/post functions
where wait is acquire, and post is release. The code has the position of
the membars in the exact correct position. The release is _before_ we do
anything in post. The acquire is _after_ we do everything in wait. If
the position of the standalone fences is changed, then the algorithm
will bite the dust.

Joe Seighs excellent algorithm is 100% correct, and the implementation I
showed you is 100% correct, period.

Will go into more detail today or tomorrow.

Chris M. Thomasson

unread,

Feb 5, 2019, 7:18:02 PM2/5/19

to

Ahhh, the following interesting discussion might be of interest wrt the
standalone fences:

https://groups.google.com/d/topic/lock-free/A1nzcMBGRzU/discussion
(read all...)

Another reason why I like standalone fences is that we can place them in
the _exact_ places they need to be. The other style of fences are
directly integrated into the std::atomic operations themselves. However,
they can be limited wrt flexibility. Take the following code into
account: It flushes all of the nodes from an atomic stack in a single
atomic operation:
_____________________________
// try to flush all of our nodes
node* flush()
{
node* n = m_head.exchange(nullptr, mb_relaxed);

if (n)
{
mb_fence(mb_acquire);
}

return n;
}
_____________________________

Notice how this specialized 100% standard membar setup is _impossible_
to accomplish with the integrated membars? Standalone fences are what I
am basically used to working with way back on the SPARC.

Chris M. Thomasson

unread,

Feb 6, 2019, 2:24:13 AM2/6/19

to

On 2/5/2019 11:24 AM, mvor...@gmail.com wrote:

> my blog entry about fast c++ semaphore implementation: http://blog.vorbrodt.me/?p=495
>

Fwiw, this is called a benaphore:

https://en.wikipedia.org/wiki/Futex#BENAPHORE

I am not sure if Joe Seigh helped invent it or not. He was working at
IBM in the 80's and 90's. Fwiw, here is a patent for an interesting
reference counting algorithm invented by Joe:

https://patents.google.com/patent/US5295262