What is boost::optional efficiency?

Question

I have the following:

class Obj;
typedef std::map<string, string> StrMap;
std::map<std::string, std::pair<Obj, StrMap> > complexMap;

The thing is that for some entries in complexMap the StrMap will be empty and I won't use it at all, so for efficiency I'm considering to use boost::optional. My question is what's the efficiency of boost::optional, I'm afraid that by paying its price I will gain nothing at the end.

Answer 1

Think of optional as a container that can hold 0 or 1 values. Your map already is a container that can hold 0 to N elements. An optional map is therefore a container-in-a-container which can hold 0 to N elements. Really, there's no benefit here.

The overhead of an empty map is quite small. Maps are really built from map nodes, internally, and an empty map just doesn´t have any nodes. (It can´t, because each node holds a value, and there´s no way by which an empty map could create a default value)

Answer 2

Moving the comment to an answer...

Think about how the optional is implemented, it normally has some internal storage (to allow it to the hold the map object - as you would in your code above), and the only difference is that it doesn't construct the map in that storage - this is left for later. However the optional object has to be constructed. So now instead of just constructing a map, you're constructing a bigger optional object in the case where you are not using the map, and when you use the map, you have to construct that too. Seems like you're doing more things for little benefit.

There are cases where optional does make sense (for example return values, where you want to indicate an invalid state for example, or you have a very expensive constructor which does lots of initialization of complex members), for objects with trivial constructors, optional really is not worth the code clutter.

Disclaimer: But as with all performance related questions, profile, profile and then profile again...

Answer 3

If you are doing a "sparse" computation, you can do two things:

1. keep a large complexMap containing the a lot of non-existing results with a boost::optional. This encapsulates the sparseness on a per-element basis.
2. create an extra layer of indirection (unordered_map e.g.) that contains pointers to the existing elements in your complexmMap. This encapsulates the sparseness on a per-map basis.

Alternative 1 will be more convenient for you as a programmer, requiring little though at the expense of space overhead. Alternative 2 will be almost perfectly space-efficient and keep complexMap as small as possible, but requires more programming work up-front.

Pick whichever alternative is more acceptable to you (hint: if you are doing gigabyte level computation in complexMap, maybe the extra level of indirection pays off, otherwise I wouldn't bother).

Other than a space-overhead, there is little other cost to boost::optional, since it does not require a default constructor or dynamic memory allocation.