5 ms·

Implementing a lightweight task scheduler in C++

47 points by dougbinks 11y ago

dougbinks 11y ago
Putting a developer blog post out on a Saturday just before you head off for the night (I'm on European time) is about as irresponsible as lockless multithreaded programming without a code review. So please feel very free to comment here, on the blog or to @dougbinks on twitter and I'll get back to you asap!
- nickpsecurity 11y ago
  That's an original response haha.
a8da6b0c91d 11y ago
Just use the cilkplus stuff? edit: thanks for the downvotes, but please explain why you wouldn't use cilkplus for this stuff? You do realize it's built into gcc and available for the other compilers?
- scott_s 11y ago
  Perhaps you're being a bit dismissive, but Cilk is an option people should explore. For those interested in how such things work, there are extensive papers from the Cilk group at MIT: http://supertech.csail.mit.edu/papers.html http://supertech.csail.mit.edu/papers.html In particular, I recommend "Cilk: An Efficient Multithreaded Runtime System" (http://supertech.csail.mit.edu/papers/PPoPP95.pdf http://supertech.csail.mit.edu/papers/PPoPP95.pdf) and "The Implementation of the Cilk-5 Multithreaded Language" (http://supertech.csail.mit.edu/papers/cilk5.pdf http://supertech.csail.mit.edu/papers/cilk5.pdf).
- dougbinks 11y ago
  Cilkplus is a valid approach if you are interested in using a task and data parallel language extension available on Intel's compiler, newer variants of gcc and Intel's fork of clang. As mentioned in the article a more comparable library for standard C++ is Intel's Threaded Building Blocks. I used to work at Intel and was a technical lead for games developer architecture feedback and ran the multicore gaming initiative for a while. The feedback on cilkplus was that it didn't allow sufficient control, and as a non-standard language feature posed issues for porting to some systems. Intel's TBB however has been used by some games developers, and its API has evolved features in response to game developer feedback. Most games developers however prefer to roll their own. Note that I didn't downvote this, but if you wanted to implement a task scheduler (the subject of the post) using cilkplus wouldn't be an obvious starting point.
Keyframe 11y ago
Would be nice to see, in contrast, a C implementation.
- dougbinks 11y ago
  The task library enkiTS has a C interface, though this simply wraps the C++ implementation. Writing a C implementation from that interface would be pretty much the same, however the virtual function and inheritance would be replaced by a function pointer and plain struct.
Matheus28 11y ago
Using "volatile" for synchronization is wrong and won't work in some architectures and compilers. MSVC does guarantee that in x86 by default (/volatile:ms), but any other compiler is free to do whatever it wants with that code. Suggest either std::atomic or intrinsics, but don't give false information in a tutorial.
- danieltillett 11y ago
  Do you know which platforms or compilers /volatile won't work?
  - deleted 11y ago
    [deleted]
  - vvanders 11y ago
    Volatile works correctly on all platforms. Don't use it as a synchronization primitive, that's not what it's meant to do. You only should use it: a. If you're reading from HW. b. If you want to use it like a const marker for member functions.
    - ridiculous_fish 11y ago
      Here are some other places where volatile is appropriate: 1. Reading or writing shared memory 2. Values which may be modified in signal handlers 3. Implementing atomic types (e.g. boost::atomic) 4. RCU (e.g. ACCESS_ONCE in Linux kernel)
      - vvanders 11y ago
        Pretty sure the lack of ordering(memory and execution) semantics for volatile invalidates all of those cases. Really you should be using the appropriate platform memory and execution barriers in place of volatile 99% of the time.
        ridiculous_fish 11y ago
zubairsaif007 11y ago
http://googler700.blogspot.com/ http://googler700.blogspot.com/

47 points by dougbinks 11y ago

Putting a developer blog post out on a Saturday just before you head off for the night (I'm on European time) is about as irresponsible as lockless multithreaded programming without a code review. So please feel very free to comment here, on the blog or to @dougbinks on twitter and I'll get back to you asap!

nickpsecurity 11y ago
That's an original response haha.

a8da6b0c91d 11y ago

Just use the cilkplus stuff? edit: thanks for the downvotes, but please explain why you wouldn't use cilkplus for this stuff? You do realize it's built into gcc and available for the other compilers?

scott_s 11y ago
Perhaps you're being a bit dismissive, but Cilk is an option people should explore. For those interested in how such things work, there are extensive papers from the Cilk group at MIT: http://supertech.csail.mit.edu/papers.html http://supertech.csail.mit.edu/papers.html In particular, I recommend "Cilk: An Efficient Multithreaded Runtime System" (http://supertech.csail.mit.edu/papers/PPoPP95.pdf http://supertech.csail.mit.edu/papers/PPoPP95.pdf) and "The Implementation of the Cilk-5 Multithreaded Language" (http://supertech.csail.mit.edu/papers/cilk5.pdf http://supertech.csail.mit.edu/papers/cilk5.pdf).
dougbinks 11y ago
Cilkplus is a valid approach if you are interested in using a task and data parallel language extension available on Intel's compiler, newer variants of gcc and Intel's fork of clang. As mentioned in the article a more comparable library for standard C++ is Intel's Threaded Building Blocks. I used to work at Intel and was a technical lead for games developer architecture feedback and ran the multicore gaming initiative for a while. The feedback on cilkplus was that it didn't allow sufficient control, and as a non-standard language feature posed issues for porting to some systems. Intel's TBB however has been used by some games developers, and its API has evolved features in response to game developer feedback. Most games developers however prefer to roll their own. Note that I didn't downvote this, but if you wanted to implement a task scheduler (the subject of the post) using cilkplus wouldn't be an obvious starting point.

Keyframe 11y ago

Would be nice to see, in contrast, a C implementation.

dougbinks 11y ago
The task library enkiTS has a C interface, though this simply wraps the C++ implementation. Writing a C implementation from that interface would be pretty much the same, however the virtual function and inheritance would be replaced by a function pointer and plain struct.

Matheus28 11y ago

Using "volatile" for synchronization is wrong and won't work in some architectures and compilers. MSVC does guarantee that in x86 by default (/volatile:ms), but any other compiler is free to do whatever it wants with that code. Suggest either std::atomic or intrinsics, but don't give false information in a tutorial.

danieltillett 11y ago
Do you know which platforms or compilers /volatile won't work?
- deleted 11y ago
  [deleted]
- vvanders 11y ago
  Volatile works correctly on all platforms. Don't use it as a synchronization primitive, that's not what it's meant to do. You only should use it: a. If you're reading from HW. b. If you want to use it like a const marker for member functions.
  - ridiculous_fish 11y ago
    Here are some other places where volatile is appropriate: 1. Reading or writing shared memory 2. Values which may be modified in signal handlers 3. Implementing atomic types (e.g. boost::atomic) 4. RCU (e.g. ACCESS_ONCE in Linux kernel)
    - vvanders 11y ago
      Pretty sure the lack of ordering(memory and execution) semantics for volatile invalidates all of those cases. Really you should be using the appropriate platform memory and execution barriers in place of volatile 99% of the time.
      - ridiculous_fish 11y ago

zubairsaif007 11y ago

http://googler700.blogspot.com/ http://googler700.blogspot.com/