Notes on Virtual Threads and Clojure | Hacker News Reader

Notes on Virtual Threads and Clojure

ales.rocks

110 pointsBorkdude58 comments

So maybe a more basic and fundamental question - but why can't OS threads be as good as these virtual threads? Why do we have to have two layers of thread abstraction? My first reaction is "eww" quickly followed by "I'm prolly not understanding something here". Why can't we make the OS handle thousands of threads?

OS can handle thousands of threads easily. Kernel threading runs into scaling problems up at the 100's of thousands to millions level.

My understanding is that OS thread operations require the processor/OS to switch between user mode and kernel mode, which is slow. Virtual threads don't require this, since they are managed entirely by the user process.

Correct. This is the main reason.

They could: Solaris had M:N threads at some point in time but 1) they're complicated 2) you pay a performance cost even if you don't use many threads..

Called LWT, but they were eventually dropped exactly for those reasons.

We can, this was inspired by a talk given by Google about their own infrastructure. But it was apparently never open sourced.

Context switching costs are slightly higher for OS threads, but the real bottleneck is in the physical memory usage. An OS thread will start with an entire 4kb (page size on most OSs) for its stack and grow by 4kb as needed. A virtual thread will often have <1kb physical memory used, to start.

In a program with lots of small OS threads, that's quite a bit of wasted space.

Thousands of threads is not a problem for any modern OS if you have enough RAM. Loom takes it up into the millions.

As for why the JVM can do this and you can't with other runtimes, it's because it needs a complex runtime with very tight integration between the compiler, the GC, the threading library and various other subsystems. That's why the moment you make a native call the JVM loses the ability to switch between the virtual threads and has to start up more OS threads to compensate - it didn't create the code that's running on the stack at that point, so it can't work its usual magic.

Fortunately the whole 'pure Java' movement of some decades ago means that actually you can do a heck of a lot of stuff without using native code. It's an ecosystem way less dependent on C extensions than most other languages.

I'm going to call them "green threads" in this context, don't read into it because the terminology is loose.

- Since GT are known to a compiler/runtime they can be cooperative, as opposed to preemptive. OS threads cannot introspect into what your code is doing. That means GT may insert suspend and resume points at API boundaries, for example at any kind of IO. While an OS could implement this in theory (switch threads at i/o syscalls) in practice I don't think there are any thread schedulers that do this.

- GT have orders of magnitude faster context switches than OS threads. All they need to do is swap a stack frame pointer.

- GT often have growable stacks that start extremely small, OS threads have larger default stack sizes that don't grow. This makes starting and destroying GT cheaper, and they can use less memory than the equivalent number of OS threads.

As for why OS threads don't just work the same, there are some disadvantages. You can't pin a GT to a single core, or set thread affinity. Context switching an OS thread is more expensive because it's doing more things, like saving the signal mask (which invokes a syscall, hence the cost). The large fixed stack size means that they don't have to perform memory allocation on a function call once the stack is too small. They have to be preemptive since the OS doesn't know anything about what the program is doing, other than a handful of i/o syscalls.

They're essentially two different technologies for two use cases. The OS threads are more robust and closer to the metal, but they are expensive to start up and switch between. However GT are small and cheap.

Another way to look at it is that there are only OS threads, and "virtual" or "green" threads are distinct concurrent tasks scheduled onto a pool of OS threads on the fly. The compiler inserts a bunch of book keeping to make scheduling those tasks easier. The only thing that makes them "thread like" is the API.

Some operating systems implement standard OS threading API's on top of a pool of true "system threads". Notably, this even included some early Java implementations, before a 1-to-1 mapping between system and "user" threads became more popular for some reason.

which makes a lot of sense once they have to map to logical cores

M:N hybrid threads were in vogue at the turn of the millennium. Solaris had them, some of the *BSDs had them and IBM almost got them in Linux. There was also a lot of research on the topic (look for scheduler activation). They went out of fashion because they slowed down parallel programs (as opposed to highly concurrent programs) and required a lot additional complexity.

Then the "10k Problem" article popularized poll-based architectures as opposed to threaded ones and the rest is history.

Scheduler activation is not so different from the modern approach, using e.g. uring or IOCP (not really poll-based). The original terminology references "virtual processors" as opposed to system-level threads, and "user threads" as opposed to arbitrary tasks, but either way a task that's about to block must have its state saved and subsequently restored once the event has been handled, and these operations are managed by the user-level runtime not the OS.

I do think it is different. In fact I think that IOCP predates the scheduler activation work.

Certainly a proactor event loop (uring iocp) is different from a reactor (poll) from an usage point of view, but you can implement one in term of the other.

Scheduler activation is different and it is just a way for the kernel to notify userspace of all rescheduling events (including running out of the scheduling quantum or taking a page fault).

Since nobody else brought it up: One big item is non-blocking I/O. The idea of non-blocking is that you can manage thousands of network connections with only a handful of threads, because when you do thread-per-connection, you'll notice that your threads are mostly asleep in typical I/O heavy networked systems (like web-server/database stuff that most of us work on). You can do non-blocking in java now, but only with nasty callbacks and Futures and thread pools and such.

In Go you get non-blocking "for free" so that it looks like blocking I/O but the runtime automatically suspends & resumes virtual threads as I/O buffers fill & drain. One of the big inspirations for Loom was Go jealousy. For all Go's faults, this is a really nice thing to have.

For those wondering about the "tail call" part that would be more interesting for Clojure than fibers:

  As adding the ability to manipulate call stacks to the JVM will undoubtedly be required, it is also the goal of this project to add an even lighter-weight construct that will allow unwinding the stack to some point and then invoke a  method with given arguments (basically, a generalization of efficient tail-calls). We will call that feature unwind-and-invoke, or UAI.

  It is not the goal of this project to add an automatic tail-call optimization to the JVM.

[1] https://cr.openjdk.java.net/~rpressler/loom/Loom-Proposal.ht...

> It is not the goal of this project to add an automatic tail-call optimization to the JVM.

Wait what? Are we getting TCO or not with Loom?

Tail-call optimisation on the JVM is already somewhat supported with an annotation / keyword (depending on language). My understanding is that the project will improve the current implementation, but you'll still need to define when a function is tail-recursive, the compiler won't do it automatically.

E.g. Scala provides such an annotation, but that is implemented by rewriting the recursive method to a non-recursive method with a loop.

Isn't that kinda how all TCO works?

First level TCO yes, however the annotation way doesn't work for mutually recursive calls.

to clarity just a tad, the Scala compiler does TCO out of the box and the annotation is added only to check that the method is in fact so optimizable

Unless something changed since 2.0.9 (last time I did anything relevant in Scala), only one level, it isn't clever enough to rewrite mutually recursive calls.

This is rather important, specially when coming from languages like Scheme that have TCO as part of the language specification compliance.

I interpret this as "we will add a primitive that will allow you to implement TCO yourself (and more), but the behavior of existing java or byte code won't change, and the stack will continue to grow, even if a call occurs in tail position". Presumably because it's hard to impossible to retrofit TCO without changing observable behavior.

Serious question, isn't that just a while/for/do loop? If people want TCO then... just write a loop, surely? I must be missing something.

You are -- non-self tail-calls. If you have mutually tail-recursive functions, say f1, f2, ..., f_n you have two problems without TCO:

1. There is no way to rewrite this into loops by just modifying the insides of these functions.

2. The remedy, which is to transform these functions and everything that calls them into a giant loop causes lots of problems:

The code will become utterly unreadable (if you do this transform manually).

Modularity is completely broken and there's no sane way to expose these functions individually to external callers.

Also, even if you don't care about either of the above: your compiler's optimizer will probably choke on it (https://blog.reverberate.org/2021/04/21/musttail-efficient-i...).

Well, good points but I was rather thinking the compiler should do it as an option.

Of lesser note, I don't believe I've ever come across mutually tail recursive functions, or the need for them, and although that may reflect my lack of experience in some areas, I guess it's not at all common? Maybe in the haskell world perhaps.

They make state machines leagues easier to reason about. Each state is its own function, and you tail-call to the next state (and pass along only the data it relies on, if you're doing things functionally).

Err, goto?

I'll read Steele's paper but introducing complexity only to struggle to delete that complexity is a strange approach

All flow control ultimately boils down to `goto`; it's how we crystallize particular usage patterns that makes it safer. Importantly, optimizing tail calls doesn't change the fact that you could always call another function before you return; you just risked blowing the stack.

I find that recursive solutions are often easier to understand and change than iterative solutions, especially because you need less incidental state (and you can manage the state you have more cleanly), so I'm not sure what you mean by "introducing complexity only to struggle to delete that complexity". That would more aptly describe my experience with writing iterative versions of naturally recursive algorithms.

(I think you may have mistaken me for someone else; I didn't recommend Steele's paper.)

Steele's paper was mentioned in the earlier link.

If goto is easily available in the high level language then creating a state machine is trivial I guess. If it's not then the compiler should be able to do TCO with jumps/gotos in the output asm or transpiled code (IIRC Bison's output uses gotos even though the input yacc rules clearly have none).

I continue to feel I'm missing something vital.

> If goto is easily available in the high level language then creating a state machine is trivial I guess.

It's still painful, because whichever state you're in probably cares about different data. Some data only needs to exist during some states. Factoring states into separate functions means each gets its own scope, and can explicitly pass only data needed for the next state forward.

> If it's not then the compiler should be able to do TCO with jumps/gotos in the output asm or transpiled code

It's nice to be able to indicate explicitly to the compiler (and other developers!) that you expect tail calls to be optimized, rather than crossing your fingers and hoping that nobody else comes along later and accidentally adds something after the call. Scala optimizes tail recursion by default, but it also has a `tailrec` annotation that causes the compiler to throw an error if it isn't able to respect that intent.

That's helpful, thanks!

Reminds me of a description of continuations as "gotos with parameters" which seems to be what you sort of want - I'll do some reading. Appreciated.

> I don't believe I've ever come across mutually tail recursive functions, or the need for them

Well, had you read the link I posted in my reply to your question, you would have ;) Anyway, there are a some useful things that are much harder to do pleasantly and efficiently without it.

No we won't. [1] does not even mention tail-call elimination. Project Loom does not change the bytecode and does not change it's semantics. I.e. we don't get guaranteed tail-call elimination.

[1]: https://openjdk.java.net/jeps/425

One issue to implement TCO is that the "security model"/circus of Java is based on the stack frames, so you can not remove stack frames without getting into trouble.

The security manager has to be removed first [1]

[1] https://openjdk.java.net/jeps/411

TCO will be part of project valhalla not loom.

Quick note that this:

> Each thread easily uses an additional Megabytes of memory

isn't quite the problem it seems because unless the thread actually _uses_ large amounts of stack, the memory consumed is mostly virtual. With today's 64-bit architectures, there is plenty of virtual address space to be burned.

Yes! I can't count how often I've read this when people talk about OS threads...

But it requires changing the virtual memory mapping tables, i.e. it requires a context switch to the kernel and back. Therefore it decreases effectiveness of TLAB caches. I.e. there is a performance cost. One that is hard to quantify for very short lived threads and only slightly better quantifiable for longer lived threads.

And every argument that OS threads are good enough is in stark contrast to the length to which people go to avoid using them. I am talking about all the async libraries/patterns/language features people use to avoid using OS-level threads.

Well not quite. The problem is that it only takes one call tree with a deep stack to cause all that memory to be allocated (slowly, using lots of page faults) and after that, it's used. The only way to get rid of it again is to swap it out, which means if you then go ahead and do another deep call it's even slower as the kernel doesn't know what it can discard and what it can't.

Deep stacks are pretty common in modern software especially for Java software.

I'm hopeful for first class support in core.async. JVM support for virtual threads is the last missing piece IMO.

When JVM lands support for virtual threads, what reasons remain for using core.async?

core.async will still be useful in ClojureScript land, though.

Channels & alts etc. are useful constructs regardless right?

Sure, but do these have API's that work with regular threads?

Yep. They’re decoupled completely from the “go” bits in core.async that are meant to make up for the lack of green threads. All of the channel operations have blocking variants that work fine with regular threads now, and they seem likely to work fine with fibers.

Didn't know that, that's great!

Does that mean we can use core.async channels without the `go` macro? How would this look?

I don't know if you mean something deeper, but core.async has <!, >!, and alts! variants that don't require a go block: <!!, >!!, and alts!!.

You can just use them like a function. But they block the thread. So if you e.g. naively call it in the REPL you will block it indefinitely. E.g.:

  (>!! (chan) "this will block the REPL")

The idea would be to pass a channel to multiple virtual threads which use the blocking versions.

Yes you can. Core.async already supports using normal threads with the `thread` macro instead of using the `go` macro.

All code looks exactly the same otherwise.

Although it doesn't seem to have a nice API for doing so, it seems like you can change the core.async executor by using alter-var-root.

https://stackoverflow.com/questions/18779296/clojure-core-as...

I'm a little confused about the "structured concurency" example?

I don't understand what the advantages of it are?

Are Virtual Threads resources that need to be explicitly cleaned up? Can't the pool grow and shrink based on demand?

In Go for example, I don't remember having to clean up fibers manually.

For example, how is the structured concurency example different from:

  (defn run-concurrently []
    (let [f1 (future (identity 2000))
          f2 (future (prn "Starting a long running operation"))
          f3 (future (Thread/sleep 1000))
          f4 (future (prn "Done."))]
        (run! deref [f1 f2 f3 f4])
        4))

  (run-concurrently)

Also as an FYI, the example can be simplified by using `with-open`.

The advantage is that it provides guarantees, that wouldn't be there otherwise.

Let's for example say one of those 4 tasks would write to a file. With structured concurrency you have a guarantee that once the supertask finishes, the file is no longer in use. Without structured concurrency you won't have that, and a subtask might error on trying to use the file or find garbage data in it. Running the supertask in a loop with structured concurrency would have no risk of running into resource contention, while without it there is that risk.

Plus structured concurrency also helps adding a deterministic bound on the amount of concurrency in the system, while just spawning more background tasks can lead to concurrency grow in an unbounded fashion.

> In Go for example, I don't remember having to clean up fibers manually.

The equivalent in Go would be to wait for subtasks to complete, using the WaitGroup pattern. And to notify the subtasks that they should complete using "Context".

My code waits for all futures to complete, that's what:

  (run! deref [f1 f2 f3 f4])

does.

At a bare minimum your code might have different behavior. Your `run! deref` will wait for each future one by one. What if the last one threw an exception while the others are running? You'd probably want the other tasks to get canceled immediately. I'm not sure what Executor.close() does exactly, but in theory it could do this for you automatically. Not something I want to write by hand for sure[1].

> In Go for example, I don't remember having to clean up fibers manually.

And that is awful if you think about it a bit. There's no composition happening, your go block just goes off somewhere without you having any control of it. It's like goto, only it forks first and never gives back the process handle[2].

[1] https://clojureverse.org/t/missionary-new-release-with-strea... [2] https://vorpus.org/blog/notes-on-structured-concurrency-or-g...

Hum, handling the first to error and interrupt the others is a good use case.

From what I read, Loom structured concurency will not automatically interrupt the other tasks though. And the .close I think will wait for all of them to complete. They said it's because you might not always want other tasks to cancel, so they made it more explicit.

But arguably, maybe if you had a catch in there it would be triggered on the first task to throw. But I can also imagine a similar function to wait for the first future to return or error in Clojure. Though I'm guessing at that point one might say that's just implementing structured concurency?

My question maybe was about the need to close virtual threads. Are they just abusing Closeable so you can use .close as a wait for all to complete even when errors are thrown feature, or do you actually leak resources if you don't clean up Virtual Threads you're done using?

I gotta say, as a programmer "of a certain age", a lot of recent advances have an everything-old-is-new-again feel to me. When I first heard of "threads" in the 90s, the term specifically referred to a mechanism for intra-process concurrency that was "lightweight", i.e. it didn't have the heavy overhead of forking a new OS process. IIRC they weren't even preemptively multitasked. Then preemptive "OS threads" became the new hotness and everything using cooperative threads was old and busted. Now a generation has passed and we have "virtual threads" or things like asyncio to solve the problems created by the thing that solved the problems of the thing before.

A similar thing has happened at the OS level with support for multiple programs. Computers started out running one program at a time. Then "multitasking" was invented, and along with it all kinds of things to make it safer and easier like users and permissions and protected memory, and it was great, many different users could run different programs on the same machine. Then we moved from running statically linked binary executables to dynamic linking and interpreted languages that load libraries at run time. Managing environments for different programs on one machine got hard. VMs and hypervisors let us segment a machine into virtual machines where the environments were easy to control. But VMs were a heavyweight solution for managing environments, so along came containers, which are kind of virtual virtual machines.

So now we're in the position where it's perfectly normal to run a program with several virtual threads running in a "real" thread in a Java virtual machine running inside a Docker container running on a VM instance in a hypervisor on some giant box somewhere. And if we're all living in a simulation, then its' probably turtles all the way down.

I don't mean this entirely as a "get off my lawn" rant. I recently re-implemented an io-heavy threaded program using asyncio and I found it genuinely better. It was easier to reason about what was happening and to get our task dependencies to execute in the right order. The code is simpler and I'm pretty happy about it. But I fully expect asyncio and virtual threads to go out of fashion in ten years, and some new preemptive, OS-managed thing will come along and become the new hotness.

ps - I found this quote in the description of Virtual Threads[1]

> Virtual threads are preemptive, not cooperative — they do not have an explicit await operation at scheduling (task-switching) points. Rather, they are preempted when they block on I/O or synchronization.

Sorry, that's not preemption, that's yielding at specific safe points. I.e. cooperative multitasking. For example, Classic MacOS's cooperative multitask didn't have an explicit yield, it yielded automatically when you polled for a new event.

[1] - http://cr.openjdk.java.net/~rpressler/loom/loom/sol1_part1.h...

Reply on news.ycombinator.com