Optional Storage

Minimising in-memory storage requirements for complex data types in C++

Craig Henderson

2004, Originally published in C/C++ Users Journal 22(5)

In a recent project I was designing a data structure that required the storage of additional data depending on information that was available at compile time, but unknown at design and implementation.

As an example of the problem, consider an unrelated system to store peopleís personal details. A subset of the information could be a list of Forenames, Surname, Maiden Name and Childrenís names. Forenames and a Surname are applicable to all people, but a Maiden Name and Childrenís names are each only applicable to a subset of people. Hereís a structure that could store all the information:

template<typename Char>
struct personal_details
{
    typedef
    enum { male, female }
    gender_t;

    gender_t                       gender_;
    std::vector<
        std::basic_string<Char> >  forenames_;
    std::basic_string<Char>        surname_;
    std::basic_string<Char>        maiden_name_;
    std::vector<
        std::basic_string<Char> >  children_;
};

There were three design goals that I aimed to achieve.

  1. Compile time safety of ensuring the optional data was not accessed when it shouldnít be.
  2. Avoid conditional heap allocation and runtime checks.
  3. Minimise the allocation space to hold redundant data.


The above structure fails to meet any of the three design goals, of course. Perhaps the most significant point of interest here is the memory allocation required in storing the maiden_name_ and children_ variables that may never be used. The actual size depends on the STL implementation in use. Table 1 shows the size with three compiler/STL combinations.

    VC7.0      VC7.0 STLPort      GCC 3.2   
sizeof(std::basic_string<char>)28124
sizeof(std::vector< std::basic_string<char> >)161212
sizeof(personal_details)925236

Table 1 - basic class sizes

template<typename Char>
struct personal_details
{
    std::vector<
        std::basic_string<Char> >  forenames_;
        std::basic_string<Char>    surname_;
};

template<typename Char>
struct personal_details_married_female
  : virtual public personal_details<Char>
{
    std::basic_string<Char>  maiden_name_;
};

template<typename Char>
struct personal_details_parent
  : virtual public personal_details<Char>
{
    std::vector<
        std::basic_string<char> >  children_;
};

template<typename Char>
struct personal_details_married_male_parent
  : public personal_details_parent<Char>
{
};

template<typename Char>
struct personal_details_married_female_parent
  : virtual public personal_details_married_female<Char>,
    virtual public personal_details_parent<Char>
{
};

Listing 1

An obvious solution to this problem is to allocate the optional variables on the heap at runtime and store pointers in the personal_details structure. However, this only meets the third design goal, and fails on the first two. So perhaps using a class hierarchy could be an answer? I could build a hierarchy to use a base class for forenames and surname and derived classes for parents and married people. Listing 1 is an example hierarchy, and shows how this solution can quickly become unwieldy and difficult to maintain. With respect to the design goals, the first and second are met, but this solution is very inefficient in terms of space allocation. Table 2 shows the sizes of these classes. The results are considerably variable for different compiler/STL configurations with size for the structure to represent the details of a married female parent ranging from 44 bytes with GCC 3.2 to 100 bytes with VC7.

So, I set about designing a structure that can, under specific compile time conditions, occupy minimal storage, and under other conditions can store a data type object and has the same semantics as the data type itself. There must, however, be no storage overhead in using the optional storage structure itself.

template<typename Type, bool store>
struct optional_storage;

optional_storage is a structure that has two template parameters; the first is the data type that could be stored, and the second is a Boolean value to determine whether storage should be allocated or not. For the case of no storage, we simply define an structure with an empty type,

template<typename Type>
struct optional_storage<Type, false>
{
    typedef struct { } type;
};
    VC7.0      VC7.0 STLPort      GCC 3.2   
sizeof(personal_details)442416
sizeof(personal_details_parent)644032
sizeof(personal_details_married_male_parent)644032
sizeof(personal_details_married_female)764024
sizeof(personal_details_married_female_parent)1006044

Table 2 - class hierarchy sizes

Now to the trickier case of allocating storage. The easiest way to achieve the goal of data type semantics is to derive the optional_storage class from the data type itself. A type is implicitly convertible to its base, so deriving will solve all the problems. Well, it would do, but for a small problem in that a structure cannot derive from a fundamental type (integrals and floating point), only from a class or another structure. To overcome this, we can create a structure that wraps the basic data type and provides operators to convert to and from the basic data type. Iíll call it mandatory, as it stores data when our optional_storage structure becomes a mandatory.

template<typename Type>
struct mandatory
{
    typedef Type type;

    type data_;

    mandatory();
    mandatory(const type &other);
    mandatory(const mandatory &other);
    operator type &();
    operator const type &() const;
};

We can now derive from a mandatory structure that wraps the data type.

template<typename Type>
struct optional_storage<Type, true>
  : public detail::mandatory<Type>
{
    typedef
    typename
    detail::mandatory<Type>::type
    type;

    optional_storage();
    optional_storage(const type &other);
};

And there we have it. A structure that will auto-magically reduce to the minimum size allocation allowed by the language for the given data type, or no data, dependent on a compile time expression. The minimum size allowed by the language depends on its use. As a member of a class or structure, it must be at least 1 byte in size and its actual size will depend on the compilerís alignment settings. As a base class, there are no restrictions, and the compiler is allowed (but not required) to optimize away this space. This is a technique known as Empty Base Optimization, and means that a class that derives from an empty base class can be the same size as if it were deriving from nothing.

Returning to the personal_details example, we can now define the structure as follows

typedef enum { male, female    } gender_t;
typedef enum { single, married } marital_status_t;

template<gender_t         G,
         marital_status_t M,
         bool             Parent,
         typename         Char=char>
struct personal_details
{
    typedef Char char_type;
    
    typedef
    std::basic_string<char_type>
    name_t;

    typedef
    std::vector<name_t>
    names_t;

    gender_t gender_;
    names_t  forenames_;
    name_t   surname_;

    optional_storage<
        name_t,
        G == female  &&  M == married>
            maiden_name_;

    optional_storage<
        names_t,
        Parent>
            children_;
};

Here, the only compulsory members are gender_, forenames_ and surnames_. All the others are optional based on one, or a combination of, template parameter values. Table 3 shows the size of the structure with each combination of template parameter values.

    VC7.0      VC7.0 STLPort      GCC 3.2   
sizeof(personal_details<male, single, false, char>)523224
sizeof(personal_details<female, single, false, char>)523224
sizeof(personal_details<male, married, false, char>)523224
sizeof(personal_details<female, married, false, char>)804428
sizeof(personal_details<male, single, true, char>)684436
sizeof(personal_details<female, single, true, char>)684436
sizeof(personal_details<male, married, true, char>)684436
sizeof(personal_details<female, married, true, char>)925236

Table 3 - sizes of personal_details using optional storage

Letís take a closer look at the definition of maiden_name_. For married women, we want to store their pre-marital name in a string type, and for all other people, a maiden name is inappropriate. We already have a type defined to store names, name_t, so we can declare maiden_name_t like this

    optional_storage<
        name_t,
        G == female  &&  M == married>
            maiden_name_;

The expression G == female && M == married is evaluated to a Boolean constant at compile time, based upon the values of G and M which are themselves template parameters to personal_details. It is this use of a Boolean constant as a template parameter that is key to optimal_storage working. This static constant is used in the selection of a type, and the type will contain, or not contain, storage for the data. Because this type selection is performed during compilation, the generated types are subject to optimization and normal error conditions. For example, consider

personal_details<male, single, true> male_single_parent;

male_single_parent is instantiated as a personal_details structure that can optimally represent an unmarried male with children, according to the rules weíve defined. This is now a concrete type, so attempting to access the maiden name of this person

male_single_parent.maiden_name_ = "Smith";

will yield a compilation error.

Optimising struct mandatory<>

The mandatory structure implemented above works a treat. But there was something niggling me about it. I wasnít happy that it always wrapped the real data type that I wanted to store. The conversion operators are implemented inline and will have no overhead in production code with any modern compiler, but they are fussy and get in the way in development (debug) code.

So I set about to improve the situation. The structure would remain the same as above for a data type that derivation from is illegal. However, in all other case, it could be optimised in code terms even if not in performance. First of all, I needed a way of determining if a type is fundamental, that is, is the type an integral type or a floating-point type. I defined a simple structure, which I can specialize for types that are fundamental. The default (unknown) case is false.

template<typename T> struct is_fundamental
{ enum { value = false }; };

Now I could easily specialize this structure for all types I know to be fundamental, and I can use the value member of the structure at compile time to determine if any given type is fundamental. Now, every type, in every combination of signed/unsigned and cv-qualifiers must be accounted for, so I created some macros. One for types that can be signed and unsigned

#define DEFINE_FUNDAMENTAL_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(TYPE) \
    template<> struct is_fundamental<signed TYPE>                     \
        { enum { value = true  }; };                                  \
    template<> struct is_fundamental<const signed TYPE>               \
        { enum { value = true  }; };                                  \
    template<> struct is_fundamental<volatile signed TYPE>            \
        { enum { value = true  }; };                                  \
    template<> struct is_fundamental<const volatile signed TYPE>      \
        { enum { value = true  }; };                                  \
    template<> struct is_fundamental<unsigned TYPE>                   \
        { enum { value = true  }; };                                  \
    template<> struct is_fundamental<const unsigned TYPE>             \
        { enum { value = true  }; };                                  \
    template<> struct is_fundamental<volatile unsigned TYPE>          \
        { enum { value = true  }; };                                  \
    template<> struct is_fundamental<const volatile unsigned TYPE>    \
        { enum { value = true  }; };

and one for those that canít

#define DEFINE_FUNDAMENTAL_WITHOUT_SIGN_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(TYPE)  \
    template<> struct is_fundamental<TYPE>                                          \
        { enum { value = true  }; };                                                \
    template<> struct is_fundamental<const TYPE>                                    \
        { enum { value = true  }; };                                                \
    template<> struct is_fundamental<volatile TYPE>                                 \
        { enum { value = true  }; };                                                \
    template<> struct is_fundamental<const volatile TYPE>                           \
        { enum { value = true  }; };

I could then use these macros to define a complete set of fundamental types

DEFINE_FUNDAMENTAL_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(char)
DEFINE_FUNDAMENTAL_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(short)
DEFINE_FUNDAMENTAL_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(int)
DEFINE_FUNDAMENTAL_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(long)
DEFINE_FUNDAMENTAL_WITHOUT_SIGN_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(bool)
DEFINE_FUNDAMENTAL_WITHOUT_SIGN_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(float)
DEFINE_FUNDAMENTAL_WITHOUT_SIGN_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(double)
DEFINE_FUNDAMENTAL_WITHOUT_SIGN_958DEC24_DCB9_4EEC_9FA4_86B73473EFFE(long double)

Ok, so now I know at compile time if a type is fundamental or not, I can reinvent the mandatory structure to encapsulate fundamental types and derive from everything else. I define the structure with two template parameters. The first is the data type, as it always was. The second is a boolean value that will determine if the data type is encapsulated (true) or derived (false). This second template parameter has a default value using the is_fundamental structure above, and will never need to be supplied by the user of the structure.

template<typename Type,
         bool IsFundamental=detail::is_fundamental<Type>::value==true>
struct mandatory;

I now partially specialize the structure using the second parameter. If the parameter is true, then the structure is unchanged from above

template<typename Type>
struct mandatory<Type, true>
{
    // ... as above
}

However, if the parameter is false, I know I can derive from the data type and provide three simple constructors.

template<typename Type>
struct mandatory<Type, false> : public Type
{
    typedef Type type;

    mandatory();
    mandatory(const type &other);
    mandatory(const mandatory &other);
};

Microsoft Visual C++, up to and including VC++.NET 2002 (VC7) does no support partial template specialization. For this compiler, the optimal_storage structure always wraps the data, and never inherits from non-fundamental types.

Conclusion

The optional_storage structure provides an easy to use interface for optimising the storage requirements of any CopyConstructible data type. Wrapping a data type within an optional_storage structure is mostly transparent, although there is a small caveat. If the contained data type has a conversion operator to another type, it will not be invoked because one implicit conversion has already been performed. In such a situation, an explicit conversion, or intermediate assignment to const Type& will be necessary. The three original design goals have all been met, and there is no storage overhead in using the optional_storage structure itself. This can be seen easily by comparing the bottom line in Table 1, our starting point, and Table 3, the optional_storage implementation. For each compiler/STL configuration the fully populated structure using optional_storage is exactly the same size as the original fully populated structure. The real benefit comes when the optional parts of the structure are eliminates, for example, a structure to represent a single male without children now occupies 52 bytes, 32 bytes and 24 bytes on VC7.0, VC7.0/STLPort and GCC3.2 respectively. This is down from 92 bytes, 52 bytes and 36 bytes on the same compilers, saving 40 bytes, 20 bytes and 12 bytes. This can add up to a massive saving in a large system storing many of these structures simultaneously.