Insert yield checks at appropriate places

9f6e5be
Opened by Eric Holk at 2014-03-04 02:23:51

  1. There's the issue of never yielding, and the issue of fairness. For 0.1 let's just try to make sure we don't tie up a scheduler forever in an iloop.

    Brian Anderson at 2011-09-14 17:49:33

  2. I added a yield after send, which I thinks makes it less likely that one might create an iloop that never yields. Do we want to try to make back edges yield for 0.1? I say no.

    Brian Anderson at 2011-09-16 18:09:57

  3. I will note that when this happens, we will probably need to change rust_task_yield_fail() in rust_task.cpp to not always fail if a task yields in an atomic section. instead, it should check if the yield was explicit or compiler-inserted, and fail if the first or silently ignore if the second.

    ben blum at 2012-08-16 20:10:04

  4. discussed at workweek, this is going to be accomplished "natively" by work stealing + keeping at least one spare thread whenever there are more tasks than threads.

    Graydon Hoare at 2013-04-18 23:24:06

  5. Maybe I don't understand what that means, but won't that just result in "extra threads" being allocated until there are as many threads as tasks?

    ben blum at 2013-06-07 22:29:11

  6. I'm pretty sure this is still an issue, so reopening. With the new runtime written in rust, we could have a #[no_yield_checks] attribute for crate-level or file-level that we'd put in the scheduler.

    ben blum at 2013-06-26 00:42:47

  7. The only overhead of a thread compared to a Rust task is the context switching at arbitrary points. Inserting yield checks would be much slower than just using 1:1 threading, at least on Linux, so I don't think it makes sense to do this. You're better off with context switches than yield checks in critical loops.

    Daniel Micay at 2013-06-26 00:48:27

  8. If I remember right, the plan was to insert checks on back-edges in the CFG (presumably including tailcalls), and to have them only actually yield 1 in BIGNUM times. It would be worth profiling but I think that would still save significantly over kernel-mode context switches..

    ben blum at 2013-06-26 01:11:46

  9. @bblum So long as the stealing and thread spawning behavior is rate limited (i.e. after the spare thread sees one of the schedulers hasn't seen a yield in K ms), the scenario you're describing would occur only when a user is exclusively making non-yielding (i.e., no i/o, no sleeping, fully cpu bound) tasks. And that's the case where multiplying threads to equal tasks is probably appropriate behavior: to saturate all the available cores with computation, as best the os kernel can.

    It is possible someone will not want this behavior in some case. If they make so many cpu-spinning tasks the os literally can't handle the overhead, or perhaps they want a fixed number of rust threads even though they want to overload them. There are other mechanisms users can employ to achieve these ends in these cases. We decided on the strategy we did because it seemed like the more appropriate default, and avoids the worst problems (systemic taxes, artificial blocking or starvation). Most of the time, tasks do i/o or enter a potential yield point (say, malloc) regularly.

    Graydon Hoare at 2013-06-26 01:36:38

  10. Somewhat off-topic: I don't think malloc is really a potential yield point, because with jemalloc it's lock-free for allocations under 4K and only hits kernel synchronization when it actually has to make a system call (allocations over 4K, and occasionally to increase the pool size for small ones). It's never really blocking.

    Daniel Micay at 2013-06-26 01:50:49

  11. Blocking's not the point. It's just a possible bit of code-we-control to put a check in, that user code is unlikely to avoid for long. Similar to putting a gc check in there.

    Graydon Hoare at 2013-06-26 02:17:59

  12. (Not at all a requirement of this scheme, agree it's off topic)

    Graydon Hoare at 2013-06-26 02:18:42

  13. hmm, I guess I agree that it would be a pretty bad tax to insert checks pervasively. We already have a bunch of other ways tasks can hang forever. But we should make some smart choices about what runtime services are good points for yield/killed checks: malloc, spawn, stack growth, whatever. Tagging this RFC and nominating for well-defined milestone.

    ben blum at 2013-07-05 08:04:06

  14. We have to be careful to keep patterns like checking the thread-local errno variable working. Inserted yield checks are definitely a feature to be aware of while writing bindings.

    Daniel Micay at 2013-07-05 08:38:34

  15. accepted for well-defined milestone

    Graydon Hoare at 2013-07-11 16:40:30

  16. note: I expect the thing to define-well here is "we are not injecting such things"

    Graydon Hoare at 2013-07-11 16:40:50

  17. Still a problem

    Patrick Walton at 2013-08-26 17:28:27

  18. I don't think this is relevant anymore. At least, it shouldn't be. We aren't do these now and have seen no mention of doing them in the future. I'll close the issue, it can be re-opened if somebody is particularly passionate about tasks yielding on allocation.

    James Miller at 2014-03-04 02:23:51