Multi-threading

[CeleritasCelery]

There is some discussion of my thoughts on multi-threaded Emacs here. Read that first. This project gives us a unique opportunity to make the interpreter thread safe. I am generally of two minds about how to handle multi-threading.

idea 1 - CSP all the way

CSP or "communicating sequential processes" is the most flexible way to implement parallelism. This is the approach used by languages like go and clojure. You essentially create first-class channels that can be passed around to other threads, and then only communicate through those channels. This let you build a topology of "communicating processes" that can sequence with each other as desired. It is very simple, flexible, and powerful.

However, you run into the issue that this method could not be made backwards compatible with existing GNU Emacs runtime. That runtime has no ability to suspend and resume threads of execution in the way that would be needed to mimic CSP. You could in theory do this with existing Emacs threading API, but is very unstable and will crash your Emacs, so it is not ready to be used. However if the threading library was ever made robust, then you could in theory model CSP in GNU Emacs.

Idea 2 - coroutine style

GNU Emacs supports stackless coroutines (called generators), which allow for basic concurrency. If you limited your multi-threading API, you could have it map to coroutines as a polyfill. This would mean you would not have to write code twice, once for multi-threading, and once for not. I imagine it looking something like this.

(let ((num 0)
      (go (goroutine (lambda (x) (yield (1+ x))))))
  (setq num (resume go num))
  (message "%d" num) ;; prints 1
  (setq num (resume go (+ num 2)))
  (message "%d" num)) ;; prints 4

This would limit thread to only communicating with the thread that spawned them, and only yielding values in the top level function (since Emacs coroutines are stackless). But you would not need an explicit channel type, and it would be easy to create polyfill version of goroutine, yield, and resume so that the same code would work in GNU Emacs and a multi-threaded Emacs. I don't like this solution as well as just using CSP. But maybe the backwards compatibility would be worth it.

why not use async/await for the backend?

I don’t think using Tokio or any other async await platform would be worthwhile. Fundamentally, they don’t offer any feature that you wouldn’t already get with threads. Plus async brings its own problems.

First is that you have to introduce function coloring into codebase. Everything needs to have two versions. Plus async code is messier and harder to reason about. We are not writing a web server, so we don’t need that complexity.

The only real advantage of async is lower resources usage. Green threads take significantly less space compared to system threads. But this is only really a concern when you want thousands of threads or are memory constrained.

The other advantage is that they can switch context a little faster because they pin threads to cores. However I see this as a disadvantage. In tokio you need to tell the runtime upfront if something is going to be compute heavy or IO heavy. But since the threads are in elisp, we can’t know that ahead of time. Many modern CPU’s have both performance cores and efficiency cores. The kernel will try to move compute heavy tasks to the p-cores and IO heavy tasks to the e-cores. But tokio can’t do that because the threads are pinned!

Also async only supports cooperative multitasking, which means a task that doesn’t play by the rules can starve others. But OS threads are preemptive, so that can’t happen.

What should be shared and what should be thread-local?

Things that are going to change only rarely such as functions can be shared between threads. However most other things like variable bindings and properties will be thread local. However to better support integration with existing elisp, thread local types will be copied to a thread as needed. This ensures that users don't have to worry about "is this variable defined in this thread or not", but still protects us from data races and other nasty concurrency bugs.

how to handle variable bindings?

As described in the previous section, the current idea is have variable bindings and symbol properites copied to other threads "on demand". Essentially when a thread first tries to access a variable that it does not have defined locally, it will send a message to the it's parent thread and ask for the current value via a channel. The parent thread will copy send a message back with the value, or message indicating that the variable is undefined. The child thread will wait until it receives a message back before continuing execution.

how to handle errors

When an error occurs in another thread, what do you do? Any channels connected to that thread would become poisoned, and would signal an error if you tried to read from them. But what about threads that don’t communicate with the main thread. Maybe you wanted to delete a file in the background or something. Raising it randomly back to the mail thread seems really disruptive. But it could also be a foot gun if it just silently ignores the error. Maybe it just prints it as s message.

[Alan-Chen99]

async/ await is useless since we dont have two colors. Some sort of executors is still useful for small tasks like fortifying a buffer. One would ideally be able to have two thread local contexts (we wont expose the two contexts to the same function though; alternatively we can give contexts an additional 'id, not sure how much change that is (we are using macros after all))

[CeleritasCelery]

Currently we have one Context per thread. What advantage do you see in having multiple per thread?

[Alan-Chen99]

async/ await is useless since we dont have two colors

actually I would like to take this statement back. Tramp says otherwise.

Apart from that, a lot of processing can benefit from a clean context. Take processing LSP returns for example; Its lots of cons cell that will just be immediately freed. A lot of processing have this pattern, it's mostly "pure".

I imagine this as we would provide an interface to run a function with arguments on another thread. The arguments would be cloned. The result of the function would be cloned back to the main thread, and it would call a callback. The user will have to specify the color. With this variables won't be shared at all (I don't think it makes sense to). It might be worthwhile to provide channels and shared buffer primitives similar to js webworkers.

I don't think "But since the threads are in elisp, we can’t know that ahead of time" is a valid argument. Take https://github.com/progfolio/elpaca for example; Elpaca pretty much rolls its own event loop with subprocesses. It would be nice if packages don't need to have custom logic to handle async

[CeleritasCelery]

I don't think "But since the threads are in elisp, we can’t know that ahead of time" is a valid argument.

That is specifically referring to tokio. It expects you to set if a task is compute heavy or IO heavy before it is run. But we can't really know that for an elisp task unless we expose that choice to the end user.

[Alan-Chen99]

This is already exposed to the end user: they must make sure to use https://github.com/jwiegley/emacs-async for compute heavy and timer.el (or something that wraps that) for IO heavy. I linked elpaca as an example, since it needs to do both and imo with tokio as backend this can be much cleaner.

imo we should give elisp the power to choose, not deciding anything for them.

[CeleritasCelery]

imo we should give elisp the power to choose, not deciding anything for them.

it doesn't have to be a choice between giving them the power to chose and deciding for them. You only have that dichotomy with async/await. If you instead use native threads then you can let the OS move the task automatically to p-cores or e-cores depending on the workload. You can't do with async (at least with Tokio) because of core-pinning. That is one of the reasons I think native threads are better.

[gagbo]

That is one of the reasons I think native threads are better.

You’re saying that you do not want to use Tokio’s green threads to build the multiple threads that can be created in Emacs right? This means you want to spawn an OS thread for each call to (go ...) in elisp? I’m afraid that could blow up if librairies start to spawn hundreds of coroutines. From the current code I assume it’s the current choice

An alternative to keep the code somewhat simple would be to create another variant of go, let’s say go-io (naming is hard), which would do the same thing but run the task in a work-stealing threadpool to try to minimize the OS resources that get created? Assuming most concurrency/parallelism demand will come from IO-bound processes, I think it would be nice to limit its resource usage this way.

(I am yet to read the clojure core.async and the Go page linked in the issue, I’ll do that soon)

One other thing that I don’t understand yet: if we copy the variable bindings when creating a thread, and that go expression doesn’t return anything, how can we communicate between the parent and child elisp threads? Disallowing mutable shared state makes sense to make the code easier to understand, so should go return some kind of internal channel object that could be polled/awaited? I guess that’s what clojure does and what you’d like to do too?

I’d like to write a little more rust, and since I’m really not advancing too much on my r7rs scheme right now, if I can help a bit here I’d be really happy to

[gagbo]

Another non-obvious thing if we’re using channels: how to deal with lifetimes since we’re managing the runtime ourselves? It is going to be a bit rambly, and I’m sorry for that, I can answer any questions/edit things until it’s clearer. The intention here is to explore a possible implementation of CSP-based multi-threading, adding first-class channels as the extension that backs go.

We want a channel to potentially hold data from 2 different contexts: the sender thread’s, and the receiver thread’s. From this, I have a few observations/questions:

• The channel can prevent garbage collection on 2 contexts just by existing? I assume that internally, a channel needs to be &'receiver_ob GcHeap<Option<Object<'sender_ob>>> on the receiver side, and that it will have consequences on trying notably to cleanup 'sender context? The channel also needs a way to communicate that there is no data left to be received
• If the channel links 2 different threads, receiving items from the channel requires copying the data between threads. This copy operation is not necessary if the channel is within a single thread. But we do not have go spawning closures in the same thread ever; so we will always copy, and it will always be necessary.

So from this, I think that communicating through channels would have extra implementation details to figure out:

• A channel needs to hold references when copied: if go argument captures a channel that’s being created in the parent scope, we need to make sure the channel actually communicates with the parent channel right?
• multi-producer channels: if all objects are lifetime-invariant, how would we have multiple producer threads send data to the same channel? Same thing with multi-consumer/work-stealing channels I assume

I think the solution to all this would be to have channels live as global objects (that also hold onto Object<'static> when they hold data to give to consumers), but I don’t know the implications for the current implementation of Object

[CeleritasCelery]

I’m afraid that could blow up if librairies start to spawn hundreds of coroutines

potentially. But a modern OS can support hundreds of threads, so I don't think this will be an issue in practice. I can't think of scenario where it would realistically be useful to spawn hundreds of coroutines in Emacs. Unless you are trying to use Emacs as a different type of program (say, a web server).

if we copy the variable bindings when creating a thread, and that go expression doesn’t return anything, how can we communicate between the parent and child elisp threads?

The way Go and Clojure do it is by having you pass in channel objects to the coroutine that needs to communicate back. But we could also create a default channel that doesn't need to be explicit. As you said, an internal channel object.

Another non-obvious thing if we’re using channels: how to deal with lifetimes since we’re managing the runtime ourselves?

The idea is that each coroutine has own all it's data and can run GC when it wants. Anytime we send something over a channel it will be copied. Yes, this adds some overhead for copying, but it makes the implementation much simpler. If we know something is not going to be used anymore by a coroutine (e.g. It is terminating), then we don't need to copy and can just give the allocated blocks to the other coroutine and it now owns them.

I’d like to write a little more rust, and since I’m really not advancing too much on my r7rs scheme right now, if I can help a bit here I’d be really happy to

Would love you help! I have not had much time to work on this recently, but still interested in pursuing the design.