Recent posts

How std::move breaks return value optimization


Posted by Diego Assencio on 2017.08.07 under Programming (C/C++)

Consider the following program:

std::vector<int> random_numbers(const size_t n)
{
    std::vector<int> numbers;

    /* generate n random numbers, store them on numbers */

    return numbers;
}

int main()
{
    /* create an array with 100 random numbers */
    std::vector<int> my_numbers = random_numbers(100);

    ...
}

Returning an std::vector<int> by value can make a developer nervous: will this cause the vector to be copied? That would be a costly performance penalty and therefore something to be avoided, if possible.

In this type of situation, a solid understanding of how return value optimization (or simply RVO, for short) works leads to inner peace. Any decent compiler will understand that numbers is a temporary variable whose value will be returned at the end of the random_numbers function, and since this returned value is an rvalue (a temporary object, see line 13), it can be used to initialize my_numbers directly, i.e., without going through any of the std::vector<int>'s constructors. In other words, no vectors should be copied or moved on the code above. How wonderful!

Let's take a closer look at how RVO removes the need for a copy operation. When random_numbers is called, memory on the call stack will be reserved for its return value (an std::vector<int>). Inside of random_numbers, numbers is clearly a temporary variable whose value will be returned at the end, so instead of copying this value to the memory location reserved for the function's return value at the very end, numbers is stored directly at that memory location. The elimination of such a copy operation when a function returns is what "return value optimization" stands for. In general, any type of optimization which causes copy operations to be eliminated is referred to as a copy elision optimization.

Despite all these facts, it is not uncommon for developers to be less confident than they should in this type of situation and prefer "being on the safe side" by writing this type of code:

std::vector<int> random_numbers(const size_t n)
{
    std::vector<int> numbers;

    /* generate n random numbers, store them on numbers */

    return std::move(numbers);   /* don't do this! */
}

As innocent as this decision may be, it is severely flawed because of the way RVO works: only a local variable or a temporary object can be stored directly at the memory location for a function's return value (function parameters are not eligible for that), and this is only allowed if such an object is directly returned by the function and has the same type as the function's return type. By adding std::move on the return statement above, we converted the type of the returned object to std::vector<int>&& (an rvalue reference to an std::vector<int>), but random_numbers returns an std::vector<int>. This violates the conditions required for RVO, and the compiler will have no choice but to make numbers be constructed outside the memory area reserved for random_numbers's return value and then moved to that location when the function returns (a move operation is still possible here since std::move(numbers) is an rvalue and will therefore trigger the move constructor for the std::vector<int> which is constructed as the return value).

For many user-defined types, such an additionally incurred move operation will be cheap, but it will definitely not be cheaper than what RVO offers and therefore, by "playing safe", we ended up inevitably pessimizing our program. Also, notice that we were lucky to have a return type (std::vector<int>) with a move constructor; had this not been the case, the added std::move would have caused the return value to be initialized through a copy constructor, which is what we wanted to avoid in the first place. Ouch!

To finalize, here is an example which involves all concepts discussed so far:

#include <iostream>

class X
{
public:
    /* default constructor */
    X() { std::cout << "X::X()\n"; }

    /* copy constructor */
    X(const X&) { std::cout << "X::X(const X&)\n"; }

    /* move constructor */
    X(X&&) { std::cout << "X::X(X&&)\n"; }
};

X good()
{
    std::cout << "good()\n";

    X x;
    return x;
}

X bad()
{
    std::cout << "bad()\n";

    X x;
    return std::move(x);
}

int main()
{
    X x1 = good();
    X x2 = bad();

    return 0;
}

The program's output illustrates how the std::move on the bad function disables RVO and forces an unnecessary move operation (this will be the case even if you compile with lots of optimizations enabled, e.g. by using -O3 on gcc):

good()
X::X()
bad()
X::X()
X::X(X&&)

Try compiling and running this program, then remove the move constructor from X. The resulting output shows that std::move now causes X to be copied:

good()
X::X()
bad()
X::X()
X::X(const X&)
Comments (1) Direct link

The intersection area of two circles


Posted by Diego Assencio on 2017.07.12 under Mathematics (Geometry)

Let $C_1$ and $C_2$ be two circles of radii $r_1$ and $r_2$ respectively whose centers are at a distance $d$ from each other. Assume, without loss of generality, that $r_1 \geq r_2$. What is the intersection area of these two circles?

If $d \geq r_1 + r_2$, the circles intersect at most up to a point (when $d = r_1 + r_2$) and therefore the intersection area is zero. On the other extreme, if $d + r_2 \leq r_1$, circle $C_2$ is entirely contained within $C_1$ and the intersection area is the area of $C_2$ itself: $\pi r_2^2$. The challenging case happens when both $d \lt r_1 + r_2$ and $d + r_2 \gt r_1$ are satisfied, i.e., when the the circles intersect only partially but the intersection area is more than simply a point. Rearranging the second inequality, we obtain $r_1 - r_2 \lt d \lt r_1 + r_2$, so we will assume this to be the case from now on.

To solve this problem, we will make use of a Cartesian coordinate system with origin at the center of circle $C_1$ such that the center of $C_2$ is at $(d,0)$ as shown on figure 1.

Fig. 1: Two intersecting circles $C_1$ (blue) and $C_2$ (red) of radii $r_1$ and $r_2$ respectively. The distance between the centers of the circles is $d = d_1 + d_2$, where $d_1$ is the $x$ coordinate of the intersection points and $d_2 = d - d_1$. Notice that $d_1 \geq 0$ since these points are always located to the right of the center of $C_1$, but $d_2$ may be negative when $r_2 \lt r_1$ since, in this case, the intersection points will eventually fall to the right of the center of $C_2$ as we move $C_2$ to the left, making $d \lt d_1$ and therefore $d_2 \lt 0$.

The circles $C_1$ and $C_2$ are described by the following equations respectively: $$ \begin{eqnarray} x^2 + y^2 &=& r_1^2 \label{post_8d6ca3d82151bad815f78addf9b5c1c6_c1}\\[5pt] (x - d)^2 + y^2 &=& r_2^2 \\[5pt] \end{eqnarray} $$ At the intersection points, we have $x = d_1$. To determine $d_1$, we can replace $x$ with $d_1$ and isolate $y^2$ on both equations above to get: $$ r_1^2 - d_1^2 = r_2^2 - (d_1 - d)^2 $$ Solving for $d_1$ is a simple task: $$ r_1^2 - d_1^2 = r_2^2 - d_1^2 + 2d_1d - d^2 \Longrightarrow d_1 = \displaystyle\frac{r_1^2 - r_2^2 + d^2}{2d} \label{post_8d6ca3d82151bad815f78addf9b5c1c6_eq_d1} $$ From equation \eqref{post_8d6ca3d82151bad815f78addf9b5c1c6_eq_d1}, we can see that $d_1 \geq 0$ since $r_1 \geq r_2$. The intersection area is the sum of the blue and red areas shown on figure 1, which we refer to as $A_1$ and $A_2$ respectively. We then have that: $$ \begin{eqnarray} A_1 &=& 2\int_{d_1}^{r_1} \sqrt{r_1^2 - x^2}dx \label{%INDEX_eq_A1_def} \\[5pt] A_2 &=& 2\int_{d - r_2}^{d_1} \sqrt{r_2^2 - (x - d)^2}dx \end{eqnarray} $$ where the factors of $2$ come from the fact that each integral above accounts for only half of the area of the associated region (only points on and above the $x$ axis are taken into account); the results must then be multiplied by two so that the areas below the $x$ axis are taken into account as well.

The computation of these integrals is straightforward. Before we proceed, notice first that: $$ \begin{eqnarray} A_2 &=& 2\int_{d - r_2}^{d_1} \sqrt{r_2^2 - (x - d)^2}dx \nonumber \\[5pt] &=& 2\int_{- r_2}^{d_1 - d} \sqrt{r_2^2 - x^2}dx \nonumber \\[5pt] &=& 2\int_{d - d_1}^{r_2} \sqrt{r_2^2 - x^2}dx \nonumber \\[5pt] &=& 2\int_{d_2}^{r_2} \sqrt{r_2^2 - x^2}dx \label{%INDEX_eq_A2} \end{eqnarray} $$ where above we used the fact that $d_2 = d - d_1$. This is the same as equation \eqref{%INDEX_eq_A1_def} if we apply the substitutions $d_1 \rightarrow d_2$ and $r_1 \rightarrow r_2$. Therefore, by computing $A_1$, we will immediately obtain $A_2$ as well. Let's then compute $A_1$ first: $$ \begin{eqnarray} A_1 &=& 2\int_{d_1}^{r_1} \sqrt{r_1^2 - x^2}dx \nonumber\\[5pt] &=& 2r_1 \int_{d_1}^{r_1} \sqrt{1 - \left(\frac{x}{r_1}\right)^2}dx \nonumber\\[5pt] &=& 2r_1^2 \int_{d_1/r_1}^{1} \sqrt{1 - x^2}dx \label{%INDEX_eq_A1} \end{eqnarray} $$ All we need to do now is to integrate $\sqrt{1 - x^2}$. The process is straightforward if we use integration by parts: $$ \begin{eqnarray} \int \sqrt{1 - x^2}dx &=& x \sqrt{1 - x^2} - \int x \left(\frac{-x}{\sqrt{1 - x^2}}\right) dx \nonumber\\[5pt] &=& x \sqrt{1 - x^2} + \int \frac{x^2 - 1}{\sqrt{1 - x^2}} dx + \int \frac{1}{\sqrt{1 - x^2}} dx \nonumber\\[5pt] &=& x \sqrt{1 - x^2} - \int \sqrt{1 - x^2} dx + \sin^{-1}(x) \end{eqnarray} $$ Therefore: $$ \int \sqrt{1 - x^2}dx = \frac{1}{2}\left( x \sqrt{1 - x^2} + \sin^{-1}(x) \right) \label{post_8d6ca3d82151bad815f78addf9b5c1c6_int_for_A1_A2} $$ Using equation \eqref{post_8d6ca3d82151bad815f78addf9b5c1c6_int_for_A1_A2} on equation \eqref{%INDEX_eq_A1} yields: $$ \begin{eqnarray} A_1 &=& r_1^2 \left( \frac{\pi}{2} - \frac{d_1}{r_1}\sqrt{1 - \left(\frac{d_1}{r_1}\right)^2} - \sin^{-1}\left(\frac{d_1}{r_1}\right) \right) \nonumber\\[5pt] &=& r_1^2 \left( \cos^{-1}\left(\frac{d_1}{r_1}\right) - \frac{d_1}{r_1}\sqrt{1 - \left(\frac{d_1}{r_1}\right)^2} \right) \nonumber\\[5pt] &=& r_1^2 \cos^{-1}\left(\frac{d_1}{r_1}\right) - d_1 \sqrt{r_1^2 - d_1^2} \label{post_8d6ca3d82151bad815f78addf9b5c1c6_eq_A1_final} \end{eqnarray} $$ where above we used the fact that $\pi/2 - \sin^{-1}(\alpha) = \cos^{-1}(\alpha)$ for any $\alpha$ in $[-1,1]$. This fact is easy to prove: $$ \cos\left(\frac{\pi}{2} - \sin^{-1}(\alpha)\right) = \cos\left(\frac{\pi}{2}\right)\cos(\sin^{-1}(\alpha)) + \sin\left(\frac{\pi}{2}\right)\sin(\sin^{-1}(\alpha)) = \alpha $$ and therefore $\pi/2 - \sin^{-1}(\alpha) = \cos^{-1}(\alpha)$. As discussed above, we can now obtain $A_2$ directly by doing the substitutions $d_1 \rightarrow d_2$ and $r_1 \rightarrow r_2$ on the expression for $A_1$ on equation \eqref{post_8d6ca3d82151bad815f78addf9b5c1c6_eq_A1_final}: $$ A_2 = r_2^2 \cos^{-1}\left(\frac{d_2}{r_2}\right) - d_2 \sqrt{r_2^2 - d_2^2} $$ The sum of $A_1$ and $A_2$ is the intersection area of the circles: $$ \boxed{ \begin{eqnarray} A_{\textrm{intersection}} &=& r_1^2 \cos^{-1}\left(\frac{d_1}{r_1}\right) - d_1\sqrt{r_1^2 - d_1^2} \nonumber \\[5pt] &+& r_2^2\cos^{-1}\left(\frac{d_2}{r_2}\right) - d_2\sqrt{r_2^2 - d_2^2} \nonumber \end{eqnarray} } \label{post_8d6ca3d82151bad815f78addf9b5c1c6_A_intersection} $$ where: $$ \boxed{ d_1 = \displaystyle\frac{r_1^2 - r_2^2 + d^2}{2d} } \quad \textrm{ and } \quad \boxed{ d_2 = d - d_1 = \displaystyle\frac{r_2^2 - r_1^2 + d^2}{2d} } \label{post_8d6ca3d82151bad815f78addf9b5c1c6_eq_d1_final} $$

Summary

Given two circles $C_1$ and $C_2$ of radii $r_1$ and $r_2$ respectively (with $r_1 \geq r_2$) whose center points are at a distance $d$ from each other, the intersection area of the circles is:

1.zero, if $d \geq r_1 + r_2$, since in this case the circles intersect at most up to a point.
2.$\pi r_2^2$, if $d \leq r_1 - r_2$, since in this case $C_2$ is entirely contained within $C_1$.
3.given by equation \eqref{post_8d6ca3d82151bad815f78addf9b5c1c6_A_intersection} in all other cases.
Comments (1) Direct link

The nature of the "this" pointer in C++


Posted by Diego Assencio on 2017.04.01 under Programming (C/C++)

Whenever you call a non-static member function of a class, you call it through an existing object of that class type. Inside the definition of such a member function, you can refer to this object through the this pointer. Unless there is a need to disambiguate the use of a certain variable name (for instance, if a class data member has the same name as a local variable of the member function), the this pointer is often not used by developers to explicitly refer to class data members. This is almost always not a problem, but as I will discuss in this post, there are situations which require special care in order to avoid certain pitfalls.

To start, consider the following piece of code:

class AddNumber
{
public:

	...

	int add(const int other) const;

private:
	int number;
};

int AddNumber::add(const int other) const
{
	return number + other;
}

When the compiler parses the code above, it will understand that on the definition of AddNumber::add, number refers to the class data member with that name, i.e., that the code above is equivalent to this:

class AddNumber
{
public:

	...

	int add(const int other) const;

private:
	int number;
};

int AddNumber::add(const int other) const
{
	return this->number + other;
}

However, if we change the name of the parameter other of AddNumber::add to number, the compiler will interpret any occurrence of number inside its definition as the function parameter number instead of the data member this->number:

class AddNumber
{
public:

	...

	int add(const int number) const;

private:
	int number;
};

int AddNumber::add(const int number) const
{
	return number + number; /* here number is not this->number! */
}

To fix this ambiguity, we can use the this pointer to indicate to the compiler that the first occurrence of number actually refers to the class data member instead of the function parameter:

class AddNumber
{
public:

	...

	int add(const int number) const;

private:
	int number;
};

int AddNumber::add(const int number) const
{
	return this->number + number; /* this is what we originally had */
}

I hope there was nothing new for you on everything discussed so far, so let's move on to more interesting things.

One could argue that classes as we see them don't really exist: they are purely syntactic sugar for avoiding having to explicitly pass object pointers around as we do in C programs. To clarify this idea, take a look at the code below: it is conceptually equivalent to the one above except for the absence of the private access specifier. To prevent any desperation in advance, the code below is not valid C++; its purpose is merely to illustrate the concepts we are about to discuss:

struct AddNumber
{
	...

	int number;
};

int AddNumber::add(const AddNumber* this, const int number)
{
	return this->number + number;
}

Why is the code above not valid? Well, for two reasons: AddNumber::add is not a valid function name in this context (it is not a member of AddNumber), and this, being a reserved keyword, cannot be used as a parameter name. While in the original version, AddNumber:add is called through an existing object of type AddNumber:

AddNumber my_adder;

...

my_adder.add(3);

in our (invalid) non-class version, AddNumber:add is called with an object as argument:

AddNumber my_adder;

...

AddNumber::add(&my_adder, 3);

Were it not invalid, the non-class version would do exactly the same as the original one. But in any case, it better represents how the compiler actually interprets things. Indeed, it makes it obvious that if we remove the this-> prefix from the first occurrence of number, we will end up with the problem discussed earlier: number will be interpreted exclusively as the function parameter. But don't take my word for it, see it for yourself:

struct AddNumber
{
	...

	int number;
};

int AddNumber::add(const AddNumber* this, const int number)
{
	return number + number; /* this pointer not used, return 2*number */
}

This brings us to the first lesson of this post: whenever you see a non-static member function, try to always read it as a stand-alone (i.e., non-member) function containing a parameter called this which is a pointer to the object the function is doing its work for.

One question which must be asked at this point is: what about static member functions? Do they also implicitly contain a this pointer? The answer is no, they don't. If they did, they would inevitably be associated with some existing object of the class, but static member functions, like static data members, belong to the class itself and can be invoked directly, i.e., without the need for an an existing class object. In this regard, a static member function is in no way special: the compiler will neither implicitly add a this parameter to its declaration nor introduce this-> prefixes anywhere on its definition.

Static member functions have, however, access to the internals of a class like any other member or friend function, provided it is given a pointer to a class object. This means the following code is valid:

class AddNumber
{
public:

	...

	static int add(const AddNumber* adder, const int number);

private:
	int number;
};

int AddNumber::add(const AddNumber* adder, const int number)
{
	return adder->number + number;
}

There is one type of situation in which the implicit presence of the this pointer on non-static member functions can cause a lot of headache to the innocent developer. Here it is, in its full "glory":

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

class WarningManager
{
public:

	...

	void add_warning(const std::string& message) const;

private:
	std::string name;
};

void WarningManager::add_warning(const std::string& message) const
{
	warnings.emplace_back([=]() {
		std::cout << name << ": " << message << "\n";
	});
}

The purpose of the code above is simple: WarningManager::add_warning populates the global array warnings with lambda functions which print some warning message when invoked. Regardless of how silly the purpose of this code may seem, scenarios like these do happen in practice. And being so, do you see what is the problem here?

If the problem is unclear to you, consider the advice given earlier: read the member function WarningManager::add_warning as a non-member function which takes a pointer called this to a WarningManager object:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

struct WarningManager
{
	...

	std::string name;
};

void WarningManager::add_warning(const WarningManager* this,
                                 const std::string& message)
{
	warnings.emplace_back([=]() {
		std::cout << this->name << ": " << message << "\n";
	});
}

You may be puzzled with the fact that name on the original version of the code was replaced by this->name on the (remember, invalid) second version. Perhaps you are asking yourself: "isn't name itself actually copied by the capture list on the lambda function"? The answer is no. A "capture all by value" capture list (i.e., [=]) captures all non-static local variables which are visible in the scope where the lambda is created and nothing else. Function parameters fall into this category, but class data members don't. Therefore, the code above is conceptually identical to the following one:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

struct WarningManager
{
	...

	std::string name;
};

void WarningManager::add_warning(const WarningManager* this,
                                 const std::string& message)
{
	warnings.emplace_back([this, message]() {
		std::cout << this->name << ": " << message << "\n";
	});
}

The problem is now easier to spot: in the original example, the name data member is not being captured directly by value, but is instead accessed through a copy of the this pointer to the WarningManager object for which WarningManager::add_warning is called. Since the lambda may be invoked at a point at which that object may no longer exist, the code above is a recipe for disaster. The lifetime of the lambda is independent from the lifetime of the WarningManager object which creates it, and the implicit replacement of name by this->name on the definition of the lambda means we can find ourselves debugging an obscure program crash.

A simple way to fix the problem just discussed is by being explicit about what we want: we want to capture name by value, so let's go ahead and make that very clear to everyone:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

class WarningManager
{
public:

	...

	void add_warning(const std::string& message) const;

private:
	std::string name;
};

void WarningManager::add_warning(const std::string& message) const
{
	const std::string& manager_name = this->name;

	warnings.emplace_back([manager_name, message]() {
		std::cout << manager_name << ": " << message << "\n";
	});
}

Inside the capture list, the string this->name will be copied through its reference manager_name, and the lambda will therefore own a copy of this->name under the name manager_name. In C++14, this code can be simplified using the init capture capability which was added to lambda functions:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

class WarningManager
{
public:

	...

	void add_warning(const std::string& message) const;

private:
	std::string name;
};

void WarningManager::add_warning(const std::string& message) const
{
	warnings.emplace_back([manager_name = this->name, message]() {
		std::cout << manager_name << ": " << message << "\n";
	});
}

In this case, we are explicitly coping this->name into a string called manager_name which is then accessible inside the lambda function. As discussed in a previous post, lambda functions are equivalent to functor classes, and in this case, manager_name is a data member of such a class which is initialized as a copy of this->name.

To close this post, I strongly recommend you read the Zen of Python. Look at the second guiding principle: "Explicit is better than implicit". After reading this post, I hope you can better appreciate what a wise statement that is! :-)

Comments (0) Direct link