Hacker News Reader

Comment by chrisseaton | Hacker News Reader

Haskell has green (N to M) threads that are pre-emptive. As does Go (but it calls them coroutines). Erlang (but it calls them processes) I'm not sure about. Maybe it only re-schedules on message sends and receives?

View on HN

Erlang does a different thing called "reduction-counting": the active process in a scheduler-thread gets a budget of virtual CPU cycles (reductions/"reds"), tracked in a VM register, and part of the implementation of each op in the VM's ISA is to reduce that reduction-count by an amount corresponding to the estimated time-cost of the op. Then, the implementation of the call and ret ops in the ISA both check the reduction-counter, and sleep the process (scheduling it to resume at the new call-site) if it has expended all its reds.

(If you're wondering, this works to achieve soft-realtime guarantees because, in Erlang, as in Prolog, loops are implemented in terms of recursive tail-calls. So any O(N) function is guaranteed to hit a call or ret op after O(1) time.)

If you're writing an Erlang extension in C (a "NIF"), though, and your NIF code will be above O(1), then you have to ensure that you call into the runtime reduction-checker yourself to ensure nonblocking behavior. In that sense, Erlang is "cooperative under the covers"—you explicitly decide where to (offer to) yield. It's just that the Erlang HLL papers over this by having one of its most foundational primitives do such an explicit yield-check.

If loops are implemented as tail calls, doesn't the call opcode get optimized away thus preventing the reduction checker from being run?

It marks the point just before the call as a yield. That yield remains after optimization.

Haskell's green threads are cooperative on memory allocation. If no memory is allocated, then a green thread will not be preempted.

In practice, memory allocation happens a lot, so it's pretty close to preemptive.

Goroutines are not preemptive. They yield at well-defined points.

I remember hearing that the scheduler will indeed pre-empt occasionally if none of the active goroutines are attempting to perform blocking calls.

No, the scheduler cannot preempt. The scheduler is called by the goroutine and given the opportunity to pause it whenever the goroutine does a channel send/receive or calls a non-inlined function or, of course, makes a blocking I/O call[1]. But the scheduler can't do anything if nobody calls it. To wit:

http://www.sarathlakshman.com/2016/06/15/pitfall-of-golang-s...

IIRC, work is underway (may be finished) to add a scheduler yield check to loops as well, which would fix the pathological case in that blog entry.

If your code is doing a lot of channel sends and/or calling a lot of non-inlined functions, it may look like preemption, but it's still cooperative. If you're writing latency-sensitive code this distinction should be kept in mind.

[1] Or whenever time.Sleep() is called, or somebody calls runtime.Gosched(). There might be other cases, would be happy to hear about it.

Reply on news.ycombinator.com