Concurrent Programming

A quick review of the Concurrency Visualizer in Visual Studio 2015

The Concurrency visualizer is a free extension available in Visual Studio 2015 that can be used to analyse the performance of a concurrent application. I am going to do a simple overview of this extension.

The tested code

This is the code I am going to profile with the extension. It basically creates four non blocking tasks that compute 1 x 1 infinitely. The main thread then waits for user input.

Concurrency Visualizer in action

CPU Utilization shows that nearly 100% of four cores are used.

cv_cpu_utilization

The profile reports shows that four CLR worker threads (9664, 6352, 5168, and 9724) in execution most of the time, and the main thread waits for I/O most of the time.

cv_threads_view_1

Clicking on a particular worker thread at a particular time shows the call stack.

cv_threads_view_call_stack

The core view show that threads switches cores while running. More specifically, our four worker threads have more than one third of their context switches that cross cores.

cv_core_view

Concurrency visualizer helps identify problems like : serialized execution (thread executing one at a time), poor work distribution, over subscription (too many active threads), overuse of I/O, inefficient synchronization (lock convoys). It seems like a great tool!

Concurrent Programming

How DataFlow avoids race conditions by default

In my previous articles, I tried to present Akka.Net. Let’s remember that the good old Task Parallel Library (TPL) also includes an implementation of the actor model in a dedicated assembly: DataFlow. The actor model is a way to simplify concurrent programming. How DataFlow solves the problem of race conditions that comes with concurrency?

We just want easy multithreading, please!

More precisely, we would like to send messages to an actor asynchronously without having to explicitly use locks or other synchronization techniques. In DataFlow, actors are represented by blocks. In the example we use an ActionBlock which expects an int and produces nothing. We want to compute the sum of numbers from one to n, which is actually easily computed by calculating n * (n + 1) / 2.

Running the program it produces the correct output:

DataFlow: 705082704 expected 705082704

But what happen? The message was processed asynchronously by the ActionBlock in a single and different thread. This is done because MaxDegreeOfParallelism is set to 1 by default. The creation of the block is equivalent to:

If I set MaxDegreeOfParallelism to 2 knowing that my cpu has more than one core, the output is incorrect and varies between executions because we have race conditions. In fact, sum is a shared variable accessed by the ActionBlock block in two different threads.

DataFlow: 509088149 expected 705082704 (first attempt)
DataFlow: 398544839 expected 705082704 (second attempt)

That’s it: set MaxDegreeOfParallelism to 1 if you are using shared variables in your blocks. That is what DataFlow do by default but sometimes it is good to do things explicitly!

Concurrent Programming

Example with Akka.Net: testing the DFS algorithm with Akka.Net TestKit

Introduction

In my first post, I introduced an example with Akka.Net by implementing an algorithm: create a tree and visit it using depth first search (DFS). In this article, we are going to test this algorithm using Akka.Net TestKit. After explaining general principles of uniting testing with Akka.Net TestKit, I will present the particular implementation used for the DFS algorithm.

Note: this example has been written using Akka.Net 1.1.2 with XUnit2, and the .Net Framework 4.6.1. The complete source code can be found on github.

How to test?

Testing one actor at a time

In order to unit test our algorithm efficiently, we need to focus on testing a small part of the code in isolation of the rest: we will test one actor at a time. First, testing more than one actors increase the difficulty to find the cause of the problem. Second, as Akka.Net is concurrent by nature, more actors can lead to more concurrent threads, and therefore our tests are more complex to understand. Third, even though integration tests are extremely important, it is not the role of unit testing. So let’s keep it simple by making small tests (at least as small as we can do) and involving only one actor per testing method.

Testing with messages only

In Akka.Net, actors do no share their state, and communicate together only with messages. To test the behavior of an actor as in reality, we need either to test if this actor has received a certain message, or if it has sent a certain message. However, there is a way to access the state of an actor in the TestKit (with TestActorRef), but the test becomes synchronous in consequence. Testing states is also important but it is not enough to test the application in real. In this article, will keep it asynchronous. For that purpose we will use TestActor and TestProbe.

Testing with mock techniques

In order to test our Actors, we will need to use the following mocking patterns.

Faking a sender with TestActor

The first scenario is simple and common. After creating an actor, we send a message to it and expect a message: this can be achieved using TestActor.

image2_fakeparent

Faking a reply-to actor in a message with TestProbe

Sometimes a message contains a reply-to IActorRef for the response. We just need to fake it using TestProbe.

image2_fakereplyto

Faking a child with TestProbe and dependency injection

Sometimes an actor reacts to a message by creating a child and sending it a message. We can test that by including a factory with the message: this is the principle of dependency injection. In the real program, the factory will create a real child. In the test program, the factory will create a probe in advance that will be accessible by the test.

image1_fakechild

Note: ICustomActorFactory and its derived classes are written in this project only, and is not provided by Akka.Net.

What to test?

A (very) short summary of my previous post

In my previous I created a tree, and visited it using the depth first search algorithm (DFS). DFS is an algorithm that visits each node of a tree in a particular order. In addition, my Akka.Net implementation of DFS had to deal with race conditions between AddRequest and VisitRequest. Finally, I also wanted to check messages consistency to verify if an AddRequest was valid before processing it (and throwing an error if not).

In order to implement all that, I created two actors: TreeActor for managing the interface between the client and the actual tree. NodeActor to represent any node of the tree. TreeActor had an IActorRef of one single NodeActor: the root of the Tree.

Finally I also needed four messages: AddRequest, AddResult, VisitRequest, VisitResult.

Here comes the to do list!

Remember that we need to test messages only, one Actor at a time. In order to (start to) be confident that my algorithm works, I am going to do the following tests.

A TreeActor should:

  • forward its requests to the Root in a simple  and valid scenario
  • throw an exception if receiving the same AddRequest twice (message consistency)
  • throw an exception if receiving an AddRequest for a non-existent child (message consistency)
  • stop sending messages while busy processing previous requests (avoid race conditions)
  • process the oldest not treated message after stopping being busy (avoid race conditions)

A NodeActor should:

  • send an AddResult to TreeActor if it is supposed to process the AddRequest
  • send an AddResult to its children if it is not supposed to process the AddRequest
  • send a VisitRequest to all its children
  • send a VisitRequest to its second child after sending it to its first child, first (message order)
  • not send a VisitRequest to its second child if waiting for a VisitResult from its first child (message order)
  • send VisitRequest to its parent after receiving VisitResult from all its children  (message order)

Let’s do this!

Instead of describing everything, I will present representative examples of each different type of tests. Of course, the complete source code can be found on github with more tests.

Testing the Tree Actor

Faking a sender with TestActor

Here we are expecting an exception (not a message). TestActor is still a the sender of the message.

Note: strangely the test above fails randomly when running all tests (it never fails individually). I think it is a bug and I should actually report it to the Akka.Net team (it might already be fixed in a later version).

Faking a child with TestProbe and dependency injection

This is the typical example:

Here we are implicitly testing the change of behavior: TreeActor is using Become internally.

Here we are nesting ExpectMsg methods because these messages are supposed to be sent in a particular chronological order.

Testing the Node Actor

Faking a reply-to actor in a message with TestProbe

This is a typical example too:

Faking a child with TestProbe and dependency injection

This example is actually also faking the sender but the fake child is more important for the test:

Here we have  three methods to test that nodes are visited in the order indicated by a depth first search.

Conclusion

I am positively impressed by Akka.Net TestKit. To be able to test a concurrent program without disabling concurrency is a major plus point. In my next articles, I will continue on presenting other aspects of this quite interesting framework.

Concurrent Programming

Example with Akka.Net: create a tree and visit it using depth first search

Introduction

Akka.Net helps building asynchronous and distributed programs. This framework is based on the actor model. In this model, actors are classes that communicate with messages only, and do not share mutable variables with other actors. Therefore, actors can safely run concurrently without synchronization mechanisms. I propose to have a look at this framework by implementing an algorithm : creating a tree, and visiting it using depth first search. In this article, I will focus on running the program in a single machine, but with multiple cores (distributed programming with Akka.Net will not be discussed). After describing the algorithm and its expected behavior in Akka.Net, I will explain the implementation.

This example has been written using Akka.Net 1.1.1 and the .Net Framework 4.6.1. The complete source code can be found on github.

Specifying the algorithm

A reminder on the theory

A depth first search (DFS) of a tree consists in visiting each node of a tree, starting from its root. The search explores a path as deep as possible before backtracking. In consequence, nodes are visited in a particular order.

image1_dfs

In C#, we can represent a tree by creating a class Node containing a list of Nodes. A tree can be built from the root to the leafs. DFS can be implemented recursively in a single thread.

We can now create a tree, and visit it using DFS:

As expected the output is:

image2_onethreadoutput

Sum it up!

DFS is algorithm that explores each node of a tree once in a particular order. A DFS based on the actor model should also respect these properties.

The Akka.Net DFS

Architecture

Everything is an actor

In the actor model, everything is an actor, so let’s create them! We need two actors. The TreeActor receives messages from the client and send them to the root node. The NodeActor receives messages from the TreeActor (if it is the root), or an other NodeActor.

image3_dfs_actors

Transmissions of messages

The NodeActor and the TreeActor can both receive the same four type of messages. The AddRequest is intended to the NodeActor creating the child. The AddResult is sent back to the TreeActor by the creator of the new node.

image4_dfs_add

The VisitRequest is received once by each actor from its parent. The VisitResult is sent back to the parent when all children have been visited. Remember that the order of visit matters in DFS.

image5_dfs_visit

Identification of race conditions

Actors can compete in delivering message and it can lead to race conditions. Sending a VisitRequest to the tree, immediately followed by an AddRequest messags can result to different outcomes: the added node may or may not receive the VisitRequest. In order to avoid this confusing behavior, the program does not allow to create and visit a tree concurrently. We will implement that by keeping information about past messages in our tree actor.

Message consistency

We will also remove an other confusing behavior: adding a child to a nonexistent parent, or adding an already existing child.

Implementation

Read-only properties for messages

As it is recommended by the documentation, messages are read-only. In this implementation, public properties are only instantiated in the constructor.

An AddRequest has an instance of ICustomActorFactory which helps create the new node to add.

During unit testing, this factory is very helpful to inject a fake node actor.

For the real program, a default implementation is provided.

An AddResult is just empty.

Each VisitRequest contains the request previously sent to the parent. It helps remember the last visited node, and deduce the next node to visit: it is like a stack.

The VisitResult is sent after all children of a node (and itself) have been visited. It also helps to deduce the next node to visit by encapsulating the VisitRequest.

The TreeActor

The TreeActor is a ReceiveActor that implements IWithUnbondedStash. In the normal behavior, any message are handled. In the busy behavior, AddRequests and VisitRequests are systematically stashed.

AddRequestHandler/AddRequestHandler are (nearly) symmetrically identical to VisitRequestHandler/VisitResultHandler. A request is handle only if no other request of the other type is being processed. The request is stashed and the tree becomes busy. If all result of a type are received, all messages are unstashed and the normal behavior is restored. This security is to prevent race conditions.

The NodeActor

A NodeActor has only one behavior.

The AddRequestHandler either creates the new node (if the request is intended to this node), or delivers the message to all children in parallel.

The VisitRequestHandler immediately sends the VisitResult if the node has no child, or sends a new VisitRequest to the first child otherwise. This new VisitRequest wraps the old one to remember which node has been visited.

The VisitResultHandler calculates the next child to visit. If no child to visit remains, a VisitResult is sent back to the parent node.

Consuming actors

We can consume our actors now!

Result

We have the same result as the first version of the DFS.

image6_akkadotnetoutput

Conclusion

The real goal of this article is to test Akka.Net capabilities with an example. We have implemented a concurrent depth first search algorithm where each node can process a different request (of the same type) at a given moment. The program can run in different threads. At first, the new paradigm is not easy to deal with, but Akka.Net comes with practices that really makes concurrent programming safer: threads communicate together with immutable messages, and computing units (actors) process messages one at a time. While immutability is at the discretion of the developer, communication and message processing are provided by the framework. However, my example is not enough to fully evaluate Akka.Net capabilities in general (local or distributed), and ultimately how it may fit or may not fit a real case scenario. Other aspects have to be studied, like logging, supervision, testing, distributed programming, reactive streams and maybe more. One of these subjects may be one in my next articles.