4 ms·

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 entir

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.

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.