This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][WIP] Experimental support for a scheduler for use in the parallel stl algorithms
AbandonedPublic

Authored by erik.pilkington on Jun 6 2017, 10:55 PM.

Details

Summary

This patch adds a simple work-stealing scheduler meant for use as a fallback implementation for the C++17 parallel stl algorithms. This scheme follows a very simple fork/join API that should be easy to map onto different underlying concurrency implementations if they are available. This should be suitable for implementing par & par_unseq on top of.

I also tried this out with a lock-free deque[0]. This provides a modest performance improvement, and might be worth implementing. For the sake of doing this incrementally this patch just contains a locking deque.

Please see the recent thread on cfe-dev for context: http://lists.llvm.org/pipermail/cfe-dev/2017-May/053841.html

I'm still pretty new to libc++ and to parallel stuff, so please feel free to tear this patch apart!
Thanks for taking a look,
Erik

[0]: https://pdfs.semanticscholar.org/3771/77bb82105c35e6e26ebad1698a20688473bd.pdf

Diff Detail

Event Timeline

dexonsmith edited edge metadata.Jun 13 2017, 3:58 PM

You mention that the lock-free deque gives a speedup. I agree that should be left for a follow-up, but what kind of speedup did it give?

Have you measured whether the parallel algorithm gives a speedup, compared to a non-parallel algorithm?

dexonsmith resigned from this revision.Oct 19 2020, 2:58 PM
dexonsmith added a reviewer: ldionne.
erik.pilkington abandoned this revision.Oct 19 2020, 3:38 PM