4 ms·

I consider it a queue, despite its non-linearizability. I'll quote from my README where I addressed this concern: One particular consequence of this design (wh

I consider it a queue, despite its non-linearizability. I'll quote from my README where I addressed this concern: One particular consequence of this design (which seems to be non-intuitive) is that if two producers enqueue at the same time, there is no defined ordering between the elements when they're later dequeued. Normally this is fine, because even with a fully linearizable queue there'd be a race between the producer threads and so you couldn't rely on the ordering anyway. However, if for some reason you do extra explicit synchronization between the two producer threads yourself, thus defining a total order between enqueue operations, you might expect that the elements would come out in the same total order, which is a guarantee my queue does not offer. At that point, though, there semantically aren't really two separate producers, but rather one that happens to be spread across two threads. In this case, you can still establish a total ordering with my queue by creating a single producer token, and using that from both threads to enqueue (taking care to synchronize access to the token, of course, but there was already extra syncrhonization involved anyway). I expect this use case to be fairly rare, though!

davidtgoldblatt 12y ago
This isn't really a great solution though, since it pushes the problem of ensuring FIFO ordering outside of the queue and onto the user; but being FIFO is entirely the point of the queue data structure. If your queue doesn't provide ordering across multiple threads, it can't meaningfully be called a multi-threaded queue, so it's not very fair to compare it to genuine multi-threaded queues. Unless I've misread the documentation, this is just a collection of SPMC queues, together with a read operation that checks all the queues for an item to dequeue, right? But there is no synchronization that occurs to tie any of these SPMC queues together. Even if you wrapped every single access to this data structure in a lock, for instance, you would not be able to ensure FIFO ordering of elements inserted into it. I think the estimation that having inter-thread ordering requirements is uncommon is incorrect. Probably the most common use of MPMC queues is as a concurrency primitive in systems using a CSP-like abstraction, where such requirements are extremely common. But you can't implement, say, Go's channels in terms of this data structure.
- cameron314 12y ago
  Yes, it is essentially an abstraction over a collection of SPMC queues (when using tokens to dequeue, it is actually a bit smart in that it tries to pair producers with consumers where possible). If you wrapped every enqueue operation in a lock and used the same producer token, then you'd essentially have a single SPMC queue, and it would be fully FIFO. But obviously this defeats the purpose somewhat, so yes, it's not a good solution if you need that guarantee. I honestly didn't consider external inter-thread ordering at all while I was designing the queue. I guess I was picturing more of a producer-consumer model, than a message passing system (where this dependence between messages across threads/producers is far more common, it seems). I'd change this constraint if I could, but I can't. It's the fundamental assumption the very heart of the entire design. I'd have to start from scratch (which I'm not prepared to do, at this point). But I've changed the README to make this limitation crystal clear (you're not the only one with reservations with regards to this aspect). I think it's still useful, perhaps not for all applications, but for many. Sorry if I came across as trying to purport it as something that it wasn't; that was not my intention at all.

davidtgoldblatt 12y ago

This isn't really a great solution though, since it pushes the problem of ensuring FIFO ordering outside of the queue and onto the user; but being FIFO is entirely the point of the queue data structure. If your queue doesn't provide ordering across multiple threads, it can't meaningfully be called a multi-threaded queue, so it's not very fair to compare it to genuine multi-threaded queues. Unless I've misread the documentation, this is just a collection of SPMC queues, together with a read operation that checks all the queues for an item to dequeue, right? But there is no synchronization that occurs to tie any of these SPMC queues together. Even if you wrapped every single access to this data structure in a lock, for instance, you would not be able to ensure FIFO ordering of elements inserted into it. I think the estimation that having inter-thread ordering requirements is uncommon is incorrect. Probably the most common use of MPMC queues is as a concurrency primitive in systems using a CSP-like abstraction, where such requirements are extremely common. But you can't implement, say, Go's channels in terms of this data structure.

cameron314 12y ago
Yes, it is essentially an abstraction over a collection of SPMC queues (when using tokens to dequeue, it is actually a bit smart in that it tries to pair producers with consumers where possible). If you wrapped every enqueue operation in a lock and used the same producer token, then you'd essentially have a single SPMC queue, and it would be fully FIFO. But obviously this defeats the purpose somewhat, so yes, it's not a good solution if you need that guarantee. I honestly didn't consider external inter-thread ordering at all while I was designing the queue. I guess I was picturing more of a producer-consumer model, than a message passing system (where this dependence between messages across threads/producers is far more common, it seems). I'd change this constraint if I could, but I can't. It's the fundamental assumption the very heart of the entire design. I'd have to start from scratch (which I'm not prepared to do, at this point). But I've changed the README to make this limitation crystal clear (you're not the only one with reservations with regards to this aspect). I think it's still useful, perhaps not for all applications, but for many. Sorry if I came across as trying to purport it as something that it wasn't; that was not my intention at all.