Ignorant newbie here, but would love to hear views on this: I always treat with great skepticism claims that you can implement an inherent operating system function (eg: threads) on top of said operating system more efficiently than can be done by the OS itself. Usually it means the implementor simply didn't understand the next level down (eg: how the kernel works) and therefore couldn't tune it to their needs. But they understand the next level up extremely well. And there's nothing wrong with this, especially since one is platform independent and the other is (usually) very tied to specifics.
The one thing that seems evident to me is that native threads, in Java, all require a stack frame and this consumes memory. At some point millions of threads will, if nothing else, require gigabytes of memory for stack space. However in this era when the kind of computers that are likely to run these applications can easily have hundreds of GB of memory, I'm not even sure if that is an inherent limitation.
So to tldr; - can someone give me the insight, what is it that makes this more efficient at the language layer than the kernel layer? Why can a high level language magically scale to millions of threads and the OS can not? What is it that allows this?
I don't disagree with other answers, but I believe the situation can be described more easily: it isn't the same primitive, so, it isn't actually the case that someone is attempting to provide the same thing but faster: the OS is giving you "pre-emptive threads", whereas these alternatives are giving you "cooperative threads".
The argument is that for restricted use cases "cooperative threads" (which are the "dual", in a mathematical sense, to "evented" execution) are going to be faster than pre-emptive threads (which would require locks around even very short shared data usage, due to the unpredicability of the scheduler).
If the OS provided true cooperative multitasking, maybe it could do it faster, but that's something that has been pretty much decided to be a flawed OS primitive between processes ("OMG Mac OS 9 / Windows 3.1" ;P), and within a single process may as well be implemented in userland with little performance loss.
This starts turning into a semantics problem. GHC is a compiler that modifies the code it has compiled to add "synchronization points" that are used under a cooperative threading model, allowing it to know with certainty that certain kinds of operations or even functions it detects to have certain properties will not be pre-empted. Given that the overall language semantics are then pure functional, the costs associated with pre-emptive scheduling are removed, but again this is only because they "cheated" and didn't build a real "preemptive" scheduler: tasks must cooperate.
In fact, there are trivial kinds of operations you can perform (such as involving FFI) that simply will never pre-empt. The primitive the operating system provides, which I maintain is a fundamentally different primitive than what people are building in these user-space modifications, is "no matter what you do, whether on accident or on purpose, whether with benign or malicious intent, you will be time-sliced; your time-slicing will thereby happen at the discretion of the system, and you will not be trusted to request or demand excessive modifications to your time". GHC is not some magic exception: it is still cooperative multitasking.
Good question. In general the non-preemptive green-thread/fiber/lightweight-thread is a pretty well understood notion. Some OS support it, e.g. Windows supports manually scheduled fiber. However, OS support is not universal. It will take time, just like the transition from process to thread. Most supports come in the form of user-mode library since it doesn't need kernel-mode support.
Native thread needs stack which can be substantial, usually ~1M. Lightweight thread just needs a data structure to hold its data, usually hundreds of bytes to a few K. It's a factor of 1000X to 10000X.
Besides the memory advantage, lightweight threads can have performance advantage over native threads since the switching of lightweight threads on the same CPU doesn't need to do a context-switch, which can have substantial performance penalty as the L1/L2 cache and all the registers of the CPU need to be flushed and reloaded. On a multi-cpu system, memory barriers need to be crossed, cache needed to be sync'ed across CPU, and the TLB might be flushed as well, depending on how the OS implements the memory model of a thread.
Lightweight thread does require more attention from app developers since they need to worry about manually yielding now.
Java has great support on NIO which when used with lightweight threads can provide amazing scalability and performance boosts. See Netty and its friends.
Think of threads as state machines. At the OS level, you have to track a lot more, because you have to service any process that can create a thread. Within your constrained environment, your 'thread' can be something as simple as a small data structure or record that does something when a message is passed to it or a function is called on it. The services you provide to each of your 'threads' can be lightweight, intelligently aggregated and prioritized, and can have only the memory allocated that is needed for the representation of that structure.
Think of a thread as if it were an object in C#, Java, whatever. Stuff happens to it, and it does stuff, but it's all based on propagation of state changes. It can be processing in serial, but because of the abstraction, it will appear to be concurrent, and therefore, effectively BE concurrent.
No concrete benchmarks but everything I can find makes the same claim. A context switch in erlang is approx 20 ns, and a OS level context switch is between 1000 and 2000 ns. Mostly because it can make more assumptions about state, less processor state flushing etc.
In general, higher levels have more knowledge of the specific problem domain, and can therefore make more assumptions, while the kernel has to cater to all needs.
In this particular case the fork/join scheduler supports the constant creation/destruction of new fibers, and of one fiber constantly "waking-up" other blocked fibers. Even if OS task switching is good, OS threads weren't meant to be short-lived and quick to start.
That said, OS task-switching can be quite good. That's why I've left the option of running Quasar actors tied to a thread rather than a fiber. I've tried to hide the implementation details as much as possible from the user of the API.
The one thing that seems evident to me is that native threads, in Java, all require a stack frame and this consumes memory. At some point millions of threads will, if nothing else, require gigabytes of memory for stack space. However in this era when the kind of computers that are likely to run these applications can easily have hundreds of GB of memory, I'm not even sure if that is an inherent limitation.
So to tldr; - can someone give me the insight, what is it that makes this more efficient at the language layer than the kernel layer? Why can a high level language magically scale to millions of threads and the OS can not? What is it that allows this?