Constexpr unions

I assume you are already familiar with constexpr functions. (If not, see a short introduction here.) In this post I wanted to share my experience with using unions in constant expressions. Unions are not very popular due to type-safety hole they open, but they offer some capabilities that I found priceless when working with Fernando Cacciola on std::optional proposal.

Background

Do you know Boost.Optional library? In very short, boost::optional<T> is a ‘compound’ value that can store any value of T plus one additional state that indicates that no value of T is currently stored. It is a nullable T.

One of the features that boost::optional offers is that when you initialize it to store the null state, it does not construct any T at all. It does not even call T’s default constructor — for performance reasons, and also in cases where T is not default-constructible. One way to implement this is to provide some raw memory buffer big enough to store an object of type T and use in-place constructor to initialize it only when necessary:

template <typename T>
class optional
{
  bool initialized_;
  char storage_[ sizeof(T) ];
  // ...
};

This is only to give you an idea of a possible implementation. In practice, it would not work due to alignment reasons; we would have to use std::aligned_storage; or we would have to use a discriminated union — this has been described in detail by Cassio Neri in ACCU Overload #112. The null-state constructor and ‘real-value’ constructor can be implemented as:

optional<T>::optional(none_t)  // null-state tag
{
  initialized_ = false;
  // leave storage_ uninitialized
};

optional<T>::optional(T const& val)
{
  new (storage_) T{val};       // placement new
  initialized_ = true;
};

The definition of the destructor, as you already figured out, is similar to:

optional<T>::~optional()
{
  if (initialized_) {
    static_cast<T*>(storage_) -> T::~T(); 
  }
};

Problem 1

In case of the std::optional, there are other features that are required of the library. One such feature is that std::optional<T> shall be a literal type: a type whose objects can be used as compile-time constants. One constraint that the Standard imposes on literal types is that they should provide a trivial destructor: a destructor that does nothing. As we can see above, optional’s destructor has to do something, so we cannot achieve our goal in general. However, we can achieve our goal for certain Ts that have a trivial destructor themselves. Imagine that T is int: we do not have to call int’s destructor — because it is trivial. Here we also arrive at the practical definition of a trivial destructor: it is a destructor that we can skip (simply not call it) without any harm.

Another requirement for literal types is that they should have at least one constexpr constructor. This constructor(s) will be used to create compile-time constants. However, in order to avoid “compile-time undefined behavior”, the Standard imposes a number of constraints on constexpr constructors and their types to make sure that no data member or base-class sub-object is left uninitialized. Thus, our implementation of optional with appropriately sized array of chars will not work because in “value” constructor the array is not initialized in member-initializer-list. We could fill the array with zeros in the null-state constructor, but this zero-fill is also a run-time cost. We would have a similar problem if we used std::aligned_storage for implementation. We also cannot use a simple discriminated union implementation (as proposed in ACCU Overload #112):

template <typename T>
class optional
{
  bool initialized_;
  union { T storage_ }; // anonymous union
};

Because in order to create an “uninitialized” optional we would have to either leave the anonymous union uninitialized, which is not acceptable in constexpr functions, or default-initialize storage_, but this is counter to our design goal: we wanted to skip T’s default construction.

Problem 2

Another ambitious design goal is the properties of the function that extracts the value contained in the optional object. In boost::optional as well as in the proposed std::optional in order to access the contained value we use operator* (the indirection operator). In order to guarantee the maximum run-time performance, we do not check if the optional object has been initialized to store a meaningful value: we state this requirement as function’s precondition, and blindly access the storage for our T:

explicit optional<T>::operator bool() const // check for being initialized
{
  return initialized_;
};

T const& optional<T>::operator*() const
// precondition: bool(*this)
{
  return *static_cast<T*>(storage_);
}

At the same time, we want to be able to call operator* at compile-time, and in this case, we want the compilation to fail if we are trying to access the value form an uninitialized optional object. We could be tempted to use the method described in my other post on compile-time computations:

constexpr explicit optional<T>::operator bool()
{
  return initialized_;
};

constexpr T const& optional<T>::operator*()
{
  return bool(*this) ? *static_cast<T*>(storage_) : throw uninitialized_optional();
}

This is not acceptable, though. We would achieve the desired compile-time behavior, but we would force a check at run-time which would hit our performance. Is it possible to do the check at compile-time, but skip it at run-time?

Solution

Both these problems are solved by using a union of T and a dummy, empty class:

struct dummy_t{};

template <typename T>
union optional_storage
{
  static_assert( is_trivially_destructible<T>::value, "" );

  dummy_t dummy_;
  T       value_;

  constexpr optional_storage()            // null-state ctor
    : dummy_{} {}

  constexpr optional_storage(T const& v)  // value ctor
    : value_{v} {}

  ~optional_storage() = default;          // trivial dtor
};

There are special rules for using unions in constexpr functions and constructors. We are required to initialize only one member of a union. (Obviously, you cannot initialize more than one, because they occupy the same storage.) This member is called active. In case we want to leave the storage uninitialized, we initialize the dummy member. This meets all the formal requirements of compile-time initialization, but since dummy_t contains no data, its value-initialization costs nothing in run-time.

Second, reading (strictly speaking: triggering lvalue-to-rvalue conversion of) the inactive member of a union is defined as being not a core constant expression, and using it in compile-time computations is a compile-time error. The following example illustrates this:

constexpr optional_storage<int> oi{1}; // ok
constexpr int i = oi.value_;           // ok
static_assert(i == 1, "");             // ok

constexpr optional_storage<int> oj{};  // ok
constexpr int j = oj.value_;           // compile-time error

Class template optional (for trivially destructible Ts) can be implemented as:

template <typename T>
// requires: is_trivially_destructible<T>::value
class optional
{
  bool initialized_;
  optional_storage<T> storage_;

public:
  constexpr optional(none_t) : initialized_{false}, storage_{} {}

  constexpr optional(T const& v) : initialized_{true}, storage_{v} {}

  constexpr T const& operator*() 
  // precondition: bool(*this) 
  {
    return storage_.value_;
  }

  // ...
};

The compile-time error message in operator* is not ideal: it does not mention optional object being uninitialized, but only the usage of inactive union member. However, the primary goal is achieved: we refuse to compile the invalid value access.

You can find the reference implementation of the proposed std::optional here.

About these ads
This entry was posted in programming and tagged . Bookmark the permalink.

13 Responses to Constexpr unions

  1. dinkaranns says:

    Funnily enough, I read the Cassio Neri’s article on Member Initialiser List just yesterday. My self-imposed task for today was to google for related topics (including std::optional proposal). Incredible timing for this post! Thanks ! :)

  2. moswald says:

    I believe the first code snippet under “Solution” should have `dummy_` and `value_` wrapped in a union.

  3. Gary says:

    Hi Andrie,

    https://github.com/akrzemi1/Optional/blob/master/optional.hpp

    line: 321: else if (initialized() == true && rhs.initialized() == true) *dataptr() = std::move(*rhs);

    Shouldn’t you call dataptr()-> T::~T();
    before trying to do a move into that space?

    • This behavior is intendes. Condition initialized() == true && rhs.initialized() == true represents the situation where both optional objects in question are “initialized”. In this case we can use T’s assignment operator. And no destructor call is necessary. Conceptually (except for exception safety guarantees, performance considerations and life-time issues) copy-assignment is equivalent to first destroying an object and then copy-constructing it.

  4. Fernando Pelliccioni says:

    Excellent article.

    The following code is invalid in C++11

    template
    union optional_storage : optional_storage
    {
    T value_;
    };

    I think it would be good to have it in the language to implement a VariantType.

  5. You need to put it into “code” tag but use square brackets:

    [code language="cpp"]
    template <typename T>
    // ...
    [/code]

    I will need to write guidelines for using this mark-up language.

  6. Savyasachi Singh says:

    I guess the operator-> method for class optional at line 365 of optional.hpp should be constexpr.
    Should it be as follows
    constexpr T const* operator ->() const {

    }

  7. Armand Leclercq says:

    I looked around for a while, and I couldn’t figure out why an union does have a different meaning and comportment in run-time and compile-time.

    For example:

    union test
    {
      double d;
      unsigned long int l;
    
      constexpr test(double val) : d{val} /* , l{static_cast<unsigned long int>(val)} */ {}
      constexpr operator unsigned long int () const { return l; }
    };
    

    As a constexpr, I cannot read my double as an unsigned long, but as “classic” C++ I can.

    Can you tell me why and where the Standard created that difference in behavior ?

    • Hi Armand. Here is the link to the relevant paper and discussion: Type punning in constant expressions.

      To add something from myself: you could use unions in two ways:

      1. Store different values at different times.
      2. Use bit-pattern of one value and interpret it as another type.

      If you use unions as in bullet one, you can see no difference in constexpr functions. If you use bullets as in bullet two, then indeed, you have the restriction.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s