Remove concurrent-queue dependency #109
Labels
enhancement
New feature or request
Comments
notgull
added a commit
that referenced
this issue
Apr 14, 2024
This commit adds an implementation of the event-listener algorithm built without locks. This is a replacement of the old no_std backend. It is written without concurrent-queue and therefore closes #109. The idea behind this implementation is to store the listeners in "slots" in an infinitely large list. Then, assign each listener a number and then use that to wait on each listener. The list used is similar to the one used by the thread-local crate. It consists of a list of "buckets" that hold slots. The number of slots increases in an amortized way. The first slot holds 1, the second slot holds 2, the third slot holds 4... all the way up to usize::MAX slots. Indexes are done by having a list of reusable indexes and using those when possible, only increasing the max index when necessary. This part of the code could use some work; under contention it's possible to make some slots unusuable. This can happen under two cases: - If there is contention on the indexes list when the listener is being freed. - If the slot is still being notified when it is attempted to be reused. Both of these cases are probably fixable, and should be fixed before release. Otherwise long running server processes using this code will run out of memory under heavy loads. From here the rest of the implementation is an atomic linked list based on the above primitives. It functions very similarly to the std variant. The main difference is that the Link structure's waker functions very similarly to AtomicWaker from the atomic-waker crate. Aside from that the code isn't very interesting on its own. Signed-off-by: John Nunley <[email protected]>
notgull
added a commit
that referenced
this issue
Apr 14, 2024
This commit adds an implementation of the event-listener algorithm built without locks. This is a replacement of the old no_std backend. It is written without concurrent-queue and therefore closes #109. The idea behind this implementation is to store the listeners in "slots" in an infinitely large list. Then, assign each listener a number and then use that to wait on each listener. The list used is similar to the one used by the thread-local crate. It consists of a list of "buckets" that hold slots. The number of slots increases in an amortized way. The first slot holds 1, the second slot holds 2, the third slot holds 4... all the way up to usize::MAX slots. Indexes are done by having a list of reusable indexes and using those when possible, only increasing the max index when necessary. This part of the code could use some work; under contention it's possible to make some slots unusuable. This can happen under two cases: - If there is contention on the indexes list when the listener is being freed. - If the slot is still being notified when it is attempted to be reused. Both of these cases are probably fixable, and should be fixed before release. Otherwise long running server processes using this code will run out of memory under heavy loads. From here the rest of the implementation is an atomic linked list based on the above primitives. It functions very similarly to the std variant. The main difference is that the Link structure's waker functions very similarly to AtomicWaker from the atomic-waker crate. Aside from that the code isn't very interesting on its own. Signed-off-by: John Nunley <[email protected]>
notgull
added a commit
that referenced
this issue
Apr 16, 2024
This commit adds an implementation of the event-listener algorithm built without locks. This is a replacement of the old no_std backend. It is written without concurrent-queue and therefore closes #109. The idea behind this implementation is to store the listeners in "slots" in an infinitely large list. Then, assign each listener a number and then use that to wait on each listener. The list used is similar to the one used by the thread-local crate. It consists of a list of "buckets" that hold slots. The number of slots increases in an amortized way. The first slot holds 1, the second slot holds 2, the third slot holds 4... all the way up to usize::MAX slots. Indexes are done by having a list of reusable indexes and using those when possible, only increasing the max index when necessary. This part of the code could use some work; under contention it's possible to make some slots unusuable. This can happen under two cases: - If there is contention on the indexes list when the listener is being freed. - If the slot is still being notified when it is attempted to be reused. Both of these cases are probably fixable, and should be fixed before release. Otherwise long running server processes using this code will run out of memory under heavy loads. From here the rest of the implementation is an atomic linked list based on the above primitives. It functions very similarly to the std variant. The main difference is that the Link structure's waker functions very similarly to AtomicWaker from the atomic-waker crate. Aside from that the code isn't very interesting on its own. Signed-off-by: John Nunley <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
concurrent-queueis a pretty heavy dependency for a crate as small asevent-listener. It would be nice if we were able to avoid using it.The text was updated successfully, but these errors were encountered: