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

Groups > comp.lang.c++ > #122560 > unrolled thread

Concurrent API's and Semantics

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

Contents

  Concurrent API's and Semantics jseigh <jseigh_es00@xemaps.com> - 2025-08-18 13:24 -0400
    Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 13:06 -0700
      Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 13:23 -0700
      Re: Concurrent API's and Semantics jseigh <jseigh_es00@xemaps.com> - 2025-08-18 18:04 -0400
        Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 15:54 -0700
          Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 15:59 -0700
          Re: Concurrent API's and Semantics jseigh <jseigh_es00@xemaps.com> - 2025-08-19 11:02 -0400
            Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-19 13:34 -0700
              Re: Concurrent API's and Semantics jseigh <jseigh_es00@xemaps.com> - 2025-08-20 09:22 -0400
                Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-20 11:51 -0700
                Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-20 12:13 -0700
            Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-19 13:42 -0700
              Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-19 14:14 -0700
                Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-19 14:19 -0700
              Re: Concurrent API's and Semantics Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-20 18:25 +0200
                Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-20 11:53 -0700
                  Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-20 12:00 -0700
                    Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-20 12:05 -0700
                  Re: Concurrent API's and Semantics Bonita Montero <Bonita.Montero@gmail.com> - 2025-09-10 17:39 +0200
                    Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-09-10 13:14 -0700
                      Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-09-10 14:20 -0700
    Re: Concurrent API's and Semantics Marcel Mueller <news.5.maazl@spamgourmet.org> - 2025-08-19 23:18 +0200
      Re: Concurrent API's and Semantics jseigh <jseigh_es00@xemaps.com> - 2025-08-20 09:35 -0400
        Re: Concurrent API's and Semantics Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-20 18:35 +0200
          Re: Concurrent API's and Semantics "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-09-08 00:29 -0700

Page 1 of 2  [1] 2  Next page →

#122560 — Concurrent API's and Semantics

There is a tendency to take api's of non-concurrent collections
(queues, stacks, maps, ...) and use them for the api's of
concurrent collections (extending them possibly).  This is what
happened in java with java.util being extended with
java.util.concurrent.  The assumption being that that single threaded
is the general case and concurrent multi-threaded is a specialization
of that.  This is problematic.  Sections of the api's become
meaningless. E.g. getting the size of a concurrent collection, or
worse, iterating over a concurrent collections.  This forces the
concurrent implementation to add suboptimal logic to make the
collection to behave like it's not concurrent, something it's not.

So, it's concurrency is the general case and single threaded is a
specialization of that.  You add restrictions to the former to get
more usable functionality for some applications.

For example, for a concurrent queue you really have just 2 methods:
enqueue and dequeue.  When  you extend that api for a single threaded
queue, you can then add all those other methods you think you might
need because you can make more assumptions about the behavior of the
collection.

If we compare the api of a concurrent queue with that of a concurrent
stack, they are basically the same, you add and remove data from the
concurrent collections.  Semantically they are different, but probably
not what you think.

Joe Seigh

[toc] | [next] | [standalone]

#122562

On 8/18/2025 10:24 AM, jseigh wrote:
> There is a tendency to take api's of non-concurrent collections
> (queues, stacks, maps, ...) and use them for the api's of
> concurrent collections (extending them possibly).  This is what
> happened in java with java.util being extended with
> java.util.concurrent.  The assumption being that that single threaded
> is the general case and concurrent multi-threaded is a specialization
> of that.  This is problematic.  Sections of the api's become
> meaningless. E.g. getting the size of a concurrent collection, or
> worse, iterating over a concurrent collections.  This forces the
> concurrent implementation to add suboptimal logic to make the
> collection to behave like it's not concurrent, something it's not.
> 
> So, it's concurrency is the general case and single threaded is a
> specialization of that.  You add restrictions to the former to get
> more usable functionality for some applications.
> 
> For example, for a concurrent queue you really have just 2 methods:
> enqueue and dequeue.  When  you extend that api for a single threaded
> queue, you can then add all those other methods you think you might
> need because you can make more assumptions about the behavior of the
> collection.

A nightmare condition, because a lot of those methods are not fun, or 
perhaps not even able to be to implemented in a lock-free manner.


> If we compare the api of a concurrent queue with that of a concurrent
> stack, they are basically the same, you add and remove data from the
> concurrent collections.  Semantically they are different, but probably
> not what you think.

Agreed. Fwiw, another fun one is the API of an eventcount for existing 
concurrent apis. Iirc, I did one many years ago and we discussed it way 
back in c.p.t. You said the membars are no so nice... Remember that old one?

The basic pattern:
____________________
// push
push();
ecount.signal();



// pop
node* w = pop_try();

if (! w)
{
     ecount.lock();

         while (! (w = pop_try()))
         {
             ecount.wait();
         }

     ecount.unlock();
}

return w;
____________________

Keeping the eventcount state separate from an existing lock-free stack 
is key. We don't want ecount.signal to always be a slow-path while 
making sure the existing lock-free stack is as is. No interference from 
the eventcount.

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

#122563

On 8/18/2025 1:06 PM, Chris M. Thomasson wrote:
> On 8/18/2025 10:24 AM, jseigh wrote:
[...]
> Keeping the eventcount state separate from an existing lock-free stack 
> is key. We don't want ecount.signal to always be a slow-path while 
> making sure the existing lock-free stack is as is. No interference from 
> the eventcount.

Found the old convo:

https://groups.google.com/g/comp.programming.threads/c/qoxirQbbs4A/m/bG9po3hsAXkJ

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

#122574

On 8/18/25 16:06, Chris M. Thomasson wrote:
> On 8/18/2025 10:24 AM, jseigh wrote:
>> There is a tendency to take api's of non-concurrent collections
>> (queues, stacks, maps, ...) and use them for the api's of
>> concurrent collections (extending them possibly).  This is what
>> happened in java with java.util being extended with
>> java.util.concurrent.  The assumption being that that single threaded
>> is the general case and concurrent multi-threaded is a specialization
>> of that.  This is problematic.  Sections of the api's become
>> meaningless. E.g. getting the size of a concurrent collection, or
>> worse, iterating over a concurrent collections.  This forces the
>> concurrent implementation to add suboptimal logic to make the
>> collection to behave like it's not concurrent, something it's not.
>>
>> So, it's concurrency is the general case and single threaded is a
>> specialization of that.  You add restrictions to the former to get
>> more usable functionality for some applications.
>>
>> For example, for a concurrent queue you really have just 2 methods:
>> enqueue and dequeue.  When  you extend that api for a single threaded
>> queue, you can then add all those other methods you think you might
>> need because you can make more assumptions about the behavior of the
>> collection.
> 
> A nightmare condition, because a lot of those methods are not fun, or 
> perhaps not even able to be to implemented in a lock-free manner.

For example in Java, the ConcurrentQueue interface might have methods
that make no sense to implement for a given concurrent queue algorithm
but you have to because the interface has it and to do that might entail
things that would slow your queue implementation down.
> 
> 
>> If we compare the api of a concurrent queue with that of a concurrent
>> stack, they are basically the same, you add and remove data from the
>> concurrent collections.  Semantically they are different, but probably
>> not what you think.
> 
> Agreed. Fwiw, another fun one is the API of an eventcount for existing 
> concurrent apis. Iirc, I did one many years ago and we discussed it way 
> back in c.p.t. You said the membars are no so nice... Remember that old 
> one?
> 
Hints on the concurrent stack vs. concurrent queue.  It's not one is LIFO
and the other FIFO.

Joe Seigh

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

#122575

On 8/18/2025 3:04 PM, jseigh wrote:
> On 8/18/25 16:06, Chris M. Thomasson wrote:
>> On 8/18/2025 10:24 AM, jseigh wrote:
>>> There is a tendency to take api's of non-concurrent collections
>>> (queues, stacks, maps, ...) and use them for the api's of
>>> concurrent collections (extending them possibly).  This is what
>>> happened in java with java.util being extended with
>>> java.util.concurrent.  The assumption being that that single threaded
>>> is the general case and concurrent multi-threaded is a specialization
>>> of that.  This is problematic.  Sections of the api's become
>>> meaningless. E.g. getting the size of a concurrent collection, or
>>> worse, iterating over a concurrent collections.  This forces the
>>> concurrent implementation to add suboptimal logic to make the
>>> collection to behave like it's not concurrent, something it's not.
>>>
>>> So, it's concurrency is the general case and single threaded is a
>>> specialization of that.  You add restrictions to the former to get
>>> more usable functionality for some applications.
>>>
>>> For example, for a concurrent queue you really have just 2 methods:
>>> enqueue and dequeue.  When  you extend that api for a single threaded
>>> queue, you can then add all those other methods you think you might
>>> need because you can make more assumptions about the behavior of the
>>> collection.
>>
>> A nightmare condition, because a lot of those methods are not fun, or 
>> perhaps not even able to be to implemented in a lock-free manner.
> 
> For example in Java, the ConcurrentQueue interface might have methods
> that make no sense to implement for a given concurrent queue algorithm
> but you have to because the interface has it and to do that might entail
> things that would slow your queue implementation down.
>>
>>
>>> If we compare the api of a concurrent queue with that of a concurrent
>>> stack, they are basically the same, you add and remove data from the
>>> concurrent collections.  Semantically they are different, but probably
>>> not what you think.
>>
>> Agreed. Fwiw, another fun one is the API of an eventcount for existing 
>> concurrent apis. Iirc, I did one many years ago and we discussed it 
>> way back in c.p.t. You said the membars are no so nice... Remember 
>> that old one?
>>
> Hints on the concurrent stack vs. concurrent queue.  It's not one is LIFO
> and the other FIFO.

Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
mpmc? A concurrent stack can be using single word exchange and cas, a 
queue might use DWCAS and a dummy node, ect... Are we talking about node 
based or array based? We can have queues that are all implemented in 
different ways, it depends on how they are meant to be used...

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

#122577

On 8/18/2025 3:54 PM, Chris M. Thomasson wrote:
> On 8/18/2025 3:04 PM, jseigh wrote:
>> On 8/18/25 16:06, Chris M. Thomasson wrote:
>>> On 8/18/2025 10:24 AM, jseigh wrote:
>>>> There is a tendency to take api's of non-concurrent collections
>>>> (queues, stacks, maps, ...) and use them for the api's of
>>>> concurrent collections (extending them possibly).  This is what
>>>> happened in java with java.util being extended with
>>>> java.util.concurrent.  The assumption being that that single threaded
>>>> is the general case and concurrent multi-threaded is a specialization
>>>> of that.  This is problematic.  Sections of the api's become
>>>> meaningless. E.g. getting the size of a concurrent collection, or
>>>> worse, iterating over a concurrent collections.  This forces the
>>>> concurrent implementation to add suboptimal logic to make the
>>>> collection to behave like it's not concurrent, something it's not.
>>>>
>>>> So, it's concurrency is the general case and single threaded is a
>>>> specialization of that.  You add restrictions to the former to get
>>>> more usable functionality for some applications.
>>>>
>>>> For example, for a concurrent queue you really have just 2 methods:
>>>> enqueue and dequeue.  When  you extend that api for a single threaded
>>>> queue, you can then add all those other methods you think you might
>>>> need because you can make more assumptions about the behavior of the
>>>> collection.
>>>
>>> A nightmare condition, because a lot of those methods are not fun, or 
>>> perhaps not even able to be to implemented in a lock-free manner.
>>
>> For example in Java, the ConcurrentQueue interface might have methods
>> that make no sense to implement for a given concurrent queue algorithm
>> but you have to because the interface has it and to do that might entail
>> things that would slow your queue implementation down.
>>>
>>>
>>>> If we compare the api of a concurrent queue with that of a concurrent
>>>> stack, they are basically the same, you add and remove data from the
>>>> concurrent collections.  Semantically they are different, but probably
>>>> not what you think.
>>>
>>> Agreed. Fwiw, another fun one is the API of an eventcount for 
>>> existing concurrent apis. Iirc, I did one many years ago and we 
>>> discussed it way back in c.p.t. You said the membars are no so 
>>> nice... Remember that old one?
>>>
>> Hints on the concurrent stack vs. concurrent queue.  It's not one is LIFO
>> and the other FIFO.
> 
> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
> mpmc? A concurrent stack can be using single word exchange and cas, a 
> queue might use DWCAS and a dummy node, ect... Are we talking about node 
> based or array based? We can have queues that are all implemented in 
> different ways, it depends on how they are meant to be used...
> 

Fwiw, here is an older one (MPMC bounded queue) I made that is a tweak 
from Dmitriy's original. NO CAS, just XADD:

https://groups.google.com/g/lock-free/c/acjQ3-89abE

Interesting convo there.

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

#122587

On 8/18/25 18:54, Chris M. Thomasson wrote:
> On 8/18/2025 3:04 PM, jseigh wrote:

>>>
>> Hints on the concurrent stack vs. concurrent queue.  It's not one is LIFO
>> and the other FIFO.
> 
> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
> mpmc? A concurrent stack can be using single word exchange and cas, a 
> queue might use DWCAS and a dummy node, ect... Are we talking about node 
> based or array based? We can have queues that are all implemented in 
> different ways, it depends on how they are meant to be used...
> 

Whatever would be equivalent to Java's ConcurrentQueue interface.
Semantics for that and not specific to any implementation thereof.

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

#122590

On 8/19/2025 8:02 AM, jseigh wrote:
> On 8/18/25 18:54, Chris M. Thomasson wrote:
>> On 8/18/2025 3:04 PM, jseigh wrote:
> 
>>>>
>>> Hints on the concurrent stack vs. concurrent queue.  It's not one is 
>>> LIFO
>>> and the other FIFO.
>>
>> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
>> mpmc? A concurrent stack can be using single word exchange and cas, a 
>> queue might use DWCAS and a dummy node, ect... Are we talking about 
>> node based or array based? We can have queues that are all implemented 
>> in different ways, it depends on how they are meant to be used...
>>
> 
> Whatever would be equivalent to Java's ConcurrentQueue interface.
> Semantics for that and not specific to any implementation thereof.

Please excuse my ignorance, not a Java guy (I don't like it), but 
implementing the following interfaces?

IProducerConsumerCollection
IEnumerable
IReadOnlyCollection
ICollection

GetEnumerator is an interesting one, needs a garbage collector, proxy 
collection, RCU.

TryPeek?

Well... Yeah, being forced to implement all of that would make a slow queue?

It's as if the API basically forces one to make sub optimal queues?

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

#122596

On 8/19/25 16:34, Chris M. Thomasson wrote:
> On 8/19/2025 8:02 AM, jseigh wrote:
>> On 8/18/25 18:54, Chris M. Thomasson wrote:
>>> On 8/18/2025 3:04 PM, jseigh wrote:
>>
>>>>>
>>>> Hints on the concurrent stack vs. concurrent queue.  It's not one is 
>>>> LIFO
>>>> and the other FIFO.
>>>
>>> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
>>> mpmc? A concurrent stack can be using single word exchange and cas, a 
>>> queue might use DWCAS and a dummy node, ect... Are we talking about 
>>> node based or array based? We can have queues that are all 
>>> implemented in different ways, it depends on how they are meant to be 
>>> used...
>>>
>>
>> Whatever would be equivalent to Java's ConcurrentQueue interface.
>> Semantics for that and not specific to any implementation thereof.
> 
> Please excuse my ignorance, not a Java guy (I don't like it), but 
> implementing the following interfaces?
> 
> IProducerConsumerCollection
> IEnumerable
> IReadOnlyCollection
> ICollection
> 
> GetEnumerator is an interesting one, needs a garbage collector, proxy 
> collection, RCU.
> 
> TryPeek?
> 
> Well... Yeah, being forced to implement all of that would make a slow 
> queue?
> 
> It's as if the API basically forces one to make sub optimal queues?

Basically, yes.

BTW, the answer to the difference between concurrent queue and
concurrent stack is forward progress guarantees.

If you put something on a queue, the likelihood of it being
dequeued increases w/ each dequeue operation on that queue.
No such guarantee with stacks.

If you make assumptions like the dequeue try rate is always
greater than than the enqueue rate then you could sort of
use a stack as a concurrent channel.

The thing with LIFO vs FIFO is with a parallel or sharded
queue you may not be able to see FIFO behavior even in
a single threaded environment depending on the implementation.

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

#122601

On 8/20/2025 6:22 AM, jseigh wrote:
> On 8/19/25 16:34, Chris M. Thomasson wrote:
>> On 8/19/2025 8:02 AM, jseigh wrote:
>>> On 8/18/25 18:54, Chris M. Thomasson wrote:
>>>> On 8/18/2025 3:04 PM, jseigh wrote:
>>>
>>>>>>
>>>>> Hints on the concurrent stack vs. concurrent queue.  It's not one 
>>>>> is LIFO
>>>>> and the other FIFO.
>>>>
>>>> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
>>>> mpmc? A concurrent stack can be using single word exchange and cas, 
>>>> a queue might use DWCAS and a dummy node, ect... Are we talking 
>>>> about node based or array based? We can have queues that are all 
>>>> implemented in different ways, it depends on how they are meant to 
>>>> be used...
>>>>
>>>
>>> Whatever would be equivalent to Java's ConcurrentQueue interface.
>>> Semantics for that and not specific to any implementation thereof.
>>
>> Please excuse my ignorance, not a Java guy (I don't like it), but 
>> implementing the following interfaces?
>>
>> IProducerConsumerCollection
>> IEnumerable
>> IReadOnlyCollection
>> ICollection
>>
>> GetEnumerator is an interesting one, needs a garbage collector, proxy 
>> collection, RCU.
>>
>> TryPeek?
>>
>> Well... Yeah, being forced to implement all of that would make a slow 
>> queue?
>>
>> It's as if the API basically forces one to make sub optimal queues?
> 
> Basically, yes.
> 
> BTW, the answer to the difference between concurrent queue and
> concurrent stack is forward progress guarantees.
> 
> If you put something on a queue, the likelihood of it being
> dequeued increases w/ each dequeue operation on that queue.
> No such guarantee with stacks.

Even if we flush the stack, say every "now and then", with XCHG? Then a 
thread might get too much work...? A while back I wrote an experimental 
"distributed" one that hashed node pointers into an array of lock-free 
stacks. A single eventcount could be used to provide waiting using 
flush_try on them as predicate.


> If you make assumptions like the dequeue try rate is always
> greater than than the enqueue rate then you could sort of
> use a stack as a concurrent channel.

push pointers to lock-free queues onto a lock-free stack?


> The thing with LIFO vs FIFO is with a parallel or sharded
> queue you may not be able to see FIFO behavior even in
> a single threaded environment depending on the implementation.

spsc or mpsc queues tend to get FIFO "righter", lol ;^) ? Well, impl 
aside for a moment... I barely remember doing a hierarchical setup. Each 
thread would have spsc and mpsc queues. The global state was an array of 
mpmc queues. I can't remember if the mpmc's were per chip, or per core 
on the chip. A thread would try all of the levels to get some work.

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

#122605

On 8/20/2025 6:22 AM, jseigh wrote:
> On 8/19/25 16:34, Chris M. Thomasson wrote:
>> On 8/19/2025 8:02 AM, jseigh wrote:
>>> On 8/18/25 18:54, Chris M. Thomasson wrote:
>>>> On 8/18/2025 3:04 PM, jseigh wrote:
>>>
>>>>>>
>>>>> Hints on the concurrent stack vs. concurrent queue.  It's not one 
>>>>> is LIFO
>>>>> and the other FIFO.
>>>>
>>>> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
>>>> mpmc? A concurrent stack can be using single word exchange and cas, 
>>>> a queue might use DWCAS and a dummy node, ect... Are we talking 
>>>> about node based or array based? We can have queues that are all 
>>>> implemented in different ways, it depends on how they are meant to 
>>>> be used...
>>>>
>>>
>>> Whatever would be equivalent to Java's ConcurrentQueue interface.
>>> Semantics for that and not specific to any implementation thereof.
>>
>> Please excuse my ignorance, not a Java guy (I don't like it), but 
>> implementing the following interfaces?
>>
>> IProducerConsumerCollection
>> IEnumerable
>> IReadOnlyCollection
>> ICollection
>>
>> GetEnumerator is an interesting one, needs a garbage collector, proxy 
>> collection, RCU.
>>
>> TryPeek?
>>
>> Well... Yeah, being forced to implement all of that would make a slow 
>> queue?
>>
>> It's as if the API basically forces one to make sub optimal queues?
> 
> Basically, yes.

It would be funny (to me) to look at that Java API and think of a 
transformer that had everything; even different sized kitchen sinks on 
it... This API is the master and we make you lose your hair and raise 
your blood pressure to try to create a highly efficient queue and/or 
stack with it! Hahahhha! ;^)

I think start with the bare minimum, perhaps:

push_try
pop_try
*flush_try // Humm, not sure.

I am not quite sure about flush_try for this low level of the API. The 
fun part about the *_try is that its already compatible with the 
predicates of an eventcount...


> 
> BTW, the answer to the difference between concurrent queue and
> concurrent stack is forward progress guarantees.
> 
> If you put something on a queue, the likelihood of it being
> dequeued increases w/ each dequeue operation on that queue.
> No such guarantee with stacks.
> 
> If you make assumptions like the dequeue try rate is always
> greater than than the enqueue rate then you could sort of
> use a stack as a concurrent channel.
> 
> The thing with LIFO vs FIFO is with a parallel or sharded
> queue you may not be able to see FIFO behavior even in
> a single threaded environment depending on the implementation.
> 

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

#122591

On 8/19/2025 8:02 AM, jseigh wrote:
> On 8/18/25 18:54, Chris M. Thomasson wrote:
>> On 8/18/2025 3:04 PM, jseigh wrote:
> 
>>>>
>>> Hints on the concurrent stack vs. concurrent queue.  It's not one is 
>>> LIFO
>>> and the other FIFO.
>>
>> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
>> mpmc? A concurrent stack can be using single word exchange and cas, a 
>> queue might use DWCAS and a dummy node, ect... Are we talking about 
>> node based or array based? We can have queues that are all implemented 
>> in different ways, it depends on how they are meant to be used...
>>
> 
> Whatever would be equivalent to Java's ConcurrentQueue interface.
> Semantics for that and not specific to any implementation thereof.

Bare bones for an API of such things:

push
push_try
pop
pop_try


Heck adding in a get_count would add unneeded overhead. Heck why not add 
in the kitchen sink as well?

Fwiw, imvho, push is generic and handles stacks and queues. Once we get 
verbose and say enqueue, well, that's too specific?

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

#122592

On 8/19/2025 1:42 PM, Chris M. Thomasson wrote:
> On 8/19/2025 8:02 AM, jseigh wrote:
>> On 8/18/25 18:54, Chris M. Thomasson wrote:
>>> On 8/18/2025 3:04 PM, jseigh wrote:
>>
>>>>>
>>>> Hints on the concurrent stack vs. concurrent queue.  It's not one is 
>>>> LIFO
>>>> and the other FIFO.
>>>
>>> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
>>> mpmc? A concurrent stack can be using single word exchange and cas, a 
>>> queue might use DWCAS and a dummy node, ect... Are we talking about 
>>> node based or array based? We can have queues that are all 
>>> implemented in different ways, it depends on how they are meant to be 
>>> used...
>>>
>>
>> Whatever would be equivalent to Java's ConcurrentQueue interface.
>> Semantics for that and not specific to any implementation thereof.
> 
> Bare bones for an API of such things:
> 
> push
> push_try
> pop
> pop_try

Heck! Actually, push/pop sure seem to imply waiting on an empty 
predicate. So:

push_try
pop_try

Is the boiled down main base API that covers most concurrent queues/stacks?


> 
> 
> Heck adding in a get_count would add unneeded overhead. Heck why not add 
> in the kitchen sink as well?
> 
> Fwiw, imvho, push is generic and handles stacks and queues. Once we get 
> verbose and say enqueue, well, that's too specific?

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

#122594

On 8/19/2025 2:14 PM, Chris M. Thomasson wrote:
> On 8/19/2025 1:42 PM, Chris M. Thomasson wrote:
>> On 8/19/2025 8:02 AM, jseigh wrote:
>>> On 8/18/25 18:54, Chris M. Thomasson wrote:
>>>> On 8/18/2025 3:04 PM, jseigh wrote:
>>>
>>>>>>
>>>>> Hints on the concurrent stack vs. concurrent queue.  It's not one 
>>>>> is LIFO
>>>>> and the other FIFO.
>>>>
>>>> Well, details matter here. Are we talking about spsc, mpsc, spmc, or 
>>>> mpmc? A concurrent stack can be using single word exchange and cas, 
>>>> a queue might use DWCAS and a dummy node, ect... Are we talking 
>>>> about node based or array based? We can have queues that are all 
>>>> implemented in different ways, it depends on how they are meant to 
>>>> be used...
>>>>
>>>
>>> Whatever would be equivalent to Java's ConcurrentQueue interface.
>>> Semantics for that and not specific to any implementation thereof.
>>
>> Bare bones for an API of such things:
>>
>> push
>> push_try
>> pop
>> pop_try
> 
> Heck! Actually, push/pop sure seem to imply waiting on an empty 
> predicate. So:
> 
> push_try
> pop_try
> 
> Is the boiled down main base API that covers most concurrent queues/stacks?
> 
> 
>>
>>
>> Heck adding in a get_count would add unneeded overhead. Heck why not 
>> add in the kitchen sink as well?
>>
>> Fwiw, imvho, push is generic and handles stacks and queues. Once we 
>> get verbose and say enqueue, well, that's too specific?
> 

Sorry Joe, for the flood. Just thinking here. The base API of push_try, 
and pop_try should be barebones baseline and even good enough to hook it 
up with an eventcount/futex to even implement push/pop with implied 
waiting? The *_try aspect of the API and the behavior should be 
compatible as predicates for an eventcount, a condvar for lock-free, in 
a sense? Futex is rather invasive, and an eventcount is rather generic 
wrt the *_try API?

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

#122599

Am 19.08.2025 um 22:42 schrieb Chris M. Thomasson:

> Bare bones for an API of such things:
> 
> push
> push_try
> pop
> pop_try

Show me any currently used implementation that has push_try or pop_try.
That doesn't make sense to me. If you want to tell another thread with
an item sth. you want to do that for sure.

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

#122602

On 8/20/2025 9:25 AM, Bonita Montero wrote:
> Am 19.08.2025 um 22:42 schrieb Chris M. Thomasson:
> 
>> Bare bones for an API of such things:
>>
>> push
>> push_try
>> pop
>> pop_try
> 
> Show me any currently used implementation that has push_try or pop_try.
> That doesn't make sense to me. If you want to tell another thread with
> an item sth. you want to do that for sure.

Sigh. A push_try can be adding something to an array based queue that is 
full, failed! A pop_try can be trying to pop from an empty condition, 
failed! They are generic and will work with lock-free stacks and queues.

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

#122603

On 8/20/2025 11:53 AM, Chris M. Thomasson wrote:
> On 8/20/2025 9:25 AM, Bonita Montero wrote:
>> Am 19.08.2025 um 22:42 schrieb Chris M. Thomasson:
>>
>>> Bare bones for an API of such things:
>>>
>>> push
>>> push_try
>>> pop
>>> pop_try
>>
>> Show me any currently used implementation that has push_try or pop_try.
>> That doesn't make sense to me. If you want to tell another thread with
>> an item sth. you want to do that for sure.
> 
> Sigh. A push_try can be adding something to an array based queue that is 
> full, failed! A pop_try can be trying to pop from an empty condition, 
> failed! They are generic and will work with lock-free stacks and queues.

An example of how they are generic enough to use means, say there is a 
node based stack or queue. The push_try would never fail because the 
thread already has a node to push. pop_try is just natural to them 
already. So, the bare bones base api is push/pop_try(). Imvho, that is 
good enough for lock-free queues and stacks. The *_try aspect means that 
pop and push (the waiting versions) can be implemented using an 
eventcount as its predicates. Humm, perhaps pop_wait and push_wait would 
be better names? Humm... ;^)

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

#122604

On 8/20/2025 12:00 PM, Chris M. Thomasson wrote:
> On 8/20/2025 11:53 AM, Chris M. Thomasson wrote:
>> On 8/20/2025 9:25 AM, Bonita Montero wrote:
>>> Am 19.08.2025 um 22:42 schrieb Chris M. Thomasson:
>>>
>>>> Bare bones for an API of such things:
>>>>
>>>> push
>>>> push_try
>>>> pop
>>>> pop_try
>>>
>>> Show me any currently used implementation that has push_try or pop_try.
>>> That doesn't make sense to me. If you want to tell another thread with
>>> an item sth. you want to do that for sure.
>>
>> Sigh. A push_try can be adding something to an array based queue that 
>> is full, failed! A pop_try can be trying to pop from an empty 
>> condition, failed! They are generic and will work with lock-free 
>> stacks and queues.
> 
> An example of how they are generic enough to use means, say there is a 
> node based stack or queue. The push_try would never fail because the 
> thread already has a node to push. pop_try is just natural to them 
> already. So, the bare bones base api is push/pop_try(). Imvho, that is 
> good enough for lock-free queues and stacks. The *_try aspect means that 
> pop and push (the waiting versions) can be implemented using an 
> eventcount as its predicates. Humm, perhaps pop_wait and push_wait would 
> be better names? Humm... ;^)

I am pondering on if flush_try is generic enough for this barebones base 
level API.

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

#122735

Am 20.08.2025 um 20:53 schrieb Chris M. Thomasson:

> Sigh. A push_try can be adding something to an array based queue that is 
> full, failed! A pop_try can be trying to pop from an empty condition, 
> failed! They are generic and will work with lock-free stacks and queues.

That doesn't make sense at all. If you want to say sth. to another
thread you can't omit that if the queue is full. And if you want
tasks from another thread you can't omit that also.

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

#122737

On 9/10/2025 8:39 AM, Bonita Montero wrote:
> Am 20.08.2025 um 20:53 schrieb Chris M. Thomasson:
> 
>> Sigh. A push_try can be adding something to an array based queue that 
>> is full, failed! A pop_try can be trying to pop from an empty 
>> condition, failed! They are generic and will work with lock-free 
>> stacks and queues.
> 
> That doesn't make sense at all. 

Really? A push_try and a pop_try are not compatible? Why?


> If you want to say sth. to another
> thread you can't omit that if the queue is full. And if you want
> tasks from another thread you can't omit that also.

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web