Found a really cool use of private inheritance in C++ in this answer on stackoverflow: http://stackoverflow.com/a/676725/422131.
More details to follow.
More details to follow.
Read more!
Wednesday, September 10, 2014
Saturday, August 23, 2014
7 useful features in C++14
C++14 is an enhancement over C++11. Here are a few features that are immediately useful:
std::make_unique- a factory function for unique_ptr (which should be the most popular smart pointer) akin tostd::make_sharedforstd::shared_ptr(which shouldn't be the most popular smart pointer).#include <memory> class Foo { public: Foo(int n) { ... }; ... }; auto fooPtr = std::make_unique<Foo>(10);std::cbeginandstd::cend, applied to STL containers give you const_iterators.std::shared_timed_mutex, a laboost::shared_mutex- a very important addition if you use a fair bit of synchronization. This provides the multiple-reader single-writer (MRSW) type of abstractions.-
Getting elements from a tuple by type (if there is a unique element of that type in the tuple).
std::tuple<int, double, std::string> threeElems = std::make_tuple(1, 2.0, "Foo"); auto strFoo = std::get<std::string>(threeElems);
This works, but would have failed had there been two elements of type std::string in the tuple. -
Note
how we had to write the type of threeElems in the last example. If we
had used auto instead, its type would be deduced as std::tuple
<int, char const*, double>
because
std::make_shareddeduces the type of the returned tuple using the types of the passed arguments. If you wanted to use a string literal whose type would be deduced as std::string, you must use an s suffix like this:
auto threeElems = std::make_tuple(1, 2.0, "Foo"s); auto strFoo = std::get<std::string>(threeElems);
-
Generic lambdas - essentially lambdas with a very succinct syntax that can be reused for multiple type. Takes a lot of crud away from writing lambdas.
std::vector<foo> vec; std::for_each(vec.begin(), vec.end(), [](auto& elem) { std::cout << elem << '\n'; });
The key is the use of theautokeyword for the parameter types. You could use multiple parameters, all declared auto, whose types are independently deduced. How does this really help? First, you don't have to write:[](Foo& elem) { std::cout << elem << '\n'; }Also, you could cache a lambda in a generic context with minimal syntactic noise and reuse it for multiple types. Consider this:auto elemPrint = [](const auto& elem) { std::cout << elem << '\n'; }; std::for_each(vecOfInts.begin(), vecOfInts.end(), elemPrint); std::for_each(vecOfStrs.begin(), vecOfStrs.end(), elemPrint);where vecOfInts, vecOfStrs, etc. all contain elements of different, unrelated type. -
Being able to write function with an
auto return type, without any trailing decltype to compute the type.
In C++11, you would write something like:
auto foo(int x, double y) -> decltype(x + y) { return x + y; }You can now simply write:
auto foo(int x, double y) { return x + y; }
There are several more changes but these stand out in terms of immediate usefulness.
Read more!
Saturday, December 14, 2013
Can you write an assignment operator?
This would be the first in hopefully a series of blog posts to talk of C++11 features and libraries that matter. But in this article, I wouldn't pick up a whole lot of C++11. Instead I shall lay some groundwork first, talking about exception safety in a very informal way and looking at the nothrow swap idiom for copy assignment. Along the way, we'll use some C++11 features (like auto) and libraries (like std::unique_ptr) with obvious syntax and simple usage.
Consider a simple class that wraps a character buffer.
What would it mean to copy an object of the above class? What would it mean to assign one object of this class to another? What would the behaviour be of such code:
And of such?
Without rolling out your own copy constructor and copy assignment operator, disastrous. In the first case the default copy constructor would create object es as a shallow copy of the object en. That would mean that after construction, es and en would both have their data member buffer pointing to the same address. When the scope in which both of these objects are created is exited, es would be destroyed first, followed by en. The destructor of es would have deallocated all the heap-memory pointed to by buffer in one fell swoop, and soon after, en's destructor would try doing the same - and disaster should strike.
The second case is worse in some respects, except that it shouldn't matter: on line 3, as es is assigned to en, the en.buffer starts pointing to the same location as the es.buffer. But en.buffer already pointed to an address at the head of a block of bytes on the heap that had "Hello" in it. Now that both en.buffer and es.buffer point to another location (with "Hola" in it), all references to the "Hello" bytes are lost. This program doesn't have any hopes of being able to track down, and deallocate when it had to, the buffer with "Hello". We have a leak, but it shouldn't matter. Shortly afterwards, when en and es both fall out of scope, es's destructor gets called followed by en's, and as in the case of copy construction above, disaster strikes.
The remedy is well-known - roll out your own copy-constructor and copy-assignment operator.
Now copy construction creates a copy of the buffer for each new object created and copy assignment takes care of deallocating the older buffer before reallocating the new buffer and copying content. Congratulations. You've just fixed a couple of bad crashes in the code. Bad news, if you wrote this code in an interview, they'll offer you a good C++ book and not the job. Porque? Que pasa? Because you goofed up the copy assignment. For what would happen if the call to std::copy threw? Ok, in this rather unimaginatively contrived example, it would likely not. But in general, we carry out several steps in the assignment: deletion of the old buffer, allocation of a new buffer and then copying. If the allocation of the new buffer fails, you have no way to get back and salvage your older data. Nor if the copy fails after that. In simple terms, the code we've written is not exception safe.
The key problem is losing the previous buffer before the new buffer is ready. If we first create the new buffer separately, then cache the old buffer, assign the new buffer and finally delete the old buffer, we've made a start.
Three points to note:
#include <iostream>
#include <cstring>
#include <algorithm>
class MyString
{
public:
// constructor
explicit MyString(const char *str) : buffer(NULL)
{
if (str && str[0] != '\0') {
auto ln = strlen(str); // C++11: auto -
// compiler determines correct type for ln
buffer = new char[ln + 1];
std::copy(str, str + ln, buffer); // more general than strncpy
}
}
// destructor
~MyString()
{
delete []buffer;
}
size_t len() const
{
if (buffer) {
return strlen(buffer);
} else {
return 0;
}
}
std::ostream& print(std::ostream& os)
{
return (os << buffer);
}
private:
char *buffer;
};
What would it mean to copy an object of the above class? What would it mean to assign one object of this class to another? What would the behaviour be of such code:
MyString en("Hello");
MyString es(en);
And of such?
MyString en("Hello");
MyString es("Hola");
en = es;
Without rolling out your own copy constructor and copy assignment operator, disastrous. In the first case the default copy constructor would create object es as a shallow copy of the object en. That would mean that after construction, es and en would both have their data member buffer pointing to the same address. When the scope in which both of these objects are created is exited, es would be destroyed first, followed by en. The destructor of es would have deallocated all the heap-memory pointed to by buffer in one fell swoop, and soon after, en's destructor would try doing the same - and disaster should strike.
The second case is worse in some respects, except that it shouldn't matter: on line 3, as es is assigned to en, the en.buffer starts pointing to the same location as the es.buffer. But en.buffer already pointed to an address at the head of a block of bytes on the heap that had "Hello" in it. Now that both en.buffer and es.buffer point to another location (with "Hola" in it), all references to the "Hello" bytes are lost. This program doesn't have any hopes of being able to track down, and deallocate when it had to, the buffer with "Hello". We have a leak, but it shouldn't matter. Shortly afterwards, when en and es both fall out of scope, es's destructor gets called followed by en's, and as in the case of copy construction above, disaster strikes.
The remedy is well-known - roll out your own copy-constructor and copy-assignment operator.
class MyString
{
public:
// constructor
// destructor
// copy constructor
MyString(const MyString& that)
{
auto ln = that.len();
if (ln) {
buffer = new char[ln + 1];
std::copy(that.buffer, that.buffer + ln, buffer);
}
}
// copy assignment
MyString& operator = (const MyString& that)
{
auto ln = that.len();
if (this != &that) {
// release earlier content
delete [] buffer;
// and mimic copy construction
buffer = new char[ln + 1];
std::copy(that.buffer, that.buffer + ln, buffer);
}
return *this;
}
// rest of the class
};
Now copy construction creates a copy of the buffer for each new object created and copy assignment takes care of deallocating the older buffer before reallocating the new buffer and copying content. Congratulations. You've just fixed a couple of bad crashes in the code. Bad news, if you wrote this code in an interview, they'll offer you a good C++ book and not the job. Porque? Que pasa? Because you goofed up the copy assignment. For what would happen if the call to std::copy threw? Ok, in this rather unimaginatively contrived example, it would likely not. But in general, we carry out several steps in the assignment: deletion of the old buffer, allocation of a new buffer and then copying. If the allocation of the new buffer fails, you have no way to get back and salvage your older data. Nor if the copy fails after that. In simple terms, the code we've written is not exception safe.
The key problem is losing the previous buffer before the new buffer is ready. If we first create the new buffer separately, then cache the old buffer, assign the new buffer and finally delete the old buffer, we've made a start.
class MyString
{
...
MyString& operator = (const MyString& that)
{
auto ln = that.len();
if (this != &that) {
// allocate and set aside
char *new_buffer = new char[ln + 1];
std::copy(that.buffer, that.buffer + ln, new_buffer);
// cache the old
char *old_buf = buffer;
// assign the new
buffer = new_buffer;
// delete the old
delete [] old_buf;
}
return *this;
}
...
};
But problems still abound. If copy threw, we'd be left with a leak. Besides, we are still dealing with a single member and this scheme quickly gets out of hand if you deal with two or more members with similar requirements. We can make a small improvement here.
class MyString
{
...
MyString& operator = (const MyString& that)
{
if (this != &that) {
// Use RAII
MyString tmpStr(that.buffer);
// swap the two pointers
std::swap(buffer, tmpStr.buffer);
// et voila!
}
return *this;
}
...
};
If an exception is thrown before line 8, nothing changes. If one is thrown after line 8, tmpStr.buffer is deallocated by a call to its destructor. The call to swap cannot throw. Once that call is complete, ownership of buffers have been exchanged and the destructor of tmpStr takes care of deallocating the older buffer of the current object (this). If we are dealing with multiple members, extending this logic requires a little extra effort. Define a swap member function, or specialize std::swap for MyString, and implement it with no-throw guarantees. A set of pointer swaps for one should be able to provide that guarantee. Your code would then look like:
namespace std
{
void swap(MyString& lhs, MyString& rhs)
{
if (&lhs != &rhs) {
char *tmp = lhs.buffer;
lhs.buffer = rhs.buffer;
rhs.buffer = tmp;
}
}
}
class MyString
{
...
MyString& operator = (const MyString& that)
{
if (this != &that) {
// Use RAII
MyString tmpStr(that.buffer);
// swap the two objects
std::swap(*this, tmpStr); // or swap(tmpStr) if swap were a member
// et voila!
}
return *this;
}
...
};
This is the standard idiom for writing copy assignments using no-throw swaps and on another day I would have happily concluded this article here. Alas! We still have a problem. If you've been attentive you may have already noticed it. What if the MyString constructor threw at line 20? It mighty well can, if say the call to std::copy threw. Ok, I hear you - it won't in the case of this example. But we are performing two operations in the constructor - allocation and assignment of values to the cells of the allocated buffer. If the latter operation throws, the destructor of MyString won't get called and we'd be leaking the memory allocated for buffer. The fool-proof way to deal with the lack of atomicity of this kind of resource allocation plus initialization issues is to harness RAII in some form to protect the smallest units of allocation. We'll use a C++11 smart pointer to do the trick for us. Here is the full listing.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <memory>
class MyString
{
public:
// constructor
explicit MyString(const char *str)
{
if (str && str[0] != '\0') {
auto ln = strlen(str);
buffer.reset(new char[ln + 1]);
std::copy(str, str + ln, buffer.get());
}
}
// copy constructor
MyString(const MyString& that)
{
auto ln = that.len();
if (ln) {
buffer.reset(new char[ln + 1]);
std::copy(that.buffer.get(), that.buffer.get() + ln, buffer.get());
}
}
// destructor
~MyString()
{}
size_t len() const
{
if (buffer) {
return strlen(buffer.get());
} else {
return 0;
}
}
// copy assignment
MyString& operator = (const MyString& that)
{
if (this != &that) {
// copy the right side
MyString tmp(that);
// relinquish our data's ownership
// to tmp, and acquire tmp's data
swap(tmp);
}
return *this;
// let tmp go out of scope and release
// our older data in its destructor
}
// nothrow swap
void swap(MyString& rhs)
{
buffer.swap(rhs.buffer);
}
std::ostream& print(std::ostream& os)
{
return (os << buffer.get());
}
private:
// C++11 smart pointer to make resource
// management of buffer exception-safe
std::unique_ptr<char[]> buffer;
};
int main()
{
MyString m1("Hello"), m2("Hola");
MyString m3(m1);
m1 = m2;
m1.print(std::cout) << std::endl;
m2.print(std::cout) << std::endl;
m3.print(std::cout) << std::endl;
}
Three points to note:
- The member buffer is now a std::unique_ptr smart pointer (actually its std::unique_ptr
specialization for arrays). - If std::copy throws on line 15 or 25 in the constructor, the destructor of buffer is called correctly and there is no leak.
- std::unique_ptr provides a no-throw swap function which can be used to perform the copy assignment.
Read more!
Sunday, October 21, 2012
Enforcing source code formatting guidelines
Last few days there has been an uptick in interest in programming processes at the workplace. Folks believe code-reviews need to be taken more seriously and we should revisit all the written guidelines which have existed for eons. Such guidelines include a relatively elaborate and fairly well-written coding standard among other things.
I spent the second half of last week creating a checklist for code review and in the process came up against all sorts of emotions about coding standards. These ranged from utter neutrality and mild intolerance to rabid disgust. The common refrain on guidelines about checking indentation, padding, etc was to give them the least priority. Unfortunately code reviews are done by most people in one pass and they have to filter each line through all the standard concerns of the reviewer - from correct functionality to correct padding and indentation. One of my colleagues suggested if we could use the IDE for enforcing formatting. It set me off on a wild-goose hunt for cool scripts / plugins for C++ on vim. I managed to find one (google.vim) and customized it a fair bit but figured that it was good for indentation and that's about it.
After grappling with the vim scripting syntax and trying out some obscenely brute-force approaches to formatting code via vim (involving vim scripting, unreadable regexps and all sorts of command-chaining) I figured I wasn't even half-way through. A little googling finally brought up a couple of code formatters: uncrustify and Artistic Style. I finally picked up the latter because of the former's documentation poverty. All impressed with astyle and for good reason:
Ok, #2 doesn't just work like that. You have to either create a file called .astylerc in your home directory (on Unix) or use set of command-line switches. I'd recommend the first approach. Here is a sample .astylerc file.
One would typically run astyle on the entire code base once and commit it to the repository. Later on it should be run on each source file each time it is committed to the repository. The only point of discomfort with tools of this type is the fact that they edit your code to fix indentation, padding and other formatting issues. I would much rather have a tool like Google's cpplint.py which points out issues but leaves it to the user to fix them. However the style enforced by cpplint.py is hard-coded to follow Google's own recommendations which differs in some matters from what we follow in our organization. So somebody has to read and edit cpplint.py to suit our purposes.
Astyle works on Windows I but haven't tried it yet. But it works perfectly on Linux and I am impressed with how little I had to try to create a .astylerc file that enforces our coding standard. After this very no one should complain about the reviewer fussing over whitespace.
I spent the second half of last week creating a checklist for code review and in the process came up against all sorts of emotions about coding standards. These ranged from utter neutrality and mild intolerance to rabid disgust. The common refrain on guidelines about checking indentation, padding, etc was to give them the least priority. Unfortunately code reviews are done by most people in one pass and they have to filter each line through all the standard concerns of the reviewer - from correct functionality to correct padding and indentation. One of my colleagues suggested if we could use the IDE for enforcing formatting. It set me off on a wild-goose hunt for cool scripts / plugins for C++ on vim. I managed to find one (google.vim) and customized it a fair bit but figured that it was good for indentation and that's about it.
After grappling with the vim scripting syntax and trying out some obscenely brute-force approaches to formatting code via vim (involving vim scripting, unreadable regexps and all sorts of command-chaining) I figured I wasn't even half-way through. A little googling finally brought up a couple of code formatters: uncrustify and Artistic Style. I finally picked up the latter because of the former's documentation poverty. All impressed with astyle and for good reason:
- Offers a fairly granular set of options to pad expressions, indent statements, place brackets, add or remove blank lines, etc.
- Is very simple to use. Here's how you format a source file from the command line:
$ astyle proj/src/lib/mysource.cpp - Has a concise but really useful documentation.
Ok, #2 doesn't just work like that. You have to either create a file called .astylerc in your home directory (on Unix) or use set of command-line switches. I'd recommend the first approach. Here is a sample .astylerc file.
One would typically run astyle on the entire code base once and commit it to the repository. Later on it should be run on each source file each time it is committed to the repository. The only point of discomfort with tools of this type is the fact that they edit your code to fix indentation, padding and other formatting issues. I would much rather have a tool like Google's cpplint.py which points out issues but leaves it to the user to fix them. However the style enforced by cpplint.py is hard-coded to follow Google's own recommendations which differs in some matters from what we follow in our organization. So somebody has to read and edit cpplint.py to suit our purposes.
Astyle works on Windows I but haven't tried it yet. But it works perfectly on Linux and I am impressed with how little I had to try to create a .astylerc file that enforces our coding standard. After this very no one should complain about the reviewer fussing over whitespace.
Read more!
Thursday, November 04, 2010
Return your objects by value (at least sometimes)
Starting where we left a year and a half back (and I swear I had no time for the blog in this intervening period), we'll look at temporaries again, but in a slightly different light. We saw in that article that it's a great idea to eliminate temporaries of non-POD types (or more correctly, types with non-trivial copy semantics) as far as possible. One big advantage of eliminating temporaries is the elimination of redundant copying from a temporary to a named instance which is how a lot of temporaries inevitably end up. Common ways in which temporaries get created are when objects are returned by value from a function call, and also when a function (say foo) is invoked in-place in the argument list of the invocation of another function (say bar) - and thus the return value of foo() is passed to bar(). Some of these cases are illustrated in the following code:
Now suppose we were to rewrite the above code to eliminate temporaries. There are a few different ways, but let's try a fairly simple approach:
In the above code, we have eliminated the pass by value of a Fud object to bar(...) but foo(...) still returns a temporary by value. Here is an enhancement:
This time there don't seem to be any temporaries and consequently no redundant copying. But the code is no longer simple. At the least, you cannot do something like bar(foo(...)) any more - nesting calls is a natural algebraic operation used to compose functions but the elimination of references takes that ability away from us. Strictly speaking, with Boost shared_ptr, we could eliminate this limitation (how? left as an exercise to the reader, an author's exclusive prerogative). But it still means that we have to incur the cost of dynamic memory allocation. Again, dynamic memory allocation is not necessarily evil - sometimes, it is even more welcome than allocating a large stack based object. But the overall readability of code has suffered as well.
What do we do? Well, it depends. A good idea is to start by passing temporaries back by value. Now don't cross your eyes - what you just read is exactly what I said and there is a little something that the C++ standard allows (without mandating) and most standard compilers implement as an optimization, which makes this possible. It is called Copy Elision and in a special form, Return Value Optimization or RVO for short.
Copy elision simply refers to elimination of redundant copying, if at all possible. For example, consider the following code:
What's happening there? A Fud instance called obj is initialized from a temporary Fud object created through Fud(1). Normally, we would expect that Fud's constructor will be invoked to create a Fud object with an initialization parameter value of 1. Next, the instance called obj will be created and initialized through a call to its copy-constructor which will copy the state of the temporary object to obj. However, it is not hard to see that the only purpose of the temporary object is to help initialize the obj instance. This code could have been written in a much simpler way as:
There would have been no calls necessary to the copy constructor of obj, nor would there be any temporary instance to destruct. The behaviour of the code would have been exactly the same (unless of course the copy constructor or destructor had side-effects - always a bad idea). Copy elision is the inbuilt optimization in the compiler which causes code like this:
to generate the equivalent of code like this:
and thus prevent needless copying. An interesting special case is Return Value Optimization (RVO). It is best illustrated with the following example:
Look at line 40 above. The function make_vec() returns a vector which is copied to the vector vec - what looks like copy initialization. Since the contained type of the vector is TestClass, you'd expect the TestClass instances to be copied, first time when they are enqueued in the vector inside make_vec (line 31) and again when the returned temporary vector from make_vec is used for copy-initialization of vec at line 40. That would be conformant behaviour, but that's often not the behaviour you get. Running on gcc 4.3.2 on OpenSuSE gave me this output:
This clearly shows that there is no copying during copy-initialization of vec - in other words there is no copy-initialization. This is an example of Copy Elision - a special case known as RVO. Internally, the compiler might generate code that arranges for a reference to vec on line 40 to be passed to the function make_vec, and obviate the local vector inside make_vec so that all push_back operations happen on this reference instead. A slight change to the above code can completely disable Copy Elision / RVO, as illustrated below:
I got this:
Quite clearly, the copy-initialization takes place and has not been optimized away.
The big advantage of RVO is that the syntax of function calls can be made to match the semantics of the mapping that the function represents. The return value rather than an out-parameter is a return value. This also allows for nested function calls, a natural algebraic expression of functional composition.
Therefore, depending on how the return value of function is going to be used - it might be a good idea to return an object by value.
Read more!
Fud foo(int i) // Fud is a copiable class
{
return Fud(i); // Temporary created
}
void bar(Fud);
...
bar(foo(1)); // Temporary passed to bar
Fud f = foo(2);
...
Now suppose we were to rewrite the above code to eliminate temporaries. There are a few different ways, but let's try a fairly simple approach:
Fud foo(int i) // Fud is a copiable class
{
return Fud(i); // Temporary created
}
void bar(const Fud&);
...
bar(foo(1)); // const-reference to temporary, no copying
Fud f = foo(2);
...
In the above code, we have eliminated the pass by value of a Fud object to bar(...) but foo(...) still returns a temporary by value. Here is an enhancement:
void foo(int i, Fud *&f) // Fud is a copiable class
{
f = new Fud(i);
}
void bar(const Fud&);
...
Fud *pfud = NULL;
foo(2, pfud);
bar(*pfud); // const-reference to temporary, no copying
...
This time there don't seem to be any temporaries and consequently no redundant copying. But the code is no longer simple. At the least, you cannot do something like bar(foo(...)) any more - nesting calls is a natural algebraic operation used to compose functions but the elimination of references takes that ability away from us. Strictly speaking, with Boost shared_ptr, we could eliminate this limitation (how? left as an exercise to the reader, an author's exclusive prerogative). But it still means that we have to incur the cost of dynamic memory allocation. Again, dynamic memory allocation is not necessarily evil - sometimes, it is even more welcome than allocating a large stack based object. But the overall readability of code has suffered as well.
What do we do? Well, it depends. A good idea is to start by passing temporaries back by value. Now don't cross your eyes - what you just read is exactly what I said and there is a little something that the C++ standard allows (without mandating) and most standard compilers implement as an optimization, which makes this possible. It is called Copy Elision and in a special form, Return Value Optimization or RVO for short.
Copy Elision
Copy elision simply refers to elimination of redundant copying, if at all possible. For example, consider the following code:
Fud obj = Fud(1);
What's happening there? A Fud instance called obj is initialized from a temporary Fud object created through Fud(1). Normally, we would expect that Fud's constructor will be invoked to create a Fud object with an initialization parameter value of 1. Next, the instance called obj will be created and initialized through a call to its copy-constructor which will copy the state of the temporary object to obj. However, it is not hard to see that the only purpose of the temporary object is to help initialize the obj instance. This code could have been written in a much simpler way as:
Fud obj(1);
There would have been no calls necessary to the copy constructor of obj, nor would there be any temporary instance to destruct. The behaviour of the code would have been exactly the same (unless of course the copy constructor or destructor had side-effects - always a bad idea). Copy elision is the inbuilt optimization in the compiler which causes code like this:
Fud obj = Fud(1);
to generate the equivalent of code like this:
Fud obj(1);
and thus prevent needless copying. An interesting special case is Return Value Optimization (RVO). It is best illustrated with the following example:
#include <vector>
#include <string>
#include <iostream>
using std::vector;
using std::string;
using std::cout;
using std::endl;
struct TestClass
{
TestClass(int i) : i_(i)
{}
TestClass(const TestClass& tc) : i_(tc.i_)
{
cout << "Copied." << endl;
}
private:
int i_;
};
vector<TestClass> make_vec()
{
vector<TestClass> vec;
vec.reserve(20);
cout << "Starting populating vector." << endl;
for (int i = 0; i < 10; i++) {
vec.push_back(TestClass(i));
}
cout << "Vector populated." << endl;
return vec;
}
int main()
{
vector<TestClass> vec = make_vec();
}
Look at line 40 above. The function make_vec() returns a vector which is copied to the vector vec - what looks like copy initialization. Since the contained type of the vector is TestClass, you'd expect the TestClass instances to be copied, first time when they are enqueued in the vector inside make_vec (line 31) and again when the returned temporary vector from make_vec is used for copy-initialization of vec at line 40. That would be conformant behaviour, but that's often not the behaviour you get. Running on gcc 4.3.2 on OpenSuSE gave me this output:
Starting populating vector.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Vector populated.
This clearly shows that there is no copying during copy-initialization of vec - in other words there is no copy-initialization. This is an example of Copy Elision - a special case known as RVO. Internally, the compiler might generate code that arranges for a reference to vec on line 40 to be passed to the function make_vec, and obviate the local vector inside make_vec so that all push_back operations happen on this reference instead. A slight change to the above code can completely disable Copy Elision / RVO, as illustrated below:
return vec;
}
int main()
{
vector<TestClass> vec;
vec = make_vec();
}
I got this:
Starting populating vector.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Vector populated.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Quite clearly, the copy-initialization takes place and has not been optimized away.
The big advantage of RVO is that the syntax of function calls can be made to match the semantics of the mapping that the function represents. The return value rather than an out-parameter is a return value. This also allows for nested function calls, a natural algebraic expression of functional composition.
Therefore, depending on how the return value of function is going to be used - it might be a good idea to return an object by value.
Read more!
Monday, February 02, 2009
Jargon Time: L-values, R-values and Temporaries
As promised here are a few fairly basic examples of C++ jargon, demystified, here in this article. We start looking at basics of C++ expressions: l-values, r-values and temporaries. The concepts are simple, but important, and would be used in later columns of this (Jargon) series.
When we write code, we express action and intent through well-formed expressions that conform to a broad syntax. Some of this action involves moving data around, some of it involves carrying out a more complex operation - and most involve both. For example:
Show line numbers
The above code involves both moving data around, and carrying out some action. In the second line, the literal double 2.0 is assigned to the double variable number. In this context number is an l-value expression - because it allows modification of the value it holds, when used on the left hand side of an assignment expression.
The expression 2.0 on the other hand can only be used to assign values to expressions such as number - in other words it can only be used on the right hand side of assignment expressions, never on the left hand side. It can also be used in function return statements. Such expressions are called r-values.
At this point we have three small observations to make:
1. An r-value can never be used on the left hand side of an assignment operation.
2. An l-value in very many cases can be used on the right hand side of assignment operations also. In this case, it simply degenerates to the value it contains. For example:
Show line numbers
In the above code snippet, on the third line, the expression number is used as an r-value and degenerates to the value contained in the l-value expression number.
Some l-values cannot be used as r-values. For example, in the above code snippet, the expression double anotherNumber is an l-value expression, but we cannot write code like:
double aThirdNumber = (double anotherNumber = 2.0);
Language rules do not allow this. So you have an example of an l-value expression that cannot degenerate to an r-value expression.
3. l-values can also be used in function return statements. However, whether it is treated as an l-value or simply degenerates to an r-value depends on the return type of the function. If a function returns a non-const reference or pointer to an object, the function call can be considered as an l-value expression. That's essentially because the return value of the function is an l-value. For example:
Show line numbers
In the above CheckedIntArray class, operator[](int) can actually be used as an l-value expression because it returns a reference to an element in the underlying array. This enables use to write code like this:
Show line numbers
In the above, the expression my_array[0] = 15; is equivalent to my_array.operator[](0) = 15;.
Many complex expressions are r-values. As well as a few simple ones:
Show line numbers
Arrays are r-values although individual elements in an array are not. Of course this does not apply to a pointer being used with an array syntax. Thus:
Show line numbers
Finally, let it be said that all expressions in C++ are either l-value or r-value expressions.
Related to the concept of r-values is the concept of temporaries. In fact temporaries are r-values (without all r-values being temporaries). Consider the following example:
Show line numbers
Here the expression 5 + 8/m is a temporary. This is a relatively simple temporary - possibly one that would only exist in the registers of the CPU. However, it is possible, and quite common, to have temporaries on the stack. The important thing to understand is that temporaries are unnamed values, which are created in the context of an expression and whose life time is limited to the period of evaluation of that expression. Consider the following expression:
string str = string("Hola amigos!");
The right hand side expression creates a temporary string object, and it is then copied to a local variable called str. Once the control of the executing program reaches past the semi-colon terminating this line of code, the temporary object is gone. Only str, containing a copy of it, exists.
There is one exception to this rule and it deals with references. In the last expression, if instead of a string variable on the left, we had a string reference, things would be a little different:
const string& str = string("Hola amigos!");
First of all, if you see we've had to add a const to the reference. We could not have had a non-const reference to a temporary. This is always the case, as you can see below:
Show line numbers
Since all temporaries are r-values, it is clear a non-const reference cannot refer to them. But, the exception that I referred to is in the life time of the temporary when a (const) reference refers to it. In this case, the temporary persists till the reference is in scope, and not just till the end of the statement that created the reference.
References are often created for function return values, although most optimizing compilers would eliminate the creation of these temporaries if the return value of the function was not assigned to any specific object. In general, reducing the number of temporaries that is created by a program is a good strategy for optimization, and to some extent, the compiler already does it.
Since all temporaries are r-values, it is clear a non-const reference cannot refer to them. But, the exception that I referred to is in the life time of the temporary when a (const) reference refers to it. In this case, the temporary persists till the reference is in scope, and not just till the end of the statement that created the reference.
References are often created for function return values, although most optimizing compilers would eliminate the creation of these temporaries if the return value of the function was not assigned to any specific object. In general, reducing the number of temporaries that is created by a program is a good strategy for optimization, and to some extent, the compiler already does it.
As a final example of how temporaries are generated, and where we can run into trouble with them if we are not careful, I present a piece of code I have seen written in several places (including products I have worked on).
Show line numbers
Can you spot the trouble with the above code. The trouble is that the member function std::string str() const of the std::stringstream class returns a temporary string. But in the expression sout.str().c_str(), we get a reference to the const char* pointer member of the returned temporary string and we copy it to the variable called str. As soon as this statement is executed, the temporary that was created as a result of the call to sout.str() is destroyed. But we still have a dangling pointer referring to its internal char * string, which is invalid for all good money. Needless to say, the last line above can even crash the program itself.
In the next edition of the Jargon column, we'll look at Namespace lookups and the Interface Principle. Keep watching, for more jargons demystified.
Read more!
L-values and R-values
When we write code, we express action and intent through well-formed expressions that conform to a broad syntax. Some of this action involves moving data around, some of it involves carrying out a more complex operation - and most involve both. For example:
Show line numbers
double number = 0.0;
number = 2.0;
double square_root = ::sqrt(number);
The above code involves both moving data around, and carrying out some action. In the second line, the literal double 2.0 is assigned to the double variable number. In this context number is an l-value expression - because it allows modification of the value it holds, when used on the left hand side of an assignment expression.
The expression 2.0 on the other hand can only be used to assign values to expressions such as number - in other words it can only be used on the right hand side of assignment expressions, never on the left hand side. It can also be used in function return statements. Such expressions are called r-values.
At this point we have three small observations to make:
1. An r-value can never be used on the left hand side of an assignment operation.
2. An l-value in very many cases can be used on the right hand side of assignment operations also. In this case, it simply degenerates to the value it contains. For example:
Show line numbers
double number = 0.0;
number = 2.0;
double anotherNumber = number;
In the above code snippet, on the third line, the expression number is used as an r-value and degenerates to the value contained in the l-value expression number.
Some l-values cannot be used as r-values. For example, in the above code snippet, the expression double anotherNumber is an l-value expression, but we cannot write code like:
double aThirdNumber = (double anotherNumber = 2.0);
Language rules do not allow this. So you have an example of an l-value expression that cannot degenerate to an r-value expression.
3. l-values can also be used in function return statements. However, whether it is treated as an l-value or simply degenerates to an r-value depends on the return type of the function. If a function returns a non-const reference or pointer to an object, the function call can be considered as an l-value expression. That's essentially because the return value of the function is an l-value. For example:
Show line numbers
template<int size>
struct CheckedIntArray {
int& operator[](int index) {
if (index >=0 && index < size) {
return array_[index];
}
throw IndexOutOfBoundsException; // some exception
}
private:
int array_[size];
};
In the above CheckedIntArray class, operator[](int) can actually be used as an l-value expression because it returns a reference to an element in the underlying array. This enables use to write code like this:
Show line numbers
CheckedIntArray<16> my_array;
my_array[0] = 15;
In the above, the expression my_array[0] = 15; is equivalent to my_array.operator[](0) = 15;.
Many complex expressions are r-values. As well as a few simple ones:
Show line numbers
int i = 0;
++i; // r-value expression
Arrays are r-values although individual elements in an array are not. Of course this does not apply to a pointer being used with an array syntax. Thus:
Show line numbers
int arr[32] = {0};
int arr2[32] = {1};
arr[0] = 5; // arr[0] is an l-value
// the following is illegal
// arr = arr2; // arr is an r-value
Finally, let it be said that all expressions in C++ are either l-value or r-value expressions.
Temporaries
Related to the concept of r-values is the concept of temporaries. In fact temporaries are r-values (without all r-values being temporaries). Consider the following example:
Show line numbers
int m = 4;
int n = 5 + 8/m;
Here the expression 5 + 8/m is a temporary. This is a relatively simple temporary - possibly one that would only exist in the registers of the CPU. However, it is possible, and quite common, to have temporaries on the stack. The important thing to understand is that temporaries are unnamed values, which are created in the context of an expression and whose life time is limited to the period of evaluation of that expression. Consider the following expression:
string str = string("Hola amigos!");
The right hand side expression creates a temporary string object, and it is then copied to a local variable called str. Once the control of the executing program reaches past the semi-colon terminating this line of code, the temporary object is gone. Only str, containing a copy of it, exists.
There is one exception to this rule and it deals with references. In the last expression, if instead of a string variable on the left, we had a string reference, things would be a little different:
const string& str = string("Hola amigos!");
First of all, if you see we've had to add a const to the reference. We could not have had a non-const reference to a temporary. This is always the case, as you can see below:
Show line numbers
const int& r = 5;
const double& s = 2.0;
Since all temporaries are r-values, it is clear a non-const reference cannot refer to them. But, the exception that I referred to is in the life time of the temporary when a (const) reference refers to it. In this case, the temporary persists till the reference is in scope, and not just till the end of the statement that created the reference.
References are often created for function return values, although most optimizing compilers would eliminate the creation of these temporaries if the return value of the function was not assigned to any specific object. In general, reducing the number of temporaries that is created by a program is a good strategy for optimization, and to some extent, the compiler already does it.
Since all temporaries are r-values, it is clear a non-const reference cannot refer to them. But, the exception that I referred to is in the life time of the temporary when a (const) reference refers to it. In this case, the temporary persists till the reference is in scope, and not just till the end of the statement that created the reference.
References are often created for function return values, although most optimizing compilers would eliminate the creation of these temporaries if the return value of the function was not assigned to any specific object. In general, reducing the number of temporaries that is created by a program is a good strategy for optimization, and to some extent, the compiler already does it.
As a final example of how temporaries are generated, and where we can run into trouble with them if we are not careful, I present a piece of code I have seen written in several places (including products I have worked on).
Show line numbers
using std::string;
using std::stringstream;
using std::cout;
using std::endl;
...
int x = 0;
double f = 1.6;
stringstream sout;
sout << "Some data values streamed: " << x << "|" << f;
const char *str = sout.str().c_str();
cout << str << endl; // this will likely print garbage
Can you spot the trouble with the above code. The trouble is that the member function std::string str() const of the std::stringstream class returns a temporary string. But in the expression sout.str().c_str(), we get a reference to the const char* pointer member of the returned temporary string and we copy it to the variable called str. As soon as this statement is executed, the temporary that was created as a result of the call to sout.str() is destroyed. But we still have a dangling pointer referring to its internal char * string, which is invalid for all good money. Needless to say, the last line above can even crash the program itself.
In the next edition of the Jargon column, we'll look at Namespace lookups and the Interface Principle. Keep watching, for more jargons demystified.
Read more!
Sunday, February 01, 2009
Parlez vous le C++?
Recently I was thinking back on my days of trying to learn C++ by reading the Usenet groups comp.lang.c++.moderated and comp.std.c++. If someone asks me the best source to learn C++ from, I would always refer to these two places (and perhaps the Boost mailing list even though it is a little more Boost-focussed). Note that I said the best source to "learn" C++ - not merely "read" it (for which here are the books).
I'll explain what I mean by that (and as usual, I'll get a bit philosophical before cutting to the chase). I read C++ on my own, almost every written word of it that I read, alone - not a soul around even to discuss, not a teacher around to cast an impression. And yet no learning is complete unless an impression of that knowledge has been cast on us - this is true for every field of learning - even learning to memorize the English alphabet. The reason must be that this impression is cast on us through multiple senses - sight and sound, if not more. On the other hand, reading a tome is one dimensional - sight. It is here that the Usenet discussion boards and other mailing lists step in. While you still only read, you read direct discussions, arguments, brain-storms, doubts, misgivings, biases - it is a lot more real than reading a chapter on C++ polymorphism. It is what eggs you on to introspect - identify with the views expressed, or refute them; in other words, your C++ perspective is built here and that is what I meant when I said "learning".
Usenet in particular provided this motivation - I have seen posts by Bjarne Stroustrup, Scott Meyers, Andrei Alexandrescu, Herb Sutter, Jim Coplien, Steve Dewhurst, Andrew König, you name one, I'd have read his posts. The debates would go on for days together, even weeks, in lists that grew deep and wide with time. I was a mere reader - my occasional two-pence in the middle of debates would be politely answered but I had not the knowledge or understanding of the language to make a serious impact. Half the time, I groped through the standard or Stroustrup's book trying to figure out what is a "temporary" or where are "incomplete types" allowed, what is the meaning of "SFINAE" or what is the "Liskov Substitution Principle". You could be excused for wondering "Is this a programming language we are reading or a Theory of Banach algebras?". I certainly did - but it was part of C++'s charm (oh! geek) - for a wannabe-mathematician-turned-nobody, this was a nice feel-good aberration in a language I wanted to "speak". But coming back to the point - this meant I had to have a basic vocabulary ready, and a familiarity with a C++ alphabet soup before I could start communicating effectively in real C++ terms. C++ is tough and exacting, it requires discipline and knowledge - and it was not defined by a Sun or a Microsoft. I plan to put up a set of articles that would help build the awareness and concepts around the C++ jargons. Happy reading!
Read more!
I'll explain what I mean by that (and as usual, I'll get a bit philosophical before cutting to the chase). I read C++ on my own, almost every written word of it that I read, alone - not a soul around even to discuss, not a teacher around to cast an impression. And yet no learning is complete unless an impression of that knowledge has been cast on us - this is true for every field of learning - even learning to memorize the English alphabet. The reason must be that this impression is cast on us through multiple senses - sight and sound, if not more. On the other hand, reading a tome is one dimensional - sight. It is here that the Usenet discussion boards and other mailing lists step in. While you still only read, you read direct discussions, arguments, brain-storms, doubts, misgivings, biases - it is a lot more real than reading a chapter on C++ polymorphism. It is what eggs you on to introspect - identify with the views expressed, or refute them; in other words, your C++ perspective is built here and that is what I meant when I said "learning".
Usenet in particular provided this motivation - I have seen posts by Bjarne Stroustrup, Scott Meyers, Andrei Alexandrescu, Herb Sutter, Jim Coplien, Steve Dewhurst, Andrew König, you name one, I'd have read his posts. The debates would go on for days together, even weeks, in lists that grew deep and wide with time. I was a mere reader - my occasional two-pence in the middle of debates would be politely answered but I had not the knowledge or understanding of the language to make a serious impact. Half the time, I groped through the standard or Stroustrup's book trying to figure out what is a "temporary" or where are "incomplete types" allowed, what is the meaning of "SFINAE" or what is the "Liskov Substitution Principle". You could be excused for wondering "Is this a programming language we are reading or a Theory of Banach algebras?". I certainly did - but it was part of C++'s charm (oh! geek) - for a wannabe-mathematician-turned-nobody, this was a nice feel-good aberration in a language I wanted to "speak". But coming back to the point - this meant I had to have a basic vocabulary ready, and a familiarity with a C++ alphabet soup before I could start communicating effectively in real C++ terms. C++ is tough and exacting, it requires discipline and knowledge - and it was not defined by a Sun or a Microsoft. I plan to put up a set of articles that would help build the awareness and concepts around the C++ jargons. Happy reading!
Read more!
Wednesday, August 13, 2008
Aliasing pointers: using "weakness" to strengthen your code
In one of my earlier articles introducing programming with Boost libraries, I had demonstrated some simple techniques using boost::shared_ptr to share dynamically allocated object instances across scopes, and manage the life cycle of such objects effectively. This was an important step in the direction of eliminating memory leaks. But this was not a complete answer to all forms of memory leaks. This article helps you distinguish between "owning" and "aliasing" semantics for pointers and introduces another class from Boost's smart pointer stable - the boost::weak_ptr. Although not a smart pointer itself, the weak_ptr adds important capability that is vital in handling memory issues and thread safety of objects.
Imagine that you are building a linked list, and you decide to store the "head" node as a shared_ptr<Node> and encapsulate inside this node, the life cycle management of all the nodes in the entire list. That way, when the "head" node goes out of scope, all the other nodes are automatically deleted. How can you do it? Well, the head pointer stores a shared_ptr<Node> pointing to the first node, the first node stores a shared_ptr<Node> pointing to the second node, and so on.
Here is the code, and it works.
This works remarkably well, and by now your penchant for using shared_ptr and RAII is seeing you write elegant code and wish away memory leaks. And then you are asked to enhance your linked list to a doubly linked list. With a deft, touch you make the necessary changes - and you are up and running again ...
... except that you have a memory leak. Believe it or not, what I promised a couple of articles ago was a fib - you can leak memory without even so much as nibbling on a pointer, and in spite of having wrapped all your heap memory in shared_ptr. Run it and you'll not see any of the messages from the destructor of Node. Come to think of it and you'll know the reason.
In the function getList, initially, the nodes head, next1 and next2 each have a reference count of 1 (at line 22, 23 and 24 respectively). Next at line 26, next1 has its ref-count bumped up to 2. In the following line 27, next2 has its ref-count bumped up to 2. So far so good - the real fun starts now. In the next line 28, head has its ref-count bumped to 2, and finally next1 has its ref-count bumped to 3. When this function returns, each of the Smart pointers have their reference counts decreased by 1. But head is copied as a return value - so the decrement nullifies, and when we reach main function at line 35, its reference count remains 2. At this point, the reference count of next1 and next2 are 2 and 1 respectively - but these objects are no longer in scope - completely encapsulated by head. At the end of the main function's scope, the ref-count of head will drop back a notch to 1 - it will not get to 0 - necessary for its internal pointer to get "destructed" and trigger the destruction of its subsequent nodes.
What caused the problem? We only introduced three lines of code - lines 11, 28 and 29 - so the problem would have to be here in these three lines.
Why did all hell break lose? Because, we used the shared_ptr indiscriminately. The shared_ptr implements a "shared ownership" idiom. In this case, head "owns" the next1 node - meaning that before head is completely "destructed", it would have ensured complete "destruction" of next1. But next1 does not own head - it only has an alias to head, in the form of the member prev. But by making it into a shared_ptr<Node>, we have unwittingly made next1 the owner of head. So we hit the chicken-and-egg problem. To reiterate what we just said about ownership semantics - before head is completely "destructed", it should ensure complete "destruction" of next1, and before next1 is completely "destructed", it should ensure complete "destruction" of head. Of course that's an impossible scenario. So we need a different construct for handling the semantics of an aliasing pointer. Here is the code example again with some changes that work reasonably well.
At this point of time, you decide to remove the first node of the list head. As part of the process, you must do something like this:
The statement at line 6, is crucial because if prev is not set to 0 at this point, an accidental dereferencing of new_head->prev at a later point in the code will bomb. At the end of the scope, at line 7, the head goes out of scope and is "destructed". What if this automatically set the prev member pointing to it to be NULL. Then we could afford to forget to write new_head->prev = 0, without facing any dire consquences.
The boost::weak_ptr is tailor-made for the purpose shown here - it models a "non-owning alias" which is automatically set to a null state when the object it points to is destructed. For this, weak_ptr always works in conjunction with a shared_ptr, and always points to an object via the shared_ptr that owns it. The following example should make all this clear:
The weak_ptr maintains a reference to a shared_ptr owning the object. But it does not bump the reference count of a shared_ptr - therefore any number of weak_ptr's can point to a shared_ptr, without affecting its life cycle in anyway. If the shared_ptr goes out of scope and the underlying object is destructed - the weak_ptr's are automatically "updated" about this change through the reference to the shared_ptr that it maintains.
In an informal way, weak_ptr's are to shared_ptr's, what soft links are to hard links on a Unix file system.
You can check the state of the underlying object through the weak_ptr, using the weak_ptr::expired() member function. You can also construct an owning reference - a shared_ptr which contributes to the reference count of the original shared_ptr - through the weak_ptr::lock() member function. This can indirectly be used to check the same condition as weak_ptr::expired() does. To understand that - look at the final example here:
The lock method is particularly crucial when sharing an object across threads. Some threads might only have an aliasing reference to the shared object in the form of a weak_ptr. This can be used to great effect. At any time when such a thread needs to share ownership of this object - it can call lock on the weak_ptr. It will get a non-null shared_ptr only if the object is still valid, and otherwise it will get a null shared_ptr.
Notice that the weak_ptr provides no ways of dereferencing the underlying pointer through it. So there are no overloaded -> or * operators for example. If you need to use these operators - use the lock method to try and get a shared_ptr and then apply these methods on the shared_ptr. In fact - a weak_ptr is not a smart pointer - I call it a "smarter" pointer.
Read more!
Imagine that you are building a linked list, and you decide to store the "head" node as a shared_ptr<Node> and encapsulate inside this node, the life cycle management of all the nodes in the entire list. That way, when the "head" node goes out of scope, all the other nodes are automatically deleted. How can you do it? Well, the head pointer stores a shared_ptr<Node> pointing to the first node, the first node stores a shared_ptr<Node> pointing to the second node, and so on.
Here is the code, and it works.
#include <iostream>
#include <boost/shared_ptr.hpp>
using std::cout;
using std::endl;
using boost::shared_ptr;
struct Node {
int n_;
shared_ptr<Node> next;
Node(int n = 0) : n_(n) {
}
~Node() {
cout << "~Node() invoked for " << n_ << endl;
}
};
shared_ptr<Node> getList() {
shared_ptr<Node> head( new Node(0) );
shared_ptr<Node> next1( new Node(1) );
shared_ptr<Node> next2( new Node(2) );
head->next = next1;
next1->next = next2;
return head;
}
int main() {
shared_ptr<Node> head = getList();
if ( head )
cout << "Got head" << endl;
return 0;
}
This works remarkably well, and by now your penchant for using shared_ptr and RAII is seeing you write elegant code and wish away memory leaks. And then you are asked to enhance your linked list to a doubly linked list. With a deft, touch you make the necessary changes - and you are up and running again ...
#include <iostream>
#include <boost/shared_ptr.hpp>
using std::cout;
using std::endl;
using boost::shared_ptr;
struct Node {
int n_;
shared_ptr<Node> next;
shared_ptr<Node> prev;
Node(int n = 0) : n_(n) {
}
~Node() {
cout << "~Node() invoked for " << n_ << endl;
}
};
shared_ptr<Node> getList() {
shared_ptr<Node> head( new Node(0) );
shared_ptr<Node> next1( new Node(1) );
shared_ptr<Node> next2( new Node(2) );
head->next = next1;
next1->next = next2;
next1->prev = head;
next2->prev = next1;
return head;
}
int main() {
shared_ptr<Node> head = getList();
if ( head )
cout << "Got head" << endl;
return 0;
}
... except that you have a memory leak. Believe it or not, what I promised a couple of articles ago was a fib - you can leak memory without even so much as nibbling on a pointer, and in spite of having wrapped all your heap memory in shared_ptr. Run it and you'll not see any of the messages from the destructor of Node. Come to think of it and you'll know the reason.
In the function getList, initially, the nodes head, next1 and next2 each have a reference count of 1 (at line 22, 23 and 24 respectively). Next at line 26, next1 has its ref-count bumped up to 2. In the following line 27, next2 has its ref-count bumped up to 2. So far so good - the real fun starts now. In the next line 28, head has its ref-count bumped to 2, and finally next1 has its ref-count bumped to 3. When this function returns, each of the Smart pointers have their reference counts decreased by 1. But head is copied as a return value - so the decrement nullifies, and when we reach main function at line 35, its reference count remains 2. At this point, the reference count of next1 and next2 are 2 and 1 respectively - but these objects are no longer in scope - completely encapsulated by head. At the end of the main function's scope, the ref-count of head will drop back a notch to 1 - it will not get to 0 - necessary for its internal pointer to get "destructed" and trigger the destruction of its subsequent nodes.
What caused the problem? We only introduced three lines of code - lines 11, 28 and 29 - so the problem would have to be here in these three lines.
Why did all hell break lose? Because, we used the shared_ptr indiscriminately. The shared_ptr implements a "shared ownership" idiom. In this case, head "owns" the next1 node - meaning that before head is completely "destructed", it would have ensured complete "destruction" of next1. But next1 does not own head - it only has an alias to head, in the form of the member prev. But by making it into a shared_ptr<Node>, we have unwittingly made next1 the owner of head. So we hit the chicken-and-egg problem. To reiterate what we just said about ownership semantics - before head is completely "destructed", it should ensure complete "destruction" of next1, and before next1 is completely "destructed", it should ensure complete "destruction" of head. Of course that's an impossible scenario. So we need a different construct for handling the semantics of an aliasing pointer. Here is the code example again with some changes that work reasonably well.
#include <iostream>
#include <boost/shared_ptr.hpp>
using std::cout;
using std::endl;
using boost::shared_ptr;
struct Node {
int n_;
shared_ptr<Node> next;
shared_ptr<Node> *prev;
Node(int n = 0) : n_(n) {
}
~Node() {
cout << "~Node() invoked for " << n_ << endl;
}
};
shared_ptr<Node> getList() {
shared_ptr<Node> head( new Node(0) );
shared_ptr<Node> next1( new Node(1) );
shared_ptr<Node> next2( new Node(2) );
head->next = next1;
next1->next = next2;
next1->prev = &head;
next2->prev = &next1;
return head;
}
int main() {
shared_ptr<Node> head = getList();
if ( head )
cout << "Got head" << endl;
return 0;
}
At this point of time, you decide to remove the first node of the list head. As part of the process, you must do something like this:
int main() {
shared_ptr<Node> new_head;
{
shared_ptr<Node> head = getList();
new_head = head->next;
new_head->prev = 0;
}
return 0;
}
The statement at line 6, is crucial because if prev is not set to 0 at this point, an accidental dereferencing of new_head->prev at a later point in the code will bomb. At the end of the scope, at line 7, the head goes out of scope and is "destructed". What if this automatically set the prev member pointing to it to be NULL. Then we could afford to forget to write new_head->prev = 0, without facing any dire consquences.
The boost::weak_ptr is tailor-made for the purpose shown here - it models a "non-owning alias" which is automatically set to a null state when the object it points to is destructed. For this, weak_ptr always works in conjunction with a shared_ptr, and always points to an object via the shared_ptr that owns it. The following example should make all this clear:
#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>
using std::cout;
using std::endl;
using boost::shared_ptr;
using boost::weak_ptr;
struct Node {
int n_;
shared_ptr<Node> next;
weak_ptr<Node> prev;
Node(int n = 0) : n_(n) {
}
~Node() {
cout << "~Node() invoked for " << n_ << endl;
}
};
shared_ptr<Node> getList() {
shared_ptr<Node> head( new Node(0) );
shared_ptr<Node> next1( new Node(1) );
shared_ptr<Node> next2( new Node(2) );
head->next = next1;
next1->next = next2;
next1->prev = head;
next2->prev = next1;
return head;
}
int main() {
shared_ptr<Node> head = getList();
if ( head )
cout << "Got head" << endl;
return 0;
}
The weak_ptr maintains a reference to a shared_ptr owning the object. But it does not bump the reference count of a shared_ptr - therefore any number of weak_ptr's can point to a shared_ptr, without affecting its life cycle in anyway. If the shared_ptr goes out of scope and the underlying object is destructed - the weak_ptr's are automatically "updated" about this change through the reference to the shared_ptr that it maintains.
In an informal way, weak_ptr's are to shared_ptr's, what soft links are to hard links on a Unix file system.
You can check the state of the underlying object through the weak_ptr, using the weak_ptr::expired() member function. You can also construct an owning reference - a shared_ptr which contributes to the reference count of the original shared_ptr - through the weak_ptr::lock() member function. This can indirectly be used to check the same condition as weak_ptr::expired() does. To understand that - look at the final example here:
#include <iostream>
#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>
using std::cout;
using std::endl;
using boost::shared_ptr;
using boost::weak_ptr;
struct Node {
int n_;
shared_ptr<Node> next;
weak_ptr<Node> prev;
Node(int n = 0) : n_(n) {
}
~Node() {
cout << "~Node() invoked for " << n_ << endl;
}
};
shared_ptr<Node> getList() {
shared_ptr<Node> head( new Node(0) );
shared_ptr<Node> next1( new Node(1) );
shared_ptr<Node> next2( new Node(2) );
head->next = next1;
next1->next = next2;
next1->prev = head;
next2->prev = next1;
return head;
}
int main() {
shared_ptr<Node> new_head;
weak_ptr<Node> alias;
{
shared_ptr<Node> head = getList();
new_head = head->next;
alias = head;
}
assert(alias.expired());
alias = new_head;
shared_ptr<Node> new_head2 = alias.lock();
assert(new_head2.use_count() == 2); // because new_head and new_head2 share ownership
return 0;
}
The lock method is particularly crucial when sharing an object across threads. Some threads might only have an aliasing reference to the shared object in the form of a weak_ptr. This can be used to great effect. At any time when such a thread needs to share ownership of this object - it can call lock on the weak_ptr. It will get a non-null shared_ptr only if the object is still valid, and otherwise it will get a null shared_ptr.
Notice that the weak_ptr provides no ways of dereferencing the underlying pointer through it. So there are no overloaded -> or * operators for example. If you need to use these operators - use the lock method to try and get a shared_ptr and then apply these methods on the shared_ptr. In fact - a weak_ptr is not a smart pointer - I call it a "smarter" pointer.
Read more!
Sunday, August 03, 2008
Expression Templates Demystified: Part 2
In this article, we would see how the use of templates can simplify and generalize the Expression Functors code, and improve performance by eliminating virtual functions.
In the example from the previous segment of this article, the Expression abstract base class represented the family of all types that could be used to represent different kinds of expressions. Two specific classes, Variable and Constant, represented the leafs of an expression tree - numeric literals and single variable names. These could be combined to form other expressions - generally represented by the ComplexExpression class. All these classes implemented the interface defined by the Expression abstract base class.
We now plan to switch from dynamic polymorphism to template driven static polymorphism. For example, given classes with a common interface but without a common base class, like the ones below:
Show line numbers
we can wrap them using a class template that has a similar interface as these:
Show line numbers
This enforces that AllFoo can only be instantiated with such classes which have the bar() method in their public interface. Thus we write the following alternate definitions:
Show line numbers
Here Expr is a class that can encapsulate all expression objects, like the ones of type Constant or Variable below.
Show line numbers
Finally, a class to represent non-terminal, complex expressions:
Show line numbers
We have just carried over the definition of the ComplexExpression class from the previous article and made it into a template class. The operator classes like Add, Subtract, Multiply and Divide should continue to work unchanged. Guess what, we just have to define the operator overloads (for +, -, * and /) and we will be done with defining our framework of algebraic expression.
Now, we would want to write expressions such as:
In the above, x is a Variable, 3 should generate a Constant, x + 3 should result in a ComplexExpr<Variable, Constant>. Further, x*x is a ComplexExpr<Variable, Variable> and (x*x+3)*(x+3) is a ComplexExpr<ComplexExpr< ComplexExpr<Variable, Variable>, Constant>, ComplexExpr<Variable, Constant> >. One can trace the template parameter types as sub-trees of the class template ComplexExpression.
Clearly, to write an expression like x+3, we need an overload of operator+ between a Variable and an integer. To write an expression like (x*x+3)*(x+3) - we need an operator* between two ComplexExpressions. To write something like, x+Constant(3), we need an overload of operator+ between Variable and Constant. Now, just as we defined the basic operators on Expression in the previous article, we could do the same on the Expr class template here, instead of overloading each operator for different combinations of types. For example:
Show line numbers
The other operators are not very difficult to write, following the above code. However, turns out that while these do take care of operators between complex expressions as well as Variables and Constants, they cannot handle real number or integer literals. To handle real number literals, we define the following overload pairs for each operator.
Show line numbers
These take care of all cases - except for a small glitch which we can pepare to live with. We can write such expressions as:
but not ones like:
If you have to be able to do this, add additional overloads like:
Show line numbers
Show line numbers
If you have any trouble understanding and compiling the code, drop me a message.
Read more!
In the example from the previous segment of this article, the Expression abstract base class represented the family of all types that could be used to represent different kinds of expressions. Two specific classes, Variable and Constant, represented the leafs of an expression tree - numeric literals and single variable names. These could be combined to form other expressions - generally represented by the ComplexExpression class. All these classes implemented the interface defined by the Expression abstract base class.
We now plan to switch from dynamic polymorphism to template driven static polymorphism. For example, given classes with a common interface but without a common base class, like the ones below:
Show line numbers
struct Foo {
void bar() {
// implementation
}
};
struct Foo2 {
void bar() {
// implementation
}
};
we can wrap them using a class template that has a similar interface as these:
Show line numbers
template<class F>
struct AllFoo {
AllFoo(F& f) : f_(f) {}
void bar() {
f_.bar();
}
};
This enforces that AllFoo can only be instantiated with such classes which have the bar() method in their public interface. Thus we write the following alternate definitions:
Show line numbers
template<class E>
struct Expr {
Expr(E& e) : e_(e) {
}
double operator() (double d) {
return e_(d);
}
E e_;
};
Here Expr is a class that can encapsulate all expression objects, like the ones of type Constant or Variable below.
Show line numbers
struct Constant {
Constant(double d) : d_(d) { }
Constant(int d) : d_(d) { }
double operator() (double) {
return d_;
}
double d_;
};
struct Variable {
double operator() (double d) {
return d;
}
};
Finally, a class to represent non-terminal, complex expressions:
Show line numbers
template<class E1, class E2, class Op>
struct ComplexExpr {
ComplexExpr(Expr<E1> l, Expr<E2> r) : l_(l), r_(r) {
}
double operator() (double d) {
return Op::apply(l_(d), r_(d));
}
Expr<E1> l_;
Expr<E2> r_;
};
We have just carried over the definition of the ComplexExpression class from the previous article and made it into a template class. The operator classes like Add, Subtract, Multiply and Divide should continue to work unchanged. Guess what, we just have to define the operator overloads (for +, -, * and /) and we will be done with defining our framework of algebraic expression.
Now, we would want to write expressions such as:
Variable x;
cout << (x+3)(2); // prints 5
cout << ((x*x+3)*(x+3))(2); // prints 35
In the above, x is a Variable, 3 should generate a Constant, x + 3 should result in a ComplexExpr<Variable, Constant>. Further, x*x is a ComplexExpr<Variable, Variable> and (x*x+3)*(x+3) is a ComplexExpr<ComplexExpr< ComplexExpr<Variable, Variable>, Constant>, ComplexExpr<Variable, Constant> >. One can trace the template parameter types as sub-trees of the class template ComplexExpression.
Clearly, to write an expression like x+3, we need an overload of operator+ between a Variable and an integer. To write an expression like (x*x+3)*(x+3) - we need an operator* between two ComplexExpressions. To write something like, x+Constant(3), we need an overload of operator+ between Variable and Constant. Now, just as we defined the basic operators on Expression in the previous article, we could do the same on the Expr class template here, instead of overloading each operator for different combinations of types. For example:
Show line numbers
template<class E1, class E2>
Expr<ComplexExpr<Expr<E1>, Expr<E2>, Add> > operator+ (E1 e1, E2 e2) {
typedef ComplexExpr<Expr<E1>, Expr<E2>, Add> ExprType;
return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<E2>(e2)) );
}
The other operators are not very difficult to write, following the above code. However, turns out that while these do take care of operators between complex expressions as well as Variables and Constants, they cannot handle real number or integer literals. To handle real number literals, we define the following overload pairs for each operator.
Show line numbers
template<class E1>
Expr<ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> > operator* (E1 e1, double d) {
typedef ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> ExprType;
return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<Constant>(Constant(d))) );
}
template<class E1>
Expr<ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> > operator* (double d, E1 e1) {
typedef ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> ExprType;
return Expr<ExprType>( ExprType(Expr<Constant>(Constant(d)), Expr<E1>(e1)) );
}
These take care of all cases - except for a small glitch which we can pepare to live with. We can write such expressions as:
Variable x;
cout << (x+3.0)(2); // prints 5
cout << ((x*x+3.0)*(x+3.0))(2); // prints 35
but not ones like:
Variable x;
cout << (x+3)(2); // prints 5
cout << ((x*x+3)*(x+3))(2); // prints 35
If you have to be able to do this, add additional overloads like:
Show line numbers
template<class E1>As it should be already apparent - there are no objects allocated on free store, no reference counted proxy wrappers, and a fair bit of compile-time type computation and call dispatching - this results in significant savings in the runtime costs of the program, apart from the obvious cut in the number of lines of code. The basic philosophy of the template based program has not changed from the non-template version - it uses functional composition involving the function call operator, and operator overloading to support naturally combining simple expressions into arbitrarily complex expressions. However, the use of templates allows a fair bit of this work to be done at compile time. This is all that is there to Expression templates. You can put together the expression framework using code given here and use the following function to test your code.
Expr<ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> > operator* (E1 e1, int d) {
typedef ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> ExprType;
return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<Constant>(Constant(d))) );
}
template<class E1>
Expr<ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> > operator* (int d, E1 e1) {
typedef ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> ExprType;
return Expr<ExprType>( ExprType(Expr<Constant>(Constant(d)), Expr<E1>(e1)) );
}
Show line numbers
int main()
{
Variable x;
cout << ((2.0*x*x + 3.0*x + 3.0)*(2.0*x*x + 3.0*x + 3.0))(2) << endl;
cout << integrate((2.0*x*x + 3.0*x + 3.0), 0, 1) << endl;
cout << integrate((2.0*x*x + 3.0*x + 3.0)*(2.0*x*x + 3.0*x + 3.0), 0, 1) << endl;
cout << integrate((x/(1.0+x)), 0, 1) << endl;
cout << integrate(x*x, 0, 7) << endl;
return 0;
}
If you have any trouble understanding and compiling the code, drop me a message.
References
- Todd Veldhuizen
: Expression Templates
http://ubiety.uwater loo.ca/~tv eldhui/pap ers/Expres sion-Templ ates/exprt mpl.html
- Expression Templates synopsis on More C++ Idioms
http://en.wikibooks. org/wiki/M ore_C%2B%2 B_Idioms/E xpression- template
- Angelika Langer: Expression Templates - Introducti
on
http://www.angelikal anger.com/ Articles/C uj/Express ionTemplat es/Express ionTemplat es.htm
Read more!
Thursday, July 31, 2008
Expression Templates Demystified
Often in course of our programming work, we want to be able to modify or customize part of a function’s logic at the point of invocation. A very simple example is the C++ STL algorithm std::find_if.
Here Predicate represents a functor (an object that overloads the function-call operator). In this particular case, the functor should take an element of the container of which first and last are iterators, and return a boolean truth value based on some criteria, possibly as a function of the element passed.
Using find_if, one can find all elements in a container, that meet a particular criteria. What’s remarkable is that, what find_if identifies as matching elements in the container is entirely dependent on the logic encoded in the Predicate functor – not on find_if’s implementation. This makes the functionality of find_if open-ended. What we are able to achieve in the process is a form of polymorphism with a very high degree of type-safety and performance. There is a specific name for such idioms – functional composition. In fact, by combining an arbitrary number of Functors with varied functionality, we can construct a fairly complex piece of functionality. This has a very useful application in developing mini-languages (also called DSELs or Domain Specific Embedded Languages - expressions with a syntactic form alien to C++ syntax, being embedded inside C++ programs as valid code. In this article and the next in this series, we look at the powerful technique called Expression Templates which helps solve these classes of problems.
We have all learned in high school Calculus course about such functions of single variable as:
F(x) = x^3 + 3x - 7
or
G(x) = x.sin x + 6
Representing such simple algebraic functions using functors is not a big hassle. For example, to represent G(x), one could write a functor like the one below:
Hide line numbersShow line numbers
Imagine you have a Calculus library written in C++ and you have a function called integrate, that is defined as follows:
Hide line numbersShow line numbers
This is essentially an area under the curve calculation that takes the average of upper bound and lower bound sums.
Now here is the deal: in course of a mathematical programming one could need to integrate dozens of such mathematical expressions. If there are 50 different expressions to be integrated, a program needs to define 50 different functors – and this is where the efficiency and ease of the system breaks down.
Imagine being able to define function objects that can evaluate arbitrary mathematical expressions and being able to pass such expressions to functions like integrate. Something like the following:
Hide line numbersShow line numbers
This almost looks like magic, doesn’t it – but it isn’t. The complex algebraic expression can, in each case, be engineered to give a functor which evaluates the expression for different values of the function argument. The standard technique or idiom used for enabling such expression building is known as Expression Templates and it is the focus area of this article. But, Expression Templates have a notorious reputation of being difficult to understand and learn and turned off many a learner. Therefore, we would try to build the logic of constructing such expressions intuitively, bit by bit. We will start off with a completely non-template version of the code – an idiom that I discovered for myself and which I call Expression Functor. We would then ‘deduce’ the Expression Template idiom as a special case of this idiom which achieves phenomenal performance improvements and code improvement, using templates.
So here we go.
Let us first break the problem into its basic elements. We begin with a simple polynomial expression:
f(x) = x + 3
Such an expression has two kinds of entities – a variable (x) and a constant (the literal 3). Both these entities are valid expressions by themselves. For example, the straight line going parallel to the x-axis at a distance of 3 units above x-axis is represented by the function f(x) = 3. Similarly, the straight line going through the origin at an angle of 45 degrees to both x and y axes is represented by the function f(x) = x. Modelling these most trivial functions will be our building blocks for non-trivial expression building.
Consider the case of the horizontal line – f(x) = 3. We want to model a function which takes any value of x and always returns 3. The basic function would be:
Hide line numbersShow line numbers
We want this to become an applicative functor like this:
Hide line numbersShow line numbers
C3 above represents the function f(x) = 3. Now we want to generalize this function to represent any real number – this is fairly straight-forward:
Hide line numbersShow line numbers
Such a functor can be used to model any constant expression. C3 would now be equivalent to Constant(3).
Next, let’s try to model the 45 degree straight line through the origin – f(x) = x. Turns out that this is even easier – "given any value x, return that very value" should summarize our function. In short:
Hide line numbersShow line numbers
These two classes are remarkable on their own, but what happens when we try to model a function like:
f(x) = x+3
What type will be x + 3 – it is not Constant, and it is not an independent variable like Variable either. So we possibly need another class to represent more complex expressions. Come to think of it. Both a Constant and a Variable are each, in themselves, an expression, and so is a more generic expression like x+3. So it would seem logical that we should have an Expression base class of which, Constant, Variable and other Expression classes can be derived classes. We define it like this:
Hide line numbersShow line numbers
There is a reason for the curious looking Expression* clone() virtual function. I have included this with the benefit of contrived foresight - having implemented this whole solution already. Without getting ahead of the story, let me tell you that it plays a small but important role in the life cycle management of Expressions. It is used to copy Expressions where needed.
Hide line numbersShow line numbers
We would refer to Expressions like Constant and variable as simple expressions. We also need to define a sub-type of Expression to represent all non-trivial (i.e. other than simple) expressions. But before that can happen, we need to understand how multiple expressions can be combined using arithmetic operators. For example, we want to be able to write such expressions as:
Hide line numbersShow line numbers
Clearly, we need to overload operators like * and + between Variables (x*x), between Constants and Variables (2*x), and between multiple ComplexExpressions (x*x and 2*x). Moreover, the literals like 1 and 2 are not Constant objects, they are doubles that need to be converted to Constant objects. So, these operators should also be overloaded for double arguments. Clearly, given the fact that all of these (Variable, Constant, ComplexExpression) are different sub-types of Expression, it will be easier if we just overload these operators between Expressions, and between Expressions and doubles.
Now any complex expression can be represented as:
f(x) = u(x) OP v(x)
OP is a binary arithmetic operator. For example:
f(x) = c is a degenerate case where, u(x) = 1, v(x) = c and OP = *. Or perhaps u(x) = 0, v(x) = c and OP = +. Assuming that we have such an operation available for each appropriate arithmetic operation, we write the class for complex expressions as a template class - the template parameter being the Binary Operation.
Hide line numbersShow line numbers
The binary operators can be easily defined using simple functors like the following:
Hide line numbersShow line numbers
Finally, when we combine two simple Expressions, we get a complex expression. For example, x might be a simple expression, but x*x is a complex expression. We want to be able to cascade the operators to any degree, thus:
x*x*x
should be a valid expression. Clearly x*x must return an object of such type that can be combined with x using a * operator. x*x must return a reference or pointer to Expression - because Expression is an abstract class so it cannot be returned by value, and besides it is not much point returning it by value because we want to treat it polymorphically (virtual function calls to operator() and clone() in ComplexExpression). Something like the following:
Hide line numbersShow line numbers
The above does not work because operator* returns a pointer to an Expression object - x*x returns a pointer. Consider an expression like x*x*2. x*x*2 is equivalent to (x*x)*2 - since x*x returns an Expression*, we need an operator* which takes a pointer (Expression*) and a double (2). The Standard does not allow an operator to be overloaded on arguments of integer types alone. Thus, operator * can only return a reference.
Hide line numbersShow line numbers
The above works but no one takes the responsibility of deallocating object referred to be the returned reference - we are left with a memory leak.
What about the following:
Hide line numbersShow line numbers
The above does not even work - because we are passing a reference to a local object created in the function. It has undefined behaviour. What do we do - well, a bit of inevitable complexity creeps in here. We need to return a pointer wrapped in smart wrappers, which can take care of the life-cycles of the underlying pointer and act as proxy objects when participating in mathematical expressions.
Consider the following definition of a reference counted wrapper cum Proxy for heap allocated Expression pointers:
Hide line numbersShow line numbers
Using this class, we can rewrite operator* like below:
Hide line numbersShow line numbers
Thus, the return value of x*x is of type ExpressionRef, and at least it wraps a polymorphic reference to Expression, and ensure that there would be no memory leaks. The only problem now is to make expressions such as x*x*x valid. x*x*x translates to (x*x)*x - whereby x*x returns ExpressionRef and x is some sub-type Expression. This is not such a big deal - we define operator * (ExpressionRef&, Expression&). We also need the alternative permutations: operator * (Expression&, ExpressionRef&). In fact, to allow expressions such as (x*x)*(x*x), one must also allow operators like: operator * (ExpressionRef&, ExpressionRef&).
At this point, all the issues with our solution are resolved - and we need to take stock of the final set of operator overloads we need to make the expressions work naturally. Here is a summary:
Expression& Op Expression&
ExpressionRef& Op ExpressionRef&
Expression& Op double - and reverse permutation
ExpressionRef& Op double - and reverse permutation
ExpressionRef& Op Expression& - and reverse permutation
That makes it 8 types of signatures. For each type, if we plan to implement +, -, * and /, then we will have a total of 32 operators. One set of operators can have real implementations and the rest can be defined in terms of the first set. Here are the definitions for the + operators.
Hide line numbersShow line numbers
To test this solution, use the following functions:
Hide line numbersShow line numbers
Having come thus far, you may have made two observations. One we have written code which is nifty, and works well but is repetitive in some parts and not very extensible. Second, although this article is about Expression Templates, we have hardly used any templates (except for the ComplexExpression class).
What are the key concepts in this code which enabled creating the Expression Functors?
1. Nesting function objects and operator() of outer objects calling operator()'s of inner objects - for example ComplexExpression::operator(). The ormal term for these idioms is Functional Composition.
2. Overloading operators on Expression types.
What we've done so far was laying the foundation for our understanding of Expression Templates. The real deal should not take a lot of time after this. We will now head into investigating how this model of functional composition can be retained and generalized, performance of the Expressions phenomenally improved, and the lines of code drastically cut - by using Templates. This is the topic of the next part of this article.
Read more!
template<class InputIterator, class Predicate>
InputIterator find_if (InputIterator first, InputIterator last, Predicate pred)
Here Predicate represents a functor (an object that overloads the function-call operator). In this particular case, the functor should take an element of the container of which first and last are iterators, and return a boolean truth value based on some criteria, possibly as a function of the element passed.
Using find_if, one can find all elements in a container, that meet a particular criteria. What’s remarkable is that, what find_if identifies as matching elements in the container is entirely dependent on the logic encoded in the Predicate functor – not on find_if’s implementation. This makes the functionality of find_if open-ended. What we are able to achieve in the process is a form of polymorphism with a very high degree of type-safety and performance. There is a specific name for such idioms – functional composition. In fact, by combining an arbitrary number of Functors with varied functionality, we can construct a fairly complex piece of functionality. This has a very useful application in developing mini-languages (also called DSELs or Domain Specific Embedded Languages - expressions with a syntactic form alien to C++ syntax, being embedded inside C++ programs as valid code. In this article and the next in this series, we look at the powerful technique called Expression Templates which helps solve these classes of problems.
We have all learned in high school Calculus course about such functions of single variable as:
F(x) = x^3 + 3x - 7
or
G(x) = x.sin x + 6
Representing such simple algebraic functions using functors is not a big hassle. For example, to represent G(x), one could write a functor like the one below:
Hide line numbersShow line numbers
1 Struct FuncG {
2 double operator(double x) {
3 return (x*sin(x) + 6) ;
4 }
5 }
Imagine you have a Calculus library written in C++ and you have a function called integrate, that is defined as follows:
Hide line numbersShow line numbers
1 template<class Func>
2 double integrate(Func f, double low, double high, double epsilon = 0.001) {
3 assert(low <= high );
4 double auc1 = 0, auc2 = 0;
5 double running_x = low;
6 while ( running_x < high ) {
7 auc1 += f(running_x) * epsilon;
8 running_x += epsilon;
9 auc2 += f(running_x) * epsilon;
10 }
11
12 return (auc1 + auc2)/2;
13 }
This is essentially an area under the curve calculation that takes the average of upper bound and lower bound sums.
Now here is the deal: in course of a mathematical programming one could need to integrate dozens of such mathematical expressions. If there are 50 different expressions to be integrated, a program needs to define 50 different functors – and this is where the efficiency and ease of the system breaks down.
Imagine being able to define function objects that can evaluate arbitrary mathematical expressions and being able to pass such expressions to functions like integrate. Something like the following:
Hide line numbersShow line numbers
1 MathFunction f = x*x + 2*x + 3;
2 double d = integrate(f, 0, 2);
3 f = x*x*sin*sin + 2*x*cos*sin + cos*cos;
4 const double PI = 3.1415926535897;
5 d = f(PI/2);
This almost looks like magic, doesn’t it – but it isn’t. The complex algebraic expression can, in each case, be engineered to give a functor which evaluates the expression for different values of the function argument. The standard technique or idiom used for enabling such expression building is known as Expression Templates and it is the focus area of this article. But, Expression Templates have a notorious reputation of being difficult to understand and learn and turned off many a learner. Therefore, we would try to build the logic of constructing such expressions intuitively, bit by bit. We will start off with a completely non-template version of the code – an idiom that I discovered for myself and which I call Expression Functor. We would then ‘deduce’ the Expression Template idiom as a special case of this idiom which achieves phenomenal performance improvements and code improvement, using templates.
So here we go.
Breaking down the problem
Let us first break the problem into its basic elements. We begin with a simple polynomial expression:
f(x) = x + 3
Such an expression has two kinds of entities – a variable (x) and a constant (the literal 3). Both these entities are valid expressions by themselves. For example, the straight line going parallel to the x-axis at a distance of 3 units above x-axis is represented by the function f(x) = 3. Similarly, the straight line going through the origin at an angle of 45 degrees to both x and y axes is represented by the function f(x) = x. Modelling these most trivial functions will be our building blocks for non-trivial expression building.
Consider the case of the horizontal line – f(x) = 3. We want to model a function which takes any value of x and always returns 3. The basic function would be:
Hide line numbersShow line numbers
1 double f(double x) {
2 return 3;
3 }
We want this to become an applicative functor like this:
Hide line numbersShow line numbers
1 struct C3 {
2 double operator() (double) {
3 return 3;
4 }
5 };
C3 above represents the function f(x) = 3. Now we want to generalize this function to represent any real number – this is fairly straight-forward:
Hide line numbersShow line numbers
1 struct Constant {
2 Constant(const double& d) : d_(d) {
3 }
4
5 double operator() (double) {
6 return d_;
7 }
8
9 const double d_;
10 };
Such a functor can be used to model any constant expression. C3 would now be equivalent to Constant(3).
Next, let’s try to model the 45 degree straight line through the origin – f(x) = x. Turns out that this is even easier – "given any value x, return that very value" should summarize our function. In short:
Hide line numbersShow line numbers
1 struct Variable {
2 double operator() (double x) {
3 return x;
4 }
5 };
These two classes are remarkable on their own, but what happens when we try to model a function like:
f(x) = x+3
What type will be x + 3 – it is not Constant, and it is not an independent variable like Variable either. So we possibly need another class to represent more complex expressions. Come to think of it. Both a Constant and a Variable are each, in themselves, an expression, and so is a more generic expression like x+3. So it would seem logical that we should have an Expression base class of which, Constant, Variable and other Expression classes can be derived classes. We define it like this:
Hide line numbersShow line numbers
1 struct Expression {
2 virtual double operator() (double) = 0;
3 virtual Expression* clone() = 0;
4 virtual ~Expression() {
5 }
6 };
There is a reason for the curious looking Expression* clone() virtual function. I have included this with the benefit of contrived foresight - having implemented this whole solution already. Without getting ahead of the story, let me tell you that it plays a small but important role in the life cycle management of Expressions. It is used to copy Expressions where needed.
Hide line numbersShow line numbers
1 struct Constant : Expression {
2 ...
3 Expression* clone() {
4 return new Constant(*this);
5 }
6 };
7
8 struct Variable : Expression {
9 ...
10 Expression* clone() {
11 return new Variable(*this);
12 }
13 };
We would refer to Expressions like Constant and variable as simple expressions. We also need to define a sub-type of Expression to represent all non-trivial (i.e. other than simple) expressions. But before that can happen, we need to understand how multiple expressions can be combined using arithmetic operators. For example, we want to be able to write such expressions as:
Hide line numbersShow line numbers
1 Variable x;
2 Expression& e = x*x + 2*x + 1;
3 double d = e(5); // d == 36
4 double d2 = integrate(e, 0, 1); // d2 == 2.33
Clearly, we need to overload operators like * and + between Variables (x*x), between Constants and Variables (2*x), and between multiple ComplexExpressions (x*x and 2*x). Moreover, the literals like 1 and 2 are not Constant objects, they are doubles that need to be converted to Constant objects. So, these operators should also be overloaded for double arguments. Clearly, given the fact that all of these (Variable, Constant, ComplexExpression) are different sub-types of Expression, it will be easier if we just overload these operators between Expressions, and between Expressions and doubles.
Now any complex expression can be represented as:
f(x) = u(x) OP v(x)
OP is a binary arithmetic operator. For example:
f(x) = c is a degenerate case where, u(x) = 1, v(x) = c and OP = *. Or perhaps u(x) = 0, v(x) = c and OP = +. Assuming that we have such an operation available for each appropriate arithmetic operation, we write the class for complex expressions as a template class - the template parameter being the Binary Operation.
Hide line numbersShow line numbers
1 template<class Op>
2 struct ComplexExpression : Expression {
3 Expression* l_;
4 Expression* r_;
5
6 ComplexExpression(Expression& l, Expression& r) : l_(l.clone()), r_(r.clone()) {
7 }
8
9 ~ComplexExpression() {
10 delete l_;
11 delete r_;
12 }
13
14 double operator() (double d) {
15 return Op::apply( (*l_)(d), (*r_)(d) );
16 }
17
18 Expression* clone() {
19 return new ComplexExpression(*l_, *r_);
20 }
21 };
The binary operators can be easily defined using simple functors like the following:
Hide line numbersShow line numbers
1 struct Add {
2 static double apply(double l, double r) {
3 return l+r;
4 }
5 };
6
7 struct Subtract {
8 static double apply(double l, double r) {
9 return l-r;
10 }
11 };
12
13 struct Multiply {
14 static double apply(double l, double r) {
15 return l*r;
16 }
17 };
18
19 struct Divide {
20 static double apply(double l, double r) {
21 return l/r;
22 }
23 };
Finally, when we combine two simple Expressions, we get a complex expression. For example, x might be a simple expression, but x*x is a complex expression. We want to be able to cascade the operators to any degree, thus:
x*x*x
should be a valid expression. Clearly x*x must return an object of such type that can be combined with x using a * operator. x*x must return a reference or pointer to Expression - because Expression is an abstract class so it cannot be returned by value, and besides it is not much point returning it by value because we want to treat it polymorphically (virtual function calls to operator() and clone() in ComplexExpression). Something like the following:
Hide line numbersShow line numbers
1 Expression* operator * (Expression& l, Expression& r) {
2 return new ComplexExpression<Multiply>(l, r);
3 }
The above does not work because operator* returns a pointer to an Expression object - x*x returns a pointer. Consider an expression like x*x*2. x*x*2 is equivalent to (x*x)*2 - since x*x returns an Expression*, we need an operator* which takes a pointer (Expression*) and a double (2). The Standard does not allow an operator to be overloaded on arguments of integer types alone. Thus, operator * can only return a reference.
Hide line numbersShow line numbers
1 Expression* operator * (Expression& l, Expression& r) {
2 return new ComplexExpression<Multiply>(l, r);
3 }
The above works but no one takes the responsibility of deallocating object referred to be the returned reference - we are left with a memory leak.
What about the following:
Hide line numbersShow line numbers
1 Expression& operator * (Expression& l, Expression& r) {
2 return ComplexExpression<Multiply>(l, r);
3 }
The above does not even work - because we are passing a reference to a local object created in the function. It has undefined behaviour. What do we do - well, a bit of inevitable complexity creeps in here. We need to return a pointer wrapped in smart wrappers, which can take care of the life-cycles of the underlying pointer and act as proxy objects when participating in mathematical expressions.
Consider the following definition of a reference counted wrapper cum Proxy for heap allocated Expression pointers:
Hide line numbersShow line numbers
1 struct ExpressionRef {
2 ExpressionRef(Expression* ptr) : sp_(ptr), ref_cnt_(1) {
3 }
4
5 ~ExpressionRef() {
6 if (--ref_cnt_ == 0) {
7 delete sp_;
8 sp_ = 0;
9 }
10 }
11
12 ExpressionRef(const ExpressionRef& source) : sp_(source.sp_) {
13 ++ref_cnt_;
14 }
15
16 inline ExpressionRef& operator = (const ExpressionRef& rhs) {
17 if ( this != &rhs ) {
18 if ( --ref_cnt_ <= 0 ) {
19 delete sp_;
20 sp_ = 0;
21 }
22
23 sp_ = rhs.sp_;
24 ++ref_cnt_;
25 }
26
27 return *this;
28 }
29
30 double operator() (double d) {
31 return (*sp_)(d);
32 }
33
34 ExpressionRef clone() {
35 ExpressionRef copy(sp_->clone());
36 return copy;
37 }
38
39 inline Expression* get() {
40 return sp_;
41 }
42
43 inline Expression& getref() {
44 return *sp_;
45 }
46
47 inline operator void*() {
48 return sp_;
49 }
50
51 private:
52 Expression *sp_;
53 int ref_cnt_;
54 };
Using this class, we can rewrite operator* like below:
Hide line numbersShow line numbers
1 ExpressionRef operator * (Expression& l, Expression& r) {
2 return ExpressionRef(new ComplexExpression<Multiply>(l, r));
3 }
4
Thus, the return value of x*x is of type ExpressionRef, and at least it wraps a polymorphic reference to Expression, and ensure that there would be no memory leaks. The only problem now is to make expressions such as x*x*x valid. x*x*x translates to (x*x)*x - whereby x*x returns ExpressionRef and x is some sub-type Expression. This is not such a big deal - we define operator * (ExpressionRef&, Expression&). We also need the alternative permutations: operator * (Expression&, ExpressionRef&). In fact, to allow expressions such as (x*x)*(x*x), one must also allow operators like: operator * (ExpressionRef&, ExpressionRef&).
At this point, all the issues with our solution are resolved - and we need to take stock of the final set of operator overloads we need to make the expressions work naturally. Here is a summary:
Expression& Op Expression&
ExpressionRef& Op ExpressionRef&
Expression& Op double - and reverse permutation
ExpressionRef& Op double - and reverse permutation
ExpressionRef& Op Expression& - and reverse permutation
That makes it 8 types of signatures. For each type, if we plan to implement +, -, * and /, then we will have a total of 32 operators. One set of operators can have real implementations and the rest can be defined in terms of the first set. Here are the definitions for the + operators.
Hide line numbersShow line numbers
1 ExpressionRef operator + (Expression& l, Expression& r) {
2 return ExpressionRef(new ComplexExpression<Add>(l, r));
3 }
4
5 ExpressionRef operator + (ExpressionRef& l, ExpressionRef& r) {
6 return l.getref() + r.getref();
7 }
8
9 ///////////////
10
11 ExpressionRef operator + (Expression& l, const double d) {
12 return l + Constant(d);
13 }
14
15 ExpressionRef operator + (const double d, Expression& l) {
16 return Constant(d) + l;
17 }
18
19 //////////////
20
21 ExpressionRef operator + (ExpressionRef& l, Expression& r) {
22 return l.getref() + r;
23 }
24
25 ExpressionRef operator + (Expression& l, ExpressionRef& r) {
26 return l + r.getref();
27 }
28
29 //////////////
30
31 ExpressionRef operator + (ExpressionRef& l, double d) {
32 return l.getref() + Constant(d);
33 }
34
35 ExpressionRef operator + (double d, ExpressionRef& r) {
36 return Constant(d) + r.getref();
37 }
To test this solution, use the following functions:
Hide line numbersShow line numbers
1 double integrate(Expression& e, double low=0, double high = 1, double epsilon = 0.001) {
2 assert(low <= high );
3 double auc1 = 0, auc2 = 0;
4 double running_x = low;
5 while ( running_x < high ) {
6 auc1 += e(running_x) * epsilon;
7 running_x += epsilon;
8 auc2 += e(running_x) * epsilon;
9 }
10
11 return (auc1 + auc2)/2;
12 }
13
14 double integrate(ExpressionRef& er, double low=0, double high = 1, double epsilon = 0.001) {
15 return integrate(er.getref(), low, high, epsilon);
16 }
17
18 int main()
19 {
20 Variable x;
21
22 cout << ((2*x*x + 3*x + 3)*(2*x*x + 3*x + 3))(2) << endl;
23 cout << integrate((2*x*x + 3*x + 3), 0, 1) << endl;
24 cout << integrate((2*x*x + 3*x + 3)*(2*x*x + 3*x + 3), 0, 1) << endl;
25 cout << integrate((x/(1+x)), 0, 1) << endl;
26 cout << integrate(Exp(), 0, 1) << endl;
27 cout << integrate(x*x, 0, 7) << endl;
28
29 return 0;
30 }
Having come thus far, you may have made two observations. One we have written code which is nifty, and works well but is repetitive in some parts and not very extensible. Second, although this article is about Expression Templates, we have hardly used any templates (except for the ComplexExpression class).
What are the key concepts in this code which enabled creating the Expression Functors?
1. Nesting function objects and operator() of outer objects calling operator()'s of inner objects - for example ComplexExpression::operator(). The ormal term for these idioms is Functional Composition.
2. Overloading operators on Expression types.
What we've done so far was laying the foundation for our understanding of Expression Templates. The real deal should not take a lot of time after this. We will now head into investigating how this model of functional composition can be retained and generalized, performance of the Expressions phenomenally improved, and the lines of code drastically cut - by using Templates. This is the topic of the next part of this article.
References
- Todd Veldhuizen
: Expression Templates
http://ubiety.uwater loo.ca/~tv eldhui/pap ers/Expres sion-Templ ates/exprt mpl.html
Read more!
Subscribe to:
Posts (Atom)
