# 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 `spawn`ed 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 `Moment`s 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:

- `main` read `value` and got the value 0.
- `addData` read `value` and got the value 0.
- `addData` added 20 to 0 and calls `set(20)`.
- `main` added 10 to 0 and calls `set(10)`, which overwrites the result from `addData`.

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.