Allocating and freeing memory (C & other languages)

This is similar to a question Patrick M posted recently, https://www.riscosopen.org/forum/forums/5/topics/10845

I’m looking for ways to allocate memory which can expand and shrink similar to the sliding heap method.
C’s malloc/free (c++’s new/delete) etc eventually fragment until there is no more available free memory.

For some reason Dynamic areas seem to be frowned upon for user code and programs should use the wimpslot even though they seem to be ideal for this purpose. Is this because they claim a “maximum size” out of the memory map on creation.

This is for a library so I wouldn’t expect every program using it to have it’s own Dynamic area, so…

a) How do I allocate a chunk of memory (pages) that can be extended and shrunk as necessary. (probably best for each app)
b) Use 1 Dynamic area for all users. (more than 1 user of the resource, can crash other users)
c) Implement a proper RO Virtual Memory manager (currently outside my skill set)
d) Other suggestions

Thankyou
Ron

If you allocate/free memory inside a DA, you face exactly the same fragmentation problem as inside the WIMP slot. Why do you think it makes a difference? It would only make a difference if you allocate for each flexible block you need one DA. Which would quickly run into problems because of address exhaustion.

Personally, I wouldn’t fear fragmentation too much. It will result in just a bit of memory waste if you are unlucky and your allocation/free pattern is unfavourable.

For some reason Dynamic areas seem to be frowned upon for user code and programs should use the wimpslot even though they seem to be ideal for this purpose. Is this because they claim a “maximum size” out of the memory map on creation.

Correct.

I’ll echo Steffen’s comments that changing your code to use a dynamic area isn’t guaranteed to make the fragmentation magically disappear.

From your previous comments it sounds like you’re mainly dealing with buffers/arrays that grow as more data is inserted. So my question is, does the data inside the buffer/array actually need to be contiguous? If you change each buffer to be something like a linked-list of fixed-size blocks then that will reduce both the fragmentation and memory overheads of the heap. Or (if you need quick random access to elements in the buffers) you can go with a tree structure where a (fixed-size) index array points to N fixed-size sub-arrays/buffers. If you can do something like this to avoid realloc() then you may also get some performance benefits because it won’t have to copy the contents of your buffer around whenever it grows beyond the limits of its current location in the heap.

You might also be able to reduce fragmentation by pooling objects together – e.g. if you have a routine that allocates 5 fixed-size blocks of memory, and the blocks are all freed at the same time, try changing it to be one allocation. Or if you have a fixed-size object type that’s frequently used, you can allocate many of them at once (in an array) and push them into a free list (returning them to that free list when they’re freed). This will limit your ability to free memory back to the system, but it should also make the heap fragmentation a lot more predictable because over time it will reach a state where almost every object allocation request can be satisfied by taking an existing object from the free list.

Ultimately, if you’re able to group objects such that all your heap allocations are the same size, then you should never have to worry about fragmentation. (Although this may need you to waste some memory, e.g. fitting objects which are 100 bytes in size into a 1024 byte allocation would have 24 bytes of wasted space on the end. So some thought may need to go in to the heap block size that you want to use, to minimise the % wasted space for typical application workloads)

Dynamic areas can be Sparse, which the application space cannot easily be. That doesn’t solve address range starvation though.

I have always considered “Dynamic” areas to be nothing like dynamic enough. A simple solution to the address starvation problem would be to add a new bit to the area flags that marks the area as “Truly Dynamic”.

Such an area is allowed to change address when resizing, calling the PreGrow(old base address)/PostGrow(new base address) handler accordingly. This way address range starvation can be easily avoided for those applications that can cope with their area moving.

Yeah, relocatable dynamic areas are something I’ve thought about as well, and shouldn’t be too hard to implement.

Sparse application space is on my wishlist – there’s support for it under the hood (AMBControl is now built ontop of the DA PMP system), the tricky bit will be extending the APIs to support it without breaking existing apps.

This sort of thing is why we spend so much effort on writing clever garbage collection systems for very dynamic language such as Smalltalk. For the cost of the work by a few people the larger community gets to have a much simpler life and a more efficient programming experience. A good GC typically cost us about 1-2% of cpu time but saves so much lost time in overflows, or memory leaks, or writing your own less-clever memory manager.
There is a large body of work to read up on covering the general subject. Lots of fun :-)

Tim said

garbage

My favourite language is PostScript. The language I recommend everyone learns is JavaScript. Everyone should know a bit of Perl, though Python is a more respectable skill. And this site is implemented in Ruby.

All OO, polymorphic, reflective and garbage collected.

I’m choosing to interpret nemo’s comment as “All OO, polymorphic, reflective garbage languages collected together” :-)