Multithreading in an expressive way with monadic expression

Hi, there is a long time I have not written anything, sorry for that! I planned to write several articles during these few next weeks. This article will deal with multithreading.

Introduction

In a lot of articles, we can read that multithreading is not easy, and other things like that. In this article, we will learn how to write multi-threaded application in a simple and a fun way.
The idea will be to write something like that

If we write a little scheme, it gives us that :

Multithreading in action
Multithreading in action

Obviously, when the function f3 starts, functions f1 and f2 must have complete. The same thing happens for the getResult. It must wait for f3, f4, f5 to complete.

Does it really exist?

Actually, it does, and it will even be in the standard in C++20. However, the feature from the C++20 suffers from different problems that are explained in the Vittorio Romeo article. Actually, this article could be a continuation of the series of articles from Vittorio.

Multithreading with Monadic Expression: Implementation

I hope you really love read ununderstandable C++ code because the code is full of template and metaprogramming. I recommend to have some basis in really modern C++ or read the series from Vittorio I was talking before. We are going to see a lot of things both in multithreading and metaprogramming

Why do we need a continuation of the series from Vittorio?

Firstly, the code provided by Vittorio does not work on Visual Studio, and I really want to have my codes work on all compilers and all operating systems. Second, in its article, he only provides a version using a function waitAndGet that prevents us to insert code into the main thread in an easy way.
The third issue is that the group of functions returns a std::tuple

For example, you must have to write something like that

But, in reality, some people will prefer the first version, other will prefer the second version. What will happen if a function does not return any arguments? According to me, the second version is more natural.

Forwarding

Because we are going to use a lot of metaprogramming, we may need to perfect forward some arguments. Here are two macro that defines a perfect forwarding. There is one macro for a normal variable and another one for auto. I was not able to use the same one for both cases because sometimes, use the form ::std::forward<decltype(variable)>(variable); is too difficult for Visual Studio, that is why I provide these both declarations.

This code does not really need any explanations.

A Latch

A latch is useful when you want to know if a job is finished or not. Let’s say you have two thread, which one of them is waiting the result coming from the second one. The first one need to wait the second to finish.

Latch
Latch

The following code shows how to implement a simple “bool_latch”

The code is based on condition_variable, mutex, and a boolean variable

The return type

Each function may return one value. However, what returns a group of functions? The better choice is to return a std::tuple. Thus, if you have three functions that return an int at the same level (running in 3 parallels threads), the result will be a std::tuple<int, int, int>.

Functions that return void.

The simple way for this case is to create an empty type that we will name nothing. Its declaration is straightforward.

The function, instead to return nothing, must return the type nothing.
Let’s say you have three functions, f1, f2, f3. f1 and f3 return an int and f2 returns nothing. You will get a std::tuple<int, nothing, int>
How to return nothing instead of void? This function explains that in a straightforward way!

Pass a tuple as an argument

Okay, now say you have a std::tuple<int, double, std::string> and, you want to give it to one function with a prototype like returnType function(int, double, std::string).
One way to do that is to use the function apply.

Here there is no problem, but assume that there is a nothing in your tuple like std::tuple<int, nothing, int>.
When you will apply this tuple to the function, you will also pass the nothing.

To avoid such problem, you must filter all the arguments and store the arguments inside a lambda function.

Architecture

This part will be the most difficult part of the article. We will see how the architecture work. It is an architecture with nodes. We will see three kinds of nodes. The root node that is the beginning of the chain of functions, the when_all node that can own one or several functions which will run in parallel and one node result_getter that represents the end of the chain of functions.

Overview

Overview of multithreading
Overview of multithreading

As you may have noticed, there is no type erasure. The type owned by the caller is the result_getter. However, the result_getter, when it executes all the functions, it must return to the root. And to do that, it must go through the when_all.

Now go to explain whole the code!

root

There is nothing difficult here. The when_all is a friend. There are two functions, the first one is called by the children and its purpose it’s only to reach the top. After, you execute the child functions through the scheduler.

when_all

This is the most difficult part.
However, everything is not difficult. There are two things that are difficult. The output_type and the execute function.

The input_type is straightforward, we take the output from the parent. The output_type is a bit tricky. The idea is to call all the function, and for each of them, add the result to a tuple.

There are several things to think about.
The exec lambda is the function that will be executed in a parallel thread. We store the value inside the good position of the tuple. If all functions have finished, we call the execute function for the directChild. This condition is checked by mLeft.

The executeOneFunction lambda is the function that computes if the function must be launched through the scheduler or not. (If there is only one function, there is no need to launch it through the scheduler because the root already did that).

The enumerate_args execute the function with each arguments, and give the index as an argument as well.

The enumerate_args is following :

result_getter

Once you are here, you may have already build your own result_getter

The idea here is to execute the function and wait for the latch to return the result. All the part for epurated tuple is done here :

The idea is to remove the nothings from the tuple, and if the tuple owns only one type, the tuple is removed and we get only the type.

Conclusion

In this article, you learned how to write safe and easy to read multi-threaded functions. There is still a lot of things to do, but it is really usable and easy to use. And if someone else has to read your code, he should be able to do so.

If you want to test it online, you can go on wandbox

Reference

Vittorio Romeo

Range : Be expressive using smart iterators with Range based containers

Hi !
Today I am not going to talk about rendering. This article will deal with expressiveness in C++. Expressiveness? Yes, but about containers, range, and iterators.
If you want to know more about writing expressive code in C++, I advise you to go on fluentcpp.
If you want to know more about range, I advise you to take a look at the Range V3 written by Eric Niebler.
The code you will see may not be the most optimized, but it gives one idea behind what ranges are and how to implement it.

Introduction

How could we define a Range ?

The objective

Prior to defining what a Range is, we are going to see what Range let us do.

Isn’t it amazing to write things like that? Okay for direct operation inside the container, it could be better in two ways:

  1. It is not “easy” to read if you want to compose operation : (unique(sort(range)) is less readable than range | sort | unique in my opinion. But it is juste one “optimisation” to do :).
  2. It may be not optimized since sort returns a Container : here a vector, and build also.

The overloading of operator<< is quite easy though:

Okay, there are a lot of templates. I hope you will not get an allergy to them. All the lines that follow will use and abuse of templates and SFINAE.

The definition of a Range

A range is a way to traverse a container. They are at one abstraction above of iterators. To be simple, a Range own the first iterator, and the final one. It comes with a begin and one end function.

Smart (Or proxy) iterator

Okay, now things are becoming tricky. I hope that I lost no one.

What exactly is an iterator ?

To be simple, an iterator is an abstraction of a pointer.
It exists several catetegories of iterators, to be simple, here is the list:

  1. input : They can be compared, incremented, and dereferenced as rvalue (output ones can be dereferenced as lvalue).
  2. Forward : not a lot of difference with the prior.
  3. Bidirectional: They can be decremented.
  4. Random Access : They support arithmetic operators + and -, inequality comparisons.

Smart Iterator in details

Lazy Initialization

This statement tells us “If the result of the operation is not needed right now, there is no need to compute it”. To be simple, the operation will be done when we will need to get the result. With iterator, it could be done when you dereference it for instance.

Different types of smart iterator

Filter iterator

This iterator will jump a lot of values that do not respect a predicate. For example, if you want only the odd values of your container, when you increment the iterator, it will advance until the next odd value and will skip all the even ones.

Transform iterator

This iterator will dereference the iterator, apply a function to the dereferenced value and returns the result.

Implementation

Basics

Here we are going to implement our own iterator class. This class must be templated twice times.
The first template argument is the iterator we want to iterate on. The second template argument is a tag that we use to perform a kind of tag dispatching.
Moreover, this iterator must behave as … an iterator !

So, we begin to write :

One of above typename will fail if Iterator does not behave like one iterator.
The Tag has a constructor and can own several data (function / functor / lambda), other iterators(the end of the range?) or other things like that.

The iterator must respect the Open Closed Principle. That is why you must not implement the methods inside the class but outside (in a namespace detail for instance). We are going to see these methods later. To begin, we are going to stay focused on the RangeIterator class.

Constructors

We need 3 constructors.
1. Default constructor
2. Variadic templated constructor that build the tag
3. Copy constructor

And we need as well an assignment operator.

There are no difficulties here.

They also need comparison operators !

And they are quite easy !

Reference or value_type dereferencement

I hesitate a lot between return either a reference or a copy. To make transform iterator easier, I make the return by copy.
It means that you cannot dereference them as a lvalue :

The code is a bit tricky now because the dereferencement could not be the value you are waiting for. See the std::back_insert_iterator for instance.

Forward iterator to go farther !

Again, simple code !

Backward iterator, to send you in hell !

Okay, now as promised, we are going to see how beautiful C++ templates are. If you don’t want to be driven crazy, I advise you to stop to read here.
So, we saw that not all iterators have the “backward” range. The idea is to enable this feature ONLY if the iterator (the first template argument) supports it also.
It is the moment to reuse SFINAE (the first time was for the “is_range” structure we saw above).
We are going to use the type_trait std::enable_if<Expr, type>.
How to do that?

You MUST template this function, else the compiler can not delete it !!!

FYI : If you have C++17 enabled, you can use concepts (at least for GCC).

Random iterator

Now you can do it by yourself.
But here some code to help you (because I am a nice guy :p)

Details

Okay, now we are going to see what is hiden by detail::RangeIterator.

Normal iterators

In this namespace, you MUST put the tag and the function on it.

Here are the functions for normal iterator.

It is simple, if it is a normal iterator, it behaves like a normal one.

Transform iterator

I will not talk about the filter iterator since it is not complicated to make it once we understand the ideas. Just be careful about the construct function…

The tag

So, what is a Transform iterator? It is simply one iterator that dereference the value, and apply a function to it.
Here is the Tag structure.

It owns one std::function and that’s it.

The usefulness of the transform iterator is when you dereference it. So you need to reimplement only the dereference function.

Thanks to overloading via tag dispatching this function should (must??) be called without any issues (actually you hope :p).

However, if you want to use several files (thing that I only can to advise you), you cannot do it by this way but specialize your templates. But you cannot partially specialize template function. The idea is to use functor!

Here is a little example using dereference function.

The builder : pipe operator (|)

Okay, you have the iterator, you have the range class, you have your function, but now, how to gather them?

What you want to write is something like that:

First, you need a function that Create one range that own two iterators.
One that begins the set, and the other one that ends it.

Once you have that, you want to overload the pipe operator that makes it simple :

Warning : Don’t forget to take care about rvalue references to be easy to use !

Conclusion

So this article presents a new way to deal with containers. It allows more readable code and take a functional approach. There is a lot of things to learn about it, so don’t stop your learning here. Try to use one of the library below, try to develop yours. Try to learn a functional language and … Have fun !!!!

I hope that you liked this article. It is my first article that discuss only C++. It may contains a lot of errors, if you find one or have any problems, do not forget to tell me!

Reference

Range V3 by Eric Niebler : His range library is really powerfull and I advice you to use it (and I hope that it will be a part of the C++20).
Ranges: The STL to the Next Level : because of (thanks to?) him, I am doing a lot of modifications in all my projects… x).
Range Library by me : I will do a lot of modifications : Performance, conveniance and others.