## Dining philosophers in C++11: Chandy-Misra algorithm

In my previous post, Dining Philosophers in C++11, I have provided an implementation for the dining philosophers problem using modern C++ features, such as threads and mutexes. However, it was noted in the comments that the implementation did not prevent the philosophers starving to death when you remove the waiting times.

An algorithm that prevents the philosophers from starving was proposed by Mani Chandy and J. Misra and is known as the Chandy/Misra solution. This is a bit different than the original problem because it requires the philosophers to communicate with each other. The algorithm, as described on Wikipedia, is the following:

1. For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty.
2. When a philosopher wants to use a set of resources (i.e. eat), said philosopher must obtain the forks from their contending neighbors. For all such forks the philosopher does not have, they send a request message.
3. When a philosopher with a fork receives a request message, they keep the fork if it is clean, but give it up when it is dirty. If the philosopher sends the fork over, they clean the fork before doing so.
4. After a philosopher is done eating, all their forks become dirty. If another philosopher had previously requested one of the forks, the philosopher that has just finished eating cleans the fork and sends it.

In order to implement this, we must make several changes to the solution proposed in the previous post:

• forks and philosophers must have identifiers
• there is an initial setup of both forks and philosophers
• use std::condition_variable to communicate between threads
• increase the number of philosophers

Because it has been also argued that string_view is only available in C++17 and this implementation is supposed to work in C++11, I have replaced that with std::string const&.

In this implementation, philosophers, i.e. threads, need to communicate with each other to request the forks, i.e. resources. For this, we will use a std::condition_variable, which is a synchronization primitive that enables the blocking of one or more threads until another thread notifies it. A std::condition_variable requires a std::mutex to protect access to a shared variable. The following class, sync_channel, contains both a condition variable and a mutex and provides two methods: one that waits on the condition variable, blocking the calling thread(s), and one that notifies the condition variable, unblocking all the threads that are waiting for a signal.

The table class from the previous implementation is modified: the forks are no longer defined here, but a sync_channel is used to prevent philosophers start dining until the table setup is completed. Its name has been changed to table_setup.

The fork class is no longer a wrapper for a mutex. It has an identifier, an owner, a flag to indicate whether it is dirty or clean, a mutex, and a sync_channel that enables owners to request used forks. It has two methods:

• request() that enables a philosopher to request the fork. If the fork is dirty, it is set to clean, and the ownership is given to the philosopher that asked for it. If the fork is clean (i.e. the current owner is eating), than the philosopher that asked for it will block, waiting for it to become dirty (i.e. the current owner has finished eating).

• done_using() a philosopher indicates that has finished eating and notifies other philosopher that is waiting for the fork that it can have it.

There are less changes to the philosopher class: it has an identifier, and there are no more waiting times to simulate eating and thinking. There are some small changes to the following methods:

• dine(): each philosopher only starts eating after the entire table has been setup. A condition variable, from the table_setup object is used for this.

• eat(): each philosopher first requests the left and right fork. When they are available, they are locked using std::lock() to avoid possible deadlocks, and then their ownership is transfered to a std::lock_guard object, so they are properly released when done. After eating, the fork is set as dirty and other philosophers waiting for it are notified of this.

According to the initial setup, each fork is given to the philosopher with the lower ID. That means fokm 1, placed between philosopher 1 and N, goes to philosopher 1. Fork 2, placed between philosophers 2 and 3 is given to philosopher 2. Eventually, fork N, placed between philosophers N and 1, is given to philosopher 1. Overall, this means all philosophers have initially 1 fork, except for the first one that has two, and the last philosopher, that has none.

Put all together, the code looks like this:

The output of the program looks like this:

Hits for this post: 1911 .

## Dining Philosophers in C++11

UPDATE: for an implementation of the Chandy/Misra solution see Dining philosophers in C++11: Chandy-Misra algorithm

The problem of the dining philosophers, first proposed by Edsger Dijkstra and reformulated by Tony Hoare, is a famous problem for concurrent programming that illustrates problems with synchronizing access to data. The description of the problem, taken from Wikipedia, is the following:

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

The idea is to find a solution so that none of the philosophers would starve, i.e. never have the chance to acquire the forks necessary for him to eat.

Below I propose a simple implementation to this problem using C++11 language and library features. The following classes are defined:

• fork represents a fork at the table; the only member of this structure is a std::mutex that will be locked when the philosopher picks up the fork and unlocked when he puts it down.

• table represents the round table where the philosophers are dining. It has an array of forks, but also an atomic boolean that indicates that the table is ready for the philosophers to start thinking and eating.

• philosopher represents a philosopher dining at the table. It has a name and a reference to the forks on his left and right.

Most of the implementation of the solution is part of the philosopher class. When an object of this class is instantiated, a thread is started. This thread is joined when the object is destroyed. The thread runs a loop of thinking and eating until the dinner is signaled to end by setting the ready member of the table to false. There are three main methods in the philosopher class:

• dine() is the thread function; this is implemented as a simple loop of thinking and eating.

• think() is the method that represents the thinking period. To model this the thread sleeps for a random period of time.

• eat() is the method that models the eating. The left and right forks are acquired in a deadlock free manner using std::lock. After the forks, i.e. mutexes, are acquired, their ownership is transfered to a std::lock_guard object, so that the mutexes are correctly released when the function returns. Eating is simulated with a sleep.

To see how this works, we create a table object and an array of phylosophers. Upon creating the philosopher objects their own working thread is started, but nothing happens until the table is signaled as being ready. Philosophers then compete for the forks (i.e. mutexes), eat and think until the dinner is signaled as finished by setting the ready flag of the table object back to false.

The whole implementation is show below:

The output for this program (that varies with each execution) has the following form:

Though the problem is usually described in terms of five philosophers, any number of philoposhers can be present at the table (of course, at least two are necessary for the problem to make sense). Adding more philosophers does not require any changes in the implementation.

Hits for this post: 1907 .

## New standard library features in Visual C++ 2017 RC

The new Visual C++ 2017, currently in release candidate phase, provides a series of updates and fixes to both the C++ compiler and the standard library. A comprehensive list of these improvements is available at What’s New for Visual C++ in Visual Studio 2017 RC.

In this article, I want to shortly look at the new standard library features from VC++ 2017.

• std::any (available in header <any>) is a class that represents a type-safe container that can hold the value of any copy-constructible object. To read the value stored in an any variable you need to use the non-member function std::any_cast.

• std::optional (available in header <optional>) is a class template that may or may not contain a value any moment in time. If it contains a value, it is allocated as part of the optional object, and therefore does not incur any memory overhead.

• std::variant (available in header <variant>) is a class template that represents a type-safe union. A variant can hold any number of alternatives, but they cannot be of type reference, array or void. The first alternative must be default constructible, because variants are default constructible and a default-constructed variant object contains a value of its first alternative. If the first alternative is not default-constructible, std::monostate (an empty, default-constructible class) can be used for that purpose. If it contains a value, it is allocated as part of the variant object, and therefore does not incur any memory overhead.

• std::basic_string_view (available in header <string_view>) is a class template that represents a view of a contigous sequence of characters (defined by a pointer to the start of the sequence and a count). Several type aliases are available:

basic_string_view has an interface almost identical to basic_string so that switching from the later is as simple as possible. A typical useage of this class template is for function parameters as a replacement for constant references to basic_string.

Additional new supported C++17 standard library features are:

• std::apply is a function template that invokes a specified callable object with a tuple of arguments.
• std::make_from_tuple is a function template that creates an object by invocking its constructor with the members of a specified tuple.

To have all these available the /std::c++latest compiler switch must be used. This can be also set from the project properties, at C/C++ > Language > C++ Language Support.

Hits for this post: 3898 .

## Impressions from the ISO C++ committee meetings in Issaquah

Last week I was in Redmond for the Microsoft MVP 2016 Summit. At the same time, the ISO C++ committee was having its fall meeting in Issaquah, which is very close to Redmond. Therefore, after the summit ended, a group of VC++ MVPs, including myself, decided to make the short trip to Issaquah and attend as observers the meetings, that are actually opened for the public. It was a very interesting experience and I am glad that I had the opportunity to take it.

The committee is organized in several working groups (WG) and study groups (SG). You can actually read all about that here. These groups have separate meetings as they are focussed on different things. I have attended a meeting of the Evolution Working Group (aka EWG), as, at that point, it looked like the most interesting of them all. These meetings actually took place in the same location where the final version of C++14 was voted.

Apart from the topics that have been discussed, which I will not elaborate on here, even though they were interesting and important, it was rather the way the committee is working that it was of most interest to me. I always had the impression that discussions were held in the fashion of the debates in the British Parliament or something similar, and I was surprised to see a much more organized, though still vocal, group. People are patiently taking turns to speak, constantly come with unexpected arguments or counter examples and eventually take polls to see what is the group’s overall opinion on the discussed topic(s). It also helped understand the process proposals go through from an initial form to the one that is eventually voted, if that is the case. I realized that it is way too easy for us to complain that things take too much time to be accepted. The reality is there are so many details that have to be taken into account and it takes many people to see them all. Everything needs to be backward compatible and it takes a lot of scrutiny and proposal iterations to reach a generally accepted form.

Overall, it was definitely a trip worth making, and I am looking forward to doing that again. I also encourage all of you that are interested in that and have the opportunity to take it.

For information about the progress in Issaquah see Herb Sutter’s Trip report: Fall ISO C++ standards meeting (Issaquah).

Hits for this post: 3074 .

## Top 10 features that I miss from C++

DISCLAIMER: the following is a pure hypothetical list of wishes I had about C++. You should treat it as it is. This is not supposed to be a collection of community agreed list of wishes, nor it is intended to make complete sense, as some of these features are available through the standard library. Please procedure further with that in mind.

I was thinking lately what are the top language features I am missing from C++ but are available in other similar languages (such as C# or Java). After some consideration I have come up with the following list. Note that this list refers to language features only, and not library features and they are listed in a rather random order.

• Native string type, other than char*, rather a language built-in std::string
• Native datetime type, that would allow us to specify points of times without a built-in resolution. Obviously adding this after the chrono library makes no sense. This refers rather to a language feature that should have been available from the beginning. The reason for that is specifying date and time is a common operation we often need to do.
• Native interfaces, other than abstract classes with pure virtual functions only as it is currently possible, because such classes can also contain data members. The reason for this is convenience in defining interface. The syntax for this should not require us to define the member functions as virtual and pure, they should be virtual implicitly. Interface member functions should also be mandatory public so we should not have to declare that either. And last, but not lease, interfaces define contracts and therefore a special interface class should not allow to define data members, not static methods.
• Properties, basically a pair of get/set accessors over a data member. Having automatic properties to create data members and accessors would be even better. We manually write these all the time and having the compiler generate them for us would be a productivity boost.
• Extension methods that would enable extending exiting types with new methods without modifying the type itself. This can be be achieve in different ways, but support in the language for this feature means we can extend existing code with new methods without touching it, and call these methods as they were actual member of the class.
• Template type constraints basically what concepts will provide in the future, so I will not insist on this. Current workarounds with enable_if and SFINAE, static_assert and even deleted functions currently exist.
• Events to enable a subject to notify observers that something has happened. Obviously this can be implemented explicitly using existing functionality, having native support for that would simplify writing code and increase productivity.
• Switching on other types than integral types, especially on strings. In general it should be possible to switch on any compile time constant expression. The reason for this is to replace if-else statements with a simpler to write and read switch statement.
• Finally block for a try-catch so we can specify code that should execute regardless of whether an exception occurs or not. This is supposed be achieved by implementing the RAII idiom. Resources should be released properly upon destruction, but the reality is that a lot of code does not use RAII. Having finally blocks would enable us to run clean up code either if an exception occurred or not.
• Static classes, that can contain only static members, and static constructors, that are called before main and have access only to static members of a class (there is actually a proposal for static constructors under discussion for standardization). Helper functions may be implemented as static members of a class, and having the class as static would be a constraint on the class to only contain static members.

I do known and understand the principles of C++ and I know these may look counter intuitive. I know why string is a library container, and why time points are available through a library and why these are general purpose implementations intended to meet many needs. For instance the chrono library is resolution agnostic, which means that in the future clocks will deliver picosecond resolution we won’t need to update the library to benefit from that.

On the other hand the reality is that general purpose implementations lack many features developers use all the time, such as converting a string to upper or lower case. This is available in many languages or string libraries, but not in the standard library string. Yes, we can implement that simply in a helper function, but if extension methods were available we could call such a helper function as it was a member of the string class, which would look, arguably, more natural, and also similar to what is available in other languages.

Another reality is that many developers use more than just one language. Some of these features would enable developers coming from a background of .NET or Java development to get a faster and better grasp at C++.

The most important benefits of these feature would be less and probably more readable code and an increased productivity. There are workarounds for these and, yes, we can live without them. But I do not believe that makes at least some of them unreasonable.

I would like to hear what are the features that you miss the most and see if they also appear on this list.

Hits for this post: 4186 .

## My book on modern C++ programming

I am happy to announce that my book on modern C++ programming called Modern C++ Programming Cookbook, published by Packtpub, can now to pre-ordered. The book will be published around mid 2017, but pre-ordering gives you early access to the content as it is written.

As the title shows, the book is a cookbook with a collection of more than 100 recipes that will either teach you how to use modern C++ language or standard library features or solve common problems you face constantly. The book also covers useful patterns and idioms implemented in modern C++, but also several major testing frameworks. Recipes are exclusively using features from C++11/14/17. Each recipe teaches you how to do something and how that works, all with useful code examples.

What you will learn from the book:

• Get to know about the new core language features and the problems they were intended to solve
• Understand the standard support for threading and concurrency and know how to put them on work for daily basic tasks
• Leverage C++â€™s features to get increased robustness and performance
• Explore the widely-used testing frameworks for C++ and implement various useful patterns and idioms
• Work with various types of strings and look at the various aspects of compilation
• Explore functions and callable objects with a focus on modern features
• Leverage the standard library and work with containers, algorithms, and iterators
• Use the new utility additions to the standard library to solve common problems developers encounter
Hits for this post: 2983 .

## A better date and time C++ library

C++11 added a date and time utility library called chrono, available in namespace std::chrono and header <chrono>. The problem with it is that the library is a general purpose one and therefore lacks many useful features, such as working with dates, weeks, calendars, timezones and other related features. Fortunately, a rich date and time library based on chrono has been created by Howard Hinnant and is available on github. The library is called date and is actually a collection of several small libraries:

• date: the main library, available in header date.h, defines new date and time classes and operations with them. All the other libraries are based on this one.
• timezones: a library for timezones, available in files tz.h/tz.cpp, based on the IANA timezone database
• chrono_io: a library for streaming durations, available in header chrono_io.h
• iso_week: a library that implements the ISO week calendar, available in header iso_week.h
• julian and islamic: libraries that implement the Julian and Islamic calendars, available in headers julian.h and islamic.h

You can find all the necessary documentation on github. Here are several links:

In this article we will look at some examples for working with dates and ISO weeks. This library introduces many new types to handle various date and time representations. Among these we will look at:

• sys_days: A count of days since std::system_clock‘s epoch. This is a time_point with a resolution of a day, and is implicitly convertible to std::system_clock::time_point, that has a much smaller resolution (millisecond or nanosecond), but not the other way around. To go the other way you must use floor().
• year_month_day: A type that holds a day with fields for year, month (1 to 12) and day (1 to 31).
• year_month_weekday: A type that holds a day with fields for year, month (1 to 12), a day of the week (0 to 6), and an index in the range [1, 5] that indicates the number of the week in the month.
• year_weeknum_weekday: A type that hold a year, a weeknum (1 to 53) and a weekday (0 to 6). This can convert implicitly to and from a sys_days.

For using the library we need the following:

• include header date.h and namespaces date and date::literals
• for iso weeks we also need header iso_week.h and namespaces iso_week and iso_week::literals
• NOTICE: The namespaces date::literals and iso_week::literals define types and literal operators with the same name and therefore can lead to name collisions; therefore you should only include them in the scope where you need them.

We will use the following lambda expression to print various dates to the console:

NOTICE: All the ‘today’ and related dates below are based on 2016-10-31.

Let us look at some examples:

• create sys_days objects (including literals):

• create year_month_day objects (including literals):

• creating year_month_weekday literals and converting to year_month_day

• create year_month_day values for today, yesterday and tomorrow

• create year_month_day values for first and last day of the month

Update: The following, as indicated by Howard Hinnant in the comments, can also be used:

• create iso_week literals

• get the iso week number for today

We will look at more utilities and examples in another post.

Hits for this post: 4459 .

## A comparison of two std::transform alternatives revisited

In the previous post I have compared two alternative ways of transforming a string to upper case, both using std::transform: one that modifies an existing string and one that generates a new one by inserting at the end using std::back_inserter. For the second alternative I have presented two implementations, one that does an initial reservation for the newly created string and one that does not.

The curious conclusion of the tests was that the version with reserve was actually slower than the one that did not perform an initial reservation.

The solution was built with Visual Studio 2015 Update 2. As it was later noticed in the comments, the actual cause of that is a Microsoft optimization for std::string by using an array of 16 characters for strings that do not exceed this size and only dynamically allocate memory for larger strings. Since all the strings had a length between 3 and 12 characters, this optimization was used for all strings. Therefore, reserve() dynamically allocated memory that was never used and its execution time only added to the overall time.

To actually be able to test the performance of these two implementations with VC++, the strings should be larger than 16 characters. So I changed the code to generate strings between 17 and 25 characters long.

The results this time were totally different. The 3rd version with initial reserving was more performant than the one that did not do that. It can also be noticed that the more strings need to be transformed the more similar times it takes for all the versions.

 No of strings time v1 time v2 time v3 Percentage of slowdown with v2 Percentage of slowdown with v3 1000 122 219 205 79.5 68.0 10000 1202 2178 2055 81.2 71.0 100000 13563 22758 21431 67.8 58.0 1000000 136160 225669 214149 65.7 57.3 10000000 1368034 2268991 2155969 65.9 57.6 100000000 23090172 27997658 27322888 21.3 18.3

In the chart below with blue it is represented the results for version 2 and with orange the results for version 3 (with initial reservation).

Note: Generating 100 milion strings between 17 and 25 characters require a lot of memory. In my tests it peaked to 13GB. So if you want to run the code you should be aware of this.

Hits for this post: 3871 .

## A comparison of two std::transform alternatives

UPDATE: For an update on the implementation and the conclusions see A comparison of two std::transform alternatives revisited.

I was writing a small utility function to transform a string to uppercase. The obvious solution for that is std::transform, but as I was writing it I realized there are several alternatives:

• transform an existing string, by setting its elements to uppercase one by one
• iterate over an existing string, and insert a copy of its uppercased elements into another string, initially empty, using std::back_inserter

Obviously, the second approach should be slower since it has to deal with buffer reallocations. However, I was curious how slower comparing to the first approach that would be. So I decided to test it.

UPDATE: It has been suggested that in the second version I should make a reserve of the string before using std::back_inserter to add characters to the string. Therefore I added a 3rd version that does that.

This is how I implemented the two version different versions of the helper function:

To test it, I decided to randomly generate strings. The length of the strings and their content is randomly generated. Both functions are tested with the same strings after a copy is initially done.

The results, tested with a 64-bit release build with Visual Studio 2015 Update 2, look like below. Times are in microseconds.

 No of strings time v1 time v2 time v3 Percentage of slowdown with v2 Percentage of slowdown with v3 1000 40 57 64 42.5 60 10000 593 568 637 42.5 53.1 100000 3894 5769 6497 48.2 66.8 1000000 40005 57852 65793 44.6 64.5 10000000 394573 584048 734463 48 86.1 100000000 4298742 6171199 7577972 43.6 76.3

I have run this several times with similar results. The following image shows how much slower the versions using std::back_inserter were comparing with the version that modifies the string directly. With blue it is represented the results for version 2 and with orange the results for version 3 (with initial reservation).

This clearly indicates that using std::back_inserter is slower, and it is actually 30 to 60% slower. However, what has surprized me is that reserving the necessary space for the string before std::back_inserter starts inserting elements is even slower (in some cases it can take twice as much time than version 1). Of course this measures the time to allocate the buffer too, not just the time for transforming the string, but the point here is to profile the entire function, not just the transform operation.

Hits for this post: 4230 .

## Building the 64-bit version of Chromium Embedded Framework on Windows

The Chromium Embedded Framework (CEF for short) is an open source framework for embedding Chromium-based browsers in other applications. The base implementation is targeting C/C++ applications but ports for other languages exist (these include Java, C#, Delphi, Python).

The nightly builds (for various systems and platforms) of CEF are available for download at https://cefbuilds.com/. These include:

• CEF source code necessary to build your apps with
• CEF dynamic and static library files (together with its dependencies) that you must use in your application
• C++ wrappers for the C API
• source code of two sample applications, one called CefSimple and one called CefClient
• symbol files for debugging binary distribution of CEF
• build of CefClient sample app with all dependencies and resources

Building the 64-bit version of the sample applications is not straight forward though. In this article I will show what you have to do make it work.

### Prerequisites

The following prerequisites are necessary:

• Visual Studio 2013
• CMake tools

Notice: Though CMake should be able to generate projects for Visual Studio 2015, I was not able to make it happen. Moreover, the cef_sandbox.lib lib is built with Visual C++ 2013 which means the modules that are linking it should also be built with the same tool set.

You should download the nightly build of the development branch for Windows 64 bit and unzip it.

### Create Visual Studio projects

To create Visual Studio projects run the following command from the CEF’s main folder in a console:

This will create:

• a VC++ 2013 solution called cef.sln in the main folder
• VC++ 2013 project files for libcef_dll, cefsimple, cefclient
• two additional project files called ALL_BUILD and ZERO_CHECK

This is how the content of the CEF folder looks after generating the Visual Studio project and solution files.

This is how the Visual Studio solutions looks.

### Create 64-bit configurations

Though the download is suppose to represent the 64-bit version of the framework, and the DLLs and LIBs in the Debug and Release folder (i.e. the CEF builds and its dependencies) are indeed built for the x64 platform, the generated projects do not have configurations targeting the x64 platform.

What you have to do is:

• create configuration for targeting the x64 platform (by copying the settings from x86)
• change the Output Directory for all projects and configurations to be \$(SolutionDir)\$(Configuration)\ which means the output folder will be the existing Debug or Release folder from the main CEF folder.
• for the libcef_dll project change the Librarian > All Options > Additional options to /machine:X64 %(AdditionalOptions)
• for the cefsimple and cefclient projects change the additional dependencies settings to point to libcef.lib, libcef_dll_wrapper.lib and cef_sandbox.lib, instead of the relative paths as in the project.

This is how the list should look for all platforms and configurations:
• for the cefsimple and cefclient projects add \$(SolutionDir)\$(Configuration)\ to the Library Directories for all configurations and platforms
• modify the Post Build Event for the cefsimple and cefclient projects to no longer copy files from the solution’s Debug and Release folders to the project’s Debug and Release folders.

Initially, the post build event looks like this (for Debug configurations)

It should be changed to look like this (beware at the output folder indicated by outputresource; it should be the Debug\Release folder in the main folder):

### Resources

In the main folder there is a sub-folder called Resources. The entire content of this folder must be copied to the out folders, Debug and/or Release. These files are necessary for the sample applications to run properly.

### Building and running

With all these in place you can build the projects. The build should succeed and the content of the Debug folder for instance should look like below.

You can then run the two sample applications. This is how cefsimple looks.

This is how cefclient looks.

Hits for this post: 10470 .