westonpace opened a new pull request #10400: URL: https://github.com/apache/arrow/pull/10400
The Chase-Lev deque allows for a pop operation and a steal operation. It is commonly implemented using lock-free methods. The following is a fairly literal implementation of the ppopp13 paper using simple pointers. I also have a shared_ptr version but it is not lock free because it uses std::shared_ptr atomic methods which are not lockfree (at least on my GCC version). When I add benchmarks (soon, in a later PR) I will share some comparisons of the two. Until then I will leave this in draft state. ## Original paper: https://www.dre.vanderbilt.edu/~schmidt/PDF/work-stealing-dequeue.pdf ## Follow-up describing best way to implement lock-free: https://fzn.fr/readings/ppopp13.pdf ## Example implementation: https://github.com/taskflow/taskflow/blob/master/taskflow/core/tsq.hpp -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected]
