You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2021/05/26 01:04:30 UTC

[GitHub] [arrow] westonpace opened a new pull request #10400: ARROW-12877: [C++] Create implementation of chase-lev deque

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:
users@infra.apache.org

[GitHub] [arrow] westonpace commented on pull request #10400: ARROW-12877: [C++] Create implementation of chase-lev deque

Posted by GitBox <gi...@apache.org>.
westonpace commented on pull request #10400:
URL: https://github.com/apache/arrow/pull/10400#issuecomment-854518600


   This works and is correct, but it causes false positives in the thread sanitizer.  Furthermore, in macro-level benchmarks it does not appear to offer any real performance benefit over a naive mutex-based implementation.  I'm going to close this.


-- 
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:
users@infra.apache.org

[GitHub] [arrow] github-actions[bot] commented on pull request #10400: ARROW-12877: [C++] Create implementation of chase-lev deque

Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #10400:
URL: https://github.com/apache/arrow/pull/10400#issuecomment-848381065


   https://issues.apache.org/jira/browse/ARROW-12877


-- 
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:
users@infra.apache.org

[GitHub] [arrow] westonpace closed pull request #10400: ARROW-12877: [C++] Create implementation of chase-lev deque

Posted by GitBox <gi...@apache.org>.
westonpace closed pull request #10400:
URL: https://github.com/apache/arrow/pull/10400


   


-- 
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:
users@infra.apache.org