Dynamic memory allocation?
ManAtWork
Posts: 2,178
Until now, I have used only fixed size buffers and arrays of objects. On the P1 the resources were very limited and my applications had only a fixed number of connections, data objects or whatever. On the P2 we have much more memory and more CPU power so that we could afford dynamic memory allocation and some sort of variable size container classes if it's really necessary. The question is: is it?
An example: I have a variable number of peripheral devices connected. Each has a variable number of objects (ports, sensors, buttons or whatever) that can be addressed. The application has a variable list of tasks to perform on theese objects. Some of them are executed repeatedly, some are queued until a trigger condition arrives.
Of course, with dynamic allocation the total memory space is still limited but I don't have to pre-allocate everything for the worst case. Instead, I can trade the number of IO objects agains number of task objects as I like. The disadvantage is that all that nasty errors like dangling pointers and fragmentation can happen if it's not handled carefully. Also, memory housekeeping takes time so allocation and deallocation should be avoided inside time-critical loops.
What do you think? Is it worth the extra work? Has anybody already used malloc()/free()? In a closed and embedded system it can usually be avoided. But if you have some sort of operating system that can be configured by the end user in the field then it makes sense, I think.
Comments
Fragmentation will eventually be fatal if not rebooted regularly. I think the primary objective of garbage collection (The Flex suite as built in support for this) is as a solution to fragmentation. The catch is GC is known for its non-deterministic erratic processor hogging.
Always remember that there's nothing magical about C-style global malloc/free functions. You can just declare a buffer in some location (an "arena" or "zone") and instantiate your objects somewhere inside. If they're all to be freed at the same time, you can pack them tight and there will be no overhead or any fragmentation (this is called a "bump allocator"). Many possible strategies there.
Fragmentation happens mainly because of many small allocations of different sizes that happen very often, especially when they are interleaved with few larger size allocations. If you have a text based user interface that handles strings dynamically plus a GUI that needs large bitmaps that's one of the bad cases. There are ways to get around this by keeping recycling bins for the sizes most oftenly used. Another trick is to allow only sizes that equal a power of two. That reduces fragentation a lot because it increases the chances that freed object can be re-combined to larger chunks.
Luckily, I don't need strings and garbage collection. New objects are allocated only if peripheral devices are plugged in or removed or if the user changes the task list. That's not a time critical operation and I can simply flag an error if I run out of memory. Of course, the kernel system has to use static allocation, only, so it can still run regardless of a heap overflow.
Yes, I know. 25 years ago I created my own operating system which used a quite efficient binary tree search best-fit algorithm for memory allocation. But before I re-activate that code I hoped that there was something already included in FlexC.
Fragmentation is solved by using virtual memory. In hindsight, I'm realising the sales pitch for VM, of isolating and linearising each task's space, was more a side effect. Being able to remap memory to avoid entirely the ultimate fate of fragmentation without triggering massive locking was the real reason for VM. But that obviously comes with the burden of implementing it.
Short answer is you better want dynamic allocation for a damn good reason. The hazards are endless.
I agree with Evanh on his last two posts.
In the process of running VM's, it's probably a routine thing to relaunch fresh instances to preempt the inevitable failure of what is going on in the container.
although having similar names, Virtual Machine and Virtual Memory Management are two unconnected things.
Huh, I've not had a discussion where the two were in the same conversation before. But then I've not discussed either subject online much in the past either. Once on a Wikipedia talk page.
When the marketers invented the Virtual Machine name I guess they also attempted to renamed Virtual Memory at the same time. VMM was originally Virtual Memory Manager MMU - The hardware that implemented VMM. Which generally also included Memory Protection ... and the escalating levels of added security over the years.
EDIT: Err, my memory needs fixed.
It was always MMU.
Virtual memory and address remapping is way too complex. You need an MMU in hardware for this to work in an efficient way. It is definitely beneficial for an all-purpose operating system but doesn't make sense for an embedded system where only one application is running. If required (not for me) we could use two different heaps to avoid fragmentation, one for strings and one for other data objects.
The Amiga OS had no virtual memory and was much more stable and responsive than windows. Once a friend visited me and wanted me to show me a game he programmed. He copied some files to the RAM disk an my Amiga. Some months later he came again with a newer version. He was puzzled by the error message "file exists" when he tried to copy the files, again. I haven't switched off or re-booted the Amiga for several months! And this was the computer I developped software on every day. Try this with a windows machine.
Wait, I know one case of a purely software based VMM/MMU. A friend of mine invented a garbage collector for Java which is real-time capable. That means it has predictable upper limits for the time an allocation or de-allocation takes. (Well, actually, there is no de-allocation. It happens in the background if you have a garbage collector)
It was implemented by using only fixed size memory chucks. If you need a larger block of memory it is broken up into pieces and an index map is created as a look-up table for accessing the memory. This is all handled fully transparently by the compiler and the virtual machine so the user sees it as continous memory. The index map is organized as binary tree so the time for a pointer de-reference increases from constant to log(n) time. This increases the execution time of an average program by less than 10% but totally eliminates long lockings by the garbage collector.
So the answer is "no"?
It exists in FlexC. I haven't recently tried to use malloc() and co, the heap wasn't dynamic last I checked, but there was a stack based equivalent that definitely did provide dynamic allocations:
__builtin_alloca(size)as per thec.mddocs. It automatically deallocates upon function exit. As such, it's unlikely to fragment with only one C task.EDIT: I guess the initial stack size is all of spare hubRAM. So any new tasks can do the same but only within its assigned stack space.
EDIT2: I guess it's sort of the same for heap too. Just the heap also made the binary file size bigger. Or maybe I just did something wrong and it was somehow a static allocation. I moved to
alloca()and that did the job.So calling alloca() from main() would be safe but calling it from within a (sub-)function is dangerous as you don't have control over the life time of that memory.
There is a malloc() and a free() function in flexprop/include/libc/stdlib/malloc.c but I haven't found any documentation about how to use it. Well, the call itself is trivial but do I need to setup the heap in advance or does it take all hub memory that isn't used by the stack by default? I have to ask Eric...
The auto-deallocation upon function exit suited me fine. I haven't needed any since then.
Yes, declaring the memory space for the heap as global variable doesn't make sense. It would make the binary file larger. But we could use alloca() at the beginning of main() to assign memory to the heap. So that is taken away from the main stack space which should be all the hub RAM not used by anything else.
Perhaps it would make sense sometimes to have fixed size relatively large chunks of memory like disk sectors, which can be easily managed?
Interesting thread! I didn't implement
alloca()in Catalina because it is non-standard and generally considered bad practice. However there are times it would come in VERY handy to be able to dynamically allocate Hub RAM specifically, such as in LARGE programs where the heap is in XMM RAM (malloc()andfree()allocate from the heap). A quick summary of Catalina's memory modes on the Propeller 2:CODE HEAP STACK ==== ==== ===== NATIVE HUB HUB HUB (also TINY and COMPACT) SMALL XMM HUB HUB LARGE XMM XMM HUBIn any mode you can dynamically allocate Hub RAM on startup using the FREE_MEM pointer (which is what plugins do) but there is no easy way to do so from C. Adding
alloca()would be almost as good as having a dedicatedhub_malloc()andhub_free()(which I had also considered but dismissed because it would be even less standard). This would be an easy way to improve performance of XMM programs at the cost of a little portability. However, while do I tend to be a purist about such things, I am not a complete fanaticRoss.
My fault, again.
It is all documented very well in "general.pdf". I haven't looked for it there because I thought malloc() was a C function.
Thanks @ersmith !