Scala-native: Threading model

[mdedetrich]

Currently Scala-Native is single threaded, ideally we want to support multiple true threads.

Personally I think that Scala-Native should try and mimick the Java threading model as much as possible, its one of the most flexible and high performing threading models (many limitations that come from Java's threading model come from the expressiveness of the language and not necessarily due to the JVM). It also gives the principle of least surprise

If LLVM allows you to implement an even better threading model, than that should be explored. Another option is to use green threads. We should probably explore what other languages do as well

[sjrd]

Personally I think that Scala.js should

I guess you meant Scala Native.

[densh]

Java Threading & Memory Models are designed to make shared mutable memory with explicit locking tolerable. Considering that both of those are considered to be anti-patterns in Scala, just blindly implementing them in Scala Native wouldn't make much sense. On the other hand, we do want some API compatibility story in this space to make it possible to cross-compile between JVM and Native.

[mdedetrich]

I guess you meant Scala Native.

Fixed

Java Threading & Memory Models are designed to make shared mutable memory with explicit locking tolerable. Considering that both of those are considered to be anti-patterns in Scala, just blindly implementing them in Scala Native wouldn't make much sense.

This is pretty much hidden from the end user, due to the use of ThreadPool and ForkJoin pool. Java's memory model is actually fairly low level, which makes it "easier" to implement your own threading/concurrency mechanisms ontop of it

Considering that both of those are considered to be anti-patterns in Scala, just blindly implementing them in Scala Native wouldn't make much sense

Its also the highest performing model for parallelism and as mentioned before, its something thats hidden from the user. Current Scala users don't deal with locks (and we are dealing with the Java model for threading), but if you are making high performing concurrent data structures with a "functional" interface, you need locks and shared memory if you don't want terrible performance

Have a look at the pains that Go is going through, even though their channels are somewhat analogous to green threads, a lot of their stdlib users mutex's/locks/semaphores due to performance reasons.

At least in my opinion, if not having a fairly low level mechanism for threading is somewhat antipattern to the goals of Scala native, which is meant to leverage performance which high level language that we love (Scala). I don't see an issue with using a lower level memory model if the users don't have to deal with its semantics, which in most cases they won't, but we do need such semantics to create high performance concurrent code (whether that be collections or otherwise). Also Scala also uses a lot of internal Java concurrent collections, which are deliberately coded with locks (and whatnot) for performance reasons.

[andreaTP]

I basically agree with @mdedetrich Scala Native should expose the most low level interface to enable cross compatibility with C libraries and let users build on top of it the desired abstraction,
Providing a strong and cosistent concurrency model like Go or Pony does is the road to have it opinionated for the rest of the life of the project.

[densh]

What I was actually implying is that JMM offers way more guarantees than what most people need in Scala, and over-constraints the implementors by limiting optimisations that can be made to satisfy those guarantees. It seems like a total overkill if most people don't even do shared mutable memory that much.

Not only that, the official "blessed" concurrency primitives are too high-level. E.g. there is no way to directly CAS a field or insert a memory fence when you need it unless you use internal JDK APIs like sun.misc.Unsafe (and that's what most concurrency-related libraries in JVM world use under the hood.) We want less guarantees by default, more direct control, so that you can build anything you want on top of it as a library.

[mdedetrich]

We want less guarantees by default, more direct control, so that you can build anything you want on top of it as a library.

Sounds good, however I am unsure as to how green threads fit into this model. Green threads are a pretty high level concept, with implementations that differ amongst different runtimes. They also force a specific programming model.

I guess my general point is that when you have a look at what has happened with other languages that implement green threads, they always end up using locks/semaphores/mutex's with shared memory to implement their own high performant concurrent data structures/libraries. If you want to implement something like a ConcurrentHashMap, you are going to need these features to get any sane performance out of the datastructure. As mentioned before, Go doesn't even use green threads for their own internal libraries, even though its one of their touted concurrency models

[andreaferretti]

Also, consider that the threading model is intertwined to the memory and garbage collection model. For instance, Nim (in default mode) exposes separate garbage collected heaps for each thread, and a shared heap that is manually allocated. This is not ideal for many applications, but has the advantage that GC on one thread will not stop the world for other threads. The JVM offers a single shared heap, and this has consequences on the available GC strategies.

That sais, I agree that the concurrency model should be low level, in order to allow various other concurrency models (parallel collections, actors, STM, CSP, ....) on top of it. But it should be high level enough to:

• abstract over the differences of the underlying OS
• allow a less conservative garbage collector

[mdedetrich]

Also, consider that the threading model is intertwined to the memory and garbage collection model. For instance, Nim (in default mode) exposes separate garbage collected heaps for each thread, and a shared heap that is manually allocated. This is not ideal for many applications, but has the advantage that GC on one thread will not stop the world for other threads.

Indeed this is how nim deals with the "stop the world" issue. And yes its very true that how your GC is designed ties in strongly with your threading model. Its also a good way to deviate from JVM (like providing almost realtime guarantees for garbage collection). Should probably explore that the Azul guys do. Rubinius is meant to do some crazy stuff, so does LuaJit

[mdedetrich]

Also note that Haskell supports real threads and locks, just as it supports green threads. You can read about it here https://wiki.haskell.org/Concurrency

[mdedetrich]

Here is an SO answer about the issues that Rust had in regards to implementing green threads in the language. May not be entirely relevant to Scala Native, but worth looking into

http://stackoverflow.com/questions/29428318/why-did-rust-remove-the-green-threading-model-whats-the-disadvantage

[densh]

@mdedetrich Rust experience is an extremely valuable data point, thanks for sharing. Green threads were expensive for Rust given that they don't need safe-points at the moment due to their ownership-based memory model. We'll need safe-points for a better/safer GC implementation and they can also be re-used to implement green threading with preemption.

[densh]

Related: https://github.com/scala-native/scala-native/issues/189

[sirinath]

Also just pointer OMR has a threading components. Perhaps this can also be explored before finalising.

[schmitch]

Just to drop myself in a bit, shouldn't we also looking for a way to get this work with akka? I mean if scala-native has some kind of akka support (while dropping their java stuff) would be highly appreciated.
So the Threading Model should be somewhat compatible with Akka I guess.

[densh]

Absolutely, running Akka's test suite with minimal modifications would be an ultimate stress test for the model.

[ekrich]

I think it may make sense to implement Thread and ThreadPools via Posix threads to target existing Java and Scala code. This should be available on many platforms and can also support real time thread priorities on RT platforms. Alternative concurrency models may be a better approach but this makes for a good API story.

[nadavwr]

@ekrich I agree that using pthreads makes lots of sense for Scala Native, and that supporting real time priorities can be a appealing (with the same disclaimer regarding alternative concurrency models 😉).

While the JVM is clearly not real time, there are systems that require real time priority scheduling but are tolerant to low-latency garbage collections pauses. I've implemented pthread bindings for the JVM in the past specifically for use with real time threads, for such a system. It's a tuning nightmare, but real time priority scheduling does work. Coming up with a pthreads-based alternative to java.util.Thread was fairly easy. The aspects related to real time priorities were the only real challenges involved—but should be simpler for Scala Native, where there's no JIT and where garbage collection implementation is... negotiable.

I understand recent versions of Boehm GC support multithreaded operation with little-to-no changes to client code, so having a 3rd party binding for pthread could be the easiest way to get some initial thread support.

Beyond that, implementing java.util.Thread and scala.scalanative.runtime.Monitor should be fairly straightforward with pthread mutexes and condition variables, with the huge caveat that code featuring shared mutable state ported from the JVM will be unreliable without a compatible memory model.

Real time thread support will be more complicated so long as GC is implied. It would work—low priority threads will yield the CPU to high priority threads just fine—but arbitrarily long stop-the-world collection pauses mean that a low priority thread can circumspectly stall a higher priority thread simply by generating garbage. Using Boehm GC in serial-and-incremental mode might be enough to get slow-but-deterministic behavior.

If we want Scala Native to have more meaningful support for real time priorities and garbage collection, we need a garbage collector that supports multiple isolated heaps within the same process (allowing e.g. Nim-like memory management as described by @mdedetrich). Unfortunately, Boehm GC only supports a single shared heap. This SO question has some discussion about alternatives to Boehm GC that do support multiple heaps, but at first glance none of them are as elegant as Boehm GC.

[nadavwr]

The need for a concurrency-friendly memory model only arrives when we use multiple cores. If we were to implement pthreads-based java.util.Thread and Monitor, with the additional step of setting thread affinity to core #0, we would be multithreaded-single-core, and all memory-model related synchronization problems go away. This would allow to reliably run any code that would operate correctly on a single-core machine.

Alternative API can be provided to start threads without setting CPU affinity.

[mdedetrich]

The thing is that this model is terrible when you actually do want to use multiple cores on the same machine for a single process instance. As node.js has shown us, unless you only make evented IO apps only being able to use single cores has really bad performance characteristics.

Obviously you can multiplex on all of the different cores, but I would rather implemented multi threading properly. In any case, I believe you can do what you are describing right now with ForkJoinPool on a single core, no?

[nadavwr]

@mdedetrich To clarify, I do not consider a single-core pthreads-based implementation a "model". A proper model would be like you propose—"freestyle" threading combined with a Java-like memory model.

I was merely pointing out a path of least effort of getting partway there, while gaining support of code that relies on java.util.Thread along the way. If and when Scala Native implements a full memory model compatible with the JVM memory model, the only thing to be done is to remove a call to pthread_setaffinity_np() from java.util.Thread implementation.

Regarding ForkJoinPool—code developed with Scala Native in mind has the privilege of picking and choosing a concurrency strategy that doesn't implode on Scala Native. Developers dealing with 3rd party libraries do not have that luxury...

Take the current implementation of the global execution context as an example. It has a bunch of limitations—no support for Await, and—anecdotally—futures only execute once main() is over. This isn't a problem for good clean Scala code, but places an undue burden on people porting existing code to Scala Native. An execution context based on actual threads will simply work (albeit locked to a single core).

[binary132]

Why use pthreads instead of c++ <thread>?

[nadavwr]

@binary132 Well, for one, pthreads provides finer-grained control than C++ threads does. Real time threads are still a pipe dream at this stage, but are one example of something pthreads would support and C++ threads won't. Another advantage is build simplicity—for pthreads you only need Scala code, no C++ bindings needed.

I see that C++ is very much present in Scala Native's native dependencies (e.g. [nativelib/src/main/resources]). @densh can you provide some guidance as to when you might prefer C++ dependencies?

[ekrich]

@nadavwr I sort of see the point of using C as that is the least common denominator. I once played with the Java Realtime Reference Implementation on TimeSys. Had to build your on kernel but it worked pretty good and was easier than writing straight POSIX RT code.

[muxanick]

@nadavwr Can you please elaborate on features with are not supported by c++ threads?
And binding them to scala native doesn't loose any flexibility.
I have Thread and GreenThread classes pre-implemented on top of c++ threads and it works well so far, no need additional libraries, just two small cpp files.

[jbsolomon]

Has there been any further development or discussion on this topic? It is quite important.

I haven't read the whole _thread_ (no pun intended), but I think offering an adaptor -- even if it's not a built-in -- for C++11 std::thread is a decent way to move forward, since C++ is already a native dependency.

[lilac]

As a long time java/scala developer, I think go's concurrency model is much simpler than java's. Also java world has invested a lot to green thread. We should learn from this, and borrow more from the success story of go routine.

[mdedetrich]

@lilac This is kinda unrelated. If scala-native provides lower level abstractions (such as threads) then you can implement whatever you want, including go style co routines.

The main issue with supporting threads is it complicates GC a lot, its a very hard thing to do. This is why the memory model is being debated.

Also most people in Scala program concurrent code using either Future or one of the other IO/Task types. This works in environments where there is only one thread/core (i.e. Scala.js).

[lolgab]

Actually Boehm supports threads very well.
I started the process of making immix/commix aware of threads, But make them even fast isn't easy because you need to minimise locking and contentions.
About the fact of implementing go style green threads on top of Java lang threads, probably you can, but I'm not sure if you can make them context switch fast without having the GC know them.
My personal opinion is that Scala Native should implement what Scala is using on JVM, to allow porting existing Scala libraries as seamless as possible.
When project Loom becomes a thing and people will start to do blocking calls instead of using event loops (Future, etc.) to do concurrency, then Scala Native will be forced to implement some sort of green thread model to be able to reuse Scala libraries.
Until then I'm even fine with a single thread and using fork when I need parallelism :-)
If someone wants to join efforts to continue working on threads, I'm in :)

[mdedetrich]

About the fact of implementing go style green threads on top of Java lang threads, probably you can, but I'm not sure if you can make them context switch fast without having the GC know them.

Of course its possible, you have full control over the GC in Scala Native. Yes its hard, but in general this topic is hard.