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.
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.
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?
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.
Hints on the concurrent stack vs. concurrent queue. It's not one is LIFO
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?
and the other FIFO.
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.
Hints on the concurrent stack vs. concurrent queue. It's not one is LIFO
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?
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...
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...
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.
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.
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?
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.
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?
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?
Am 18.08.25 um 19:24 schrieb jseigh:
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.
Indeed.
These two types of containers do not have any subset-API, in no direction.
Typically non-concurrent collections lack operations like get_or_add or add_or_update. They are essential atomic primitives.
The other direction you mentioned already.
But /some/ concurrent containers may implement even concurrent iteration
in a well defined way. E.g. when there is a before/after relation of
added or removed elements a container may guarantee that only elements
added after the current iterator are seen and that the current element
stays valid until the iterator is moved. I already had such use cases.
Other implementations might provide snapshot isolation. I even used this
in a larger, mainly in-memory DB application.
Furthermore the atomic implementation may also differ in the complexity guarantees. It AFAIK impossible to implement a lock-free hash table with O(1).
Basically they are different types of containers.
So, it's concurrency is the general case and single threaded is a
specialization of that.
Not even that. Although you can write non-concurrent containers that implement all functions that the concurrent ones need. But some of them
are almost useless without concurrency, e.g. try_update(key, new, old)
of associative containers.
Bare bones for an API of such things:
push
push_try
pop
pop_try
There's Dr. Cliff Click's lock-free open addressing hashtable.
I know how to do a lock-free chained hashtable. There's 3 or 4
hacks needed to make it work especially w/ resizing. But
it's a lot of work to do a POC and there would be no point in
me doing that.
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.
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.
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.
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... ;^)
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.
| Sysop: | Tetrazocine |
|---|---|
| Location: | Melbourne, VIC, Australia |
| Users: | 11 |
| Nodes: | 8 (0 / 8) |
| Uptime: | 50:10:43 |
| Calls: | 166 |
| Files: | 21,502 |
| Messages: | 77,728 |