<< Previous Next >>

Initial ideas for the threading model

The main idea behind the threading model in Storm is to highlight which threads are used to execute certain pieces of code. This idea comes from my experience when writing threaded applications using the traditional threading model without specific language support. Eventually you are going to have a hard time figuring out which code is reachable from each thread, and therefore you are not sure what you have to lock when you for one reason or another introduce some kind of cache in some commonly used type later on.

I think this difficulty stems from that "classic" languages like C/C++ and Java lacks a built-in understanding of threads, and is therefore unable to help the programmer using threads safely. Put this in contrast to, for example, the type system present in these languages. The type system knows how your different objects look like in the memory, keeps track of what memory is of which type and tells you when you are doing a mistake. This means that you will never get unpredictable results by accidentally mixing up two different and incompatible types. Instead the language will detect this mistake and report an error. This is not the case when using threads.

When using threads, you need to be careful to keep track of any shared data between the threads in order to avoid a possible race-condition. Aside from that, you need to be careful about causing deadlocks when using locks and similar mechanisms. Therefore, there is a lot to keep track of when using threads. However, the language does not provide the programmer much or any help in keeping track of this information, and the language can therefore generally not provide much help in detecting potential threading issues in the code.

My idea is to teach the compiler about threads and integrate it into the language by introducing named threads, much like named types into the language. For example, you might define two threads thread UI; thread Worker; for your UI application to easily be able to offload heavy work onto a separate thread for background work. The benefit of named threads is that you can define certain objects, functions and variables as belonging to a certain thread, for example like this:

class Foo on UI { ... };
void bar() on Worker { };

What this means is that the language will make sure that any code or variable accesses inside the Foo class will be executed on the UI thread. The same holds for the bar function. If a function or a class is not marked with a thread, that function or class will be executed on the calling thread. My hope is that this will provide the programmer with enough information about which thread is going to run the specified code, as well ass making inter-thread communication easier by integrating it into the language. Just calling a function declared to be exectued on another thread will be automatically dispatched to that thread.

This means that each thread will have a main message-loop and a mailbox for incoming messages, much like in the Actor model. Calling functions across threads will simply cause the language to send a message to the target thread and (possibly) wait for a response. We still have a small issue with the objects not marked as belonging to a thread though. Imagine code on thread UI calls some code on thread Worker, passing an object O to Worker. Since Storm will manage at least some object by reference (like Java does to all user-defined types), both the UI and the Worker thread now has access to the same memory of object O. Since O does not enforce execution on a specific thread, both the UI and the Worker thread could access the object at the same time, which could cause race-conditions and other unpleasant suprises that we wanted to avoid in the first place. My idea to solve this kind of problems is to always do a deep- copy of objects when they are passed between threads, effectively giving each thread its own heap of objects. Objects assigned to a thread are the exception to this rule, as they will enforce execution on another thread anyway. As long as the language provides a good default ways of copying objects as required, this will not be an issue to the programmer. Since inter-thread calls are more expensive, it might be a good idea to make them different syntactically from regular calls.

What about deadlocks? This depends on how function calls across threads are implemented. Functions without return values are trivial, just send the message to the other thread and keep working. Any subsequent calls to the thread will be ordered anyway and we avoid deadlocks when the other thread may call this thread again. The tricky part is with functions that returns a value. One idea would be making them return future objects, that do not have a value until they are actually used. Another would be to use callbacks. What I want to accomplish is, however, something similar to "regular" single threaded programming, without complex concepts and lots of callbacks. This would mean that the calling thread would be blocked until the call has completed. The problem is that just blocking can potentially cause deadlocks, and kind of defeats the multithreading in the first place (everything will be executed serially anyway). My idea for a solution to this problem is to allow the blocked thread to keep on processing messages during the time is is blocked. This could cause some confusion with the programmer, since during a regular function call, something entirely different may happen, which at first seems strange. However, you could argue that the same things could happen in single-threaded applications as well when the called function may call some function in the calling object again. This is also something that speaks to some special calling syntax for inter-thread calls.

Sometime some form of mechanism to examine another thread's message queue is required. For example, it might be interesting to see if the thread could accept my call directly, or how many calls are waiting for processing. These are nothing that I have worked out at this stage yet, this requires some more research, as with the rest of the threading model!

Aside from only managing named threads, this will most likely be extended to support specifying the owning thread at creation time as well, to allow for more complex behaviours to be implemented. Also note that this is still initial ideas of the main features of the threading model, and it will most likely change later on.

Comments

Alex Telon

2014-10-19 22:04 (UTC)

Named threads sounds interesting and fun! I really like the whole idea you are describing and the whole thing got me thinking!

First of, will the threads be kernel or user threads? If one or the other, would it be a good idea to have different types of threads so that the user can force it to be of one type or another?

Would it be possible/feasible for you to have threads work like a class (a bit like Java does it)? So bascially there would this one baseclass (basethread) called Thread which you can use right from the box. But you could also create your subthreads that inherit from Thread. Lets say you want to work on a RTS on a single CPU core and really want to be able to give the threads different priorities. The baseclass, Thread, would maybe have priority of say 5, but subclasses could have a higher/lower value to allow for different types of threads where some will preempt some others automagically! :)

Maybe you could then put in some of the default behaviours that you have talked about in the baseclass like deep-copy and stuff which could then be overriden by subclasses if thats what the programmer wants. Same thing with the message-loop and the mailbox, if these are just part of the baseclass then these too could be overridden by the user.

Other uses could for example be custom thread pooling management in different thread types or

Custom thread restrictions. Meaning that if

nonReturnThread Worker;

void bar() on Worker { ... }; // ok!

int foo() on Worker { ... }; // not-ok!

Where nonReturnThread is a type of thread that cannot be used on classes with a return type. Or:

functionalThread FunctionalThread;

int add(x,y) on FunctionalThread { ... }; // ok!

int addToScore(x) on FunctionalThread { ... }; // not-ok!

where functionalThread is a type of thread that only work if add() does not have any instance variables. What I think Im meaning with that is that add() cannot have its own internal variables that are initialized internally but is rather functional in that it only processes what it gets in and always returns the same thing given the same parameters. With this kinds restriction on the classes/methods that can use the thread one could for example skip certain difficult parts of concurrency handling in some threads since the classes/methods using them are guaranteed to have certain properties.

Anyways, the examples are not of importance but the general idea Im trying to explain is what I am trying to get at. But maybe this already is something that exists in many languages and I in my ignorance have just missed this?

btw:

"to accomplis is" <-- spelling

Filip Strömbäck

2014-10-20 13:18 (UTC)

Much of the design decisions for the threading model comes from my bad experiences when working with threading in UI, and therefore much of the design is based on you having a handful of threads (therefore the decision to name them) which need really simple communication in between them. Therefore my idea is to use kernel threads for the named threads, at least until I realize that it is not enough. This idea is also reflected in the decision to not require all objects to be bound to threads, like in other implementations of the Actor model, where it seems that each object has its own thread. Allowing objects without threads also gives the programmer a bit more power to choose what is to be threaded and what not (I do not yet know if this is good or bad).

I have not yet settled on exactly how to implement the thread object. Probably it will be some kind of type in the system, however I am not yet sure if it should be possible to extend it in the ways you describe. To ensure thread-safety in the language I will at least need to ensure that a thread is not represented by more than one object. The other way around would be fine, but completely useless since the language would then enforce so that only one of the threads would be active at any given time, effectively merging them into one thread. This makes the thread-class fairly boring to extend.

Instead I have ideas of supporting some interface that will "generate" threads. For example, it may be possible to implement a thread pool as not an extension of a Thread type, but instead as an extension to some ThreadProvider interface. At creation time, the language will then ask the ThreadProvider for a suitable thread and then assign the object to that thread. The downside of this is that once objects are assigned to threads, they are stuck there, even if the load is later found to be uneven. If objects are allowed to change threads, then my assumption about shared data is violated instead, which might be really bad. This stems from the idea that if two objects happen to be on the same thread, they will share data. Maybe the data should always be copied to objects assigned to threads, even if they happen to be assigned to the same thread in order to make it easier to reason about what will actually happen in more complex cases where threads are dynamically assigned. In that case it would not be any problem to let objects be run on any thread in a thread pool for example.

It would be nice to allow users to modify the main message loop, in my current idea the message loop plays an important role in the system for dynamic code reloading and replacing. One assumption of this system is that all threads will eventually return to the main loop, and at that point we know that we will not have any dynamically generated functions on the stack (we will not return into generated code). This is important because this is the point where we can actually safely delete old code. Otherwise we can not be entirely sure no thread will return into some old code. It is possible to track otherwise, and I will probably do that at a later stage. Another possible issue is that the message dispatch logic might not be expressible in the language. This minor issue can of course be solved by making the language better! A third point about the message loop is that the message loop is where the user-mode code is interacting with the rest of the compiler, and it has to be right. Therefore I do not think I will allow complete re-writing of the message loop in user-mode code. It should still be extensible somehow, but you will probably not write the while (true) yourself. I think I need that to be in the compiler to be able to let the compiler evolve without bothering too much about old extensions to the message loop.

It is an interesting idea about stateless threads. Since my idea about global variables is to make them thread-local, this would correspond to disallowing thread-local variables for some thread. Interesting idea, which might be useful!

Thanks for your thoughts! It is really good to get other views on useful features. As I mentioned earlier, this is by no means final yet!

Alex Telon

2014-10-20 18:48 (UTC)

Okey, sounds good! Using the Actor model fully so that every object has its own thread would force lots of OO people to rethink a bit and could be an issue. But I duno, if the model really is great then maybe the right move is to go all in here.

<blockquote>"To ensure thread-safety in the language I will at least need to ensure that a thread is not represented by more than one object."</blockquote>

So, basically normal inheritance wont work since if we run something along these lines:

thread Parent implements Thread {

...

}; // Parent is a Thread

thread Child extends Parent; // Child is a subThread of Parent```

Then there would be one thread that could be represented by both Child and Parent? Did I understand the issue correctly?

<blockquote>"The other way around would be fine, but completely useless since the language would then enforce so that only one of the threads would be active at any given time, effectively merging them into one thread. This makes the thread-class fairly boring to extend."</blockquote>

The other way would for example be having two objects having two differently named threads but they sublcass a common thread?

I could se a potential use for this if I am working with a RTS problem (gonna have a course in that soon). Lets say I have a family of threads that have different priorities that SHOULD not run at the same time but should always preempt eachother if they are running at the same time. This could be achived for example buy subclassing a thread so that I know for sure that no matter how many cores I have in my hardware two classes using any thread from my family of classes will never run at the same time.

This is ofcource solvable otherwise but It might be good for that reason.

The ThreadProvider interface idea sounds interesting.

Not being able to change the message loop should not be a problem, esp since you really have good reasons not to make that public. The biggest reason being that you can change the default behaviour later on.

Alex Telon

2014-10-20 18:51 (UTC)

Have you implemented the GitHub mardown yourself or using some library? I was testing my text above on two seperate online github markdown preview sites and it worked there. It seems that ``` did not count when it was in a outcommented codeline here.. Below is a repost that hopefully is more readable

<blockquote>"To ensure thread-safety in the language I will at least need to ensure that a thread is not represented by more than one object."</blockquote>

So, basically normal inheritance wont work since if we run something along these lines:

thread Parent implements Thread {

...

}; // Parent is a Thread

thread Child extends Parent; // Child is a subThread of Parent

Then there would be one thread that could be represented by both Child and Parent? Did I understand the issue correctly?

The other way would for example be having two objects having two differently named threads but they sublcass a common thread?

This is ofcource solvable otherwise but It might be good for that reason.

The ThreadProvider interface idea sounds interesting.

Alex Telon

2014-10-20 18:55 (UTC)

Bah, okey no inline html either.

A way to delete/edit posts would be nice. Maybe let the IP that wrote the comment be able to edit within a 30min frame. That or letting us see a preview would be great which seems easier :)

Keep up the good work!

Filip Strömbäck

2014-10-21 00:17 (UTC)

I am using a library called Parsedown, which seems to implement almost all features of GitHub markdown. For example, it seems like it implements the "choose language" by ignoring it at the moment. I also agree to your idea that preview is a good idea, and have added it now.

Btw, ask Behnam why it is a bad idea to allow arbitrary HTML in comments :) Editing posts is also something that requires more bookkeeping, possibly in the form of user accounts. Aside from that, I store comments in text-files which are not too fun to edit from PHP afterwards :) Who needs a database when you have a filesystem?

What I mean by disallowing two objects to represent the same thread, I mean that two instances of these classes should always represent two different threads. Subclassing does not make a difference here, since I will still only have one object if I instantiate a subclass. Think of it like this: I want to be able to compare thread objects with the ==-operator in java, and if it returns true, it is the same thread.

The confusing part might be that I see the named threads as instances of object, rather than just referring a type. So wherever you declare your threads, you actually create an instance of some Thread-object or something like that, then you can assign these instances to objects with syntax. I just realized that the naming convention suggests otherwise :)

With this implementation the scenario you are describing is sadly not possible. However, if there is also support for lightweight threads or coroutines. Then maybe you would be able to do like this:

coroutine Foo on Worker;

class Bar on Foo ...

This is an interesting idea suggested by Göran Rydqvist, but it would maybe require the programmer to manually choose where to preempt the running thread.

I've been thinking a bit more about whether or not to make it possible for objects to switch thread or not, and realized that I will have a somewhat similar problem later on anyway, since the user may change threads of an object later on through live updates anyway. Therefore it might be a good idea to always copy parameters when calling threaded objects and then simply allow somewhat more sophisticated thread objects, for example thread pools which then dynamically dispatch incoming messages to whichever thread happens to be running. Maybe combine this by having another but similar syntax for calling threaded objects and functions (for example foo->bar()) to indicate that it might be a bad idea to send huge objects as parameters to that function.

Alex Telon

2014-10-21 18:42 (UTC)

Great, the preview will do fine. I agree who needs a database anyways?

But seriously though, regarding html. A subset of html could be implemented safely I believe. The link below shows an official(?) allowed subset https://github.com/github/markup/tree/master#html-sanitization

So in the following code Bar and Foo are running on seperate threads?

class Foo on Worker;

class Bar on Worker;

If that is the case then yes its sadly a bit confusing.

Yes, I guess coroutines could solve the same problem. Though having to do the preempting seems to be a tad more work than simply give the coroutines priorities and trust that if several are ready (to execute) they will be given the proper order. But thats not important, I just thought of a reason to why doing that could be of interest.

Yeah that seems like a good reason to always copy parameters between threads.

About the syntax: foo->bar() I would only be required to use this when there is ambiguity I assume? I must say that having Foo->bar() and class Bar on Foo is confusing since I assume one Foo is a variable and that the other is not. :P

Will a function be able to pass which thread its running on as a parameter to another class? Otherwise calling back would be difficult? What about dynamic and/or anonymous thread assigment, would that be possible? (or is that just dumb?)

Its really difficult to reason about a language that does not exist in contexts which you never have dealt with! :P

Filip Strömbäck

2014-10-22 08:56 (UTC)

Yes, a subset of HTML could definitely be implemented safely, but then I need to hack something together instead of using the built-in features in PHP to escape all html :) But, yes it would be nice sometimes. I'm just too lazy!

Regarding your example: assuming we allow some more sophisticated thread subtyping (or ThreadProvider) it depends. The idea is that if Worker represents a single thread, then the language will always make sure we're running on that thread. If Worker instead refers to a thread-pool, then the language makes sure your code is executed on one of the threads in the pool.

The idea of priorities for coroutines is interesting, since the arrival of new messages provides a good point for the language runtime to switch thread if neccessary. In that case the yield statements could be used to allow any lower-priority tasks to run even if you are more prioritized. The pre-emption in coroutines could be a little problematic, since I have no idea about what happens if we happen to switch while inside a system call or something like that... It could be done by letting the compiler emit code to regularly check for new messages of higher priority, but I do not know if this is good since all code will have to pay a performance penalty in this case.

My idea about the different syntax is something like this: Since calls to a different thread have slightly different semantics than regular function calls (for example, by-value parameters instead of by-reference), it might be a good idea to indicate this difference by making those calls clearly visible in the source code as well. That is about what it is to it. I understand the confusion, I have not yet thought about exactly how the threads are going to act in the language, and as a start I simply thought of them like named types, much like classes. However, it does seem convenient to be able to use the thread objects just like any other object as well, but my old naming convention stuck :) That also needs some work! I am starting to realize the number of design decisions you have to make when doing something like this. Everything has implications, and you need to understand what it means, or at least try it out a little before you can make a good decision!

The idea with everything is that you should not have to think about threads, so when calling a function (even through a function pointer or an interface) the language will make sure it runs the code on the correct thread, even though the actual call may be invoked from another thread. This is why I want the inter-thread calls to be as close in syntax and semantics to regular function calls as possible! But yes, it should be possible to get "your" thread, as well as to tell newly created objects to run on the same thread as well.

Right now I am actually considering what happens if you skip the named threads altogether, and just mark specific objects as threaded objects. The system will then allocate some processing resource to those objects and the programmer will be happy (hopefully). This means that the runtime could then just allocate a thread pool of its own and run the code as it sees fit. This is actually not too far from the idea that we treat all threaded objects as a potentially different thread (by copying parameters). This needs more exploration!

Alex Telon

2014-10-22 09:16 (UTC)

Yes, dont implement it yourself, its not an important feature. :P

Yes, everything has its implications. When working on our tiny addition to the Processing.js language in our live coding project I realized that too. EVERYTHING is important and you have to have a clear idea of what and why you are doing what you do. And then always reflect on those (what/why) ideas when you are designing. And that was just and addition of a tool to add code through code, not a language in itself ;)

I agree that its important to somehow distinguish between what will be normal by-reference and by-value calls.

Now I have to get back to my screencast assignment.

New comment

You can use GitHub flavored markdown here. Parsed by Parsedown, which does not support all of GitHub's features. For example, specifying the language of code listings is not supported.