How to make a cosine table with templates compile with less than 8 gigabyte of ram?

Question

I'm trying to generate a cosine/sine table for fixed point arithmatic using a 2.14 signed format (2 bit signed integer, 14 bit fraction). The argument to cosine/sine is normalized and folded around 180, 90 and 45 degrees axis so I only need cosine and sine values from 0 to 45 degrees (or 12867 as fixed point). The code computes a slightly larger table going from 0 to 1 radians (or 16384 as fixed point).

I've tested this code for 8.8, 7.9, 6.10, 5.11, 4.12 and 3.13 bit fixed point but can't compile it for 2.14 bit fixed point. I stoped it when g++ was using around 7 GiB of ram and still growing.

So how do I make the templates use less ram?

#include <stdint.h>
#include <math.h>

template <uint16_t...> struct IndexList {};

template <uint16_t left_base, typename LeftList,
          uint16_t right_base, typename RightList> struct Merge;

template <uint16_t left_base, uint16_t... left,
          uint16_t right_base, uint16_t... right>
struct Merge<left_base, IndexList<left...>,
             right_base, IndexList<right...> > {
    typedef IndexList<left..., right...> Result;
};

template <uint16_t base, uint16_t n> struct Indexes {
    static constexpr uint16_t left_base = base;
    static constexpr uint16_t left = n / 2;
    static constexpr uint16_t right_base = base + n / 2;
    static constexpr uint16_t right = n - n / 2;
    typedef typename Merge<left_base,
                           typename Indexes<left_base, left>::Result,
                           right_base,
                           typename Indexes<right_base, right>::Result
                           >::Result Result;
};

template <uint16_t base> struct Indexes<base, 0> {
    typedef IndexList<> Result;
};

template <uint16_t base> struct Indexes<base, 1> {
    typedef IndexList<base> Result;
};

template <uint16_t bits, uint16_t fraction>
class FixedPoint {
public:
    constexpr FixedPoint(double x) : raw_(x * (1 << fraction)) { }
private:
    uint16_t raw_;
};

template <uint16_t bits, uint16_t fraction, typename IndexList> struct TableEntries;
template <uint16_t bits, uint16_t fraction, uint16_t... I>
struct TableEntries<bits, fraction, IndexList<I...> > {
    using FP = FixedPoint<bits, fraction>;
    enum { N = sizeof...(I) };
    FP data[N];
    constexpr inline TableEntries()
        : data({ FP(cos(double(I) / (1 << fraction)))... }) {}
};

template<uint16_t bits, uint16_t fraction>
class Table {
public:
    constexpr Table() { }
private:
    static constexpr uint16_t NUM = 1 << fraction;
    typedef typename Indexes<0, NUM>::Result IndexList;
    TableEntries<bits, fraction, IndexList> entries;
};

Table<2, 14> table;

Answer 1

I think that you'd be much better off by writing a small code generator that can generate the .c files for such tables.

Unfortunately, C++ tries very hard to be a pure functional compile-time programming language, but it's also very hard to implement. C++ compile-time computations seem to still be a bit of a fantasy if you're trying to be pragmatic about it :(