Bounded SPSC Queue

[polyfractal]

Hi Contain-RS!

I've been tinkering with a bounded SPSC queue for Rust and was curious if it should fall under the Contain-RS banner? It provides a nice performance boost over sync_channel, which is the only other SPSC queue I could find (bounded_spsc_queue uses a simple ringbuffer instead of a linked-list like sync_channel).

Definitely a more niche collection, since you have to specifically want a bounded SPSC queue rather than something a bit more generic/flexible like the other queues in std

If this seems like something Contain-RS would like, I'd love some eyeballs on the code. I think it is correct, but this low-level Rust code is very new to me, and I may be doing some very silly / stupid / dangerous stuff. :)

https://github.com/polyfractal/bounded-spsc-queue

[Gankra]

Hey! I'm not a lock-free guru (and that stuff is seriously delicate) so I've pinged the larger community for help. I am also unsure if a SPSC queue is in scope, but at very least I'm happy to help review!

[Aatch]

Nothing obvious jumps out at me. Other than the "problem" of the head and tail counters overflowing, but that's just a known hazard for this method (and not exactly a big problem on 64-bit platforms).

Just to work through my reasoning:

• Since it's only a single producer and a single consumer, only one thread can update each counter.
• Since the counters are monotonically incrementing, you can't get the problem of overwriting an element or trying to read the same element twice.
• Since it's bounded, you don't have to worry about the storage disappearing from underneath you.

[Aatch]

Hmm, actually, the destructor seems a little suspect. It's not really an atomicity issue, but I think that you'll leak data because you aren't emptying the queue first.

[polyfractal]

Thanks for the review, really appreciate the extra eyeballs! All of this manual allocation and memory munging is new to me. I couldn't figure out a way to do this less manually (e.g. using Box instead of allocate)...I mostly followed the Vec code as a guide.

Nothing obvious jumps out at me. Other than the "problem" of the head and tail counters overflowing, but that's just a known hazard for this method (and not exactly a big problem on 64-bit platforms).

Yeah, I wasn't sure if I should add code for wrapping. It would add a bit of complexity, but not too terrible? Or perhaps just make the queue stop accepting writes before it overflows? I'll definitely add a note in the docs about it.

Hmm, actually, the destructor seems a little suspect. It's not really an atomicity issue, but I think that you'll leak data because you aren't emptying the queue first.

Ah good catch, I didn't even think about that. Should I just iterate over the remaining "live" values and call drop() for each of them?

[Gankra]

Yeah that's the convention we generally follow (usually just move the value out and let the dtor run when we forget it).

[polyfractal]

Great, thanks!

Gonna close this issue, since it doesn't seem to fit in Contain-rs. I wonder if there should be a ConcurrentContain-rs for the various esoteric lock-free containers :)

Thanks again for the review, really appreciate it