Boost.MPL and type list generation

Question

Background

This is for a memory manager in a game engine. I have a freelist implemented, and would like to have a compile-time list if these. (A MPL or Fusion vector, for example). The freelist's correspond to allocation sizes, and when allocating/deallocating objects of size less than a constant, they will go to the corresponding freelist.

In the end, this means small objects globally have amortized constant time allocation and constant time deallocation. (Yay.)

Problem

The problem is generating the types I need, so I may eventually use Fusion to instantiate those types. The types in use are (shortened, etc.):

template <size_t N>
struct data_block
{
    size_t mSize; // = N
    char mData[N];
};

template <typename T, size_t ElementsPerPage,
    template <typename> class Allocator = std::allocator >
class freelist { /* ... */ };

template <typename T>
class callocator; // allocator that uses malloc/free

The freelist's will manage data_block's of power-of-2 sizes, starting from a minimum going to a maximum. So what I want is:

static const size_t MinimumSmallSize = 4; // anything smaller gets rounded up
static const size_t MaximumSmallSize = 512; // anything bigger goes to the large allocator
static const size_t ElementsPerPage = 4096;

// mpl magic

To generate this:

typedef boost::mpl::vector<
    freelist<data_block<4>, ElementsPerPage, callocator>,
    freelist<data_block<8>, ElementsPerPage, callocator>
    // ...
    freelist<data_block<256>, ElementsPerPage, callocator>
    freelist<data_block<512>, ElementsPerPage, callocator>
    > free_list_collection;

Obviously, I could do this by hand but I'd rather avoid that for a more general and tweakable interface. Using the Fusion vector in code should be simpler than hard-coded members, too.

Question

I'm not sure the best way to go about this; I've never used MPL extensively before. Any ideas? I had a few poor ideas such as making a range, then remove_if it's not power of 2, etc., but surely that's not best. Maybe something recursive instead, that doubles each time, pushing into my result vector? I'm not sure how to go about that.

Legatee

Have you considered using Boost Pool Library for this kind of memory management? ;) – Faceharden

BTW, do not abuse template metaprogramming... with TMP everything happens "behind the curtains", and your code may soon become unmantainable, barely-compilable and full of black magic. Prefer to use explicit code generation for metaprogramming, it's much more clear and "debugable". – Faceharden

For your first question, yes. I have this question to work on, then the actually pools themselves. I'm comparing the two (my freelist and Boost's pools) and am leaning towards the pools. My implementation was surprisingly similar, but doesn't come with free updates, so to speak. :) (And has been tested more thoroughly) About your second statement, I agree using the wrong tool for the job creates a mess, but I have created a small nearly 3-line solution to the problem, and it works quite well. I'll be posting it in several hours, though, as I have class to attend first. – Legatee

For learning purpose, I would also suggest checking out Alexandrescu's Small Object Allocator. The usage is simple (just inherit from Loki::SmallObject, you may precise some template parameters) and it uses a similar system of several lists (per size). Check the header at loki-lib.cvs.sourceforge.net/loki-lib/loki/include/loki/… and do try and read the explanations in the book :) – Rixdollar

@Faceharden while you are right in general, if you look at his answer you will see that he reached a good equilibrium. certainly not passed the unmaintainability point. – Delft

Answer 1

This is the best solution I came up with, and it's fairly simple. It requires a log and pow meta-template, which I've included for those who want to play or try it:

#include <boost/mpl/for_each.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/mpl/vector.hpp>
#include <iostream>

namespace bmpl = boost::mpl;

//// helpers
template <size_t N, size_t Base>
struct log
{
    static const size_t value = 1 + log<N / Base, Base>::value;
};

template <size_t Base>
struct log<1, Base>
{
    static const size_t value = 0;
};

template <size_t Base>
struct log<0, Base>
{
    static const size_t value = 0;
};

template <size_t N, size_t Power>
struct pow
{
    static const size_t value = N * pow<N, Power - 1>::value;
};

template <size_t N>
struct pow<N, 0>
{
    static const size_t value = 1;
};

//// types and constants
template <size_t N>
struct data_block
{
    size_t mSize; // = N
    char mData[N];
};

template <typename T, size_t ElementsPerPage,
    template <typename> class Allocator = std::allocator >
class freelist { /* ... */ };

template <typename T>
class callocator; // allocator that uses malloc/free

static const size_t MinimumSmallSize = 4;
static const size_t MaximumSmallSize = 512;
static const size_t ElementsPerPage = 4096;

//// type generation
// turn a power into a freelist
template <typename T>
struct make_freelist
{
    static const size_t DataSize = pow<2, T::value>::value;
    typedef data_block<DataSize> data_type;

    typedef freelist<data_type, ElementsPerPage, callocator> type;
};

// list of powers
typedef bmpl::range_c<size_t, log<MinimumSmallSize, 2>::value,
                        log<MaximumSmallSize, 2>::value + 1> size_range_powers;

// transform that list into freelists, into a vector
typedef bmpl::transform<size_range_powers, make_freelist<bmpl::_1>,
                            bmpl::back_inserter<bmpl::vector<> > >::type size_range;

//// testing
struct print_type
{
    template <typename T>
    void operator()(const T&) const
    {
        std::cout << typeid(T).name() << "\n";
    }
};

int main(void)
{
    bmpl::for_each<size_range>(print_type());
    std::cout << std::endl;
}

The core of it is just a struct and two typedef's. The log trick reduced the size of the range greatly, and pow of course just undoes the log. Works exactly how I'd like, and I don't see any way to make it simpler.

That said, I've decided to go with Boost.Pool, so I won't be needing my solution (because their pool sizes are dynamic, not compile-time.) But this was good fun.

Legatee

Hi GMan, thanks for sharing the code. Do you open source code that you wrote for the global allocator? It'd be great if you could. I'm trying to make a semi-dynamic allocator and have created an early version of it: github.com/vietlq/galloc. Hope you can open your code too. Thanks. – Grasmere

@Viet: I might be able to give specific functionality, but I can't give you all the code. :\ – Legatee

That should be ok then. At least I get an idea. Thanks. – Grasmere