smol-rs / concurrent-queue

Concurrent multi-producer multi-consumer queue
Apache License 2.0
254 stars 21 forks source link

Improve documentation of internals of `bounded` implementation #63

Open fogti opened 5 months ago

fogti commented 5 months ago

see also https://github.com/smol-rs/concurrent-queue/pull/58#discussion_r1536655857 and a few related comments.

The logic in large parts of the bounded implementation is somewhat non-obvious, and partially stems from other code bases, so it might be a good idea to write down how it works, and that it works correctly, or find a document that already properly does that and link to it. (ad the comments that already exist partially duplicate each other, not necessarily adding to understanding of how all the components interact)

notgull commented 5 months ago

This post by stjepang might be helpful. I'm relatively sure that the core algorithm hasn't changed much since then.

cc https://github.com/smol-rs/smol/pull/302

fogti commented 5 months ago

I'm aware of that document (at least, I've read it in the past), but it doesn't really document how the book-keeping lines up (e.g. slot, tail, lap), and how/when these are incremented, what the intended flow is (in a blocking case, and a "channel filled enough that no blocking needs to happen" case), what edge cases might exist.

notgull commented 5 months ago

@taiki-e might be more familiar with the implementation of these channels