7

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; } }
Improve this question
5
  • How is my C++ memory pool WHAT? Commented Apr 21, 2009 at 7:36
  • Just wondering if there is any way to optimize it, or better conventions etc.. Commented Apr 21, 2009 at 7:39
  • Okay, fixing title to make it clearer. Commented Apr 21, 2009 at 7:42
  • 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. Commented May 20, 2009 at 2:05
  • @Tom well according to definitions online cplus.about.com/od/glossar1/g/heap.htm a heap is any block of memory used to allocate dynamic variables. Commented May 20, 2009 at 2:19

4 Answers 4

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Ah yes, that appears to be the correct term. I thought it was called a memory pool.
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.

Improve this answer

7 Comments

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.
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++).
"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.
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.
@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!
|
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.

Improve this answer

2 Comments

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.
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.
1

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

Improve this answer

5 Comments

You bring up a good point I suppose, I was only thinking of containing PODs.
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.
What do you recommend? Will I need to override the global delete operator?
If you only use the heap for a limited set of classes you should better override the operator delete for them.
You can use placement new easily enough with this kind of allocator.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.