This is the second part of the Parallel execution for contests series. For your convenience you can find other parts in the table of contents in Part 1 — Powershell

Hello! Today we continue working on parallel codes for contests. Let’s go.

Test cases

Last time we saw how to execute multiple instances of program at once. However, sometimes it is not enough to just run multiple applications, especially when we are solving problems from a single input file. Fortunately, usually there are multiple test cases in each file.

Most of the contests’ tasks are joined in batches. Authors of the task do it in order to rule out programs which try to guess the answer or to avoid possibility of solving a task by hand. Usually, in the first line of the input there is a number indicating total number of test cases stored in the file.

To achieve greater performance we can use similar approach as in previous part of this series. This time we will run every test case using different thread. However, we need to take care of reading input and writing output.

Let’s say that our input file looks like this:

Ideally we would like to calculate every test case using different thread. However, we cannot start second thread before the first one ends reading input since we cannot mix the data. Of course, reading from the console is usually synchronized internally, however, we usually cannot read all required data with one simple call to API. We need to execute multiple ReadLines to obtain and parse the input.

There are different approaches. First, we might want to use one thread to read input, parse it, and dispatch to other threads. This would look like follows:

This approach is pretty straightforward, however, it requires parsing the whole input, storing it in memory, and passing only the relevant part to the worker threads. Since we would like to run our algorithm with minimal changes, this might be unacceptable.

We also might use three lambdas:

This approach is very similar to the previous one and has almost the same drawbacks. This time it might be easier to divide our algorithm in three separated parts, however, we still need to store all input data in memory.

This is why we are going to use different approach.

Serializing with events

We are going to use ManualResetEvent to keep threads in order. We use it in the following way:

With this approach we don’t need to store data and pass it between lambdas. Of course it would be great if we would be able to encapsulate events logic in nice functions so we don’t need to remember all the details.

Implementation

We start with the following implementation:

In line 10 we define a function with two parameters: first parameter indicating numer of tasks to run (number of test cases), second parameter is a lambda which accepts two lambdas and one integer. First lambda is lambda to indicate reading, second lambda is for writing, integer is an id of the task.
In line 12 we create a collection for executed tasks. Next, we define two events which will be used throughout the work.
In lines 16-42 we start a task. We pass it two lambdas. They do nothing on first invocation, however, on the second invocation they set an events. This is because first task is always allowed to read or write so it doesn’t need to wait for anyone.
In lines 44-80 we start other tasks. They as well get two lambdas, but this time they (lambdas) need to wait on an event on first invocation.
In lines 82-105 we create last task. Lambdas for this task only needs to wait for an event on first invocation.

We use this code in the following way:

So our worker function only needs to invoke two functions in correct order and we have all serialization done out of the box.

Summary

We are now able to run multiple instances of our application and solve multiple test cases in parallel with almost no changes in algorithm. Next time we are going to examine C++ implementation since most of contests algorithms are written in C++.