# Archive for the ‘threads’ Category

In this short lesson we will discuss how to parallelize a simple and rather inefficient (because this is not an in-place version) implementation of quick-sort using asynchronous tasks and futures.

We will perform some benchmarking and performance analysis and we will try to understand how we can further improve our implementation.

## Quick sort

In this section, I will briefly refresh your memory on quick-sort. I will do so by showing you a simple and self-explicative Haskell version first. We will also write a C++ (serial) version of the same code implementation C++ that we will use as a basis for our parallelization.

Here it goes the Haskell version:

```quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
```

It is beautifully simple: in order to sort a list with at least, `p` one element is only necessary to partition sort the rest of the elements `xs` into two sublists:

• `lesser`: containing all the elements in `xs` smaller than `p`
• `greater`: containing all the elements in `xs` greater than `p`
Once both sublists are sorted we can finally return the whole sorted list using by simply returning gluing `lesser`, `p` and `greater` together in this order.

If you still have trouble understanding the quick-sort algorithm please refer to Wikipedia.

## Quick-sort serial version

The following is the serial C++ implementation of the same idea described above. It should be pretty easy to map the following implementation to the Haskell one. Run it on Wandbox

```template <typename T>
void quick_sort_serial(vector<T>&amp; v) {
if (v.size() <= 1) return;
auto start_it = v.begin();
auto end_it = v.end();

const T pivot = *start_it;

//partition the list
vector<T> lesser;
copy_if(start_it, end_it, std::back_inserter(lesser),
[&amp;](const T&amp; el) { return el < pivot; });

vector<T> greater;
copy_if(start_it + 1, end_it, std::back_inserter(greater),
[&amp;](const T&amp; el) { return el >= pivot; });

//solve subproblems
quick_sort_serial(lesser);
quick_sort_serial(greater);

//merge
std::copy(lesser.begin(), lesser.end(), v.begin());
v[lesser.size()] = pivot;
std::copy(greater.begin(), greater.end(),
v.begin() + lesser.size() + 1);
}
```

## Parallelizing Quick-sort using std::future

In order to speed-up things we are going to use the fact that quick-sort is a divide and conquer algorithm. Each subproblem can be solved independently:
creating and sorting `lesser` and `greater` are two independent tasks. We can easily perform both on different threads.

The following is the first parallel version of the `quick_sort_serial()` above.
Run it on Wandbox

```template <typename T>
void filter_less_than(const vector<T>&amp; v, vector<T>&amp; lesser, const int pivot) {
for (const auto el : v) {
if (el < pivot) lesser.push_back(el);
}
}

template <typename T>
void quick_sort_parallel1(vector<T>&amp; v) {
if (v.size() <= 1) return;
auto start_it = v.begin();
auto end_it = v.end();

const T pivot = *start_it;
vector<T> lesser;
auto fut1 = std::async(
std::launch::async,
[&amp;]() {
filter_less_than<T>(std::ref(v), std::ref(lesser), pivot);
quick_sort_parallel1<T>(std::ref(lesser));
});

vector<T> greater;
copy_if(start_it + 1, end_it, std::back_inserter(greater),
[&amp;](const T&amp; el) { return el >= pivot; });

quick_sort_parallel1(greater);

fut1.wait();

std::copy(lesser.begin(), lesser.end(), v.begin());
v[lesser.size()] = pivot;
std::copy(greater.begin(), greater.end(),
v.begin() + lesser.size() + 1);
}
```

As you can notice, the creation and sorting of lesser and are performed in parallel. Each thread running an instance of `quick_sort_parallel1()` will create another thread running quick-sort on one of the two sub-problems while the other subproblem is solved by the current thread.

This is exactly what we are doing when we spawn the following async task:
we are creating a task that will populate `lesser` with all the elements from `v` less than `pivot` and, once ready, it will sort it.
Please note that everything we need to have modified by reference need to be wrapped in a `std::ref` as we discussed in the previous lessons.

The following picture shows how the execution unfolds for the unsorted list: [2,7,1,6,9,5,8,3,4,10]:

The following code shows hot to spawn an async thread solving the `lesser` subproblem:

```  vector<T> lesser;
auto fut1 = std::async([&amp;]() {
filter<T>(std::ref(v), std::ref(lesser), pivot);
quick_sort<T>(std::ref(lesser));
});
```

While this task is running on the newly created thread, we can solve `greater` on the current thread.

The asynchronous task will recursively spawn other async tasks until a list of size `<=1` is created, which is of course already sorted. There is nothing to do in this case.

Once the main thread is done with sorting the `greater` list, it waits for the asynchronous task to be ready using the `std:.future::wait()` function.
Once `wait` returns, both lists are sorted, and we can proceed with merging the result and finally, here it is, we have a sorted list.

## Performance analysis

Let's quickly analyze our implementation. We will compare execution time for the single-thread and async-parallel versions above.

Let's start our analysis by taking looking at this graph depicting the execution time (average of 10 runs) for both versions above:

It might be a surprising result to see that the Async parallel version is way slower than the single threaded version, ~55x slower!
Why is that? The reason is that, the parallel version creates a new thread for every single subproblem, even for the ones that are quite small.
Threads are costly to manage by the OS, they use resources and need to be scheduled. For smaller tasks the overhead caused by the additional thread is larger than the gain in performance that we might get by processing the sublist in parallel. This is exactly what is happening.

In order to solve this issue, we want to modify the async code above so that a new thread is spawned only when the input list `v` is larger than a certain threshold. The code below implements the aforementioned idea:

```template <typename T>
void quick_sort_async_lim(vector<T>&amp; v) {
if (v.size() <= 1) return;
auto start_it = v.begin();
auto end_it = v.end();

const T pivot = *start_it;
vector<T> lesser;

vector<T> greater;
copy_if(start_it + 1, end_it, std::back_inserter(greater),
[&amp;](const T&amp; el) { return el >= pivot; });

if (v.size() >= THRESHOLD) {
auto fut1 = std::async([&amp;]() {
filter<T>(std::ref(v), std::ref(lesser), pivot);
quick_sort_async_lim<T>(std::ref(lesser));
});

quick_sort_async_lim(greater);
fut1.wait();

} else {
//problem is too small.
//Do not create new threads
copy_if(start_it, end_it, std::back_inserter(lesser),
[&amp;](const T&amp; el) { return el < pivot; });
quick_sort_async_lim(lesser);
quick_sort_async_lim(greater);
}

std::copy(lesser.begin(), lesser.end(), v.begin());
v[lesser.size()] = pivot;
std::copy(greater.begin(), greater.end(),
v.begin() + lesser.size() + 1);
}
```

As you can notice, the only addition that this optimized version has is that a new thread is spawned only when the size of the input list is larger than `THRESHOLD` If the list is too small, then we fall back on the classic single-thread version.
The following pictures show the result for the optimized version above with value of `THRESHOLD=4000`. As you can notice the execution time drops sensibly w.r.t single thread version. We have achieved `~4x` speedup with a minimal programming effort.

We have introduced a new parameter in our code, and we need to figure out what is the best value of `THRESHOLD`. In order to do so, let's analyze the performance of the code above for various values of the threshold.
The following graph depict the execution time for various values of `THRESHOLD`. Note that the `y-axis` is in log scale. The execution time drops quite abruptly from `0` to `300`.

## Conclusion

We have used std::future to parallelize the quick-sort algorithm. The async code differs slightly from the serial single thread implementation, but runs 4x faster. On the other hand, we have learned that running too many threads it is definitely not a good idea because each thread comes with an overhead: the OS needs to allocate resources and time to manage them.

## Introduction

In this lesson we will talk about a way of returning values from threads, more precisely we will talk about `std::future` which is a mechanism that C++ offers in order to perform asynchronous tasks and query for the result in the future.
A future represents an asynchronous task, i.e. an operation that runs in parallel to the current thread and which the latter can wait (if it needs to) until the former is ready.
You can use a future all the time you need a thread to wait for a one-off event to happen. The thread can check the status of the asynchronous operation by periodically polling the future while still performing other tasks, or it can just wait for the future to become ready.

## Introduction

In the previous lesson we have seen how data can be protected using `mutex`. We now know how to make threads do their work concurrently without messing around with shared resources and data. But sometimes we need to synchronize their actions in time, meaning that we might want a thread `t1` to wait until a certain condition is true before allowing it to continue its execution.

This lesson discusses the tools that we can use to achieve such behavior efficiently using `condition variables`.

In this lesson, we will cover the topic of data sharing and resources between threads. Imagine a scenario where an integer `o` needs to be modified by two threads `t1` and `t2`. If we are not careful in handling this scenario a data race might occur. But what is a data race exactly?

## Data Race

A data race occurs when two or more threads access some shared data and at least one of them is modifying such data. Because the threads are scheduled by OS, and scheduling is not under our control, you do not know upfront which thread is going to access the data first. The final result might depend on the order in which threads are scheduled by the OS.

Race conditions occur typically when an operation, in order to be completed, requires multiple steps or sub-operations, or the modification of multiple data. Since this sub-operations end up being executed by the CPU in different instructions, other threads can potentially mess up with the state of the data while the other's thread operation is still ongoing.

tutorial3

# Modern C++ Concurrency - How to use a thread object correctly.

This lesson is going to be more theory focused because we will covers some important fact about how to correctly use the `thread` object.
For instance we will be talking about how to

1. Pass around `thread`s
2. Have side effect on object passed to `thread` by reference
3. How to avoid common undefined reference situations
4. How to identify threads uniquely by an id.

tutorial2

# Modern C++ Concurrency - Cumulative sum of a vector - Part 2

In this tutorial we will continue the exercice we started out in part-1 and we will:

1. split the work among a number of threads that will be specified by the user via command line
2. perform some benchmarking to see how our code scales as the number of threads increases. We will compare the execution time of the version of the program running on one thread versus the execution time when running on an increasing number of threads.

tutorial1

# Modern C++ Concurrency - Cumulative sum of a vector - Part 1

In this tutorial we will write a c++ code that will take as input a large list of numbers and it will return the cumulative sum of them.
In order to speed up the process we will write this code so it uses two threads. In the process we will learn how to use a callable object with the `operator()` redefined to create and run a thread.

# Hello world Concurrency in C++

## What is concurrency?

Let’s start off by answering the following question: what is concurrency? Intuitively, concurrency is the execution of operations at the same time. The key part here is at the same time.
Computers are concurrent machines. Nowadays PCs are equipped with several processors and that means that we can exploit all of them at the same time to speed up our software.
Normally an executable runs on a single processor, meaning that at any given time only one of its instructions is executed.
Concurrency is all about executing several instructions at the same time for the same executable.

## Hello world code

The C++11 standard introduced a new thread library that allows for standardized programming of concurrent software using threads, but it also offers a bunch of other tools to make concurrent programming safe: synchronization, and atomic operations for instance. Do not worry is any of these words ring a bell now. We will learn a lot about them.

Let’s start whit writing our first concurrent code. Read On…