Optimization of compile time constants

Question

I'm trying to implement a class like std::pair but with more than 2 components. Since in my application it may happen that some of the tuple components are already known at compile-time, i would like to have the following space optimization: when I know that a component is a compile-time constant, just declare it as a 'static const' member, so that it will not waste storage in individual class instances. The const qualifier assures that any attempt to modify the value at run-time will result in a compilation error, at least if we exclude impolite const_cast(s).

I ended up with the following implementation, a ntuple class

template<typename T0_ = void,
     typename T1_ = void,
     typename T2_ = void,
     typename T3_ = void 
     > class ntuple;

and a class used to tag compile-time constants

template<class type_, type_ value_> class constant 
{
   typedef type_ type;
   static const type value = value_;
};

and a bunch of partial specializations of the ntuple class

template<typename T0_>
class ntuple<
 T0_
> {
public:
static const int n=1;
typedef T0_ T0;
static const bool is_static = false;
static const bool is_static0 = false;
T0_ i0;
};

template<
typename T0_, T0_ value0_
>
class ntuple<
constant<T0_, value0_>
> {
public:
static const int n=1;
typedef T0_ T0;
static const bool is_static = true;
static const bool is_static0 = true;
static const T0_ i0 = value0_;
};

template<
typename T0_, T0_ value0_
> const T0_ ntuple<
constant<T0_, value0_> >::i0;

template<
typename T0_,
typename T1_
>
class ntuple<
T0_,
T1_
> {
public:
static const int n=2;
typedef T0_ T0;
typedef T1_ T1;
static const bool is_static = false;
static const bool is_static0 = false;
static const bool is_static1 = false;
T0_ i0;
T1_ i1;
};

template<
typename T0_,
typename T1_, T1_ value1_
>
class ntuple<
T0_,
constant<T1_, value1_>
> {
public:
static const int n=2;
typedef T0_ T0;
typedef T1_ T1;
static const bool is_static = false;
static const bool is_static0 = false;
static const bool is_static1 = true;
T0_ i0;
static const T1_ i1 = value1_;
};

template<
typename T0_,
typename T1_, T1_ value1_
> const T1_ ntuple<
T0_,
constant<T1_, value1_> >::i1;

template<
typename T0_, T0_ value0_,
typename T1_
>
class ntuple<
constant<T0_, value0_>,
T1_
> {
public:
static const int n=2;
typedef T0_ T0;
typedef T1_ T1;
static const bool is_static = false;
static const bool is_static0 = true;
static const bool is_static1 = false;
static const T0_ i0 = value0_;
T1_ i1;
};

template<
typename T0_, T0_ value0_,
typename T1_
> const T0_ ntuple<
constant<T0_, value0_>,
T1_ >::i0;

template<
typename T0_, T0_ value0_,
typename T1_, T1_ value1_
>
class ntuple<
constant<T0_, value0_>,
constant<T1_, value1_>
> {
public:
static const int n=2;
typedef T0_ T0;
typedef T1_ T1;
static const bool is_static = true;
static const bool is_static0 = true;
static const bool is_static1 = true;
static const T0_ i0 = value0_;
static const T1_ i1 = value1_;
};

template<
typename T0_, T0_ value0_,
typename T1_, T1_ value1_
> const T0_ ntuple<
constant<T0_, value0_>,
constant<T1_, value1_> >::i0;

template<
typename T0_, T0_ value0_,
typename T1_, T1_ value1_
> const T1_ ntuple<
constant<T0_, value0_>,
constant<T1_, value1_> >::i1;

This way the members tagged as constant<.,.> are not stored as class members, thus reducing the object size. The number of partial specialization required can be huge, 2^N for N=1,2,3,4 i report only up to N=2: i wrote a simple script to generate all of them. The class can be used as follows

ntuple<int, int, bool> tup1;
tup1.i0=2;
tup1.i1=0;
tup1.i2=true;
assert (tup1.i0==2);
assert (tup1.i1==0);
assert (tup1.i2==true);

ntuple<int, constant<int, 3>, constant<bool, false> > tup2;
tup2.i0=2;
// tup2.i1=0;  // cannot be assigned, is static a constant
// tup2.i2=true; // cannot be assigned, is static a constant 
assert (tup2.i0==2);
assert (tup2.i1==3);
assert (tup2.i2==false);

assert (sizeof(tup1)>sizeof(tup2));

Like this the class works perfectly. Now, I only would like to improve the declaration syntax of ntuples as follows

ntuple<int, int_<3>, bool_<true> >

instead of

ntuple<int, constant<int, 3>, constant<bool, true> >

where int_ and bool_ may be defined as

template<int i> struct int_ : constant<int, i> {};
template<bool b> struct bool_ : constant<bool, b> {};

or i could just use the boost::mpl analogues instead, this is not the point. To achieve this the simple solution is to write another script and generate all possible specializations for all permutations of constant and non-constant template parameters, where the constant template parameters could be int_, bool_, char_ etc. This is feasible, but at the cost of a factorial increase of the number of partial specializations. I was thinking of changing the definition of the ntuple class as follows

 template<typename T0_ = void,
 typename T1_ = void,
 typename T2_ = void,
 typename T3_ = void,
 bool const0 = is_const<T0_>::value,
 bool const1 = is_const<T1_>::value,
 bool const2 = is_const<T2_>::value,
 bool const3 = is_const<T3_>::value
 > class ntuple;

with

template <class T> is_const { static const bool value = false; };
template <int i> is_const<int_<i> > { static const bool value = true; };
template <bool b> is_const<bool_<b> > { static const bool value = true; };

and specialize ntuple as follows

 template<typename T0_,
 typename T1_,
 typename T2_,
 typename T3_> class ntuple<T0_,T1_,T2_,T3_,false,false,false,false> { ... };

 template<typename T0_,
 typename T1_,
 typename T2_,
 typename T3_> class ntuple<T0_,T1_,T2_,T3_,true,false,false,false> { ... };

etc.. This will reduce the number of partial specialization to the same number as before, and only requires to specialize the traits class for each valid 'constant' type. The problem is, i would like to avoid the extra template parameters. I could do this by inheritance, defining an auxiliary class

 template<typename T0_ = void,
 typename T1_ = void,
 typename T2_ = void,
 typename T3_ = void,
 bool const0 = is_const<T0_>::value,
 bool const1 = is_const<T1_>::value,
 bool const2 = is_const<T2_>::value,
 bool const3 = is_const<T3_>::value
 > class ntuple_impl;

specialize as above and then

 template <class T0, class T1, class T2, class T3>
 class ntuple  : ntuple_impl<T0, T1, T2, T3, 
                 is_const<T0>::value, 
                 is_const<T1>::value, 
                 is_const<T2>::value,
                 is_const<T3>::value> { ... };

but i would like to avoid inheritance, since the resulting object would be larger than necessary in some cases because it will contain ntuple_impl as sub-object. I would know if there is another solution to this problem. Thanks. Giuliano

Answer 1

Even though this question is over a year old, I feel it deserves a proper answer.

Following Xeo's idea, you could do exactly what you want in a much simplier manner. Here I assume you want pure c++03.

First of all, declare a type to be used merely as placeholder

struct _;

Declare also the type to be interpreted as a static constant.

template<typename T, T>
struct constant;

Note that no definition is necessary for neither of the above.

The next step is to define the type which will represent an element of the tuple, that is, the type which actually holds data.

template<typename T>
struct element
{
    typedef T type;
    type value;
};

template<>
struct element<_>;

The key point is to specialize element for constant and whichever other types you want, like the int_ and bool_ you cited.

template<typename T, T val>
struct element<constant<T, val> >
{
    typedef T const type;
    static type value = val;
};

template<typename T, T val>
typename element<constant<T, val> >::type element<constant<T, val> >::value;

From this point, defining ntuple is straightforward.

template<typename T0_ = _, typename T1_ = _, typename T2_ = _, typename T3_ = _>
struct ntuple : element<T0_>, ntuple<T1_, T2_, T3_, _>
{
    typedef element<T0_> head;
    typedef ntuple<T1_, T2_, T3_, _> tail;
};

//nil
template<>
struct ntuple<_, _, _, _>
{};

To access the meta data stored by ntuple, one uses the metafunction get_type

template<std::size_t n, typename T>
struct get_type;

template<std::size_t n, typename T0, typename T1, typename T2, typename T3>
struct get_type<n, ntuple<T0, T1, T2, T3> > : get_type<n-1, typename ntuple<T0, T1, T2, T3>::tail>
{};

template<typename T0, typename T1, typename T2, typename T3>
struct get_type<0, ntuple<T0, T1, T2, T3> >
{
    typedef typename ntuple<T0, T1, T2, T3>::head::type type;
};

Likewise, to access the runtime data, one uses the function get_value

template<bool cond, typename T>
struct enable_if
{
};

template<typename T>
struct enable_if<true, T>
{
    typedef T type;
};

template<std::size_t n, typename T0, typename T1, typename T2, typename T3>
typename enable_if<n, typename get_type<n, ntuple<T0, T1, T2, T3> >::type&>::type
get_value(ntuple<T0, T1, T2, T3>& tuple)
{
    return get_value<n-1>(static_cast<typename ntuple<T0, T1, T2, T3>::tail&>(tuple));
}

template<std::size_t n, typename T0, typename T1, typename T2, typename T3>
typename enable_if<!n, typename ntuple<T0, T1, T2, T3>::head::type&>::type
get_value(ntuple<T0, T1, T2, T3>& tuple)
{
    return static_cast<typename ntuple<T0, T1, T2, T3>::head&>(tuple).value;
}

template<std::size_t n, typename T0, typename T1, typename T2, typename T3>
typename enable_if<n, typename get_type<n, ntuple<T0, T1, T2, T3> >::type const&>::type
get_value(ntuple<T0, T1, T2, T3> const& tuple)
{
    return get_value<n-1>(static_cast<typename ntuple<T0, T1, T2, T3>::tail const&>(tuple));
}

template<std::size_t n, typename T0, typename T1, typename T2, typename T3>
typename enable_if<!n, typename ntuple<T0, T1, T2, T3>::head::type const&>::type
get_value(ntuple<T0, T1, T2, T3> const& tuple)
{
    return static_cast<typename ntuple<T0, T1, T2, T3>::head const&>(tuple).value;
}

To count the number of elements stored in the tuple, there is a function called get_size

template<std::size_t n, typename T>
struct get_size_impl;

template<std::size_t n, typename T0, typename T1, typename T2, typename T3>
struct get_size_impl<n, ntuple<T0, T1, T2, T3> > : 
        get_size_impl<n+1, typename ntuple<T0, T1, T2, T3>::tail>
{
};

template<std::size_t n>
struct get_size_impl<n, ntuple<_, _, _, _> >
{
    static std::size_t const value = n;
};

template<std::size_t n>
std::size_t const get_size_impl<n, ntuple<_, _, _, _> >::value;

template<typename T0, typename T1, typename T2, typename T3>
std::size_t get_size(ntuple<T0, T1, T2, T3> const&)
{
    return get_size_impl<0, ntuple<T0, T1, T2, T3> >::value;
}

Finally an overload of the operator << for printing purposes

template<typename Char, typename CharTraits, typename T0, typename T1, typename T2, typename T3>
void print_element(std::basic_ostream<Char, CharTraits>& ostream, ntuple<T0, T1, T2, T3> const& tuple)
{
    ostream << static_cast<typename ntuple<T0, T1, T2, T3>::head const&>(tuple).value;
    if(get_size(tuple) > 1)
        ostream << std::basic_string<Char, CharTraits>(", ");

    print_element(ostream, static_cast<typename ntuple<T0, T1, T2, T3>::tail const&>(tuple));
}

template<typename Char, typename CharTraits>
void print_element(std::basic_ostream<Char, CharTraits>& ostream, ntuple<_, _, _, _> const&)
{

}

template<typename Char, typename CharTraits, typename T0, typename T1, typename T2, typename T3>
std::basic_ostream<Char, CharTraits>& operator <<(std::basic_ostream<Char, CharTraits>& ostream, ntuple<T0, T1, T2, T3> const& tuple)
{
    ostream << Char('<');
    print_element(ostream, tuple);
    ostream << Char('>');
}

The following use case illustrates the use of ntuples and make it clear that the targeted optimization is achieved.

int main()
{
    ntuple<char, int, long> a;
    ntuple<constant<char, '8'>, int, constant<long, 888> > b;
    ntuple<constant<char, '9'>, constant<int, 99>, constant<long, 999> > c;

    assert(sizeof(a) > sizeof(b));
    assert(sizeof(b) > sizeof(c));

    get_value<0>(a) = '1';
    get_value<1>(a) = 10;
    get_value<2>(a) = 100;
//    get_value<0>(b) = '2';    //assignment of read-only location
    get_value<1>(b) = 20;
//    get_value<2>(b) = 200;    //assignment of read-only location
//    get_value<0>(c) = '3';    //assignment of read-only location
//    get_value<1>(c) = 30;     //assignment of read-only location
//    get_value<2>(c) = 300;    //assignment of read-only location

    std::cout << std::endl;
    std::cout << "a = " << a << ", length: " << get_size(a) << ", size in bytes: " << sizeof(a) << std::endl;
    std::cout << "b = " << b << ", length: " << get_size(b) << ", size in bytes: " << sizeof(b) << std::endl;
    std::cout << "c = " << c << ", length: " << get_size(c) << ", size in bytes: " << sizeof(c) << std::endl;
}

This simple case covers ntuples which have a maximum of 4 elements. It should be straightforward to extend it to as many elements as wanted (and supported by the compiler used). In fact, no script whatsoever is needed to generate code using this approach.