Thread: stack-based allocation

Hi,

I'm making an allocator with different allocation strategies. One of these strategies is a stack allocation.

I want to preallocate a large block of memory and pick from this space when allocating memory. The picking would be sequential so it would resemble to a stack.

In theory it seems fine. But how can I return chunks of such a memory block?

Suppose a quick draft (see comment in allocate):

Code:

init()
{
    myMemory = ::operator new(LOTS);
}

void* allocate(int size)
{
    // what i'm trying is this
    // problem is, compiler doesn't know the size of void*
    // i'm sure there's a way to do this, but i don't know any
    void* result = myMemory + index;
    index += size;

    return result;
}

void* myMemory;
int index;

So, any idea how I could return the address in myMemory that happens to be at the given index?

Any way to do this without templating (allocator relies on an abstract strategy that can be stack, heap, etc)?

Thanks!

Originally Posted by eXodus31337

Any way to do this without templating (allocator relies on an abstract strategy that can be stack, heap, etc)?

I am not sure what you mean here: making it into a class template should not pose a problem to your allocation strategy. I have not tried this myself, but you could define a class template with the exact same interface as std::allocator, and even implement the class template by keeping a std::allocator member and forwarding all function calls except allocate, deallocate and max_size to that std::allocator member (since the allocate member function effectively is where you implement your allocation strategy, and this must be matched in deallocation).

Originally Posted by eXodus31337

Still, anyone knows how to return the address at the top of the stack? That is, base myMemory pointer plus a given index? Compiler wants to know the size of the data when I would only want to offset it manually.

One way that you could try is to make myMemory a char* instead of a void*.

Keep in mind that, due to alignment requirements of a particular object, you can only safely use the returned memory for objects of type T where sizeof(T) == sizeof(char).

gg

Originally Posted by Codeplug

Keep in mind that, due to alignment requirements of a particular object, you can only safely use the returned memory for objects of type T where sizeof(T) == sizeof(char).

Mind elaborating? I note that the allocate() function in eXodus31337's example differs from the allocate() function in an allocator using the interface of std::allocator since eXodus31337's version presumably allocates size number of bytes, not size * sizeof(T) number of bytes (since there is no template parameter T to begin with).

EDIT:
I went back to read an article I bookmarked on allocators, and the relevant portion is:

The standard does not guarantee that 'mem_' will have a correct alignment for something else than 'char'. And this is deadly. There are rumors that the next revision of the standard will address this problem, but until then...

To avoid the second issue, we could dynamically allocate 'mem_' (the standard guarantees correct alignment for dynamically allocated memory).

Consequently, it seems like your concern is misplaced.

I think what codeplug is referring to is this:

Code:

char *p1 = allocate(sizeof(char)*3);
double *p2 =allocate(sizeof(double));

If we assume that myMemory is aligned to a nice 8-byte boundary when init() is finished, what is the address given to p2? It will not be aligned to a nice 8-byte boundary, I can promise. Since some processors do not "agree with" reading data at unaligned addresses, this would cause an "unaligned access" error. Sure, x86 would gladly accept this sort of thing (with a 1 clock penalty if read from L1 cache, potentially more if reading from L2 cache or external memory).

--
Mats

Originally Posted by matsp

If we assume that myMemory is aligned to a nice 8-byte boundary when init() is finished, what is the address given to p2? It will not be aligned to a nice 8-byte boundary, I can promise. Since some processors do not "agree with" reading data at unaligned addresses, this would cause an "unaligned access" error.

That makes sense, assuming that the memory pool was supposed to be used by objects of different types. Unfortunately eXodus31337 is rather vague about that, and in fact I am a little confused as to whether eXodus31337 intends to follow my suggestion of copying the default allocator's interface.

Yes, rounding the size up to the next 8- or 16-byte boundary will do the trick - and you can do that with a couple of simple math/logic operations.

--
Mats

it works like a charm now
even runs on my psp without alignment problems. thanks all of you.