Home

Awesome

tiny::optional <!-- omit in toc -->

tests of gcc on linux tests of clang on linux tests of msvc on windows tests of clang on windows tests of gcc on windows tests of clang on macOS

Introduction

The goal of this library is to provide the functionality of std::optional while not wasting any memory unnecessarily for

  1. types with unused bits (currently double, float, bool, raw pointers; note that NaNs, nullptr etc. are still valid non-empty values!), or
  2. custom types with unused states, or
  3. where a specific programmer-defined sentinel value should be used (e.g., an optional of int where the value 0 should indicate "no value").

⚠️ Warning: This library exploits undefined/platform specific behavior on x86/x64 architectures to implement the first case. However, this first case can be disabled to allow using the second and third cases also on other architectures. See chapter "Disabling platform specific tricks (TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS)" for more details.

For a quick start, see the following example, also available live on godbolt:

//--------- Automatic exploitation of unused bit patterns ---------
// Assume you have the following optional variable:
std::optional<double> stdOptional;

// The size of it is 16 bytes due to padding; 7 bytes are wasted:
static_assert(sizeof(stdOptional) == 16);

// Replacing std::optional with tiny::optional does not waste space:
tiny::optional<double> tinyOptional;
static_assert(sizeof(tinyOptional) == 8);

// This works automatically for bool, float, double and raw pointers.


//--------- Usage of sentinel values ---------
// But what about other types, such as integers? If you know that not the 
// whole value range is used, you can instruct the library to exploit this.
// For example, assume you have an optional index into e.g. some array:
std::optional<int> stdIndex;
// which has a size of 8 bytes due to padding:
static_assert(sizeof(stdIndex) == 8);

// Assume you know that negative values can never occur. Then you can instruct
// the library to use e.g. -1 as "sentinel" and save half the memory:
tiny::optional<int, -1> tinyIndex;
static_assert(sizeof(tinyIndex) == 4);
// This is more expressive and safe than using a raw variable with a comment:
int poorMansTinyIndex = -1; // -1 value indicates emptiness

// Of course, attempting to store the value -1 in tinyIndex is an error
// and actually triggers an assertion (if not compiled with NDEBUG):
//    tinyIndex = -1; // Uncomment to trigger assert

// Note that without such a user supplied sentinel value, the optional is 
// not "tiny", because in principle the whole value range could be used:
static_assert(sizeof(tiny::optional<int>) == sizeof(std::optional<int>));

// You can also instruct the library to use a member variable of the
// contained type to store the information about the empty state. See below.

Motivation

Use case 1: Wasting no memory

std::optional always uses a separate bool member to store the information if a value is set or not. A bool always has a size of at least 1 byte, and often implies several padding bytes afterwards. For example, a double has a size of 8 bytes. A std::optional<double> typically has a size of 16 bytes because the compiler inserts 7 padding bytes after the internal bool. But for several types this is unnecessary because they have unused bit patterns. Therefore, std::optional often just wastes memory and is not very cache-friendly. This library exploits these unused bit patterns to store the information if a value is set or not in-place within the payload itself, without loosing any "valid" values. To emphasize this:

See the end of the readme for details on how the library achieves this.

tiny::optional can also be "taught" how it may store a custom payload type with an unused state without requiring an additional internal bool. See the chapter about tiny::optional_flag_manipulator.

The results below show that in memory bound applications this can result in a significant performance improvement. This optimization is similar to what Rust is doing for booleans and references.

Note: The built-in exploitation of unused bit patterns is available only on x86/x64. If you try to compile the library on any other platform you get a compiler error. To allow the following use cases on other platforms, you can disable the platform specific tricks as explained in the chapter "Disabling platform specific tricks (TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS)".

Use case 2: Using sentinel values

Sometimes one wants to use special "sentinel" or "flag" values to indicate that a certain variable does not contain any information. Think about a raw integer int index that stores an index into some array and where the special value -1 should indicate that the index does not refer to anything. Looking at such a variable, it is not immediately clear that it can have such a special "empty" state. This makes code harder to understand and might introduce subtle bugs.

The present library can be used to provide more semantics: tiny::optional<int, -1> immediately tells the reader that the variable might be empty, and that the "sentinel" -1 must not be within the set of valid values. At the same time, it does not waste additional memory (i.e. sizeof(tiny::optional<int, -1>) == sizeof(int)), in contrast to std::optional<int>.

Note: In contrast to the first use case, the sentinel value is "removed" from the range of valid values of the type. So -1 cannot be stored in tiny::optional<int, -1>.

Requirements

Besides the C++ standard library, there are no external dependencies. The library requires at least C++17. The monadic operations and_then() and transform() are always defined (although the C++ standard introduced them starting only with C++23). When C++20 is enabled, the three-way comparison operator operator<=>() and the monadic operation or_else() are additionally implemented.

The full functionality of the library is supported only on x64 and x86 architectures on Windows, Linux and Mac. By disabling tricks relying on undefined behavior, as explained in "Disabling platform specific tricks (TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS)", any standard conforming platform should work.

The library is regularly tested on MSVC, clang and gcc on Windows, Linux and Mac (see the github actions).

Limitations

Platform specific behavior

This library exploits platform specific behavior (i.e. undefined behavior). So if your own code also uses platform specific tricks, you might want to check that they are not incompatible. Compare the section below where the tricks employed by this library are explained.

Note that you can disable them by defining TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS, as explained in the chapter "Disabling platform specific tricks (TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS)".

Compatibility with std::optional

Currently, the following components of the interface of std::optional are not yet supported:

Moreover, the monadic operation transform() always returns a tiny::optional<T>, i.e. specification of a sentinel or some other optional as return type (tiny::optional_sentinel_via_type etc.) is not possible. As a workaround, you can use and_then().

Installation

This is a header-only library.

Installation using cmake

Via find_package (recommended):

  1. Clone or download the tiny-optional repository.
  2. In its root directory, execute 
    cmake -B build
sudo cmake --install build
    to generate the files in the folder build and then install them to the default location (e.g. /usr/local/ on linux, C:\Program Files on Windows). Alternatively, to install into some custom directory: 
    cmake -B build -DCMAKE_INSTALL_PREFIX="/path/to/custom/tiny/optional/install/dir"
cmake --install build
  3. In your own project's CMakeLists.txt, add: 
    find_package(tiny-optional CONFIG REQUIRED)
target_link_libraries(<target> PRIVATE tiny-optional::tiny-optional)
    where <target> is the cmake target that uses the library. If you had installed the library in a custom location, you need tell cmake about it, e.g. via CMAKE_PREFIX_PATH (for example, run cmake as cmake <path> -DCMAKE_PREFIX_PATH="/path/to/custom/tiny/optional/install/dir").

Alternative via add_subdirectory:

  1. Put all files of the tiny-optional library in a subdirectory of your own project, so that you end up with own_project/tiny-optional/CMakeLists.txt and own_project/tiny-optional/include/.
    (Actually, not all files but only those in tiny-optional/CMakeLists.txt and tiny-optional/include/ are required.)
  2. In your own project's own_project/CMakeLists.txt, add: 
    add_subdirectory(tiny-optional)
target_link_libraries(<target> PRIVATE tiny-optional::tiny-optional)

Manual installation

Just copy the folder from the include directory containing the headers to your project. Include it via #include <tiny/optional>.

Preprocessor flags

Compatibility between different versions

Different versions of tiny::optional are only guaranteed to be API and ABI compatible between different patch versions. Different major and different minor versions are not compatible. This breaks with usual semantic versioning rules (where newer minor versions are compatible with older ones), mainly because most updates to tiny::optional are breaking changes and therefore would lead to very high major versions fast (which look "weird").

The types defined by the library are in an inline namespace that encodes the major and the minor version numbers, causing build time errors when mixing different versions.

Also see chapter "Helpers to distinguish types at compile-time (metaprogramming)".

Natvis

The include directory contains a Natvis file which improves the display of the optionals in the Visual Studio debugger considerably. Copy and add the Natvis file to your project, or append its content to your existing Natvis file. See the official Microsoft documentation for more information on Natvis.

The Natvis visualizers show whether the optional contains a value or not, and if it does, the contained value. Unfortunately, when you specialize tiny::optional_flag_manipulator, it is not reasonably possible to write a generic Natvis visualizer because Natvis does not allow to call any functions (even if they are constexpr). So you need to add additional visualizers for each custom specialization yourself. The same holds true for tiny::optional_inplace.

Notes:

Usage

Using tiny::optional as std::optional replacement

Instead of writing std::optional<T>, use tiny::optional<T> in your code. If the payload T is a float, double, bool or a pointer/function pointer (in the sense of std::is_pointer), the optional will not require additional space. E.g.: sizeof(tiny::optional<double>) == sizeof(double).
Notes:

For other types (where the automatic "tiny" state is not possible), the size of tiny::optional is equal to that of std::optional. E.g. sizeof(tiny::optional<int>) == sizeof(std::optional<int>), or sizeof(tiny::optional<SomeStruct>) == sizeof(std::optional<SomeStruct>).
But note that you can teach the library about custom types, see the chapter about tiny::optional_flag_manipulator below.

Besides this, all standard operations such as assignment of std::nullopt are supported (with the exceptions listed above).

Using a sentinel value

tiny::optional has a second optional template parameter: tiny::optional<T, sentinel>. sentinel is not a type but rather a non-type template parameter ("NTTP"). Setting this sentinel value instructs the library to assume that the value sentinel cannot occur as a valid value of the payload T and thus allows the library to use it to indicate the empty state. As a result: sizeof(tiny::optional<T, sentinel>) == sizeof(T).

The sentinel should be of type T. Any value is possible that is supported by the compiler as a non-type template parameter. That means integers, and since C++20 also floating point types and literal class types (i.e. POD like types) that are equipped with an operator==.

Examples: tiny::optional<unsigned int, MAX_UINT> and tiny::optional<int, -1>.

Note: Attempting to store the sentinel value in the optional is illegal. If NDEBUG is not defined, an appropriate assert() gets triggered. For example, if you define tiny::optional<int, -1> o;, setting o = -1; is not allowed and triggers the assert.

Storing the empty state in a member variable

Imagine you have a simple POD-like data structure such as

struct Data
{
    int var1;
    double var2;
    MoreData * var3;
    // More stuff...
};

and you need an optional variable of Data. Writing tiny::optional<Data> works but the optional requires an additional internal bool, so the size of tiny::optional<Data> will be the same as std::optional<Data>. This is unnecessary since some members of Data have unused bit patterns, namely var2 and var3. The library allows to exploit this by specifying an accessible member where the emptiness flag can be stored: tiny::optional<Data, &Data::var2>. The resulting optional has the same size as Data. Using tiny::optional<Data, &Data::var3> works as well here. In fact, all the types mentioned above where the library stores the empty flag in-place can be specified. Moreover, all members for which a specialization of tiny::optional_flag_manipulator exist (see chapter below), work too.

Additionally, there is the option to use a sentinel value for the empty state and instruct the library to store it in one of the members. The sentinel value is specified as the third template parameter. For example, if you know that Data::var1 can never be negative, you can instruct the library to use the value -1 as sentinel: tiny::optional<Data, &Data::var1, -1>. Again the resulting tiny::optional will not require additional memory compared to a plain Data.

Note: When storing the flag in a member variable, gcc with optimizations turned on likes to warn about possible uninitialized accesses (-Wmaybe-uninitialized). These are false positives. gcc fails to figure out that certain branches that would lead to access of uninitialized memory cannot occur because these branches are protected by has_value() calls. Unfortunately, gcc sometimes still attributes the warnings to a location in the user code rather than the library, so although the library actually by itself disables the warning locally (in the tiny/optional.h header file), it might still occur. In fact, even the standard stdlibc++ implementation of std::optional at least until gcc 13 can trigger this warning. If it happens to you, I suggest to disable the warning locally.

Note: Using a member like this is actually undefined behavior. Hence it is available only on x86/x64. To allow compilation on other platforms, see the chapter "Disabling platform specific tricks (TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS)". In this case the member pointer argument is ignored and a separate bool is used.

The full signature of tiny::optional

Given the explanations above, the full signature of tiny::optional is:

namespace tiny {
    template <
        class PayloadType, 
        auto sentinelOrMemPtr = UseDefaultValue, 
        auto irrelevantOrSentinel = UseDefaultValue>
    class optional;
}

The first template parameter specifies the type that should get stored in the optional. The second and third parameters are optional. If the second parameter is not a member pointer, the value is used as sentinel for the empty state. If the second parameter is a member pointer, it has to point to a member of PayloadType in which case the emptiness flag is stored in that member. Only in this case the third parameter may be optionally specified to indicate a sentinel value to store in that member.

Available non-member definitions

The template function tiny::make_optional() can be used to create a tiny::optional. Contrary to std::make_optional(), it can accept two additional optional template parameters corresponding to sentinelOrMemPtr and irrelevantOrSentinel explained above. Examples:

tiny::make_optional(42.0); // Constructs tiny::optional<double>(42.0)
tiny::make_optional<unsigned int, 0>(42u); // Constructs tiny::optional<unsigned int, 0>(42)

struct Foo{
    int v1;
    double v2;
    Foo(int v1, double v2);
};
tiny::make_optional<Foo>(2, 3.0); // tiny::optional<Foo>(2, 3.0), has size of std::optional
tiny::make_optional<Foo, &Foo::v1, -1>(2, 3.0); // tiny::optional<Foo, &Foo::v1, -1>(2, 3.0)

All the comparison operators operator==, operator<=, etc. are provided, including the spaceship operator<=> similar to the ones for std::optional.

Additionally, std::hash is specialized (as for std::optional) for the optional types defined by this library.

An appropriate deduction guide is also defined, allowing to write e.g. tiny::optional{42} to construct a tiny::optional<int>{42}. Note that this does not allow you to specify a sentinel.

Helpers to distinguish types at compile-time (metaprogramming)

There are a few helpers available which facilitate checks at compile-time:

Specifying a sentinel value via a type

tiny::optional accepts as second or third template parameter a value, i.e. they are non-type template parameters. Especially in C++17, this can be restricting since e.g. floating point values cannot be used in templates. But they can be static member constants. To this end, the library provides an additional type

namespace tiny {
    template <
        class PayloadType, 
        class SentinelValue, 
        auto memPtr = UseDefaultValue>
    class optional_sentinel_via_type;
}

where the sentinel value is expected to be given by SentinelValue::value. Note that this second template parameter is not optional. If you do not need a sentinel, just use tiny::optional<PayloadType>. The third parameter is optional and can be a member pointer to instruct the library to store the sentinel value in that member, similar to tiny::optional. I.e. the SentinelValue::value gets stored in memPtr. Contrary to tiny::optional, it has to be the third and not the second parameter. This is for technical reasons (you cannot mix type and non-type template parameters, and having an optional parameter second and a mandatory third parameter makes no sense).

An optional type with automatic sentinels for integers and guarantee of in-place

The type tiny::optional_aip ("aip" for "always in-place") is similar to tiny::optional but with automatic "swallowing" of a value for integers to provide a sentinel, and a compilation error if no sentinel is automatically found. Hence, its size is ALWAYS the same as the size of the payload.

Its declaration is basically tiny::optional_aip<PayloadType, SentinelValue = ...>. If you omit the SentinelValue, then:

In all other cases, you have to specify a sentinel yourself, e.g. tiny::optional_aip<char, 'a'>. If you do not, then a compilation error occurs. Hence, tiny::optional_aip is guaranteed to have the same size as the payload.

The type has been suggested in this issue.

Teaching tiny::optional about custom types (tiny::optional_flag_manipulator)

Introduction

The library provides a customization point: By specializing tiny::optional_flag_manipulator for a custom type, you instruct the library to always place the emptiness flag within the payload type, and how to do that. The method of customization by means of a specialization is the same as used by e.g. std::hash and fmt::formatter.

Example

Assume you have some custom type MyNamespace::IndexPair defined as

namespace MyNamespace
{
    class IndexPair
    {
        // ...
        // Both can never be negative at the same time.
        int mIndex1;
        int mIndex2;
    };
}

You, as the author of IndexPair, know that not the whole theoretical range of values is used, i.e. there is some combination of values of member variables that are unused in your application: Both indices can never be negative simultaneously. Therefore, you want to exploit this, so that a tiny::optional<IndexPair> should always be in the "tiny" state (sizeof(tiny::optional<IndexPair>) == sizeof(IndexPair)). This can be achieved by specializing tiny::optional_flag_manipulator as follows:

#include <tiny/optional_flag_manipulator_fwd.h>
#include <new> // for placement new

namespace MyNamespace
{
    class IndexPair
    {
    public:
        void SetIndices(int idx1, int idx2)
        {
            mIndex1 = idx1;
            mIndex2 = idx2;
        }
       
        int GetIndex1() const { return mIndex1; }
        int GetIndex2() const { return mIndex2; }
    
    private:
        // Both can never be negative at the same time.
        int mIndex1;
        int mIndex2;
    };
}

template <>
struct tiny::optional_flag_manipulator<MyNamespace::IndexPair>
{
    static bool is_empty(MyNamespace::IndexPair const & payload) noexcept
    {
        // Needs to return true if the optional should be considered empty.
        // I.e. if the given "payload" state indicates emptiness. It can be called after 
        // init_empty_flag() or invalidate_empty_flag() by the library.
        return payload.GetIndex1() < 0 && payload.GetIndex2() < 0;
    }
    
    static void init_empty_flag(MyNamespace::IndexPair & uninitializedPayloadMemory) noexcept
    {
        // uninitializedPayloadMemory is a reference to an **uninitialized** payload (i.e. 
        // the constructor of the payload has not been called, but the memory has been
        // already allocated).
        // This function is called when the optional is constructed in an empty state or
        // once it should become empty. The function must initialize the memory such that 
        // the optional is considered empty, i.e. is_empty(uninitializedPayloadMemory) must
        // return true afterwards.
        ::new (&uninitializedPayloadMemory) MyNamespace::IndexPair(); // Placement new
        uninitializedPayloadMemory.SetIndices(-1, -1);
    }
    
    static void invalidate_empty_flag(MyNamespace::IndexPair & emptyPayload) noexcept
    {
        // This function is called just before a (non-empty) value is stored in the
        // optional. The given "emptyPayload" is currently indicating the empty state,
        // i.e. is_empty(emptyPayload) returns true.
        // The function must deconstruct the flag value in "emptyPayload" which was 
        // previously constructed by init_empty_flag(). After this function returns,
        // the library constructs the payload. After that, is_empty() must return false.
        // Note: The memory pointed to by "emptyPayload" must not be freed. It is handled
        // by the library.
        emptyPayload.~IndexPair();
    }
};

You first need to include <tiny/optional_flag_manipulator_fwd.h> to make the primary tiny::optional_flag_manipulator template known to the compiler. Additionally, the <new> header is required to be able to use placement new.

Details

⚠️ It is quite crucial to place the definition of the specialization as close as possible below the definition of the payload type IndexPair, i.e. in the same header file: You need to ensure that every time an instantiation of tiny::optional<IndexPair> happens, the compiler sees the specialization. If the compiler sometimes sees it and sometimes it does not see it, you have undefined behavior. In practice, the result can be that it appears to work sometimes and sometimes not (see e.g. this post), or that you have two tiny::optional<IndexPair> instances with different sizes, possibly causing access violations and other hard to track bugs because of mismatching memory layouts. This is nothing special with the library: You have the exact same issues when specializing e.g. std::hash or fmt::formatter. If you put the specialization into a dedicated header file and forget to include it somewhere where tiny::optional<IndexPair> is used, you most likely already have undefined behavior. So the best way to avoid all of this is to put the specialization right next to your type, in the same file.
Side note: Forward declaring IndexPair and using tiny::optional<IndexPair> as function parameter or return type is ok, since these do not represent instantiation points.

The tiny::optional_flag_manipulator specialization needs to happen in the tiny namespace. So if the IndexPair is in a namespace (like MyNamespace in the example), ensure that the specialization is not in the namespace ::MyNamespace::tiny.

There are 3 functions that the specialization needs to define:

In other words, the tasks of the 3 functions are:

All three functions must be noexcept. This is necessary to satisfy the same exception guarantees as std::optional. Setting the optional into the empty state should always be possible. If exceptions could be thrown from init_empty_flag(), the optional could be left in a weird in-between state. (So, requiring noexcept avoids complications such as std::variant::valueless_by_exception.) Especially note that the constructor that you usually call in init_empty_flag() must therefore not throw exceptions.

⚠️ As a guideline, ensure that the payload can transition to the state which indicates emptiness ONLY by calling init_empty_flag(). The empty state should not be constructable via the payload's default constructor, move constructor, move assignment operator and any other member function, except possible a single dedicated one that is used exclusively by the init_empty_flag() specialization.

Consider as a bad example:

struct TypeBecomingEmptyAfterMove {
  std::vector<int> v;
};

template <> 
struct tiny::optional_flag_manipulator<TypeBecomingEmptyAfterMove> {
    static bool is_empty(TypeBecomingEmptyAfterMove const & payload) noexcept {
        return payload.v.empty();
    }

    static void init_empty_flag(
            TypeBecomingEmptyAfterMove & uninitializedPayloadMemory) noexcept {
        ::new (&uninitializedPayloadMemory) TypeBecomingEmptyAfterMove();
    }

    static void invalidate_empty_flag(
            TypeBecomingEmptyAfterMove & emptyPayload) noexcept {
        emptyPayload.~TypeBecomingEmptyAfterMove();
    }
};

tiny::optional<TypeBecomingEmptyAfterMove> is treated as empty if TypeBecomingEmptyAfterMove::v is empty. Especially note that the move constructor and move assignment operator of TypeBecomingEmptyAfterMove empty v, and thus cause a transition to the empty state when stored in tiny::optional. Now consider:

tiny::optional<TypeBecomingEmptyAfterMove> nonEmpty(std::vector<int>{1,2,3});
tiny::optional<TypeBecomingEmptyAfterMove> o = std::move(nonEmpty);

The nonEmpty optional would become empty due to the move because nonEmpty.v becomes empty. This happens "implicitly" from the point of view of tiny::optional rather than explicitly via e.g. tiny::optional::reset(). Thus, tiny::optional does not call the destructor of the payload TypeBecomingEmptyAfterMove stored in nonEmpty and then init_empty_flag() to initialize the empty flag cleanly. Instead, when nonEmpty is destroyed in the example, it ends up calling invalidate_empty_flag() rather than the destructor of TypeBecomingEmptyAfterMove. This can cause problems.

In theory this is happens to be fine in the example because invalidate_empty_flag() happens to call the destructor of TypeBecomingEmptyAfterMove, too. Also, the move constructor and assignment operators of tiny::optional could detect this case and handle it properly. But for two 2 reasons, this is not supported at the moment:

As such, calling the move constructor or move assignment operator of tiny::optional performs a debug assert() that the emptiness state of the moved-from object does not change.

Storing the empty flag in only part of the payload

The above examples used the whole memory given in init_empty_flag() to initialize a full instance of the payload. We just defined that a specific state of the full payload is to be interpreted as empty state. In principle, one can also use just a part of the memory, e.g. the part where IndexPair::mIndex2 is located, and to not initialize all the other members at all. If the other member are expensive to initialize, this can improve performance. This works in practice but it is actually undefined behavior according to the C++ standard. So use this possibility at your own risk.

⚠️ If the optional_flag_manipulator specialization initializes only part of the payload, the payload's member functions really must not change the instance stored in the optional such that tiny::optional transitions from non-empty to empty or vice versa! As explained in the previous section, this is not supported anyway. But to explain the problems, consider the TypeBecomingEmptyAfterMove type again, and the code:

tiny::optional<TypeBecomingEmptyAfterMove> nonEmpty(std::vector<int>{1,2,3});
TypeBecomingEmptyAfterMove t = std::move(*nonEmpty);

Notice that in contrast to the example from the previous section the code TypeBecomingEmptyAfterMove t = std::move(*nonEmpty) calls the move assignment operator of TypeBecomingEmptyAfterMove directly rather than the move assignment operator of tiny::optional (which would debug assert, as explained above).

The nonEmpty optional will become empty due to the move because nonEmpty.v becomes empty. This happens "magically" from the point of view of tiny::optional; it happens completely outside of tiny::optional. There is no way for tiny::optional to detect the sudden change of emptiness. Thus, tiny::optional has no chance to make the transition "clean", even in theory. So, when nonEmpty is destroyed in the example, it ends up calling invalidate_empty_flag() rather than the destructor of TypeBecomingEmptyAfterMove. In the example this is happens to be fine because invalidate_empty_flag() happens to call the destructor of TypeBecomingEmptyAfterMove, too. But if your optional_flag_manipulator specialization does not call the constructor and destructor of the whole payload type, you get undefined behavior (i.e. some sort of memory leak), since tiny::optional originally constructed the whole payload but invalidate_empty_flag() destroys only part of it. Since there is no way to detect the problem, there is also no debug assert().

Also compare this issue.

Enumerations

Enumerations typically do not exhaust their full value range, so they are an obvious choice for saving memory. Unfortunately, C++ does not provide any reflection mechanism with which the library could automatically figure out unused numeric values. Instead, the user of the library needs to specify the sentinel.

Assume you have an enumeration

enum class MyEnum
{
    Value1,
    Value2,
    Max // Does not represent a valid value.
};

The Max element was introduced "artificially"; it is not used as a valid enumeration value by the application, but instead can be used to automatically deduce the number of values in the enumeration and, in our case, to get a nice named representation of a sentinel that can be used by tiny::optional.

There are now two options:

  1. Explicitly specify the sentinel value always: tiny::optional<MyEnum, MyEnum::Max> (also compare the chapters above).
  2. Specialize tiny::optional_flag_manipulator for MyEnum and then use tiny::optional<MyEnum>. ⚠️ BUT: USE WITH CARE! SEE THE WARNING BELOW!

Since the second case might be quite common and the three functions required in the specialization always look the same, the library provides a helper tiny::sentinel_flag_manipulator which can be used to specialize tiny::optional_flag_manipulator. Simply inherit publicly from tiny::sentinel_flag_manipulator and specify the enumeration type as first template argument and the sentinel as second:

template <> 
struct tiny::optional_flag_manipulator<MyEnum>
    : tiny::sentinel_flag_manipulator<MyEnum, MyEnum::Max>
{ };

This "registers" MyEnum::Max as sentinel for the empty state whenever you write tiny::optional<MyEnum>.

⚠️ As noted above, you need to ensure that the specialization is consistently seen by instantiations of tiny::optional. For enumerations, there is a pitfall regarding forward declarations.
First, consider what happens if you attempt to instantiate tiny::optional with a class type that is just forward declared: you get a compiler error (since tiny::optional requires a complete type). So by putting the specialization into the same file as the payload type, you guarantee that at every instantiation with your class type tiny::optional sees the specialization.
Problem for enumerations: C++ allows to forward declare (most) enumerations, and forward declared enumerations are complete since the forward declaration contains the underlying type. So if you use tiny::optional with a forward declared enumeration MyEnum, you will not get a compiler error. That by itself is nice and fine. But if somewhere in your code you have the tiny::optional_flag_manipulator specialization for MyEnum, but the specialization is not seen everywhere where a forward declared MyEnum is used to instantiate tiny::optional, you get undefined behavior, as explained already above.

So, what to do? Forbidding forward declarations of specific enumerations by convention is brittle and most likely futile. My advice would be to use the tiny::optional_flag_manipulator specialization method only for enumerations defined in structs/classes, since those cannot be forward declared. This forces users of the enumeration to include the header where the enumeration is defined, together with the tiny::optional_flag_manipulator specialization (which of course should be defined in the same header).

Types that you have not authored

As explained above, the tiny::optional_flag_manipulator specialization should be placed right next to the targeted payload type. So, what about types from other libraries such as the standard library (std::vector,...), boost, etc, where you cannot modify the header files which define these types? In this case there is no sensible places to specialize tiny::optional_flag_manipulator: The only two valid places are the header file of the type, or the tiny/optional.h file, both of which you should not change. Thus, there is simply no good way to achieve what you want. A hacky workaround would be to create a dedicated header file, say my_vector.h, that includes e.g. <vector> and specializes tiny::optional_flag_manipulator for std::vector, and then to always include my_vector.h everywhere instead of <vector>. Or the other way around, create a custom my_tiny_optional.h header file, and always include it. I really do not recommend either of these solutions.

Generic alternative

Instead of relying on the automatism of tiny::optional, you can instead use tiny::optional_inplace which accepts a FlagManipulator:

namespace tiny {
    template <class PayloadType, class FlagManipulator>
    class optional_inplace;
}

As before, PayloadType is the type to store in the optional. The expected interface of FlagManipulator is identical to the one expected from the tiny::optional_flag_manipulator specialization.

Example: Assume you have an iterator class from some library, and that iterator knows if it is still valid:

class Iterator
{
public:
    Iterator() noexcept
        : mIsValid(false), mIndex(0)
    { }

    Iterator(std::size_t index) noexcept
        : mIsValid(true), mIndex(index) 
    { }

    bool IsValid() const noexcept {
        return mIsValid;
    }

    // More members, e.g. operator++().

private:
    bool mIsValid;
    std::size_t mIndex;
    // Maybe more members that 
};

Now, assume you have some function that must return either a valid iterator or none at all. You could define that an invalid iterator indicates "no iterator", but this might not be obvious to readers. You could also return a std::optional<Iterator> or tiny::optional<Iterator> and guarantee that the iterator is always valid if the optional is not empty. But this will waste some space. In principle, you would like to write tiny::optional<Iterator, &Iterator::mIsValid, false> (which would cause the library to store the emptiness by means of a mIsValid=false value). But the members are private, so this does not work. Instead you can use tiny::optional_inplace<Iterator, FlagManipulator> with a custom manipulator definition:

struct FlagManipulator
{
    static bool is_empty(Iterator const & iter) noexcept
    {
        return !iter.IsValid();
    }

    static void init_empty_flag(Iterator & uninitializedIteratorMemory) noexcept
    {
        // Placement new because memory is already allocated.
        // Default constructor of Iterator will set mIsValid=false.
        ::new (&uninitializedIteratorMemory) Iterator();
    }

    static void invalidate_empty_flag(Iterator & emptyIterator) noexcept
    {
        // Deconstruct the iterator constructed in init_empty_flag().
        // The memory itself will be handled by the library.
        // After this function returns, the library will construct the new valid iterator.
        // That the new iterator will always have IsValid()==true was one of the basic
        // assumptions in this example.
        emptyIterator.~Iterator();
    }
};

Usage example:

int main()
{
    tiny::optional_inplace<Iterator, FlagManipulator> o;
    static_assert(sizeof(o) == sizeof(Iterator));
    assert(o.empty());
    
    // Construct some valid iterator and store it.
    Iterator iter{5};
    o = iter;

    // Note: Attempting to store an invalid iterator is illegal and causes a debug assert:
    //o = Iterator{};
}

Alternative for static constexpr

A simpler alternative is possible via tiny::optional_sentinel_via_type if the sentinel can be stored in a static constexpr variable of a class, the sentinel value can be compared with operator== and it can be assigned with operator=. For example:

struct MicroSecondsSentinel
{
  // The sentinel value.
  static constexpr auto value = std::chrono::microseconds::min();
};

tiny::optional_sentinel_via_type<std::chrono::microseconds, MicroSecondsSentinel> o;
static_assert(sizeof(o) == sizeof(std::chrono::microseconds));

In this example the value std::chrono::microseconds::min() is used to indicate an empty optional. Hence, it is no longer a valid value to store in the optional.

Note: E.g. tiny::optional<std::chrono::microseconds, std::chrono::microseconds::min()> would be invalid C++20 because std::chrono::duration (and thus std::chrono::microseconds::min()) is not a literal class type.

Disabling platform specific tricks (TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS)

The built-in exploitation of unused bit patterns and the built-in use of member variables as location for the empty state is only available on x86/x64. The reason is that I have not enough experience for e.g. ARM to be confident that similar exploitations of undefined behavior works reliably there. If you try to compile the library on any other platform you get a compiler error.

However, because the custom sentinel functionality and custom specializations of tiny::optional_flag_manipulator do not rely on undefined behavior, you can disable any tricks that rely on undefined behavior by compiling your program with TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS. The code is then completely C++ standard compliant and works on any platform.

Defining TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS will have the following effects:

If TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS is defined, you can still specify custom sentinels via the template parameter of tiny::optional. Moreover, specializations of tiny::optional_flag_manipulator still work. (Any undefined behavior you might exploit in these specializations, such as storing the empty state in a member, is your responsibility!)

Mixing code that was compiled with and without TINY_OPTIONAL_USE_SEPARATE_BOOL_INSTEAD_OF_UB_TRICKS would lead to incorrect behavior because the involved types have different sizes. To prevent this, the types defined by the library are implemented in an inline namespace that encodes the configuration. If you try to mix different configurations, you will get errors related to missing or mismatching symbols.

Performance results

Runtime

First note that one goal of the library has no runtime performance impact: Namely it provides a more semantically expressive way to have variables where a special value indicates the empty state, i.e. instead of

int oneBasedIndex; // 0 means "does not reference anything"

one can write

tiny::optional<int, 0> oneBasedIndex;

The second goal of the library is get rid of the additional bool required to store the empty state where possible. This reduces the size and thus should improve runtime performance in applications where memory bandwidth is the limiting factor. But as always, you have to profile it in your specific application if tiny::optional results in a performance improvement. As a somewhat contrived example that highlights a rather extreme case, consider the type

struct WeirdVector
{
    tiny::optional<double> x, y, z;
    tiny::optional<double> length2;
};

which has a size of 32 bytes. Using std::optional<double> instead, it is twice as large, i.e. has a size of 64 bytes. The following piece of test code is rather memory bound:

template <class T>
constexpr T Sqr(T v) { return v*v; }

double PerformTest(std::vector<WeirdVector> & values) 
{
    for (WeirdVector & vec : values) {
        if (vec.x || vec.y || vec.z) {
            vec.length2.emplace(Sqr(vec.x.value_or(0)) + Sqr(vec.y.value_or(0)) + Sqr(vec.z.value_or(0)));
        }
    }

    double totalLength = 0;
    for (WeirdVector & vec : values) {
        totalLength += vec.length2.value_or(0);
    }
    return totalLength;
}

Running this code with tiny::optional and with std::optional on an Intel Core i7-4770K results in the following: Performance results clang 13 and gcc 11 were compiled with -O3 -DNDEBUG -mavx on WSL, MSVC 19.29 used /O2 /arch:AVX /GS- /sdl-. The vertical axis shows the ratio of the execution time for std::optional divided by the execution time of the version with tiny::optional. A value of 1 thus means that they are equally fast, a value >1 means that tiny::optional is faster. The horizontal axis depicts the number of values in the input container values. The three vertical lines show when the values using tiny::optional completely fill the L1 (64kiB per core), L2 (256kiB per core) and L3 cache (8.0MiB) of the Intel i7-4770K.

If the data of both the std and the tiny version fit completely into the L1 cache, there is not much performance difference. That tiny::optional is slightly faster for MSVC is apparently because MSVC is better at optimizing tiny::optional than std::optional. Once the the std data no longer fits in the L1 cache, the tiny case is always faster compared to the std case by roughly a factor of 1.5x. The std case needs to load more data from the slower caches. The peak improvement is reached once most of the tiny data still fits into the L3 cache but the std data does not (meaning that a significant part of the std data needs to be retrieved from RAM), in which case the tiny version is up to roughly 3x faster. Once most of the data in both cases no longer fit, the improvement converges to a factor of roughly 2x. The reason is that most data needs to be streamed from the RAM and the amount of data in the tiny case is half of that of the std case.

Build time

To benchmark the time it takes to compile code using tiny::optional rather than std::optional, the following bit of generated C++ code is used:

struct S0
{
    struct impl{};

    void test() {
        o = std::nullopt;
        [[maybe_unused]] bool v1 = o.has_value();
        o = impl{};
        [[maybe_unused]] auto v2 = o.value();
        v2 = *o;
        o.reset();
        o.emplace(v2);
        [[maybe_unused]] bool v3 = static_cast<bool>(o);
    }
    
    tiny::optional<impl> o; // or std::optional
};

int main()
{
    S0 s0;
    s0.test();
}

However, not only a single class S0 but additional ones S1, S2, etc. get generated and used to achieve meaningful build times. The same code but with tiny::optional replaced with std::optional is also measured. The ratio of the times (build time of tiny::optional divided by the build time of std::optional) is shown in the following figure: Build times clang 13 and gcc 11 are used on WSL, and cl.exe means MSVC 19.29. clang without the -stdlib=libc++ flag uses gcc's stdlibc++.

Obviously, tiny::optional takes roughly ~1.5x-2x longer to compile than std::optional. The more generic interface of tiny::optional requires additional template meta-programming, which apparently takes its toll. But note that this is a rather extreme example since here the optional dominates the build time completely. In larger real world projects (where build times actually matter) one would expect that the overwhelming majority of all variables are not optionals, meaning that the usage of tiny::optional should not have a noticeable impact. Indeed, replacing all occurrences of std::optional in a commercial application with several million lines of code did not result in a measurable slowdown of the build.

How the library exploits platform specific behavior

The library exploits platform specific behavior (that is not guaranteed by the C++ standard) to construct optionals that have the same size as the payload. Specifically:

Additional ideas (not yet implemented!):

Related work

The discussion on reddit has shown that some other libraries with similar intent exist:

Moreover, a few years after the initial release of tiny::optional, the opt::option library has been published (discussion on reddit). It supports more types out-of-the-box than tiny::optional, where the empty state is stored in-place.

Also, Rust's Option implements some magic for references and bools.