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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.


Marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 8/19/25 17:18, Marcel Mueller wrote:

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.

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.

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.

You'd want a common subset to be the base api. Then you could add specializations for concurrent and non-concurrent cases.

Rust's traits are a nice concept because you can add them after the
fact. In Java, if I wanted to do that, I would have to define the
subset api and then write wrapper classes to implement that for
existing java collections.

Joe Seigh

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)