counting_semaphore question

[M***@dastardlyhq.com]

I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
parameter value. eg you can do:

std::counting_semaphore sem(2)

which will let a max of 2 threads into the protected block at a time or:

std::counting_semaphore<some number> sem(2)

such as

std::counting_semaphore<10> sem(2)

I don't understand what the '10' will do. Its returned by the max()
method but whats its purpose since if its the maximum possible threads
you could have in the protected block it makes no sense because you can't
change that value after creation as far as I can see.

Thanks for any help.

[Bonita Montero]

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)
std::counting_semaphore<some number> sem(2)
such as
std::counting_semaphore<10> sem(2)
I don't understand what the '10' will do. ..

The ten gives an upper limit beyond the semaphore wont't increment.

Usually you won't need a C++20 semaphore yourself. For most purpose
the mutex and the condition_variable is sufficient.
But if you will build your own synchronization-primitives you inter-
nally would also need a semaphore. The semaphore class itself is
usually built on top of the system-provided futex. I implemented
a reader's writer lock with configurable priority for either rea-
ders or writers (std::shared_mutex only supports reader-priority)
and therefore I needed C++20's counting_semaphore and binary_sema-
phore (which is an template-alias for counting_senaphore<1>).

[M***@dastardlyhq.com]

On Wed, 11 Sep 2024 13:48:04 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)
std::counting_semaphore<some number> sem(2)
such as
std::counting_semaphore<10> sem(2)
I don't understand what the '10' will do. ..

The ten gives an upper limit beyond the semaphore wont't increment.

What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

Post by Bonita Montero
Usually you won't need a C++20 semaphore yourself. For most purpose
the mutex and the condition_variable is sufficient.

Condition variables IMO are unintuitive (eg the internal state change from
waiting on condition variable to waiting on mutex is completely invisible)
and hence very prone to logical bugs. I tend to avoid them where possible.

[Bonita Montero]

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Post by M***@dastardlyhq.com
Condition variables IMO are unintuitive (eg the internal state change from
waiting on condition variable to waiting on mutex is completely invisible)
and hence very prone to logical bugs. I tend to avoid them where possible.

If you have a producer-consumer-pattern condition variables are the most
efficient way to handle this pattern.

[M***@dastardlyhq.com]

On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?

Maximum threads that can wait on the semaphore and 11 gets an error?
Maximum threads that can ever access the protected section and after 10 have
accessed it the section is blocked to all threads?

Post by Bonita Montero

Post by M***@dastardlyhq.com
Condition variables IMO are unintuitive (eg the internal state change from
waiting on condition variable to waiting on mutex is completely invisible)
and hence very prone to logical bugs. I tend to avoid them where possible.

If you have a producer-consumer-pattern condition variables are the most
efficient way to handle this pattern.

Efficient maybe, but the code can be obtuse and debugging a pain.

[Bonita Montero]

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero
The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?

If you have a maximum counter of ten and an initial counter of two
you may increment the counter further eight times until another
release doesn't increment the counter.

Post by M***@dastardlyhq.com

Post by Bonita Montero
If you have a producer-consumer-pattern condition variables are
the most efficient way to handle this pattern.

Efficient maybe, but the code can be obtuse and debugging a pain.

The trick with condition variables is that the condition is met,
i.e. there are items to consume, there are no further kernel-calls.
That's basically the same with Java monitors with the slight dif-
ference, that monitors can be implemented somewhat more efficient
than a mutex / condvar combination.

[M***@dastardlyhq.com]

On Wed, 11 Sep 2024 15:54:12 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero
The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?

If you have a maximum counter of ten and an initial counter of two
you may increment the counter further eight times until another
release doesn't increment the counter.

I don't see how it works in practice.

acquire() increments the counter and it won't go beyond 2 (or whatever
you set the maximum thread acquire count to) once 2 have aquired it and
release() decrements it.

I've tried setting the max counters to all sorts of values including zero and
it makes no difference whatsoever to how this code executes:

#include <stdio.h>
#include <unistd.h>

#include <thread>
#include <semaphore>

using namespace std;

counting_semaphore<1> sem(2);

void func(int i)
{
printf("Thread %d waiting\n",i);
sem.acquire();
printf("Thread %d acquired\n",i);
sleep(1);
printf("Thread %d releasing\n",i);
sem.release();
}

int main()
{
thread thr[10];
printf("Max = %d\n",sem.max());
for(int i=0;i < 10;++i) thr[i] = thread(func,i);
for(int i=0;i < 10;++i) thr[i].join();
return 0;
}

[David Brown]

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?
Maximum threads that can wait on the semaphore and 11 gets an error?
Maximum threads that can ever access the protected section and after 10 have
accessed it the section is blocked to all threads?

You are talking about a counting semaphore here - the number will be the
maximum value of the count. (The actual maximum value could be bigger
than the template parameter, but not smaller than it.) If this maximum
value is 10, then you can acquire the semaphore 10 times without
blocking - any future acquires will block until there are releases.

Semaphores can be acquired and released by any threads - one thread can
acquire often, another thread can release them, or you can have any
combination. They are not used for protection sections or data - they
are used as signalling mechanisms. One or more "producer" thread might
make objects, and one or more "consumer" threads used them, in which
case your 10 here is the maximum number of these objects that will be
buffered up at a time.

Post by M***@dastardlyhq.com

Post by Bonita Montero

Post by M***@dastardlyhq.com
Condition variables IMO are unintuitive (eg the internal state change from
waiting on condition variable to waiting on mutex is completely invisible)
and hence very prone to logical bugs. I tend to avoid them where possible.

If you have a producer-consumer-pattern condition variables are the most
efficient way to handle this pattern.

Efficient maybe, but the code can be obtuse and debugging a pain.

<https://en.cppreference.com/w/cpp/thread/counting_semaphore>

This suggests that semaphores may be an alteranative to condition
variables but with better performance. (Individual implementations may
vary, of course.)

[Chris M. Thomasson]

Post by David Brown

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?
Maximum threads that can wait on the semaphore and 11 gets an error?
Maximum threads that can ever access the protected section and after 10 have
accessed it the section is blocked to all threads?

You are talking about a counting semaphore here - the number will be the
maximum value of the count.  (The actual maximum value could be bigger
than the template parameter, but not smaller than it.)  If this maximum
value is 10, then you can acquire the semaphore 10 times without
blocking - any future acquires will block until there are releases.
Semaphores can be acquired and released by any threads - one thread can
acquire often, another thread can release them, or you can have any
combination.  They are not used for protection sections or data - they
are used as signalling mechanisms.  One or more "producer" thread might
make objects, and one or more "consumer" threads used them, in which
case your 10 here is the maximum number of these objects that will be
buffered up at a time.

[...]

Think of creating a queue with 100,000 elements in it. The semaphore to
protect this queue should have an initial state of 100,000. The least
min value, should be high because the queue might have 1.9 million
elements in there. So, for this queue:

std::counting_semaphore<PTRDIFF_MAX> sem(100000);

right? There are 100000 elements in the queue because its initialized
that way. A single thread can pop and work on 100000 elements before it
blocks on a queue empty condition.

[David Brown]

Post by Chris M. Thomasson

Post by David Brown

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the
protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?
Maximum threads that can wait on the semaphore and 11 gets an error?
Maximum threads that can ever access the protected section and after 10 have
accessed it the section is blocked to all threads?

You are talking about a counting semaphore here - the number will be
the maximum value of the count.  (The actual maximum value could be
bigger than the template parameter, but not smaller than it.)  If this
maximum value is 10, then you can acquire the semaphore 10 times
without blocking - any future acquires will block until there are
releases.
Semaphores can be acquired and released by any threads - one thread
can acquire often, another thread can release them, or you can have
any combination.  They are not used for protection sections or data -
they are used as signalling mechanisms.  One or more "producer" thread
might make objects, and one or more "consumer" threads used them, in
which case your 10 here is the maximum number of these objects that
will be buffered up at a time.

[...]
Think of creating a queue with 100,000 elements in it. The semaphore to
protect this queue should have an initial state of 100,000. The least
min value, should be high because the queue might have 1.9 million
std::counting_semaphore<PTRDIFF_MAX> sem(100000);
right? There are 100000 elements in the queue because its initialized
that way. A single thread can pop and work on 100000 elements before it
blocks on a queue empty condition.

Roughly yes - assuming you are setting up the queue with the first
100,000 elements and then creating the semaphore, then allowing the
queue to grow or shrink unhindered. It's more common for queues to
start with a semaphore of count 0 (an empty queue) and then add
elements, but if you have 100,000 elements in advance then this would be
a more efficient initialisation.

You can also omit the template parameter, in which case an
implementation-defined default is used. A quick test on godbolt's gcc
shows that this gives a max() of 0x7fff'ffff, and that this is the
largest value supported by the C++ library used by that implementation -
it keeps the count as a signed 32-bit integer. Attempting to use
PTRDIFF_MAX triggers a static assertion:

static_assert(__least_max_value <= __semaphore_impl::_S_max);

I don't know if this is a conformance flaw in the C++ standard library,
or if I just haven't read the documentation details well enough. And I
couldn't see any specification for what the default value should be, but
I can't think of any other reasonable choice than the biggest acceptable
value.

[Chris M. Thomasson]

Post by David Brown

Post by Chris M. Thomasson

Post by David Brown

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?
Maximum threads that can wait on the semaphore and 11 gets an error?
Maximum threads that can ever access the protected section and after 10 have
accessed it the section is blocked to all threads?

You are talking about a counting semaphore here - the number will be
the maximum value of the count.  (The actual maximum value could be
bigger than the template parameter, but not smaller than it.)  If
this maximum value is 10, then you can acquire the semaphore 10 times
without blocking - any future acquires will block until there are
releases.
Semaphores can be acquired and released by any threads - one thread
can acquire often, another thread can release them, or you can have
any combination.  They are not used for protection sections or data -
they are used as signalling mechanisms.  One or more "producer"
thread might make objects, and one or more "consumer" threads used
them, in which case your 10 here is the maximum number of these
objects that will be buffered up at a time.

[...]
Think of creating a queue with 100,000 elements in it. The semaphore
to protect this queue should have an initial state of 100,000. The
least min value, should be high because the queue might have 1.9
std::counting_semaphore<PTRDIFF_MAX> sem(100000);
right? There are 100000 elements in the queue because its initialized
that way. A single thread can pop and work on 100000 elements before
it blocks on a queue empty condition.

Roughly yes - assuming you are setting up the queue with the first
100,000 elements and then creating the semaphore, then allowing the
queue to grow or shrink unhindered.  It's more common for queues to
start with a semaphore of count 0 (an empty queue) and then add
elements, but if you have 100,000 elements in advance then this would be
a more efficient initialisation.

I sure think so. :^)

Post by David Brown
You can also omit the template parameter, in which case an
implementation-defined default is used.  A quick test on godbolt's gcc
shows that this gives a max() of 0x7fff'ffff, and that this is the
largest value supported by the C++ library used by that implementation -
it keeps the count as a signed 32-bit integer.  Attempting to use
    static_assert(__least_max_value <= __semaphore_impl::_S_max);

Oh shit! I assumed setting it to PTRDIFF_MAX is okay. Shit! Well, damn.
thanks for the info David. Sometimes I think the template parameter is
there for specialization purposes ala binary semaphore with its template
param as 1.

Post by David Brown
I don't know if this is a conformance flaw in the C++ standard library,
or if I just haven't read the documentation details well enough.  And I
couldn't see any specification for what the default value should be, but
I can't think of any other reasonable choice than the biggest acceptable
value.

Agreed. Again, thanks for the info. :^)

[David Brown]

Post by Chris M. Thomasson

Post by David Brown

Post by Chris M. Thomasson

Post by David Brown

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?
Maximum threads that can wait on the semaphore and 11 gets an error?
Maximum threads that can ever access the protected section and after 10 have
accessed it the section is blocked to all threads?

You are talking about a counting semaphore here - the number will be
the maximum value of the count.  (The actual maximum value could be
bigger than the template parameter, but not smaller than it.)  If
this maximum value is 10, then you can acquire the semaphore 10
times without blocking - any future acquires will block until there
are releases.
Semaphores can be acquired and released by any threads - one thread
can acquire often, another thread can release them, or you can have
any combination.  They are not used for protection sections or data
- they are used as signalling mechanisms.  One or more "producer"
thread might make objects, and one or more "consumer" threads used
them, in which case your 10 here is the maximum number of these
objects that will be buffered up at a time.

[...]
Think of creating a queue with 100,000 elements in it. The semaphore
to protect this queue should have an initial state of 100,000. The
least min value, should be high because the queue might have 1.9
std::counting_semaphore<PTRDIFF_MAX> sem(100000);
right? There are 100000 elements in the queue because its initialized
that way. A single thread can pop and work on 100000 elements before
it blocks on a queue empty condition.

Roughly yes - assuming you are setting up the queue with the first
100,000 elements and then creating the semaphore, then allowing the
queue to grow or shrink unhindered.  It's more common for queues to
start with a semaphore of count 0 (an empty queue) and then add
elements, but if you have 100,000 elements in advance then this would
be a more efficient initialisation.

I sure think so. :^)

Post by David Brown
You can also omit the template parameter, in which case an
implementation-defined default is used.  A quick test on godbolt's gcc
shows that this gives a max() of 0x7fff'ffff, and that this is the
largest value supported by the C++ library used by that implementation
- it keeps the count as a signed 32-bit integer.  Attempting to use
     static_assert(__least_max_value <= __semaphore_impl::_S_max);

Oh shit! I assumed setting it to PTRDIFF_MAX is okay. Shit! Well, damn.
thanks for the info David. Sometimes I think the template parameter is
there for specialization purposes ala binary semaphore with its template
param as 1.

That seems likely. It also allows for specialisation for different
sizes, though that did not appear to be used for by the library with the
gcc on godbolt. A small max value could perhaps be implemented with
fixed size queues instead of variable ones, and (without having
considered implementations in detail) it is plausible that a semaphore
counter with a 32-bit counter could be more efficient than one with a
64-bit counter. But most likely specialisation is a binary semaphore
(the <semaphore> header already has "using binary_semaphore =
counting_semaphore<1>;").

Post by Chris M. Thomasson

Post by David Brown
I don't know if this is a conformance flaw in the C++ standard
library, or if I just haven't read the documentation details well
enough.  And I couldn't see any specification for what the default
value should be, but I can't think of any other reasonable choice than
the biggest acceptable value.

Agreed. Again, thanks for the info. :^)

[Bonita Montero]

That seems likely.  It also allows for specialisation for different
sizes, though that did not appear to be used for by the library with
the gcc on godbolt.  A small max value could perhaps be implemented
with fixed size queues instead of variable ones, ...

The queue is for for sure maintained by the kernel and is a linked list.

... and (without having considered implementations in detail) it is
plausible that a semaphore counter with a 32-bit counter could be more
efficient than one with a 64-bit counter.

I guess that it's unlikely that the counter is 64 bit.

But most likely specialisation is a binary semaphore (the <semaphore>
header already has "using binary_semaphore = counting_semaphore<1>;").

That's how the standard specifies binary_semaphore as an alias to
counting_semaphore<1>.

[Bonita Montero]

Post by Bonita Montero
I guess that it's unlikely that the counter is 64 bit.

The initialitation value of a Posix semaphore is an unsigned int.
The initialitation value of a System V semaphore is an int.

[Chris M. Thomasson]

Post by Bonita Montero

That seems likely.  It also allows for specialisation for different
sizes, though that did not appear to be used for by the library with
the  gcc on godbolt.  A small max value could perhaps be implemented
with fixed size queues instead of variable ones, ...

The queue is for for sure maintained by the kernel and is a linked list.

... and (without having  considered implementations in detail) it is
plausible that a semaphore counter with a 32-bit counter could be more
efficient than one with a 64-bit counter.

I guess that it's unlikely that the counter is 64 bit.

Well, I was wondering about using std::ptrdiff_t. It's a little "easier"
to implement a fast semaphore using signed integers. :^)

Post by Bonita Montero

But most likely specialisation is a binary semaphore  (the <semaphore>
header already has "using binary_semaphore = counting_semaphore<1>;").

That's how the standard specifies binary_semaphore as an alias to
counting_semaphore<1>.

Exactly.

[Chris M. Thomasson]

Post by Bonita Montero

That seems likely.  It also allows for specialisation for different
sizes, though that did not appear to be used for by the library with
the  gcc on godbolt.  A small max value could perhaps be implemented
with fixed size queues instead of variable ones, ...

The queue is for for sure maintained by the kernel and is a linked list.

We used to refer to these as kernel waitsets back in the day. Still,
keep the benaphore in mind:

https://www.haiku-os.org/legacy-docs/benewsletter/Issue1-26.html#Engineering1-26

Post by Bonita Montero

... and (without having  considered implementations in detail) it is
plausible that a semaphore counter with a 32-bit counter could be more
efficient than one with a 64-bit counter.

I guess that it's unlikely that the counter is 64 bit.

But most likely specialisation is a binary semaphore  (the <semaphore>
header already has "using binary_semaphore = counting_semaphore<1>;").

That's how the standard specifies binary_semaphore as an alias to
counting_semaphore<1>.

[Chris M. Thomasson]

Post by Chris M. Thomasson

Post by Bonita Montero

That seems likely.  It also allows for specialisation for different
sizes, though that did not appear to be used for by the library with
the  gcc on godbolt.  A small max value could perhaps be implemented
with fixed size queues instead of variable ones, ...

The queue is for for sure maintained by the kernel and is a linked list.

We used to refer to these as kernel waitsets back in the day. Still,
https://www.haiku-os.org/legacy-docs/benewsletter/Issue1-26.html#Engineering1-26

Implementing correct condvars on windows was an interesting thing back
in the day. It seemed that the bugged algos would be around 100:1 ratio.
Using an explicit waitset was one way, however, it limited one to
SCHED_OTHER.

[Ben Bacarisse]

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 14:10:05 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Sorry, I still don't get it. What do you mean by maximum counter?

You might want to consider who you are talking to.

Let's take std::counting_semaphore<M> sem(N); as an example. The N is
the important number but it is not a 'maximum' in any hard sense -- it
is simply the initial value of the counter. If it were some sort of
hard maximum, std::counting_semaphore sem(0); would be useless but it
isn't -- it simply means that at least one release() is needed before an
acquire() won't block. Of course, if often /does/ represent the
maximum number of threads that can access some resource because the
usual pattern is to use std::counting_semaphore sem(N) with the standard
pattern of every thread calling acquire() and then release().

The template parameter M is very different and rather unusual. It is,
first and foremost, just a hint to the implementation about how much
space will be needed for the counter, so the most useful value for M is
1 because some systems can implement binary semaphores more efficiently
than counting ones.

But this "limit" is not enforced other than by making the behaviour
undefined when it is exceeded. Pre-conditions on the operations state
that the counter must always be >= 0 and <= M, but you won't be able to
check this unless the implementation decides to enforce these
pre-conditions with some sort of error report.

[M***@dastardlyhq.com]

On Thu, 12 Sep 2024 11:25:07 +0100

Post by Ben Bacarisse

Post by M***@dastardlyhq.com
Sorry, I still don't get it. What do you mean by maximum counter?

You might want to consider who you are talking to.

I guess so.

Post by Ben Bacarisse
The template parameter M is very different and rather unusual. It is,

And very poorly explained in all the online documentation.

Post by Ben Bacarisse
But this "limit" is not enforced other than by making the behaviour
undefined when it is exceeded. Pre-conditions on the operations state

Clang seems to ignore it. You can call release() as much as you like and
it'll just keep increasing the counter.

[David Brown]

On Thu, 12 Sep 2024 07:34:23 -0700

Post by M***@dastardlyhq.com
Clang seems to ignore it. You can call release() as much as you like and
it'll just keep increasing the counter.

It "ignores" it exactly the same way as the following declaration
std::uint_fast8_t n = 2;
might "ignore" the 8 in the type name and allow you to increment the
variable well past 255. Come to think of it, the underlying reasons for

Incrementing integrals beyond their max value can have valid uses.

No, it cannot.

A method
allowing you to increment a counter beyond the apparent max counter value -
not so much.

Agreed. That's why you need to put an appropriate max counter value in
the template parameter of a std::semaphore. But the /initial/ value of
the semaphore counter should often be something other than its /max/
value, thus you need the two numbers.

It is perfectly explained in the spec. And it's been thoroughly

LOL! Ah, a comedian has joined us!

It certainly makes sense in the page at

<https://en.cppreference.com/w/cpp/thread/counting_semaphore>

and also in the C++ standard.

But those are references - they make it perfectly clear what the
template parameter does, and how it affects the preconditions for the
constructor and the release() method. However, they do not say /why/
you might want a particular value for the LeastMaxValue. That has been
explained in posts in this thread.


You started this thread from a position of ignorance - there was
something you did not know, and you asked about it. That is a great way
to start.

But for some reason you have moved onto /wilful/ ignorance - you are
determined to ignore the information you have been given, to argue with
an insult people trying to help you, and to deride the whole concept. I
really don't get it. Did you want to know about the template parameter
or not?

[M***@dastardlyhq.com]

On Fri, 13 Sep 2024 08:39:50 +0200

Post by David Brown

might "ignore" the 8 in the type name and allow you to increment the
variable well past 255. Come to think of it, the underlying reasons for

Incrementing integrals beyond their max value can have valid uses.

No, it cannot.

Clearly you've never done any low level networking where id fields are fixed
sized and will eventually wrap. Eg, TCP sequence number. I'm sure there are
a myriad of other examples.

Post by David Brown

It is perfectly explained in the spec. And it's been thoroughly

LOL! Ah, a comedian has joined us!

It certainly makes sense in the page at
<https://en.cppreference.com/w/cpp/thread/counting_semaphore>

If you think thats clear I'd hate to see what you consider obtuse.

Post by David Brown
But for some reason you have moved onto /wilful/ ignorance - you are
determined to ignore the information you have been given, to argue with
an insult people trying to help you, and to deride the whole concept. I
really don't get it. Did you want to know about the template parameter
or not?

Or alternatively some people just can't explain things very well. 2 people
managed it - you and the others didn't.

[David Brown]

Post by M***@dastardlyhq.com
On Fri, 13 Sep 2024 08:39:50 +0200

Post by David Brown

might "ignore" the 8 in the type name and allow you to increment the
variable well past 255. Come to think of it, the underlying reasons for

Incrementing integrals beyond their max value can have valid uses.

No, it cannot.

Clearly you've never done any low level networking where id fields are fixed
sized and will eventually wrap. Eg, TCP sequence number. I'm sure there are
a myriad of other examples.

Clearly you can make up a complete load of drivel with no basis in reality.

So let me be /clear/ here. There is /no/ valid use of incrementing
something beyond its maximum value. The whole concept makes no sense.

There /are/ lots of valid uses of wrapping types. Sequence numbers in
low-level networking would be one example of that - one which I /have/
used countless times in my work. But that is not incrementing beyond a
max value - it is using a modulo wrapping increment to give a result
/within/ the valid range, not beyond it.

Post by M***@dastardlyhq.com

Post by David Brown

It is perfectly explained in the spec. And it's been thoroughly

LOL! Ah, a comedian has joined us!

It certainly makes sense in the page at
<https://en.cppreference.com/w/cpp/thread/counting_semaphore>

If you think thats clear I'd hate to see what you consider obtuse.

Have you ever considered that /you/ might be the problem here? Other
people seem to understand it fine. Consider the common factor in all
your difficulties understanding the template parameter.

Post by M***@dastardlyhq.com

Post by David Brown
But for some reason you have moved onto /wilful/ ignorance - you are
determined to ignore the information you have been given, to argue with
an insult people trying to help you, and to deride the whole concept. I
really don't get it. Did you want to know about the template parameter
or not?

Or alternatively some people just can't explain things very well. 2 people
managed it - you and the others didn't.

I think the explanations given here have been solid - even Bonita gave
some reasonable answers.

But does all this mean that you now understand what the integer template
parameter is for, and what it does? And do you understand how to use
the counting semaphore? If so, that's great.

[M***@dastardlyhq.com]

On Fri, 13 Sep 2024 12:54:53 +0200

Post by David Brown

Post by M***@dastardlyhq.com
Clearly you've never done any low level networking where id fields are fixed
sized and will eventually wrap. Eg, TCP sequence number. I'm sure there are
a myriad of other examples.

Clearly you can make up a complete load of drivel with no basis in reality.

Oh dear, someones been caught out and is throwing his toys out the pram.

Post by David Brown
So let me be /clear/ here. There is /no/ valid use of incrementing
something beyond its maximum value. The whole concept makes no sense.

Bollocks.

Post by David Brown
There /are/ lots of valid uses of wrapping types. Sequence numbers in
low-level networking would be one example of that - one which I /have/
used countless times in my work. But that is not incrementing beyond a
max value - it is using a modulo wrapping increment to give a result
/within/ the valid range, not beyond it.

Oh right, so for 32 bit TCP seq number instead of just doing:

++tcp->seq_num;

which would autonatically wrap after 2^32, in your world we'd have do to:

tcp->seq_num = (uint32_t)(((uint_64_t)tcp->seq_num + 1) % 0x100000000L);

Really?

Don't be an ass.

Post by David Brown

Post by M***@dastardlyhq.com
If you think thats clear I'd hate to see what you consider obtuse.

Have you ever considered that /you/ might be the problem here? Other
people seem to understand it fine. Consider the common factor in all
your difficulties understanding the template parameter.

If it wasn't so vague I wouldn't have needed to ask the question.

Post by David Brown
But does all this mean that you now understand what the integer template
parameter is for, and what it does? And do you understand how to use
the counting semaphore? If so, that's great.

Aww bless, so kind.

[Bonita Montero]

Post by M***@dastardlyhq.com
++tcp->seq_num;
tcp->seq_num = (uint32_t)(((uint_64_t)tcp->seq_num + 1) % 0x100000000L);
Really?
Don't be an ass.

I've also not seen any meaningful code which shows what this
maximum is good for .... But what sense should a wrap-around
make with a semaphore ??? A semaphore should remember all its
releases if possible.

[M***@dastardlyhq.com]

On Fri, 13 Sep 2024 15:29:37 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
++tcp->seq_num;
tcp->seq_num = (uint32_t)(((uint_64_t)tcp->seq_num + 1) % 0x100000000L);
Really?
Don't be an ass.

I've also not seen any meaningful code which shows what this
maximum is good for .... But what sense should a wrap-around
make with a semaphore ??? A semaphore should remember all its
releases if possible.

Its not about semaphores any more, its about wrapping values in general.

[David Brown]

Post by Bonita Montero

Post by M***@dastardlyhq.com
++tcp->seq_num;
tcp->seq_num = (uint32_t)(((uint_64_t)tcp->seq_num + 1) % 0x100000000L);
Really?
Don't be an ass.

I've also not seen any meaningful code which shows what this
maximum is good for ....

This has already been explained in this thread - the maximum value is
there so that an implementation can have more efficient versions for
some maximum values - typically a maximum of 1 (a binary semaphore), and
possibly for small fixed values. For bigger values, I'd not expect to
see any different in the efficiency.

Post by Bonita Montero
But what sense should a wrap-around
make with a semaphore ??? A semaphore should remember all its
releases if possible.

Of course a semaphore has to remember all its releases - unless you try
to release beyond its maximum. And of course wrapping the count would
be completely useless.

[David Brown]

Post by M***@dastardlyhq.com
On Fri, 13 Sep 2024 12:54:53 +0200

Post by David Brown

Post by M***@dastardlyhq.com
Clearly you've never done any low level networking where id fields are fixed
sized and will eventually wrap. Eg, TCP sequence number. I'm sure there are
a myriad of other examples.

Clearly you can make up a complete load of drivel with no basis in reality.

Oh dear, someones been caught out and is throwing his toys out the pram.

Post by David Brown
So let me be /clear/ here. There is /no/ valid use of incrementing
something beyond its maximum value. The whole concept makes no sense.

Bollocks.

Post by David Brown
There /are/ lots of valid uses of wrapping types. Sequence numbers in
low-level networking would be one example of that - one which I /have/
used countless times in my work. But that is not incrementing beyond a
max value - it is using a modulo wrapping increment to give a result
/within/ the valid range, not beyond it.

++tcp->seq_num;
tcp->seq_num = (uint32_t)(((uint_64_t)tcp->seq_num + 1) % 0x100000000L);
Really?
Don't be an ass.

What /are/ you talking about? Do you even know how arithmetic works in
C++ ?

If you have "uint32_t seq_num = 0xffffffff;", then write "seq_num++;",
you are /not/ "incrementing beyond its maximum value". You are
incrementing modulo 2 ^ 32, because that's how the operation works in C++.

And if you have "int32_t seq_num;" and are using "++" to increment it
and think you have wrapping, then you are writing crap code.

Post by M***@dastardlyhq.com

Post by David Brown

Post by M***@dastardlyhq.com
If you think thats clear I'd hate to see what you consider obtuse.

Have you ever considered that /you/ might be the problem here? Other
people seem to understand it fine. Consider the common factor in all
your difficulties understanding the template parameter.

If it wasn't so vague I wouldn't have needed to ask the question.

It is not vague. Did you actually read the cppreference link, or the
C++ standards?

Post by M***@dastardlyhq.com

Post by David Brown
But does all this mean that you now understand what the integer template
parameter is for, and what it does? And do you understand how to use
the counting semaphore? If so, that's great.

Aww bless, so kind.

You really are a poor excuse for a human being.

[M***@dastardlyhq.com]

On Fri, 13 Sep 2024 16:46:31 +0200

Post by David Brown

Post by M***@dastardlyhq.com
++tcp->seq_num;
tcp->seq_num = (uint32_t)(((uint_64_t)tcp->seq_num + 1) % 0x100000000L);
Really?
Don't be an ass.

What /are/ you talking about? Do you even know how arithmetic works in
C++ ?

Oh do tell us.

Post by David Brown
If you have "uint32_t seq_num = 0xffffffff;", then write "seq_num++;",
you are /not/ "incrementing beyond its maximum value". You are
incrementing modulo 2 ^ 32, because that's how the operation works in C++.

Do you understand plain english? Given you're name I assume its not your
2nd language. Or is hair splitting your argument of last resort when you know
you're painted into a corner?

Post by David Brown
And if you have "int32_t seq_num;" and are using "++" to increment it
and think you have wrapping, then you are writing crap code.

If you say so genius.

Post by David Brown

Post by M***@dastardlyhq.com
Aww bless, so kind.

You really are a poor excuse for a human being.

And you're just another aspie fuckwit who can't handle losing an argument.
Pity semaphore doesn't have a swivel_on_it() method you could use.

[Andrey Tarasevich]

On Thu, 12 Sep 2024 07:34:23 -0700

Post by M***@dastardlyhq.com
Clang seems to ignore it. You can call release() as much as you like and
it'll just keep increasing the counter.

It "ignores" it exactly the same way as the following declaration
std::uint_fast8_t n = 2;
might "ignore" the 8 in the type name and allow you to increment the
variable well past 255. Come to think of it, the underlying reasons for

Incrementing integrals beyond their max value can have valid uses. A method
allowing you to increment a counter beyond the apparent max counter value -
not so much.

You are still not getting it. The point is that 255 is _not_ necessarily
the max value of `std::uint_fast8_t`, in which case incrementing past
255 is _not_ "incrementing beyond their max value". Template parameter
of `std::counting_semaphore` is like that as well.

[Andrey Tarasevich]

Post by M***@dastardlyhq.com
Clang seems to ignore it. You can call release() as much as you like and
it'll just keep increasing the counter.

It "ignores" it exactly the same way as the following declaration

std::uint_fast8_t n = 2;

might "ignore" the 8 in the type name and allow you to increment the
variable well past 255. Come to think of it, the underlying reasons for
why it can be so are very similar.

It is perfectly explained in the spec. And it's been thoroughly
explained here. What's the difficulty?

[M***@dastardlyhq.com]

On Thu, 12 Sep 2024 07:34:23 -0700

Post by M***@dastardlyhq.com
Clang seems to ignore it. You can call release() as much as you like and
it'll just keep increasing the counter.

It "ignores" it exactly the same way as the following declaration
std::uint_fast8_t n = 2;
might "ignore" the 8 in the type name and allow you to increment the
variable well past 255. Come to think of it, the underlying reasons for

Incrementing integrals beyond their max value can have valid uses. A method
allowing you to increment a counter beyond the apparent max counter value -
not so much.

It is perfectly explained in the spec. And it's been thoroughly

LOL! Ah, a comedian has joined us!

[Chris M. Thomasson]

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Post by M***@dastardlyhq.com
Condition variables IMO are unintuitive (eg the internal state change from
waiting on condition variable to waiting on mutex is completely invisible)
and hence very prone to logical bugs. I tend to avoid them where possible.

If you have a producer-consumer-pattern condition variables are the most
efficient way to handle this pattern.

Really?

[Bonita Montero]

Post by Chris M. Thomasson

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Post by M***@dastardlyhq.com
Condition variables IMO are unintuitive (eg the internal state change from
waiting on condition variable to waiting on mutex is completely invisible)
and hence very prone to logical bugs. I tend to avoid them where possible.

If you have a producer-consumer-pattern condition variables are the most
efficient way to handle this pattern.

Really?

Yes. If the consumer and producer are constantly processing you usually
have no kernel-calls.

[Chris M. Thomasson]

Post by Bonita Montero

Post by Chris M. Thomasson

Post by Bonita Montero

Post by M***@dastardlyhq.com
What upper limit? The max number of threads allowed in the protected section
above is 2, not 10. Or do you mean it'll only count up to 10 threads waiting
and ignore any beyond that? What happens if thread 11 comes along?

The static parmeter is the maximum counter and the the two is the
initial counter. So two threads can currently acquire that semaphore.

Post by M***@dastardlyhq.com
Condition variables IMO are unintuitive (eg the internal state change from
waiting on condition variable to waiting on mutex is completely invisible)
and hence very prone to logical bugs. I tend to avoid them where possible.

If you have a producer-consumer-pattern condition variables are the most
efficient way to handle this pattern.

Really?

Yes. If the consumer and producer are constantly processing you usually
have no kernel-calls.

Huh? What about the contention that can cause slow paths to me hit that
might get into a kernel wait on a sync object?

Put a convar-mutex based FIFO under heavy load vs a lock/wait-free one?
What one is more efficient? Yes there are atomic FIFO's that have wait
free fast paths.

[Bonita Montero]

Post by Chris M. Thomasson
Huh? What about the contention that can cause slow paths to me hit that
might get into a kernel wait on a sync object?

If the queue never runs empty there's never a wait. And usually
there's no overlap since enqueuing and dequeuing are very short.

[Chris M. Thomasson]

Post by Bonita Montero

Post by Chris M. Thomasson
Huh? What about the contention that can cause slow paths to me hit
that might get into a kernel wait on a sync object?

If the queue never runs empty there's never a wait. And usually
there's no overlap since enqueuing and dequeuing are very short.

I am talking about a condvar/mutex based queue vs a lock-free, or even
"mostly" wait-free queue under heavy contention... Which one is going to
be more efficient?

[Bonita Montero]

Post by Chris M. Thomasson
I am talking about a condvar/mutex based queue vs a lock-free, or even
"mostly" wait-free queue under heavy contention... Which one is going to
be more efficient?

Lock-free queues are inefficient because they've to be polled.

[Chris M. Thomasson]

Post by Bonita Montero

Post by Chris M. Thomasson
I am talking about a condvar/mutex based queue vs a lock-free, or even
"mostly" wait-free queue under heavy contention... Which one is going
to be more efficient?

Lock-free queues are inefficient because they've to be polled.

Hummm. Several things come to mind. An eventcount?

[Chris M. Thomasson]

Post by Chris M. Thomasson

Post by Bonita Montero

Post by Chris M. Thomasson
I am talking about a condvar/mutex based queue vs a lock-free, or
even "mostly" wait-free queue under heavy contention... Which one is
going to be more efficient?

Lock-free queues are inefficient because they've to be polled.

Hummm. Several things come to mind. An eventcount?

An eventcount is akin to a condvar for lock/wait free algorithms.

Actually, another solution that works okay is a heavily fast-pathed
semaphore.

[M***@dastardlyhq.com]

On Sat, 14 Sep 2024 01:43:26 +0200

Post by Bonita Montero

Post by Chris M. Thomasson
I am talking about a condvar/mutex based queue vs a lock-free, or even
"mostly" wait-free queue under heavy contention... Which one is going to
be more efficient?

Lock-free queues are inefficient because they've to be polled.

Everything has to be polled at some level except hardware interrupt based
code.

[Bonita Montero]

Post by M***@dastardlyhq.com
On Sat, 14 Sep 2024 01:43:26 +0200

Post by Bonita Montero

Post by Chris M. Thomasson
I am talking about a condvar/mutex based queue vs a lock-free, or
even "mostly" wait-free queue under heavy contention... Which one is
going to be more efficient?

Lock-free queues are inefficient because they've to be polled.

Everything has to be polled at some level except hardware interrupt based
code.

If the queue is empty CPU-time is usually handed voluntary to
another thread - not with a lock-free-queue.

[M***@dastardlyhq.com]

On Sat, 14 Sep 2024 11:40:22 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
On Sat, 14 Sep 2024 01:43:26 +0200

Post by Bonita Montero

Post by Chris M. Thomasson
I am talking about a condvar/mutex based queue vs a lock-free, or
even "mostly" wait-free queue under heavy contention... Which one is
going to be more efficient?

Lock-free queues are inefficient because they've to be polled.

Everything has to be polled at some level except hardware interrupt based
code.

If the queue is empty CPU-time is usually handed voluntary to
another thread - not with a lock-free-queue.

I think you missed the point - locks are just a kernel construct. Their state
still has to be polled by the kernel. Unless the locking mechanism is
implemented in hardware then software has to manage it whether in user space
or kernel space.

[Bonita Montero]

Post by M***@dastardlyhq.com

Post by Bonita Montero

Post by M***@dastardlyhq.com
Everything has to be polled at some level except hardware interrupt based
code.

If the queue is empty CPU-time is usually handed voluntary to
another thread - not with a lock-free-queue.

I think you missed the point - locks are just a kernel construct. Their
state still has to be polled by the kernel.

No, their state is maintained in userspace and the kernel is only there
for the slow path when there's contention.

Post by M***@dastardlyhq.com
Unless the locking mechanism is implemented in hardware then software
has to manage it whether in user space or kernel space.

The fast-path is implemented in hardware through the support of atomics.

But that wasn't the point in the discussion because this doesn't relate
to lock free queue's drawback that there's no slow path and the queue
has to be polled.

[M***@dastardlyhq.com]

On Sat, 14 Sep 2024 13:15:01 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
Unless the locking mechanism is implemented in hardware then software
has to manage it whether in user space or kernel space.

The fast-path is implemented in hardware through the support of atomics.

An assembler opcode , even a single one like x86 CMPXCHG, is still software.
There is no hardware mechanism in desktop PCs that can inspect a lock (or an
atomic) and raise an interrupt.

[Bonita Montero]

Post by M***@dastardlyhq.com
An assembler opcode , even a single one like x86 CMPXCHG, is still software.

The implementatoin of this opcode is hardware.

Post by M***@dastardlyhq.com
There is no hardware mechanism in desktop PCs that can inspect a lock
(or an atomic) and raise an interrupt.

The fast-path, i.e. when there's no contender, proceeds completely in
userspace.

[M***@dastardlyhq.com]

On Sat, 14 Sep 2024 17:26:47 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
An assembler opcode , even a single one like x86 CMPXCHG, is still software.

The implementatoin of this opcode is hardware.

Its probably implemented in microcode just like all the others but even if
it wasn't, so what? Its still software.

[Bonita Montero]

Post by M***@dastardlyhq.com
Its probably implemented in microcode just like all the others but even if
it wasn't, so what? Its still software.

It needs an atomic read-modify-write cycle, that's not possible with
microcode but a cache-subsystem that supports this.

[M***@dastardlyhq.com]

On Sat, 14 Sep 2024 17:50:29 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
Its probably implemented in microcode just like all the others but even if
it wasn't, so what? Its still software.

It needs an atomic read-modify-write cycle, that's not possible with
microcode but a cache-subsystem that supports this.

Microcode has full control of the hardware. If it needs to immediately lock all
cache memory it can.

[Bonita Montero]

Post by M***@dastardlyhq.com
Microcode has full control of the hardware. If it needs to immediately
lock all cache memory it can.

If the cache doesn't support atomic read-modify-write cycles a different
microcode doesn't help. The caching-logic itself is not controlle by
microcode.

[M***@dastardlyhq.com]

On Sat, 14 Sep 2024 17:57:35 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
Microcode has full control of the hardware. If it needs to immediately
lock all cache memory it can.

If the cache doesn't support atomic read-modify-write cycles a different
microcode doesn't help. The caching-logic itself is not controlle by
microcode.

If the cache doesn't support it then nothing will help including hard
wired TTL logic in the CPU or whatever automagical solution you think works.
Microcode exists to operate the hardware at the lowest level, thats its
entire purpose.

[Bonita Montero]

Post by M***@dastardlyhq.com
If the cache doesn't support it then nothing will help including hard
wired TTL logic in the CPU or whatever automagical solution you think
works. Microcode exists to operate the hardware at the lowest level,
thats its entire purpose.

The point was that how the cache works isn't controlled my microcode.
But your statement was that read-modify-write cycles are enabled by
microcode.

[M***@dastardlyhq.com]

On Sun, 15 Sep 2024 11:48:14 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
If the cache doesn't support it then nothing will help including hard
wired TTL logic in the CPU or whatever automagical solution you think
works. Microcode exists to operate the hardware at the lowest level,
thats its entire purpose.

The point was that how the cache works isn't controlled my microcode.
But your statement was that read-modify-write cycles are enabled by
microcode.

All CPUs are different, I don't even know which one you're talking about any
more. A manufacturer will build microcode to control whatever it needs to.
If the cache needs to be locked by microcode then they'll build that in to its
functionality.

[Bonita Montero]

All CPUs are different, ...

A microcode-contolled cache would be too slow. Such instructions
are hardwired for sure.

[M***@dastardlyhq.com]

On Sun, 15 Sep 2024 14:50:05 +0200

Post by Bonita Montero

All CPUs are different, ...

A microcode-contolled cache would be too slow. Such instructions
are hardwired for sure.

Too slow? Given an i5 can execute ~350 GIPS of microcoded opcodes how
exactly did you work that out? Also given anything done to the cache needs
to wait for the next opcode to exec anyway unless its DMA then there's no
reason for it to execute any faster than a standard opcode.

[Bonita Montero]

Too slow? ...

Yes, an L1-hit is only 3-4 clock cycles.

[Scott Lurndal]

Post by Bonita Montero

All CPUs are different, ...

A microcode-contolled cache would be too slow. Such instructions
are hardwired for sure.

Have you ever designed CPU hardware? You don't seem to understand
how microcode works..

[Scott Lurndal]

Post by Bonita Montero

Post by M***@dastardlyhq.com
If the cache doesn't support it then nothing will help including hard
wired TTL logic in the CPU or whatever automagical solution you think
works. Microcode exists to operate the hardware at the lowest level,
thats its entire purpose.

The point was that how the cache works isn't controlled my microcode.

That is, of course, not necissarily true. It is entirely likely
that a microcoded implementation has direct access to signals that
control cache behavior in a multitude of ways (pun intended).

Post by Bonita Montero
But your statement was that read-modify-write cycles are enabled by
microcode.

Indeed, all the microcode need do is assert a 'bus lock' signal to
serialize chip-wide events, including a RMW cycle.

[Chris M. Thomasson]

Post by Bonita Montero

Post by M***@dastardlyhq.com

Post by Bonita Montero

Post by M***@dastardlyhq.com
Everything has to be polled at some level except hardware interrupt based
code.

If the queue is empty CPU-time is usually handed voluntary to
another thread - not with a lock-free-queue.

I think you missed the point - locks are just a kernel construct.
Their state still has to be polled by the kernel.

No, their state is maintained in userspace and the kernel is only there
for the slow path when there's contention.

Post by M***@dastardlyhq.com
Unless the locking mechanism is implemented in hardware then software
has to manage it whether in user  space or kernel space.

The fast-path is implemented in hardware through the support of atomics.
But that wasn't the point in the discussion because this doesn't relate
to lock free queue's drawback that there's no slow path and the queue
has to be polled.

You have to think outside the box for a moment... :^) There are
interesting ways to turn lock/wait/obstruction-free algorithms into ones
that can wait on conditions. This gives them lock/wait free fast paths.
The slow paths (waiting in kernel, signalling/broadcasting) are only hit
on certain conditions.

So if the queue is empty, a thread can choose to wait if it wants to.

[Chris M. Thomasson]

Post by Chris M. Thomasson

Post by Bonita Montero

Post by M***@dastardlyhq.com

Post by Bonita Montero

Post by M***@dastardlyhq.com
Everything has to be polled at some level except hardware interrupt based
code.

If the queue is empty CPU-time is usually handed voluntary to
another thread - not with a lock-free-queue.

I think you missed the point - locks are just a kernel construct.
Their state still has to be polled by the kernel.

No, their state is maintained in userspace and the kernel is only there
for the slow path when there's contention.

Post by M***@dastardlyhq.com
Unless the locking mechanism is implemented in hardware then software
has to manage it whether in user  space or kernel space.

The fast-path is implemented in hardware through the support of atomics.
But that wasn't the point in the discussion because this doesn't relate
to lock free queue's drawback that there's no slow path and the queue
has to be polled.

You have to think outside the box for a moment... :^) There are
interesting ways to turn lock/wait/obstruction-free algorithms into ones
that can wait on conditions. This gives them lock/wait free fast paths.
The slow paths (waiting in kernel, signalling/broadcasting) are only hit
on certain conditions.
So if the queue is empty, a thread can choose to wait if it wants to.

Actually, an eventcount is so generic that it might be interesting to
see it as a standard entity in C/C++... :^)

[Bonita Montero]

Post by Chris M. Thomasson
You have to think outside the box for a moment... :^) There are
interesting ways to turn lock/wait/obstruction-free algorithms into ones
that can wait on conditions. This gives them lock/wait free fast paths.
The slow paths (waiting in kernel, signalling/broadcasting) are only hit
on certain conditions.

If there's a slow path with a lock-free algorithm it's not lock-free
any more.

[Chris M. Thomasson]

Post by Bonita Montero

Post by Chris M. Thomasson
You have to think outside the box for a moment... :^) There are
interesting ways to turn lock/wait/obstruction-free algorithms into
ones that can wait on conditions. This gives them lock/wait free fast
paths. The slow paths (waiting in kernel, signalling/broadcasting) are
only hit on certain conditions.

If there's a slow path with a lock-free algorithm it's not lock-free
any more.

So? The point is that the fast-paths will be lock-free and the slow
paths can allow a thread to wait if it wants to on certain conditions.
So, its pretty nice.

[Bonita Montero]

Post by Chris M. Thomasson
So? The point is that the fast-paths will be lock-free and the slow
paths can allow a thread to wait if it wants to on certain conditions.
So, its pretty nice.

Then that's sham to call it lock-free if there is a slow path.

[Chris M. Thomasson]

Post by Bonita Montero

Post by Chris M. Thomasson
So? The point is that the fast-paths will be lock-free and the slow
paths can allow a thread to wait if it wants to on certain conditions.
So, its pretty nice.

Then that's sham to call it lock-free if there is a slow path.

Humm... It seems like you missed my point. Think of an eventcount. It
turns the lock-free algorithm into a "thing" that has lock-free fast
paths. A thread can choose to wait if it wants to. Wait on certain
conditions if it wants to, ect...

Be sure to keep in mind that a thread can always use a try_pop() (poll,
whatever)... Or, it can choose to wait on an eventcount. Say if 5
try_pop()'s fail in a row, it chooses to wait... This is akin to the
logic of so-called adaptive mutexes... They will spin in user-space a
"couple" of times to avoid a wait in the kernel... This is a way to
avoid a "really" slow path (wait in kernel), so to speak.

Besides waits, there is another "class" of slow paths. Keep in mind that
a slow path can be signalling or broadcasting, waiting aside for a moment...

;^)

[Bonita Montero]

Post by Bonita Montero

Post by Chris M. Thomasson
So? The point is that the fast-paths will be lock-free and the slow
paths can allow a thread to wait if it wants to on certain
conditions. So, its pretty nice.

Then that's sham to call it lock-free if there is a slow path.

Humm... It seems like you missed my point. ..

A lock-free algorithm hasn't a slow path.

[Chris M. Thomasson]

Post by Bonita Montero

Post by Bonita Montero

Post by Chris M. Thomasson
So? The point is that the fast-paths will be lock-free and the slow
paths can allow a thread to wait if it wants to on certain
conditions. So, its pretty nice.

Then that's sham to call it lock-free if there is a slow path.

Humm... It seems like you missed my point. ..

A lock-free algorithm hasn't a slow path.

You need to think of "combining" an existing lock-free algorithm with
the ability to be able to actually wait, say on queue empty
conditions... Does it make it not always lock-free anymore? Yes. Does it
make it sometimes lock-free wrt striving to hit fast-paths, yup... Does
it give a thread the ability to choose to wait or try a couple of times
and possibly do something else? Yup. Actually, I wrote about that last
pattern a while back wrt using try_lock on a mutex. The gist was, why
wait when we can try to do something else...? It's an interesting
pattern that not that hard to learn for sure.

[Chris M. Thomasson]

Post by Bonita Montero

Post by M***@dastardlyhq.com
On Sat, 14 Sep 2024 01:43:26 +0200

Post by Bonita Montero

Post by Chris M. Thomasson
I am talking about a condvar/mutex based queue vs a lock-free, or
even "mostly" wait-free queue under heavy contention... Which one is
going to be more efficient?

Lock-free queues are inefficient because they've to be polled.

Everything has to be polled at some level except hardware interrupt based
code.

If the queue is empty CPU-time is usually handed voluntary to
another thread - not with a lock-free-queue.

Did you ever think of using the lock-free queue along with something
that can allow it to wait on certain conditions? Several solutions are
out there...

[Andrey Tarasevich]

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)

No, there's nothing "max" about that 2 here. 2 means that the semaphore
will be created with 2 available "permissions to enter" (permissions to
`acquire()`) initially. The number of available "permissions" can be
increased by calling `release()` after creating the semaphore. Call
`release()` 3 more times on our semaphore right away, and the initial 2
will increase to 5. So, 2 is not "max".

The "max" is set by the template parameter `LeastMaxValue`.

Post by M***@dastardlyhq.com
I don't understand what the '10' will do. Its returned by the max()
method but whats its purpose since if its the maximum possible threads
you could have in the protected block it makes no sense because you can't
change that value after creation as far as I can see.

The purpose of the template `LeastMaxValue` parameter is to let the
implementation choose the best representation for the internal counter.
Platforms will probably strive to use its native atomic types to
represent the counter. But if you supply `LeastMaxValue` that's too
large to fit into any atomic type, the implementation will be forced to
switch to another approach to ensure the semaphore works properly.

[M***@dastardlyhq.com]

On Wed, 11 Sep 2024 07:37:13 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)

No, there's nothing "max" about that 2 here. 2 means that the semaphore
will be created with 2 available "permissions to enter" (permissions to
`acquire()`) initially. The number of available "permissions" can be
increased by calling `release()` after creating the semaphore. Call
`release()` 3 more times on our semaphore right away, and the initial 2
will increase to 5. So, 2 is not "max".
The "max" is set by the template parameter `LeastMaxValue`.

It seems I'm not the only one getting confused here. If I write:

std::counting_semaphore<10> sem(2)

then the semaphore can only be aquired TWO times, not 10. I don't understand
what the 10 is supposed to do as changing the 10 to 0,1 or 1000 makes no
difference whatsoever to how many times acquire() can be called before
release() is called in the tests I've done.

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
I don't understand what the '10' will do. Its returned by the max()
method but whats its purpose since if its the maximum possible threads
you could have in the protected block it makes no sense because you can't
change that value after creation as far as I can see.

The purpose of the template `LeastMaxValue` parameter is to let the
implementation choose the best representation for the internal counter.

Huh?

[Bonita Montero]

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 07:37:13 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)

No, there's nothing "max" about that 2 here. 2 means that the semaphore
will be created with 2 available "permissions to enter" (permissions to
`acquire()`) initially. The number of available "permissions" can be
increased by calling `release()` after creating the semaphore. Call
`release()` 3 more times on our semaphore right away, and the initial 2
will increase to 5. So, 2 is not "max".
The "max" is set by the template parameter `LeastMaxValue`.

std::counting_semaphore<10> sem(2)
then the semaphore can only be aquired TWO times, not 10. I don't understand
what the 10 is supposed to do as changing the 10 to 0,1 or 1000 makes no
difference whatsoever to how many times acquire() can be called before
release() is called in the tests I've done.

10 is the maximum count the semaphore is allowed to reach, therefore
binary_semaphore, which is an alias-template to counting_semaphore<1>,
has a maximum count of one.

[M***@dastardlyhq.com]

On Wed, 11 Sep 2024 17:27:17 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 07:37:13 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)

No, there's nothing "max" about that 2 here. 2 means that the semaphore
will be created with 2 available "permissions to enter" (permissions to
`acquire()`) initially. The number of available "permissions" can be
increased by calling `release()` after creating the semaphore. Call
`release()` 3 more times on our semaphore right away, and the initial 2
will increase to 5. So, 2 is not "max".
The "max" is set by the template parameter `LeastMaxValue`.

std::counting_semaphore<10> sem(2)
then the semaphore can only be aquired TWO times, not 10. I don't understand
what the 10 is supposed to do as changing the 10 to 0,1 or 1000 makes no
difference whatsoever to how many times acquire() can be called before
release() is called in the tests I've done.

10 is the maximum count the semaphore is allowed to reach, therefore
binary_semaphore, which is an alias-template to counting_semaphore<1>,
has a maximum count of one.

We're going around in circles. Instead of reading the man page how about
trying some code. How many times to you think this loop will run before it
hangs? 100 or 2?

#include <stdio.h>
#include <semaphore>

std::counting_semaphore<100> sem(2);

int main()
{
for(int i=0;;++i)
{
sem.acquire();
printf("Acquired %d\n",i);
}
return 0;
}

Answer: 2

[Bonita Montero]

Post by M***@dastardlyhq.com
We're going around in circles. Instead of reading the man page how about
trying some code. How many times to you think this loop will run before it
hangs? 100 or 2?
#include <stdio.h>
#include <semaphore>
std::counting_semaphore<100> sem(2);
int main()
{
for(int i=0;;++i)
{
sem.acquire();
printf("Acquired %d\n",i);
}
return 0;
}
Answer: 2

There's nothing wrong with what I said. Once the semaphore is created
its maximum count isn't relevant any more. The return statement isn't
necessary since after two turns the loop is blocked by acquire(). Don't
care for semaphores, you'd need them only in special cases. For locking
shared resources a mutex is sufficient and for produver-consumer-pat-
terns a mutex along with a condition variable is optimal.
Java has lived a long time without semaphores but just with monitors
(a more efficient glue of a mutex and a condvar) and the semaphore
that was introduced later is almost never used.

[M***@dastardlyhq.com]

On Wed, 11 Sep 2024 18:16:11 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
We're going around in circles. Instead of reading the man page how about
trying some code. How many times to you think this loop will run before it
hangs? 100 or 2?
#include <stdio.h>
#include <semaphore>
std::counting_semaphore<100> sem(2);
int main()
{
for(int i=0;;++i)
{
sem.acquire();
printf("Acquired %d\n",i);
}
return 0;
}
Answer: 2

There's nothing wrong with what I said. Once the semaphore is created
its maximum count isn't relevant any more. The return statement isn't

You're making zero sense. Maybe just admit you don't know what the template
parameter is for, which also seems to be the case for the people who wrote the
documentation for it.

[Bonita Montero]

Post by M***@dastardlyhq.com
You're making zero sense. Maybe just admit you don't know what the template
parameter is for, which also seems to be the case for the people who wrote the
documentation for it.

The template parameter is the maximum release count as I've already
said. Beyond that you'vw got undefined behaviour.

[Chris M. Thomasson]

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 17:27:17 +0200

Post by Bonita Montero

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 07:37:13 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)

No, there's nothing "max" about that 2 here. 2 means that the semaphore
will be created with 2 available "permissions to enter" (permissions to
`acquire()`) initially. The number of available "permissions" can be
increased by calling `release()` after creating the semaphore. Call
`release()` 3 more times on our semaphore right away, and the initial 2
will increase to 5. So, 2 is not "max".
The "max" is set by the template parameter `LeastMaxValue`.

std::counting_semaphore<10> sem(2)
then the semaphore can only be aquired TWO times, not 10. I don't understand
what the 10 is supposed to do as changing the 10 to 0,1 or 1000 makes no
difference whatsoever to how many times acquire() can be called before
release() is called in the tests I've done.

10 is the maximum count the semaphore is allowed to reach, therefore
binary_semaphore, which is an alias-template to counting_semaphore<1>,
has a maximum count of one.

We're going around in circles. Instead of reading the man page how about
trying some code. How many times to you think this loop will run before it
hangs? 100 or 2?
#include <stdio.h>
#include <semaphore>
std::counting_semaphore<100> sem(2);
int main()
{
for(int i=0;;++i)
{
sem.acquire();
printf("Acquired %d\n",i);
}
return 0;
}
Answer: 2

Afaict, you set the initial state of the semaphore to two. Therefore
acquire will block (actually deadlock here) after two calls as in your
test code...

https://en.cppreference.com/w/cpp/thread/counting_semaphore
______________
As its name indicates, the LeastMaxValue is the minimum max value, not
the actual max value. Thus max() can yield a number larger than
LeastMaxValue.
______________

[Andrey Tarasevich]

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 07:37:13 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
I've been looking at counting_semaphore and it looks useful but something
that doesn't seem to be properly explained anywhere is the template
std::counting_semaphore sem(2)

No, there's nothing "max" about that 2 here. 2 means that the semaphore
will be created with 2 available "permissions to enter" (permissions to
`acquire()`) initially. The number of available "permissions" can be
increased by calling `release()` after creating the semaphore. Call
`release()` 3 more times on our semaphore right away, and the initial 2
will increase to 5. So, 2 is not "max".
The "max" is set by the template parameter `LeastMaxValue`.

std::counting_semaphore<10> sem(2)
then the semaphore can only be aquired TWO times, not 10.

Are you trying to troll people or what?

If you write

std::counting_semaphore<10> sem(2);

then the semaphore can be acquired 2 times. But it can also be released
instead at least 8 times, after which it can be acquired 10 times.

See the math? 2 + 8 = 10?

The 10 is the "least" max value, meaning that the implementation has to
let you release your freshly created `sem` _at_ _least_ 8 times, but can
also permit you to release, say, a 1000 or more times.

[M***@dastardlyhq.com]

On Wed, 11 Sep 2024 20:56:12 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
then the semaphore can only be aquired TWO times, not 10.

Are you trying to troll people or what?

I get REALLY sick of people who think someone who's asking a question that
they know the answer to as trolling.

Post by Andrey Tarasevich
If you write
std::counting_semaphore<10> sem(2);
then the semaphore can be acquired 2 times. But it can also be released
instead at least 8 times, after which it can be acquired 10 times.

Thank you. You've explained in 2 lines what no one else managed.

Post by Andrey Tarasevich
See the math? 2 + 8 = 10?

No need to be patronising though thats par for the course on this group.

Post by Andrey Tarasevich
The 10 is the "least" max value, meaning that the implementation has to
let you release your freshly created `sem` _at_ _least_ 8 times, but can
also permit you to release, say, a 1000 or more times.

Sounds profoundly useless but at least now I know. Though I can't imagine
when I'd ever use it.

[David Brown]

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 20:56:12 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
then the semaphore can only be aquired TWO times, not 10.

Are you trying to troll people or what?

I get REALLY sick of people who think someone who's asking a question that
they know the answer to as trolling.

You already accused everyone else in the thread of not knowing what they
are talking about. Let's try to keep things light.

Post by M***@dastardlyhq.com

Post by Andrey Tarasevich
If you write
std::counting_semaphore<10> sem(2);
then the semaphore can be acquired 2 times. But it can also be released
instead at least 8 times, after which it can be acquired 10 times.

Thank you. You've explained in 2 lines what no one else managed.

Post by Andrey Tarasevich
See the math? 2 + 8 = 10?

No need to be patronising though thats par for the course on this group.

Post by Andrey Tarasevich
The 10 is the "least" max value, meaning that the implementation has to
let you release your freshly created `sem` _at_ _least_ 8 times, but can
also permit you to release, say, a 1000 or more times.

Sounds profoundly useless but at least now I know. Though I can't imagine
when I'd ever use it.

If you write :

std::counting_semaphore<10> sem(2);

Then you can take the semaphore twice before blocking. You can then
release it up to 10 times. But releasing it /more/ than ten times might
be UB. I say it /might/ be UB, because the semaphore has a value you
can read with sem.max() which gives the true maximum value, which might
be bigger than the 10 that you asked for.

It is not immediately obvious why this template parameter exists. The
answer is the internal implementation of the semaphore, which requires a
queue of blocked threads. A binary semaphore has a maximum of 1, and
may be implemented more efficiently than a counting semaphore with a
higher maximum. For a low maximum, the queue might be implemented as a
std::array<> of the appropriate size. For a higher maximum, perhaps the
implementation uses a std::vector<>. So you pick the template parameter
here to be at least as big as you will ever need for the semaphore, but
aim to be as small as you can.

[M***@dastardlyhq.com]

On Thu, 12 Sep 2024 13:30:56 +0200

Post by David Brown

Post by M***@dastardlyhq.com
On Wed, 11 Sep 2024 20:56:12 -0700

Post by Andrey Tarasevich

Post by M***@dastardlyhq.com
then the semaphore can only be aquired TWO times, not 10.

Are you trying to troll people or what?

I get REALLY sick of people who think someone who's asking a question that
they know the answer to as trolling.

You already accused everyone else in the thread of not knowing what they
are talking about. Let's try to keep things light.

Well lets just say some of them should never consider teaching as a career.

Post by David Brown
It is not immediately obvious why this template parameter exists. The
answer is the internal implementation of the semaphore, which requires a
queue of blocked threads. A binary semaphore has a maximum of 1, and
may be implemented more efficiently than a counting semaphore with a
higher maximum. For a low maximum, the queue might be implemented as a
std::array<> of the appropriate size. For a higher maximum, perhaps the
implementation uses a std::vector<>. So you pick the template parameter
here to be at least as big as you will ever need for the semaphore, but
aim to be as small as you can.

Makes sense.

[Bonita Montero]

Post by M***@dastardlyhq.com
Thank you. You've explained in 2 lines what no one else managed.
10 is the maximum count the semaphore is allowed to reach ...

But you didn't understand that.

Post by M***@dastardlyhq.com
Sounds profoundly useless but at least now I know. Though I can't imagine
when I'd ever use it.

I also don't know what this is good for.

[Andrey Tarasevich]

Post by M***@dastardlyhq.com
Sounds profoundly useless but at least now I know. Though I can't imagine
when I'd ever use it.

2 and 255 in this example

std::counting_semaphore<255> sem(2);

follow pretty much the same semantics and serve pretty much the same
purpose as 2 and 255 in the following example

std::uint_least8_t n = 2;

(Even though the latter does not mention 255 explicitly, I hope you'll
figure out where it hides.)

Whether you will ever "use" it or not is a different question.