1

I've recently come up with an idea of pooling memory in a C++ program with a statically initialized array (ie. "static byte Memory[Size]"). The process of allocating blocks of memory would be similar to calling malloc up front for the pool. I then built this allocator and there seems to be no problems. Is there any issues with this allocator architecture other than limited memory space?

Note: The way I reserve blocks of memory is by creating a linked list of blocks that store size, pointer and neighbors. Not that it is important to the question.

James Nguyen
  • 1,079
  • 1
  • 10
  • 20
  • May I ask *why* you made such a thing? What is wrong with the default allocator? What are you going to use it for? What problem is it supposed to solve? – Some programmer dude Jun 02 '17 at 08:23
  • @Someprogrammerdude One of the reasons why people build custom allcoators, book-keeping, memory-pooling, etc.As for this question, I was just curious. – James Nguyen Jun 02 '17 at 08:25
  • So you dynamically allocate a bunch of static arrays and then use the arrays as storage for the allocator? Or do I misunderstand? Because it seems silly. – DeiDei Jun 02 '17 at 08:26
  • @DeiDei I reserve a large block of static memory, say 1 MB, and my program uses it's "dynamic allocations" there – James Nguyen Jun 02 '17 at 08:27
  • 1
    I do not see any issue with creating your allocator. In fact, in my domain we use that frequently due to performance and safety-critical certification. Be sure, however to not use std::list for the block management, as STL use dynamic memory intensively (you would loose all the benefits of the custom allocator). – Adrian Maire Jun 02 '17 at 08:29
  • @AdrianMaire I use a custom bare-bones forward and backward list (just pointers) – James Nguyen Jun 02 '17 at 08:30
  • Compelling examples of custom C++ allocators? https://stackoverflow.com/questions/826569/compelling-examples-of-custom-c-allocators – Lanting Jun 02 '17 at 08:30
  • The only issue is that have to code all of that manually. If that's just curiosity then it's fine. However I wouldn't do that in a real project unless I was absolutely sure that I need it. But that would require some testing that it gives any benefits. – freakish Jun 02 '17 at 08:31
  • @Lanting The question is really not about whether you should use custom allcoators, it's more about if this allocator design is valid. – James Nguyen Jun 02 '17 at 08:31
  • @freakish I actually have a working model (granted it's not optimized) but it works. – James Nguyen Jun 02 '17 at 08:32
  • @Jarann I'm sure it works. But the question is: is it beneficial? – freakish Jun 02 '17 at 08:33
  • @freakish I just finished it (hence the question) so I'm running some benchmarks compare to heap memory. – James Nguyen Jun 02 '17 at 08:34
  • 2
    The "why" doesn't really matter, I was just curious. As for the question itself I don't see any problems with the design. But if you want more input on the design itself and less on the actual code, then I suggest you post on https://softwareengineering.stackexchange.com/ instead. And if you want input on the (working) code then http://codereview.stackexchange.com/. – Some programmer dude Jun 02 '17 at 08:34
  • I did this once, my binary size exploded. No idea why zeroed arrays are stored as is in the binary – Passer By Jun 02 '17 at 11:05
  • @PasserBy, Do you explicitly set your array to zero? uninitialized global arrays should go in the `.bss` section and the start-up code usually sets this whole region to zero, instead of `memcpy`ing it from `.data`. – Lanting Jun 02 '17 at 12:59
  • @Lanting I had a static array of ints in a template class without explicit zeroing them, expecting static initialization to zero them – Passer By Jun 02 '17 at 14:16

1 Answers1

4

TI's sysbios actually provides an implementation for their microcontrollers that looks similar to what you describe. They call this implementation heapbuf

The heapbuf is a single array that has been split up in n equally sized blocks. The heapbuf also holds the pointer to the first empty block, and every empty block holds the pointer to the next empty element.

This specific implementation is only able to allocate blocks of exactly that size, however has no fragmentation issues. If you have a lot of small objects of roughly the same size, it should offer great performance (as allocation is of constant cost and only requires you to update the pointer to the first empty block).

Your note however, is important to the question. And the issue with blocks of different sizes is as follows:

  • The first block might not fit, so you need to do a list traversal until you find a large enough open space.
  • After you have allocated all your memory in blocks of 1k, you decide to free them all and now you have a linked list of many free 1k blocks, have you decided on how to and when to merge them?

The developers of freeRTOS also ran into these issues and therefore provide multiple heaps that take different compromises (eg, fast, but no freeing at all, or a bit slower but no merging of freed blocks, or slow but merging of freed blocks). There is an overview of their implementations here: http://www.freertos.org/a00111.html

Lanting
  • 3,060
  • 12
  • 28