Allocation of variable-sized class

Question

I have a variable length data structure, a multi-dimensional iterator:

class Iterator
{
public:
    static Iterator& init(int dim, int* sizes, void* mem)
    {
        return *(new (mem) Iterator(dim, sizes));
    }

    static size_t alloc_size(int dim)
    {
        return sizeof(Iterator) + sizeof(int) * 2 * dim;
    }

    void operator++()
    {
        // increment counters, update pos_ and done_
    }

    bool done() const { return done_; }
    bool pos()  const { return pos_; }

private:
    Iterator(int dim, int* sizes) : dim_(dim), pos_(0), done_(false)
    {
        for (int i=0; i<dim_; ++i) size(i) = sizes[i];
        for (int i=0; i<dim_; ++i) counter(i) = 0;
    }

    int  dim_;
    int  pos_;
    bool done_;
    int  size   (int i) { return reinterpret_cast<int*>(this+1)[i]; }
    int& counter(int i) { return reinterpret_cast<int*>(this+1)[dim_+i]; }
};

The dimensionality of the iterator is not known at compile time but probably small, so I allocate memory for the iterator with alloca:

void* mem = alloca(Iterator::alloc_size(dim));

for (Iterator& i = Iterator::create(dim, sizes, mem); !i.done(); ++i)
{
    // do something with i.pos()
}

Is there a more elegant way of allocating memory for the iterator? I am aware of the fact that upon returning from a function, its stack is unwound, thus alloca must be used in the caller's stack frame (see e.g. here). This answer suggests that the allocation be performed in a default parameter:

static Iterator& init(int dim, int* sizes, void* mem = alloca(alloc_size(dim)));

However elegant, this solution does not help me: Default argument references parameter 'dim'. Any suggestion for a nice solution?

My eyes hurt on looking at this. Looks like mix of infinite recursion (`bool done() const { return done(); }`) with undefined behavior. — Tadeusz Kopec for Ukraine, Jul 20 '12 at 11:41
@TadeuszKopec: hehe right, sorry :) I meant `done_` of course. Correcting it. — marton78, Jul 20 '12 at 12:27
Still I think that dereferencing result of `reinterpret_cast` is undefined behavior. Why variable-sized object? What's wrong with good old `std::vector` as a member? — Tadeusz Kopec for Ukraine, Jul 20 '12 at 12:56
What else would you do with the result of a `reinterpret_cast` than to dereference it? I'm not a language lawyer, so it may be undefined behaviour, but I can't think of any case where this conversion might fail. And about the reason why I don't use `std::vector`: call it premature optimisation :) — marton78, Jul 20 '12 at 13:07
The only thing you are allowed to do with `reinterpret_cast` result is cast it back to original type, providing that intermediate type is large enough to hold casted value. Any other use is UB. Also `this + 1` is UB, unless used in an object that is inside an array. — Tadeusz Kopec for Ukraine, Jul 20 '12 at 14:11

score 2 · Accepted Answer · answered Jul 20 '12 at 12:01

2

Unfortunately, given that dim is a run-time value, there isn't any way to do this other than with a macro:

#define CREATE_ITERATOR(dim, sizes) \
    Iterator::init(dim, sizes, alloca(Iterator::alloc_size(dim)))

answered Jul 20 '12 at 12:01

ecatmur

152,476
27
293
366

score 1 · Answer 2 · answered Jul 20 '12 at 11:15

1

You could have the dimension parameter as a template argument.

answered Jul 20 '12 at 11:15

Some programmer dude

400,186
35
402
621

Nope, I need it to be specified at run-time. – marton78 Jul 20 '12 at 12:24

score 0 · Answer 3 · answered Jul 20 '12 at 11:50

0

My suggestion might not be what you are looking for but why not have a create|make_iterator function that does the alloca call?

answered Jul 20 '12 at 11:50

Jim Hansson

132
7

1

That doesn't work, since memory allocated by `alloca` is freed automatically as soon as the function returns, as detailed above. – marton78 Jul 20 '12 at 12:25

score 0 · Answer 4 · answered Jul 20 '12 at 15:05

I wouldn't recommend to use alloca at all. If dim value is small, then some fixed-size buffer inside a class would be sufficient. If dim is large then heap allocation cost would be neglectable comparing to complexity of other operations performed on your iterator (note that for very large dim values alloca may cause stack overflow). You may choose between fixed buffer and heap allocation at runtime, depending on dim size.

So I'd recomend approach similar to small string optimization in std::string.

Perhaps, some kind of COW (copy on write http://en.wikipedia.org/wiki/Copy-on-write) techique may be also useful for your iterators.

Note, that this technique cannot be used with alloca, only with heap allocation. Morever, it's almost impossible to copy or copy initialize your iterators if they use alloca (at least without more and more ugly macroses).

Alloca is evil :)

Allocation of variable-sized class

4 Answers4

Linked