Is it possible to generate an array of data using templates into the programme memory?

[AdrianH]

I'm writing for a micro controller, so I don't have a lot of space.

A little background for those who don't know. When you have constant arrays, they are stored in the programme memory space. Upon execution, they are copied into the data space for easy access. To save space in the data space, it is possible to stop it from being copied. Some compilers will deal with this by just specifying the array as const, g++ has a type modifier called PROGMEM.

In any case, the problem is that I'd like to generate some data, preferably without using an external programme to do it. Hence, my question using the template system. Now I could possibly use macro metaprogramming via boost instead of template metaprogramming, and I may have to go that route. However there are limitations, especially since its numbering system is only equivalent to an unsigned byte, which I possibly could use, but could become more messy than if I use the template system that has long long types as well as a whole slue of type safety mechanisms.

Any help would be appreciated.

Thanks,


Adrian

[JLBorges]

If the values are constants known at compile-time, boost::mpl::vector_c<> can hold them for you. And you wouldn't need any runtime memory for the array.

#include <iostream>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/for_each.hpp>

struct print_it
{
    template< typename T > void operator() ( T v ) const
    { std::cout << v << ' ' ; }
};

struct sum_it
{
    explicit sum_it( int& r ) : sum(r) {}
    template< typename T > void operator() ( T v ) const { sum += v ; }
    int& sum ;
};

struct A
{
    const int arr[10] = { 12, 34, 56, 78, 91, 23, 45, 67, 89, 11 } ;
    void print() const { for( int v : arr ) print_it()(v) ; }
    int sum() const { int s = 0 ; sum_it fn(s) ; for( int v : arr ) fn(v) ; return s ; }
};

struct B
{
    using arr = boost::mpl::vector_c<int, 12, 34, 56, 78, 91, 23, 45, 67, 89, 11 > ;
    void print() const { boost::mpl::for_each<arr>( print_it() ) ; }
    int sum() const { int s = 0 ; boost::mpl::for_each<arr>( sum_it(s) ) ; return s ; }
};

int main()
{
    std::cout << "sizeof(A): " << sizeof(A) << '\n'
               << "sizeof(B): " << sizeof(B) << '\n' ;

    A a ; a.print() ; std::cout << "    sum: " << a.sum() << '\n' ;
    B b ; b.print() ; std::cout << "    sum: " << b.sum() << '\n' ;
}

Output:

sizeof(A): 40
sizeof(B): 1
12 34 56 78 91 23 45 67 89 11     sum: 506
12 34 56 78 91 23 45 67 89 11     sum: 506

[AdrianH]

Yeah, I will be doing something like this, however I'll still need to somehow build the data set into the program memory's data segment. This is why:

Using a template for storage, to then calculate an output is a great idea, until you start to require the underlying template data to be emitted as well. In which case, storing the data is a good idea in terms of size. This is because a fetch from memory instruction may be smaller than a load constant instruction. But even if it is a little bigger, when you iterate over many elements this does become smaller since you are using the same set of instructions to to the same thing as a template emitting each element, requiring N x the size of each load constant instruction.

So you see, I need to emit into the program memory a data segment that contains some of the underlying data that is stored in the template. Though I will still need the template system for certain compile time checks.

I'll probably will just have to use a combo of the preprocessor and the mpl libraries to get things done.

[JLBorges]

> I need to emit into the program memory a data segment that contains some of the underlying data

This might force the compiler to do just that:

constexpr int array[] = { 0, 1, 2, 3, 4, 5 } ;

extern const int* force_it() { return array ; } 

[AdrianH]

That's interesting. But I need to build the data up from information. There may be intermediate calculations. constexpr may be useful if I were using a c++11 compiler, but I'm unfortunately still stuck in the middle ages with at most a c++0x, and that's iffy as the crappy IDE doesn't allow for setting the switches for the compiler. :(

Also, if I understand it's usage right, shouldn't it be:

int const array[] = { 0, 1, 2, 3, 4, 5 } ;

constexpr int* force_it() { return array ; }

I don't think that constexpr relates to an array. Only to functions. Mind you, I've not actually used it before, and I don't have anything to test it on at the moment. Further, why did you use the extern on the function when it contained a body?

[JLBorges]

> I don't think that constexpr relates to an array.

No, it does not.


> Only to functions

Or objects.

#include <cstdlib>

constexpr int a[5] = { 0, 1, 2, 3, 4 } ; // array of 'constexpr int'
int constexpr b[5] = { 0, 1, 2, 3, 4 } ; // array of 'constexpr int'

char test[ a[1] + b[2] ] ; // fine; ( a[1] + b[2] ) is a constexpr

using array_type = int[5] ;
constexpr array_type c = { 0, 1, 2, 3, 4 } ; // array of constexpr int
// the constexpr applies to int and not the array

// int test2 = ( c[2] += 100 ) ; // error: c[2] is a contexpr

const array_type d = { std::rand(), std::rand(), 2, 3, 4 } ; // array of const int
// the const applies to int and not the array

// int test3 = ( d[2] += 100 ) ; // error: d[2] is a const int

// char test4 [ d[2] ] ; // error; d[2] is not a constexpr 

> Further, why did you use the extern on the function when it contained a body?

Just to emphasize that the function has external linkage; the it can be called from other translation units. The superfluous extern was documentation; to make the intent clear.

Note: I'm not sure if a constexpr function has internal or external linkage; if the function has internal linkage, a smart compiler can still optimize the whole thing away.

[AdrianH]

Oh, I see. Interesting....

I sorta found a solution in populating a data set. Unfortunately, the g++ compiler is too old. It relies on variadic templates.

#include<iostream>

template <int ...list>
struct elements
{
        static int const values[sizeof...(list)];
        static int const size = sizeof...(list);
};

template <int ...list>
int const elements<list...>::values[sizeof...(list)] = { list... };

int main()
{
        typedef elements<5,6,7,8> x;
        for (int i=0; i < x::size; ++i)
                std::cout << x::values[i] << std::endl;
        return 0;
}

Unfortunately, I don't think there is a way to get this to work pre c++0x using the workarounds for variadic templates. It might be possible. It depends on SFINAE and my sanity. ;)

Oh wait, yeah, it is possible. Ooooooh the kludgyness of it all. :/

[JLBorges]

> work pre c++0x using the workarounds for variadic templates.

You may want to have a look at the Boost preprocessor library.
And boost mpl etc. do have work-arounds for older compilers.
See Compilers Tested at the bottom of this page:
http://www.boost.org/users/history/version_1_53_0.html

BTW, forgot to mention a caveat for the earlier post: The stuff about constexpr and arrays was based on my observations of how compilers behaved in practice (and not on a dissection of the clauses in the IS relating to constexpr).

[AdrianH]

Yeah, I did say that I may have to use boost's macro metaprogramming (i.e. boost/preprocessor) to get around this in my first post.

And the mpl's workarounds won't allow for a list of numbers to be plunked in like my variadic code did. I'd most likely need to use lists or possibly tuples for this.

[JLBorges]

piotr5 faced a similar problem, and come up with an ingenious solution (for pods) using unions and boost mpl, but without variadic templates:
http://www.cplusplus.com/forum/general/99587/#msg537311

That ought to interest you.

[AdrianH]

That is interesting. I almost burst out laffing. :D

Though it will work in g++ using __attribute__((packed)), I think that unions are subjected to the same alignment issues as structs without it.

Also, I'd have to check to see that the optimiser generates this in a data segment and not as code. Otherwise, it's not what I'm looking for.

[AdrianH]

Looks like I was wrong. It won't work in the version of g++ I'm using.

error: member 'TemplateToArray<...>::cut' with copy assignment operator not allowed in union
error: member 'TemplateToArray<...>::cut' with constructor not allowed in union

Oh well. On the plus side, I've finally gotten boost to run under this friggn IDE. Man was that painful.

[AdrianH]

Wrote a file that generates the class using file recursion. This worked, until I tried to use it in the IDE. Turns out file recursion using the boost library doesn't work when the current directory is not in the list of include paths. :( That was disappointing, though it was fun. Haven't used file recursion in a long time.

I think the only way for it is to put the data into a list which then populates the memory array, while also populating a array_c like template (looks like it is limited to 20 elements when not using a compiler that doesn't have variadic templates).

Hrm...

[JLBorges]

> array_c like template (looks like it is limited to 20 elements
> when not using a compiler that doesn't have variadic templates)

As per the documentation the limit is customizable, and 20 is just the default value.

Something like

#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
#define BOOST_MPL_LIMIT_VECTOR_SIZE 50 // must be a multiple of 10 

before the inclusion on any boost headers.
http://www.boost.org/doc/libs/1_53_0/libs/mpl/doc/refmanual/limit-vector-size.html

[AdrianH]

Hmmm, was looking for this in the vector doc and couldn't find a direct link. :(

Thanks.