Improvements for this C++ stack allocator?

Question

Any suggestions for my stack based allocator? (Except for suggestions to use a class with private/public members)

struct Heap
{
    void* heap_start;
    void* heap_end;
    size_t max_end;

    Heap(size_t size)
    {
        heap_start = malloc(size);
        heap_end = heap_start;
        max_end = size + (size_t) heap_start;
    }

    ~Heap()
    {
        ::free(heap_start);
    }

    void* allocate(size_t bytes)
    {

        size_t new_end = ((size_t) heap_end) + bytes;

        if( new_end > max_end )
            throw std::bad_alloc();

        void* output = heap_end;
        heap_end = (void*) new_end;
        return output;
    }

}

Just wondering if there is any way to optimize it, or better conventions etc.. — Unknown, Apr 21 '09 at 07:39
This is a linear allocator, perfect if you don't care about deallocation or can deallocate all at once. I wouldn't describe it as a heap. — Tom Leys, May 20 '09 at 02:05
@Tom well according to definitions online http://cplus.about.com/od/glossar1/g/heap.htm a heap is any block of memory used to allocate dynamic variables. — Unknown, May 20 '09 at 02:19

Artyom · Answer 1 · 2009-04-21T08:03:27.363

4

size_t new_end = ((size_t) heap_end) + bytes;

Not good, never do things like that, you assume that sizeof(size_t)==sizeof(void*), also what happens if bytes==(size_t)(-1) this would not work

Additionally, you need make sure that pointers that you are return are aligned. Otherwise you would have problems. So you need to make sure that bytes are multiple of 4 or 8 according to your platform.

class {...
char *max_end,*head_end,*heap_start;
};

...
max_end=heap_start+size;
...
bytes=align_to_platform_specific_value(bytes);
if(max_end-heap_end >= bytes) {
   void* output = (void*)heap_end;
   heap_end+=bytes;
   return output;
}
throw std::bad_alloc();

Suggestion? Do not reinvent the wheel. There are many and good pool libraries.

edited Apr 21 '09 at 08:03

answered Apr 21 '09 at 07:56

Artyom

31,019
21
127
215

But the reason I didn't use char is because char is not guaranteed to be 1 byte. size_t to my knowledge is always void* because a type could span the whole address space. Also my gcc compiler doesn't let me do void* arithmetic. But you have a point with the alignment: its a space/time tradeoff. – Unknown Apr 21 '09 at 08:09
1

Standard defiantly defines sizeof(char)=1, standard does not define sizeof(size_t)==sizeof(void*) even it is common in practice, but it does define sizeof(intptr_t)==sizeof(void*) (but intptr_t is not avalible for some compilers like VC++). – Artyom Apr 21 '09 at 08:29
"its a space/time tradeoff." it is correctness question. On some platforms (like ARM) a process may fail if you do unaligned access. Also, your data uses atomic operations (for example mutex) it would faile if it is not unaligned. – Artyom Apr 21 '09 at 08:47
Where is the specification that says char is guaranteed to be 1 byte? I believe that it is possible, but I just want to see for myself just in case there is an odd compiler that happens to use different size chars. Or that someone may have defined char as a wide char. – Unknown Apr 21 '09 at 22:09
In 5.3.3 Sizeof [expr.sizeof] you can find "sizeof(char), sizeof(signed char) and sizeof(unsigned char) are 1. The result of sizeof applied to any other fundamental type is implementation-defined". – Francesco Dec 21 '11 at 12:51
@Francesco I was talking about that sizeof(size_t) != sizeof(void*) which is on some doomed compilers. And yes I know that `sizeof([[un]signed] char) == 1` according to the standard – Artyom Dec 21 '11 at 15:45
1

@Artyom I know that you know :) but the first comment by Unknown stated that "char is not guaranteed to be 1 byte" which is not true. So I wanted to support your comment and not to argue against it! – Francesco Dec 22 '11 at 11:16

justinhj · Accepted Answer · 2018-09-15T19:11:34.823

4

You've implemented a stack based allocator. You can't free up without leaving gaps. Usually a pool refers to a block of contiguous memory with fixed sized slots, which are doubly linked to allow constant time add and delete.

Here's one you can use as a guide. It's along the same lines as yours but includes basic iterators over allocated nodes, and uses templates to be type aware.

edited Sep 15 '18 at 19:11

answered Apr 21 '09 at 08:09

justinhj

11,147
11
58
104

Ah yes, that appears to be the correct term. I thought it was called a memory pool. – Unknown Apr 21 '09 at 08:14

score 2 · Answer 3 · answered Apr 21 '09 at 07:39

2

Two obvious problems:

1/ You don't have a deallocate().

2/ A deallocate() will be very hard to write with your current strategy unless you're always going to deallocate in the exact reverse order of allocating. You'll need to cater for the case where a client wants to deallocate memory in the middle of your used section.

Of course, if you do deallocate in reverse order, (2) is not a problem. And if you never free memory at all, (1) is also not a problem.

It depends on what you want it to do.

answered Apr 21 '09 at 07:39

paxdiablo

854,327
234
1,573
1,953

Well as a usual memory pool, you just allocate a bunch of objects, and then deallocate them all in 1 function call. But then I completely forgot about sharptooth's point that I may need to call each of their destructors if they are not PODs. – Unknown Apr 21 '09 at 07:44
You only need to call the destructors if they have file handles / other objects open that do not live in the pool. If everything allocates only memory and all that memory is in the pool, you don't strictly need to call destructors. – Tom Leys May 20 '09 at 02:18

score 1 · Answer 4 · answered Apr 21 '09 at 07:40

1

Your heap doesn't allow deallocation. How will you use it for objects allocated with new in C++?

answered Apr 21 '09 at 07:40

sharptooth

167,383
100
513
979

You bring up a good point I suppose, I was only thinking of containing PODs. – Unknown Apr 21 '09 at 07:42
Even with POD you will have to take care of operator delete. If you don't do so, the default operator delete will be used which will likely crash your program. – sharptooth Apr 21 '09 at 07:45
What do you recommend? Will I need to override the global delete operator? – Unknown Apr 21 '09 at 07:54
If you only use the heap for a limited set of classes you should better override the operator delete for them. – sharptooth Apr 21 '09 at 07:55
You can use placement new easily enough with this kind of allocator. – justinhj Apr 21 '09 at 16:55

Improvements for this C++ stack allocator?

4 Answers4

Linked