Efficient Pure Functional Programming in C++ Using Move Semantics


In which I briefly mention what pure functional programming is, explain why this can be slow in C++, and use move semantics to solve that problem. Be warned that this post is a bit longer than usual for this blog, and that it assumes more knowledge of C++11 than my posts usually do.

Pure functional programming is programming without state. In short, functions should not modify their input, not modify local or global state, but return new values instead. Often, we also want to avoid variables completely.

For instance, instead of doing:

void square(vector<int>& v) { /*multiply each element with itself*/ }

void imperative()
{
    vector<int> v = getNumbers();
    square(v);
    doStuffWith(v);
}

we do

vector<int> squared(const vector<int>& v) { /*return a new vector with squared elements*/ }

void functional()
{
    doStuffWith(
        squared(
            getNumbers()));
}

As you might already have noticed, this style results in more copies than the imperative style, which will lead to less efficient code. Depending on the problem you are solving, this might or might not matter, but one of the few real arguments for using C++ is that you have a problem that needs an efficient solution.

Let’s take a look at an example program, translate it from imperative to functional style, and finally use move semantics (explained later) to eliminate the performance hit. For our example, we will compute the root mean square of a function. Wikipedia has a good definition, but in short: Given a list of numbers, square each of them, take the mean of those squares, and return the square root of that number.

First, let’s define some helper functions:

double sum(const std::vector<double>& v)
{
    return std::accumulate(v.begin(), v.end(), 0, std::plus<double>());
}

double mean(const std::vector<double>& v)
{
    return sum(v) / v.size();
}

The square root function already exists as std::sqrt, so we don’t need to define that. The only missing piece is a function computing the square of a vector of numbers. In good old C++, there are two ways of doing this:

vector<int> square(vector<int> v); //(Or the argument could be a const reference)

void square(vector<int>& v);

The first version creates a copy of the vector, containing the squared number. This is perfect for functional code, but makes a copy that might be unnecessary. The second version modifies the argument, which is faster and often seen in imperative code. Since we assume we want efficiency, we’ll go with the second one in the examples that follow.

Here is the full, traditional, stateful solution, including square and a usage example:

    void square(std::vector<double>& v)
    {
        std::transform(v.begin(), v.end(), v.begin(), [](double d) { return d*d; });
    }

    double rms(std::vector<double>& v)
    {
        square(v);
        double the_mean = mean(v);
        double the_rms = std::sqrt(the_mean);
        return the_rms;
    }

    int main()
    {
        std::vector<double> v = {1,2,3};
        double the_rms = rms(v);
        std::cout << the_rms << std::endl;
        return 0;
    }

I won’t go into the full discussion of why functional programming is nice, but with no state there is a whole class of problems we never get into. How often have you not found a bug that was due to some code you didn’t know about mutating some seemingly unrelated state? Also, functions are a lot easier to both test and reason about when the only thing they care about is their input and output.

Let’s have a look at a pure functional alternative:

    std::vector<double> squared(std::vector<double> v)
    {
        std::transform(v.begin(), v.end(), v.begin(), [](double d) { return d*d; });
        return std::move(v);
    }

    double rms(const std::vector<double>& v)
    {
        return std::sqrt(mean(squared(v)));
    }

    int main()
    {
        std::cout << rms({1,2,3}) << std::endl;
        return 0;
    }

As you can see, no state, and no variables except for the function parameters, which we cannot really avoid. The implementation of rms even reads exactly like its mathematical definition, root(mean(squared(numbers))). There is however the issue of the copy being made when squared() is called. (No copy should be made when squared() returns though, due to the return value optimization).

Enter C++11’s move semantics. If you don’t know what move semantics and rvalue references are, the simplest explanation I have come across is this StackOverflow answer. You really should read it through, but if you’re short on time, here is the even quicker intro: If a squared(std::vector v) somehow knew that whoever called that function would never need the original v again, it could just “steal” it instead of making a copy. In the example above, {1,2,3} is a temporary object that can never be referred to again, so instead of copying it into squared, we could just have the internal storage of v point to the same place in memory. And this is exactly what happens with rvalue references.

Rvalue references are denoted by a double ampersand: squared(std::vector&& v), and can only bind to temporaries. Here is the pure functional example again, this time using rvalue references. This version completely avoids copying the vector:

    std::vector<double> squared(std::vector<double>&& v)
    {
        std::transform(v.begin(), v.end(), v.begin(), [](double d) { return d*d; });
        return std::move(v);
    }

    double rms(std::vector<double>&& v)
    {
        return std::sqrt(mean(squared(std::move(v))));
    }

    int main()
    {
        std::cout << rms({1,2,3}) << std::endl;
        return 0;
    }

{1,2,3} is a temporary, and so rms(std::vector&& v) is free to steal its resources without a deep copy. Inside of rms however, v itself is not a temporary. It is a named variable than can be referred to, and thus it would not be safe for squared(std::vector&& v) to steal its resources. We however know that we will never use it again after calling squared(v), so we tell the compiler to go ahead and steal anyway by wrapping it in std::move(). The same is done for the return value in squared().

In the functional examples, the vector that we wanted to compute the root mean square of was a temporary, thus allowing move semantics. But what if we wanted to call rms() from a non-pure part of the code base? Here’s what would happen if the original vector was a normal variable:

    std::vector<double> v = {1,2,3};
    //rms(v); //invalid initialization of reference of type ‘std::vector<double>&&’ from expression of type ‘std::vector<int>’

As you can see, we can no longer use the functional rms(). If we however know that we will not be using the original v again, we could wrap it in std::move() as we did earlier:

    rms(std::move(v)); 

Finally, if that is not an option, we could manually make a copy:

    rms(std::vector<double>(v)); 

In a pure functional program, our functional version of rms would be both fast and fitting the style we’re in. In an imperative program, it would stylistically be a worse fit, but we still wouldn’t loose any performance.

Finally, a few notes:

  • I have not considered to what degree copy elision would achieve the same benefits as move semantics for this example.
  • I decided not to complicate the examples using templates and universal references but that would be an interesting extension.
  • If you haven’t seen move semantics before; It is a general technique that has nothing to do with functional programming. I just think they make a great team.
  • There is a whole lot more to rvalues and move semantics than could be presented here, it is seen as one of the defining features of C++11.

As usual, the code for this blog post is available on GitHub.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.

A Bad(?) Excuse for Private Inheritance


A few weeks ago I introudced private inheritance, and finished with a comment about a common excuse for using it. In this post I give an example of such usage, and discuss whether it is a good idea or not.

Say you are going to write a new class CppInfo, which will print out some information about the C++ language. Here is an example:

class CppInfo
{
public:
    string info()
    {
        return "Language: C++\nCreator : Bjarne Stroustrup\nQuality : ??";
    }
};

Now we need some way to assess the quality of C++, to replace those question marks. Luckily, there exists a class that assesses the quality of a programming language:

class LanguageQuality
{
public:
    virtual ~LanguageQuality() {}

    double quality() const
    {
        return 100.0 / charsForHelloWorld();
    }
protected:
    virtual int charsForHelloWorld() const = 0;
};

As you can see, the only thing we need to do is to create a derived class from LanguageQuality for C++, returning the number of characters required for a C++ Hello, World program.

This is where private inheritance can come in handy. We need access to LanguageQuality::quality(), and we need to override charsForHelloWorld(). If we chose to inherit privately from it in CppQuality, we get both of these, yet none of the members of LanguageQuality will be accessible by the users of that class (as shown in the last post).

Here is a version of CppInfo that inherits privately from LanguageQuality:

class CppInfo_UsingInheritance : private LanguageQuality
{
public:
    string info()
    {
        return "Language: C++\nCreator : Bjarne Stroustrup\nQuality : " + to_string(quality());
    }
private:
    int charsForHelloWorld() const
    {
        return string("#include <iostream>\nint main() { std::cout << "Hello World"; }").size();
    }
};

I have to admit, this looks pretty neat. The alternative is to create a new class whose only responsibilty is overriding charsForHelloWorld():

class CppQuality : public LanguageQuality
{
protected:
    int charsForHelloWorld() const 
    {
        return string("#include <iostream>\nint main() { std::cout << \"Hello World\"; }").size();
    }
};

And then have this as a member in CppInfo:

class CppInfo_UsingComposition 
{
public:
    string info()
    {
        return "Language: C++\nCreator : Bjarne Stroustrup\nQuality : " + to_string(cppQuality.quality());
    }
private:
    CppQuality cppQuality;
};

Now you have two classes instead of one, and 18 lines of code instead of 13. Which solution is best? I am not sure, so let’s have a look at the arguments:

The solution using inheritance is smaller. All the code is in one place, so it is easy to get an overview. We have however coupled our class CppInfo very tightly to LanguageQuality, even though their responsibilities aren’t directly related. Considering the single responsibility principle, CppInfo is about printing general info about C++, whereas LanguageQuality is about computing the quality of a programming language.

I think the principle that provides the tipping point for me in this example, is that every piece of your software should have a single reason to change. Say we want to change how we compute the quality of a language (the number of characters required for Hello, World just doesn’t cut it anymore). This would require a change to LanguageQuality. We would then probably need to update all its derived classes. And to change a class, you really should understand all its responsibilities, invariants and effects. All the other code in CppInfo has nothing to do with the change we are making, so we shouldn’t have to worry about it. Also, if we want to change what information we print out about C++ (say we want to add the publication year of the latest language standard), we want to understand how info is printed, not how the quality is computed.

Again, in a small example like this, it might not matter much, but in a larger example it will. And what starts out small has a nasty tendency to grow, so you’d better care about design from the very start.

Just for fun, here is the result after adding JavaInfo and PythonInfo:

Language: C++
Creator : Bjarne Stroustrup
Quality : 1.587302
Language: Java
Creator : James Gosling
Quality : 0.970874
Language: Python
Creator : Guido van Rossum
Quality : 5.263158

Unsurprisingly, we beat Java, but lose to Python.

Now I am interested to hear your thoughts, which solution would you choose, and why?

As usual, the code for this blog post is available on GitHub.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.

Notes From My GoogleTest Demo


I recently gave a demo of GoogleTest at Kjeller Software Community / Oslo C++ Users Group. These are the notes from my demo. My apologies to those who did not attend, these might not make much sense unless you saw the demo.

Installation

See my post about installation and setup of GoogleTest in your project.

Test types

TEST(TestCaseName, TestName)
A single test TestName belonging to the TestCaseName test case. The TEST macro converts this into class TestCaseName_TestName

TEST_F(TestFixtureName, TestName)
A single test TestName belonging to the TestFixtureName test case, which uses a fixture. The TEST_F macro converts this into class TestFixtureName_TestName : public TestFixtureName. You need to implement the TestFixtureName : public ::testing::Test class also.

TEST_P(TestFixtureName, TestName)
A single parametrized test TestName belonging to the TestFixtureName test case, which uses a fixture with a parametrized interface. You need to implement the TestFixtureName : public ::testing::WithParamInterface class also. Use GetParam() to get the parameter, and INSTANTIATE_TEST_CASE_P to instantiate tests.

Finally remember that you can use SetUp() and TearDown(), but might just as well use the plain constructor and destructor. A reason to use TearDown() instead of the destructor is if it might throw an exception (which destructors should not do).

Assertions

Here are some examples of assertions:
ASSERT_TRUE
ASSERT_FALSE
ASSERT_EQ
ASSERT_DOUBLE_EQ
ASSERT_LT
ASSERT_THROW

You can also write your own assertion functions:
AssertionResult predicateFunction(...)

Or just write a void function that does all the asserts internally:
void assertWhatever()

Some final tips

Use one test project per production project, for instance NoFlyListTest for NoFlyList. This makes it easy to find the tests for a project. If the rest of your code is decoupled, it might also speed up linking a lot, since you only need to link the test project, and not your entire solution. This especially helps if you are doing TDD, in which you will typically compile and link several times a minute.

Write short tests, and only test one thing per test. This will make it easy to figure out what went wrong when tests break in the future.

Write tests before you implement the code that passes them. This will verify that the test didn’t pass just by accident. It will also let you see how the failing test looks like, so you can make sure it is self-explanatory enough that someone will understand what went wrong when it breaks.

Don’t be a terrorist, you’ll end up in a bad place.

Source Code

If you want to have a look at the code from my Kjeller Software Community demo, it is available on GitHub.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.

Installing and Using GoogleTest with Visual Studio


Important note: This blog post is one of the top hits on Google for “googletest visual studio”. It is however quite old, and might no longer reflect the best way to use GoogleTest with Visual Studio. 

Google C++ Testing Framework (aka. GoogleTest) is a unittesting framework for C++. This post describes how to install it, and set it up in your project. I am using GoogleTest 1.6.0 here, but other versions should be similar. The instructions provided are for Visual Studio 2010, but 2012 should be exactly the same.

Installation

First of all, download the latest version from the GoogleTest download page, and unzip it. Inside, you will find a directory called msvc, which contains the Visual Studio solutions:

In this directory, you will find two solutions, gtest.sln, and gtest-md.sln. Which one you want depends on whether you are using a static or dynamic runtime. If you are unsure which one to use, take a look in your existing solution:

If you are using the DLL version of the runtime, use the gtest-md.sln solution, otherwise use gtest.sln. Before you open the solution though, make sure it is not read only, as Visual Studio will want to convert it to your version:

Open the solution you want, agree to convert the solution. Make sure you build it both in Debug and Release versions. The resulting libraries end up in gtest-1.6.0\msvc\gtest\Debug and gtest-1.6.0\msvc\gtest\Release, respectively. This is a good time to copy the libraries to wherever you keep libraries for your projects. The files you will need are gtestd.lib and gtest_maind.lib from the Debug directory, and gtest.lib and gtest_main.lib from the Release directory. In addition, you need all the headers from gtest-1.6.0\include. (Of course, you could just copy the entire gtest-1.6.0 directory and not care about which files you need.)

Setup for Your Project

I suggest to use one test project per production project. This makes it easy to find the tests you are looking for. Also, if your code is nicely decoupled, you might be able to link just these two projects, and not your entire solution. This can speed up your “red-green-refactor” cycle considerably. Finally, this makes it easy to exclude your test code from the final binary you ship. Here is an example from my Kjeller Software Community presentation:

Set the following properties for your test project:

  • Make sure to set up the test project to use the same runtime library as your production project (MT / MTd / MD / MDd).
  • Add an additional include directory c:\wherever\you\put\gtest\include
  • Add an additional library directory c:\wherever\you\put\the\libs
  • Under Linker -> Input , add a dependency on gtest.lib for your Release configuration, and gtestd.lib for your Debug configuration. Unless you want to write your own main function that runs all the tests, also add a dependency on gtest_main.lib / gtest_maind.lib, respectively. This will add a main() method to your project which discovers and runs all the tests.
  • Under Properties -> Linker -> System, set SubSystem to Console, to keep the test-window open after the tests have run.

Also make sure that your test project depends on the production project:

And that’s it! Now you can start writing and running tests, but since the documentation already describes that pretty well, I will not go into that here. If you want to have a look at the code from my Kjeller Software Community demo, it is available on GitHub.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.

New Software Community, and Google Test Demo


Together with Håkon K. Olafsen, I founded Kjeller Software Community earlier this summer. Our first meetup is due this Wednesday (September 26). I will do a demo of Google C++ Testing Framework, aka. GoogleTest, and afterwards we will have a few beers and chat about programming and all things geeky. Hopefully we will also get some good suggestions for future events and meetups. The meetup will happen at Klimt pub in Lillestrøm, at 6:00 pm.

This meetup is done in cooperation with Oslo C++ Users Group, of which I am also a member. If you are into C++, and live in the greater Oslo area, that group is also highly recommended.

Notes from the talk, and a blog post about Google Test will be up later this week.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter. You can also follow Kjeller Software Community on Twitter.

Private Inheritance


In which I introduce private inheritance, but discourage its use.

When inheriting in C++, you normally see

class Derived : public Base {};

It’s almost as if public is synonymous to inherits from. But did you know there is also private inheritance, and why you (probably) don’t see it a lot?

When inheriting publicly from a base class, all base members will be accessible from the derived class, with the same accessibility as in the base class. Given these classes:

class Base
{
public:
    void pub() {}
private:
    void priv() {}
};

class DerivedPublic : public Base
{
};

class DerivedPrivate : private Base
{
};

Public inheritance results in this:

    DerivedPublic derivedPublic;
    derivedPublic.pub();
    //derivedPublic.priv(); //error: ‘void Base::priv()’ is private

Whereas private inheritance results in this:

    DerivedPrivate derivedPrivate;
    //derivedPrivate.pub(); //error: ‘void Base::pub()’ is inaccessible
    //derivedPrivate.priv(); //error: ‘void Base::priv()’ is private

So why would you want to inherit privately? To allow Derived to access the public members of Base, without exposing them to the users of Derived.

Inside the class, the members are accessible:

class DerivedPrivate2: private Base
{
public:
    void foo() { pub(); }
};

But outside, they are not:

    DerivedPrivate2 derivedPrivate2;
    derivedPrivate2.foo();
    //derivedPrivate2.pub(); //error: ‘void Base::pub()’ is inaccessible

But wait a minute, doesn’t this look a whole lot like the good old inheritance (is-a) vs. composition (has-a)? It does indeed! Private inheritance is really a has-a. And in most circumstances composition and private inheritance are interchangeable. However, since inheritance results in stronger coupling, the general recommendation is to choose composition instead. Here is how DerivedPrivate2 would look using composition:

class NotDerived
{
public:
    void foo() { b.pub(); }
private:
    Base b;
};

Now you may be thinking: “But I read somewhere that you need to use private inheritance if you want to override a virtual Base method?” You probably did, and I’ll get back to that in the next post.

As usual, the code for this blog post is available on GitHub.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.

C++ Puzzle #1: Initialization Order


Time for another puzzle! What is the output of this program?


class Parent
{
public:
    Parent(int p=0.0) : p(p)
    {
        cout << "Parent(" << p << ")" << endl;
    }

    int p;
};

class Member
{
public:
    Member(int m=0.0) : m(m)
    {
        cout << "Member(" << m << ")" << endl;
    }

    Member& operator=(const Member& rhs)
    {
            cout << "Member is copied" << endl;
            m = rhs.m;
            return *this;
    }

    int m;
};

class Derived : public Parent
{
public:
    Derived() : foo(10), bar(foo*2)
    {
        Parent(7);
        m = Member(42);
    }

    int bar;
    int foo;
    Member m;
};


int main()
{
    Derived d;
    cout << d.p << " " << d.foo << " " << d.bar << " " << d.m.m << endl;
}

Answer: Undefined behaviour! Which means it could output whatever, crash at any point, or format your hard drive. Can you spot the source of the undefined behaviour? Hint: Look for the use of an uninitialized variable.

Did you see that the order of foo and bar in the initializer list is not in the same order as their declarations? Members are always initialized in the order of declaration, not in the order in the initialization list. This means bar is initialized before foo, using an uninitialized foo to compute its value. If you compile with all warnings enabled (always a good idea), your compiler should warn you about this. For instance, g++ tells me:

main.cpp: In constructor ‘Derived::Derived()’:
main.cpp:29:9: warning: ‘Derived::foo’ will be initialized after [-Wreorder]
main.cpp:28:9: warning:   ‘int Derived::bar’ [-Wreorder]
main.cpp:22:5: warning:   when initialized here [-Wreorder]

Next question then, what is the likely output of this program on a real compiler? On my Ubuntu 12.04 using g++ 4.6, I get:

   
Parent(0)
Member(0)
Parent(7)
Member(42)
Member is copied
0 10 8393920 42  

Lets’ walk through what happens here.

  • 1: Derived inherits from Parent. C++ guarantees that all parent objects are fully constructed before the constructor of the derived class is invoked, so the first thing that happens is that the default constructor of Parent is called. (Did I fool you with Parent(7); in the constructor though? That line will just create a local object that is never used. Had I moved it to the initializer list, it would have been used instead of the default constructor.)
  • 2: Before the body of Derived‘s constructor, all its members will be initialized. Since we don’t specifically initialize Member m in the initializer list, it is first automatically default constructed, and then re-assigned in the body of the constructor (as seen in line 5 of the output).
  • 3: On line 34 of the program, we create a local Parent object which is never used. Maybe we meant to set p to 7, but put the Parent() call in the wrong place?
  • 4-5: Now another Member is constructed, and copy assigned to m. All this re-construction and copying could have been avoided if we had moved the call Member(42) to the initializer list.
  • 6: Finally, we have a look at the resulting values of Derived‘s members:
    • p is 0, not 7 as we maybe meant it to be, as explained in 1.
    • foo is 10, hopefully as expected.
    • bar is 8393920, due to the use of the uninitialized foo, as explained earlier. This is entirely by chance, and should not be relied on! Your program might just as well crash, or do something worse.

Finally let’s clean up the program and see what happens. We reorder the declarations of foo and bar, and move all initializations to the initializer list:

ERROR: Couldn't open file: [Errno 2] No such file or directory: '/home/anders/Documents/code/blog/initialization/main2.cpp'

Now the program is well defined, and free of repeated constructors and copying. Here is the output:

Parent(7)
Member(42)
7 10 20 42

Much better! Full source here.

As usual, the code for this blog post is available on GitHub.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.