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;

This is somewhat of an abuse of variadic templates; I would say that having 16K template arguments is asking for trouble. Why do you feel like you need to specify all of the indices as template arguments? Couldn't `TableEntries` just take the `bits` and `fraction` arguments, and then calculate `N` (and therefore the indices that it needs to calculate) on its own? Also as a side note, using `cos()` in a `constexpr` function is not portable; I believe it works in gcc, but see [this SO question](http://stackoverflow.com/questions/17347935/constexpr-math-functions). — Jason R, Mar 20 '15 at 12:47
I would also ask whether you could just live with runtime initialization of the table. Is the generation of the table at compile time buying you anything tangible in your application? The price of code complexity and compile time could make it worth just initializing a `static` table at runtime. — Jason R, Mar 20 '15 at 12:49
I'd rather make this kind of table in the constructor of the class that uses it. — user3528438, Mar 20 '15 at 12:51
I don't care how you do it as long as the result is a cosine table. Using the Indexes template is the only way I found to initialize the table. If you can do it without that then I'm all ears. As to cos() not being portable: I don't quite care. Hopefully future c++ will make them constexpr. — Goswin von Brederlow, Mar 20 '15 at 12:55
The use case is for a system without fpu or math library providing cos(). So I need a compile time generated table to implement cos/sin there. — Goswin von Brederlow, Mar 20 '15 at 12:56
With C++11's limited `constexpr`, that could end up being tricky. Your method certainly is valid from a language standpoint, but you're just running up against the limits of compiler implementations. While I appreciate an elegant C++ solution, static lookup tables that are needed at compile time can be made just as effectively using a code generator program. As long as the set of fixed-point formats that you need to support are known ahead of time, I would just write another program to generate the array initializer declaration, then include the resulting text in your source code. — Jason R, Mar 20 '15 at 13:10
If you can use C++14 and its relaxed `constexpr`, then I think it could be easier. You're allowed to use `for` loops there, so you can initialize the table without the use of a really long list of indexes as template arguments. — Jason R, Mar 20 '15 at 13:11
Jason: Is there a special syntax for that or just Table() { for(...) entry[i] = cos(i / 16384.0); }? — Goswin von Brederlow, Mar 20 '15 at 13:40
@GoswinvonBrederlow: There's no special syntax; something like that should work (although I've not really done any work with C++14). You can see the differences in `constexpr` constraints between C++11 and C++14 [at cppreference.com](http://en.cppreference.com/w/cpp/language/constexpr). — Jason R, Mar 20 '15 at 13:44
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/73420/discussion-between-goswin-von-brederlow-and-jason-r). — Goswin von Brederlow, Mar 20 '15 at 13:52

score 2 · Answer 1 · answered Mar 20 '15 at 15:25

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 :(

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

1 Answers1