bystander icon indicating copy to clipboard operation
bystander copied to clipboard

Alternitive Help Queue implementation

Open the10thWiz opened this issue 2 years ago • 0 comments

I watched your streams on developing this, and I was inspired to create an alternative Help Queue implementation. I'm sure is has a bunch of bad edge cases, and isn't perfect, but I think the idea is worth sharing.

My approach does it's best to avoid the need for an inner wait free queue, by using a similar approach to the inner help queue in the current implementation. Essentially, each handle to the queue claims a node to place it's request for help in, which allows for wait free insertion (since the location it needs to put the pointer is sort of owned by the handle, no other handle will try to fill it). The nodes are arranged as a circular linked list, and the shared helpqueue object has a pointer to the current element of the list. Once the current element has been helped, the pointer is advanced to the next node of the list. I haven't figured out how to remove nodes from the list, so I just implemented a reuse scheme (similar to the one you used for haphazard), so I never need to reclaim them.

I've written my full implementation here: https://github.com/the10thWiz/help_queue

There is also an incomplete implementation of hazard pointers in there, but you can ignore it, I just haven't gotten around to just using the haphazard crate you wrote.

the10thWiz avatar Jul 08 '21 21:07 the10thWiz