Threading in Storm

This tutorial explores the threading model in Storm. In contrast to most other languages, Storm is aware of the different threads in a program and is able to use this information to ensure that no data races are possible.

The code presented in this tutorial is available in the directory root/tutorials/threads in the Storm release. You can run it by typing tutorials:threads:main in the Basic Storm interactive top-loop.

Setup

Before starting to write code, we need somewhere to work. For this tutorial, it is enough to create a file with the extension .bs somewhere on your system. The tutorial uses the name threads.bs, but any name that contains only letters will work. As a starting point, add the following code to the file: 

void main() {
}

After doing this, open a terminal and change to the directory where you created the file. Then run it by typing: 

storm threads.bs

Note that based on how you have installed Storm, you might need to modify the command-line slightly. Also, if you named your file something different than types.bs, you need to modify the name in the command accordingly.

If done correctly, Storm will find your file, notice that it contains a main function and execute it. Since the main function does not yet do anything, Storm will immediately exit without printing anything.

Running Code Concurrently

One of the main benefits of multithreading is the ability to multiple things at the same time. In Basic Storm, this can be achieved using the spawn keyword. To illustrate this, let's start by defining a function that iteratively computes the sum of the first n integers. As a starting point we artificially slow down the process by calling sleep and print the progress: 

Nat computeSum(Nat n, Str progressText) {
    Nat sum = 0;
    for (Nat i = 1; i <= n; i++) {
        sum += i;
        print("${progressText}: at ${i}, sum ${sum}");
        sleep(1 s);
    }
    return sum;
}

We can then call the function inside main as follows to compute the sum of the first 3 integers: 

void main() {
    Nat sum3 = computeSum(3, "To 3");
    print("Sum of 1 to 3 is: ${sum3}");
}

This produces the following output as we would expect: 

To 3: at 1, sum 1
To 3: at 2, sum 3
To 3: at 3, sum 6
Sum of 1 to 3 is: 6

If we would also like to compute the sum of the first 5 integers, we could do that by calling computeSum once more: 

void main() {
    Nat sum3 = computeSum(3, "To 3");
    Nat sum5 = computeSum(5, "To 5");
    print("Sum of 1 to 3 is: ${sum3}");
    print("Sum of 1 to 5 is: ${sum5}");
}

As we would expect, this causes the computations to be performed sequentially and we get the following output: 

To 3: at 1, sum 1
To 3: at 2, sum 3
To 3: at 3, sum 6
To 5: at 1, sum 1
To 5: at 2, sum 3
To 5: at 3, sum 6
To 5: at 4, sum 10
To 5: at 5, sum 15
Sum of 1 to 3 is: 6
Sum of 1 to 5 is: 15

However, since the two calls to computeSum are independent of each other, we could perform them concurrently. In Basic Storm, we can do this by adding the keyword spawn before a function call. This causes the function to be called asynchronously, and as such the expression evaluates to Future<T> instead of just T. For example, if we wish to execute the first call to computeSum asynchronously, we can modify the main function as follows: 

void main() {
    Future<Nat> sum3 = spawn computeSum(3, "To 3");
    Nat sum5 = computeSum(5, "To 5");
    print("Sum of 1 to 3 is: ${sum3.result}");
    print("Sum of 1 to 5 is: ${sum5}");
}

From the code above, we can clearly see that the spawn keyword causes the function call to return Future<Nat> instead of just Nat. The Future object therefore represents the fact that a value of type Nat will be produced at some point in the future, but that it might not be ready yet. The Future type has a member function result that can be called to extract the result. If the result is not yet available, the result function waits for the result to be produced. The code above is therefore safe even if computing the sum of the first 3 integers were to take longer than the computation of the first 5, or if we wished to use spawn for both calls to computeSum.

Furthermore, by running the program we find that it completes much quicker than before. We can also see that execution of the two calls to computeSum were executed concurrently by looking at the order of the printed lines from computeSum: 

To 5: at 1, sum 1
To 3: at 1, sum 1
To 3: at 2, sum 3
To 5: at 2, sum 3
To 3: at 3, sum 6
To 5: at 3, sum 6
To 5: at 4, sum 10
To 5: at 5, sum 15
Sum of 1 to 3 is: 6
Sum of 1 to 5 is: 15

It is worth nothing that while the output for this particular example tends to be the same each time, the order in which the lines appear are actually non-deterministic. The lines may therefore appear in a different order when you run the program.

In some cases it is useful to start a thread to take care of some task, even though we are not interested in the result produced by the spawned function. For example, if we were only interested in the print statements from computeSum above, we could simply use spawn to start the thread, but then call detach instead of result to indicate that we are not interested in the result. Calling detach is technically optional, but doing so makes Storm output any uncaugh exceptions in the spawned thread immediately, rather than waiting for another thread to call result. Since compilation errors are exceptions in Storm, not calling detach in such cases could mean that compilation errors are not visible until much later. This typically makes it quite difficult to debug such programs properly.

For example, if the result from the spawn expression is stored in a variable (or used in any other way), we can call detach as follows: 

var x = spawn computeSum(3, "To 3");
x.detach();

As a special case, if spawn appears as a statement where the result is not used or returned, then the system will automatically call detach as a convenience. As such, the following two lines are equivalent in many situations: 

spawn computeSum(3, "To 3");
(spawn computeSum(3, "To 3")).detach();

Multiple Threads

Storm implements two kinds of threads: OS threads and user threads. The first kind, OS threads, are threads that are scheduled by the operating system. Different OS threads may therefore run on different physical CPU cores. User threads on the other hand are implemented inside Storm (i.e. in userspace). They are therefore invisible to the operating system, and the operating system may not schedule them on different cores.

All user threads belong to a specific OS thread. All user threads that belong to the same OS thread are scheduled in a cooperative fashion. This means that a user thread will be executed until a point where it explicitly allows other threads to run. This is nice since it makes it easier to reason about where threads may be interrupted, but it needs some care with long-running tasks.

In the example above, spawn will create different user threads on the same OS thread. As such, they are scheduled cooperatively on the same OS thread, and are not able to execute in parallel on multiple cores. The reason the above example works well is that the call to sleep (and actually also print) lets other user threads run if necessary.

To illustrate the implications of this, let's implement a simple recursive fibonacci function and measure its execution time. We intentionally use a slow implementation to make it easier to see when we utilize multiple physical cores or not: 

Word fibonacci(Nat n) {
    if (n < 2)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

void main() {
    Moment start;
    Word value = fibonacci(40);
    Moment end;
    print("Computed fibonacci(40)=${value} in ${end - start}");
}

In the example we use the Moment class to measure execution time. As the name implies, a Moment reprents a moment in time. The Moment is initialized to the current time in a high-resolution system specific clock. We then compute the difference between two Moments to get a Duration that we print.

It is also worth noting that we make fibonacci return a Word, which is a 64-bit unsigned integer. This is to avoid overflows for a bit longer than just using a Nat.

The execution time will of course vary depending on the speed of your computer. The output on my machine is the following: 

Computed fibonacci(40)=102334155 in 2.10 s

Let's try to compute both fibonacci(40) and fibonacci(41). Of course, we can do it sequentially as follows: 

void main() {
    Moment start;
    Word value1 = fibonacci(40);
    Moment middle;
    Word value2 = fibonacci(41);
    Moment end;
    print("Computed fibonacci(40)=${value1} in ${middle - start}");
    print("Computed fibonacci(41)=${value2} in ${end - middle}");
    print("Total time: ${end - start}");
}

This produces output similar to below. Again, the times are likely to be different on your machine: 

Computed fibonacci(40)=102334155 in 2.10 s
Computed fibonacci(41)=165580141 in 3.40 s
Total time: 5.49 s

Since the two calls to fibonacci are independent of each other, we can execute them in parallell with the spawn keyword. Hopefully this allows the computation to finish quicker! 

void main() {
    Moment start;
    Future<Word> value1 = spawn fibonacci(40);
    Future<Word> value2 = spawn fibonacci(41);
    print("Finished fibonacci(40)=${value1.result}");
    print("Finished fibonacci(41)=${value2.result}");
    Moment end;
    print("Total time: ${end - start}");
}

Interestingly, the program above does not execute quicker than the sequential program. Why did we not se any speedup?

The reason is that the threads started by spawn start on the same user thread by default. This means that the two calls to fibonacci are sceduled cooperatively on a single OS thread. Since only OS threads are visible to the operating system, the operating system is unable to schedule the user threads on different cores. In our case, one call to fibonacci will simply run before the other, just as in the sequential example. As such, different user threads on the same OS thread are good for concurrent execution of different tasks that are not CPU bound. To achieve parallel execution, we need to create the user threads on different OS threads. There is a cost associated with this, which is why it is not done by default.

In Basic Storm, we can declare OS threads using the thread keyword as follows: 

thread FibA;
thread FibB;

We can then instruct the system that certain functions need to be executed by a particular thread using the on keyword: 

Word fibonacciA(Nat n) on FibA {
    return fibonacci(n);
}

Word fibonacciB(Nat n) on FibB {
    return fibonacci(n);
}

This means that the system will ensure that fibonacciA is always executed on the thread named FibA, and that fibonacciB is always executed on the thread named FibB. We can of course still call the functions normally as follows: 

void main() {
    Word value1 = fibonacciA(40);
    Word value2 = fibonacciB(41);
    // ...
}

This is, however, not very useful for us. While the system ensures that the different threads are used, the program above would first start the computation of fibonacciA on the FibA thread, then wait for the computation to complete before starting to compute fibonacciB. As such, the above is equivalent to: 

void main() {
    Word value1 = (spawn fibonacciA(40)).result();
    Word value2 = (spawn fibonacciB(41)).result();
    // ...
}

This is not what we want, since our goal is to execute the two functions in parallel. With this setup we can, however, go back to our previous idea of using spawn: 

void main() {
    Moment start;
    Future<Word> value1 = spawn fibonacciA(40);
    Future<Word> value2 = spawn fibonacciB(41);
    print("Finished fibonacci(40)=${value1.result}");
    print("Finished fibonacci(41)=${value2.result}");
    Moment end;
    print("Total time: ${end - start}");
}

If we run the program now, we can see that it finishes in around 3.4 seconds instead of almost 6 seconds. This means that we have managed to execute the compuations in parallel at last!

Sharing Data Between OS Threads

Now that we know how to execute code in parallel, let's explore how Storm makes parallel programming safe. Remember that Storm guarantees that data races are not possible. However, the following program looks like it would violate that principle: 

thread MyThread;

class Data {
    Nat value;
}

void modifyData(Data toModify) on MyThread {
    toModify.value = 10;
}

void main() {
    Data data;
    Future<void> modify = spawn modifyData(data);
    data.value = 20;
    modify.result(); // To wait for 'modifyData' to finish.
    print("After modifications: ${toModify.value}");
}

Remember that class types have reference semantics. We would therefore expect that main and modifyData would have access to the same instance of Data. Since they execute in parallel, this would constitute a data race.

However, if we run the program we will see that it always prints 20. If we remove the assignment data.value = 20 in main, we will further see that the program always prints 0, even though we ensure that modifyData has finished execution before printing the modified value. This seems strange!

The reason for the behavior above is that Storm enforces that value- and class-types are not shared between different OS threads, since that would risk creating data races. This means that Storm needs to copy data that may be passed between two thread. This decision is generally made statically. In this case, the function main is not associated with a OS thread, so it may run on any thread in the system. Since the call to modifyData has to run on the thread MyThread, Storm inserts code to send a message to the appropriate thread. As a part of that process, it also makes a deep copy of any value- and class-types passed to and from the function. We can observe this behavior by defining a copy-constructor in our class: 

class Data {
    Nat value;

    // We need to define the default constructor explicitly, since it will
    // no longer be generated by default when we define another constructor.
    init() {}

    // The copy constructor.
    init(Data other) {
        init { value = other.value; }
        print("Copied data!");
    }
}

If we run the program again, we will see that the string Copied data! is printed once, when we call modifyData. This is why the changes to Data is not visible in the main function as we initially expected.

This behavior can be summarized as: class-types have by-value semantics when they are passed across a thread boundary. This is the reason why the == operator and hash tables compare the contents of the class rather than using the identity of the object. The identity of the object might change when objects cross a thread boundary.

To illustrate this, let's modify the modifyData function to actually return the Data instance as well: 

Data modifyData(Data toModify) on MyThread {
    toModify.value = 10;
    return toModify;
}

We can then inspect the behavior more closely in our main function: 

void main() {
    Data data;
    Future<Data> modify = spawn modifyData(data);
    data.value = 20;
    Data modified = modify.result();
    print("After modifications: ${data.value}");
    print("Returned object: ${modified.value}");
    print("Are they the same? ${data is modified}");
}

At this point, we can observe that the copy constructor is called twice: once when the Data instance in the main function is passed to modifyData, and then again when the instance is returned back to main. The instance returned from modifyData has indeed been modified to contain 10 as we would expect. Finally, we can also see that data and modified do not refer to the same object, which would be the case if we had not associated modifyData with a thread. Remember that the is operator compares object identities.

Sharing Data Safely with Actors

To make it possible to safely share data between OS threads, Storm provides a third kind of type: actors. An actor is similar to a class in that it has by-reference semantics. The difference is that it retains the by-reference semantics even across thread boundaries. This might initially seem like it would violate the guarantee of no data races. However, an actor needs to be associated with a thread. Just like the functions that are associated with a thread, this means that the object may only be accessed by code running on the associated thread.

This is perhaps best illustrated with an example. Let's make a version of the Data class that is an actor and compare its behavior to the example above. An actor is declared just like a class. The only difference is that we add the on keyword followed by the associated thread: 

class ActorData on MyThread {
    Nat value;
}

We then modify the code in the main function to use the new type instead: 

void main() {
    ActorData data;
    Future<ActorData> modify = spawn modifyData(data);
    data.value = 20;
    ActorData modified = modify.result();
    print("After modifications: ${data.value}");
    print("Returned object: ${modified.value}");
    print("Are they the same? ${data is modified}");
}

If we try to run this code it produces the following error on the line data.value = 20: 

@/home/storm/threads.bs(2105-2110): Syntax error:
Unable to assign to member variables in objects running on a different thread than
the caller. Create a function in the actor that performs the desired operation instead.

As the error indicates, Storm has noticed that data is an actor associated wit the thread MyThread, while main is not necessarily executed on that thread. Therefore, to avoid data races, Storm does not allow modifying value in this manner. As the error message indicates, we need to create a function that performs the assignment for us instead. Since function calls are dispatched to the proper thread as a message, this approach will avoid data races.

For now, we can simply remove the assignment to data.value to be able to run the program. This is actually enough, even though we read from value in the print statements. This does indeed look like a data race, but Basic Storm allows it anyway. What happens in cases like these is that Basic Storm generates a function that retrieves the variable, and arranges for that function to be executed on MyThread. This means that it is possible to read member variables from actors as usual, even though the cost of doing so is much higher, and often involves a copy.

Running the program produces the following output: 

After modifications: 10
Returned object: 10
Are they the same? true

This is the behavior we initially expected from class types. As such, we can conclude that actor types retain the by-reference semantics even across thread boundaries.

Let's fix the error with the assignment in the main function above. The error message told us that we need to make a function in the actor that modifies the variable for us. In this case, we can make a function set as follows inside ActorData: 

void set(Nat newValue) {
    value = newValue;
}

Then we can replace the removed line data.value = 20; with data.set(20); in the main function. If we run the program now, it runs without errors and produces the following output (most of the time): 

After modifications: 20
Returned object: 20
Are they the same? true

It is worth noting that the program is currently non-deterministic. The output depends on whether the modifyData or the set function is executed first, and the order of these calls is not specified since they may execute in parallel. Storm does, however, guarantee that modifyData and set are not interleaved with each other, since they are scheduled cooperatively on the same OS thread.

Thread-safety

To illustrate the implications of the message-passing model in Storm, let's assume that we wish to increase value with a specific amount from two different threads. We can implement this as follows: 

thread MyThread;

class ActorData on MyThread {
    Nat value;

    void set(Nat newValue) {
        value = newValue;
    }
}

thread MyOtherThread;

void addData(ActorData toUpdate, Nat toAdd) on MyOtherThread {
    toUpdate.set(toUpdate.value + toAdd);
}

void main() {
    ActorData data;
    Future<void> modify = spawn addData(data, 20);
    for (Nat i = 0; i < 10; i++) {
        data.set(data.value + 10);
    }
    modify.result(); // Wait for completion.
    print("Final result: ${data.value}");
}

Since we add 10 to value 10 times and 20 once, we would expect this program to always print the result 120. This is, however, not the case. If I run the program on my machine, I get the following output most of the time: 

Final result: 100

What happened here? The issue lies in how we have implemented the increment operation, both in main and in addData. As it is written now, we first read from value, then add some value to it, and finally write it back using the set function. While Storm provides the guarantee that reading and writing (using set) are not interrupted by other threads, it provides no guarantees that nothing happens between these operations. As such, what happened above was likely the following:

To fix this problem, we need to make sure that the read and write to value are not interrupted by other operations. Luckily, it is enough to make sure that the increment operation occurs on the same OS thread as the one associated with the actor. The easiest way of doing this is to add a member function that performs the operation that needs to be uninterrupted: 

void add(Nat toAdd) {
    value = value + toAdd;
}

If we then make sure to call the add function wherever we increment the value, the program will work as expected, and always print 120: 

void addData(ActorData toUpdate, Nat toAdd) on MyOtherThread {
    toUpdate.add(toAdd);
}

void main() {
    ActorData data;
    Future<void> modify = spawn addData(data, 20);
    for (Nat i = 0; i < 10; i++) {
        data.add(10);
    }
    modify.result(); // Wait for completion.
    print("Final result: ${data.value}");
}

As such, we can see that the threading model in Storm generally lets us treat member functions in actors as "atomic", i.e. that they are not interrupted partway through. This has the nice property that the goal of providing a nice interface to actor types aligns well with making the interface thread safe.

There is one exception to this rule. If we call a function on another thread from the member function of an actor, other function calls may execute at that point. For example, assume that threadFn is such a function. Then, calling threadFn inside of add like below would make it possible for the threading issues we saw before to arise: 

void add(Nat toAdd) {
    Nat original = value;
    threadFn();
    value = original + toAdd;
}

Code like above does, however, make the reader question whether threadFn does something to value already, so these types of situations are not typically a big issue.

Inheritance

Finally, a quick word on inheritance related to actors. Apart from being associated to a thread, actors behave like classes. As such, it is possible to inherit from actors as well. For example, we could create an actor that adds a member variable to our ActorData as follows: 

class Derived extends ActorData {
    Nat count;
}

Since Derived inherits from ActorData that is an actor, Derived will also become an actor that is associated to the same thread as ActorData. This also applies to all types that inherit from Derived. This makes it quire convenient to use and extend functionality from a library without worrying too much about threading, as we shall see in the following tutorials.