Wednesday, March 26, 2014

std::vector with constructors that throw exceptions

When using std::vector, reallocating may happen for several reasons:

class A { ... };
std::vector<A> v;
v.push_back(A()); // may reallocate
v.resize(100); // may reallocate

When reallocation happens, all elements of the vector need to be copied or moved to a new memory location. There two things to wonder about then: will std::vector reallocate by copying, or moving the objects? And what if one of A's constructors (A(A&&)) throws and the other (A(const A&)) doesn't throw?

The table below shows the situation, as guaranteed by the C++ standard. (This article assumes that A's destructor doesn't throw any exceptions.)

Constructors No copy Copy throws Copy no throw
No move - Throws (copies) No throw (copies)
Move throws Throws (moves) Throws (moves) No throw (copies)
Move no throw No throw (moves) No throw (moves) No throw (moves)

In other words: if one of copy/move is not available, std::vector picks the other one (if none are available, you can't use std::vector). If both are available and one throws but not the other, it pick the one that doesn't throw. If both throw, it uses move (since we can't do better anyway). If none throw, it uses move.

The most non-obvious part is this: when std::vector has to chose between the slower copy constructor that does not throw, and the faster move constructor that may throw, it takes the slower, but safer, copy constructor.

What can I assume when an exception is thrown (from copy/move constructor)?

What are you allowed to assume about the state of the objects inside the vector after an exception is thrown? With respect to exceptions thrown by the copy and move constructors, you only get the basic exception guarantee: no memory leaks have occurred, and all objects (A) are in a well defined state. They may not have the same value as prior to the exception, but you can at least reassign them, e.g. v.back() = A();.

How does the compiler know whether a copy/move constructor throws?

It doesn't usually. If it can prove that it won't, it will take advantage of that to offer the best possible alternative (that's what the table above shows). If it can't prove, it will assume the worst: that the copy/move constructor may throw (in the table above). You can "force" it to assume it won't throw by using noexcept:

class A {
     A(A&&) noexcept; // force compiler to always move

Formally, the compiler encodes information about "provably not throwable" in std::is_nothrow_move_constructible (which, if pedantic, should perhaps be called is_proven_nothrow_move_constructible). The logic of the table above is then encoded in the conditional move operator std::move_if_noexcept. Indeed, this means different compilers may produce different results in terms of moving vs copying (but if a compiler moves, it's always because that was provably the better thing to do).

Do compilers actually do this correctly?

Microsoft Visual Studio 2013 with CTP 1 does not. Here's code to test it with your compiler:

struct A
 A() = default;
 A(A&&) { throw 1; }
 A(const A&) = default;

int main()
 std::vector<A> v;

 try {
 } catch (int) {
  std::cerr << "BUG: should have used copy constructor instead\n";

With MSVS 2013 CTP 1, this prints "BUG: should have used copy constructor instead". Using noexcept does not help either.

Is there a way to do avoid these issues?

Yes, only use std::vector when at least one of the copy/move constructor does not throw (and use noexcept to make sure the compiler sees that). If both constructors throw, use std::list. Since it never reallocates, you will never have these issues. std::deque can also be used if you only push_front and push_back elements, as it doesn't reallocate then.

What about exceptions thrown by other member functions (not copy/move constructor)?

(Off topic, only here to clarify the difference between the basic exception guarantee above and the more commonly known strong exception guarantee). Then you get the strong exception guarantee, which basically says that everything has been rollbacked to the state just prior to the thrown exception. All objects have the values you'd expect. This is just like when performing database transactions.

Wednesday, March 19, 2014

Inductive Reasoning Visualized

Ever wondered what inductive reasoning (technically, using inductive logic programming) would look like if you could draw a picture?
Here's how:

I'll explain what you're looking at. Let us say you know the following facts:
Gaia is a parent of Cronus.
Cronus is a parent of Zeus.
Zeus is a parent of Athena.

You also know that:
Gaia is a grandparent of Zeus.
Zeus is a grandparent of Athena.
Gaia is not a grandparent of herself.
Gaia is not a grandparent of Cronus.
Cronus is not a grandparent of Gaia.
Athena is not a grandparent of Cronus.

Now you ask the computer to induce a definition of grandparenthood based on these facts.

To do this, the machine needs to try different possibilities, and these are what you see in the graph.

On top, you see:
Now the sentence "X is a grandparent of Y" is what the machine writes as "grandparent(X,Y)", and an underscore simply means "anybody". So this is the hypothesis that "anybody is a grandparent of anybody".
The machine knows this to be false because of what you see in the red square: 4. Four is the number of "problems" found with this hypothesis: namely, it predicts that "Gaia is a grandparent of herself", which we know to be false. It predicts every instance of "is not a grandparent of" above, and there are 4 of them. Thus this hypothesis is not consistent with observations (its predictions are falsified).

Next we have
grandparent(A,_) :- parent(A,_)
which in English reads "A is a grandparent of anyone if A is a parent of anyone". As you can see, the red box says 3, because it has 3 problems: it predicts that Gaia is a grandparent of herself, since Gaia is a parent (of whom does not matter, but it happens to be Zeus), which we know to be false. For the same reason, it predicts that Gaia is a grandparent of Zeus, which is also false. Finally, it predicts that Cronus is a grandparent of Gaia, since Cronus is a parent (again, of whom does not matter). The negative example "Athena is not a grandparent of Cronus" is not (incorrectly) predicted to be true, since Athena is not a parent.

This is the basic idea in Inductive Logic Programming: we construct lots of hypotheses and test them against the examples we have. There are two solutions that look promising (green boxes):
grandparent(A,B) :- parent(A,C), parent(C,B)
which states that A is a grandparent of B if A is a parent of some C and that C is a parent of B. This is indeed the correct definition, and it does cover both positive examples ("Gaia is a grandparent of Zeus", "Zeus is a grandparent of Athena"), and does not cover any of the 4 negative examples.

The other promising solution is
grandparent(A,B) :- parent(A,C), parent(C,B), parent(B,_)
which gets the grandparent relation slightly wrong: on top of requiring the correct conditions (A is a parent of some C, which is a parent of B), it also requires the grandchild B to be a parent. So according to this definition, Athena is not the grandchild of Gaia because she does not (yet) have any children, but when she does, she'll satisfy the conditions. The machine knows this definition is worse than the right one because it cannot explain the fact that Zeus is a grandparent of Athena. Hence it only explains one of the two facts (that's the 1 in the green gox).

I'll leave it as an exercise to interpret all the other hypotheses in the graph.

The picture was produced using my ILP system Atom.