As a preface, I am aware that it is generally bad practice to use dynamic memory allocation in embedded code. On the other hand, there are certain things you 100% need it for, and if used sparingly, it can be useful.
For those of you who want dynamic memory allocation on your program, I wrote an allocator, which can be used similarly to malloc/free. It reserves a total of 1024 bytes, within which it can dynamically allocate memory for you. You can increase or decrease this amount with some minor tweaks.
Every allocation you perform has an overhead of 4 bytes, e.x., if you allocate a ten byte structure, 14 bytes of memory are used. An allocation requires time linearly proportional to the number of currently allocated blocks, and deallocation takes place in roughly constant time. For real world use, the amount of time taken in either situation is negligible, and might even be usable within an ISR (although I have not tried it). Freed blocks which can be recombined are automatically recombined to prevent fragmentation.
It provides two functions:
/* Include ElevenAlloc.h to access these functions. */
void *elevenAlloc(unsigned int amount);
void elevenDealloc(void* memPtr);
/* For example, to allocate ten ints, you could do */
int *myArray = elevenAlloc(sizeof(int) * 10);
/* Make sure you free them later to prevent memory leaks */
elevenDealloc(myArray);
Just add ElevenAlloc.h and ElevenAlloc.c to your project to revolutionize your life. The code is licensed under the BSD license, so you can use it within your project for free, but you may not remove the copyright notice.
Now, i’ve been coding for many, many years, and i’ve gotta say… i can’t think of a single situation in FRC that you would 100% need dynamic allocation for… care to share a few examples that i may have overlooked?
Sorry, I exaggerated when I said that dynamic allocation would be 100% necessary, as dynamic allocation can be written in terms of static allocation (as here). On the other hand, having a dynamic allocation system for certain things can result in cleaner code than without.
For example, lets say that in your autonomous, you want to watch out for nearby obstacles such as robots. When the rangefinder picks them up, you could store their location relative, a time, etc. Then, as objects are no longer detected for a certain amount of time, pass out of range, etc., you delete them. Now, you could have a stack, find the first unused “object”, store in it, loop through them, make sure they are within range, mark them as unused, etc.
Of course, now you just wrote a local dynamic allocator for that section of code, and when another part of your code works upon semi-similar principles, you just have to rewrite it again. Yet another chance for duplication, mistakes, and horrors.
On the other hand, you could have a generic allocator which works consistently, and use it everywhere that it results in cleaner code than the custom written stack. Don’t use this everywhere, but I’m sorry, static variables everywhere and custom stacks don’t necessarily result in more bug- free code.
There are plenty of reasons, like the one outlined above, either way if it helps programmers right more elegant code then even if it is not 100% necessary it is still a great tool. Props on writing this.
I think the O(n) insert time and the 4byte overhead needs to be improved, can you think of any ideas? This looks like a fun project. Another cool idea could be to implement a vector for storing generic data…
And yet a simpler way of doing that might be to create an array at runtime that represents the space around you, and when you detect something store a loop counter (representing time) in the corresponding space in the array. You automatically overwrite older locations, which isn’t a problem, and you only 0 something out when you actually care about whats in that space (because you’re moving there, lets say)… There are some extremely efficient algorithms you can use to move the array and rotate it and such as your robot moves (trust me, i’ve used them all before for graphics processing).
In the end, there are other ways to do it that are just as simple (or simpler) and just as elegant, but don’t carry the negatives of attempting to use dynamically allocated memory in a situation where you have extremely limited resources.
What you outline is a simple way implementing dynamic memory… why hack together something like that everytime you need to do something.
What he has done is basically provide a general way of doing what you just outlined that works for any datatype.
This a cool academic exercise but since FIRST is about real-world practices, I’ll add in another 2 cents.
“For example, lets say that in your autonomous, you want to watch out for nearby obstacles such as robots. When the rangefinder picks them up, you could store their location relative, a time, etc. Then, as objects are no longer detected for a certain amount of time, pass out of range, etc., you delete them. Now, you could have a stack, find the first unused “object”, store in it, loop through them, make sure they are within range, mark them as unused, etc.”
Such a data structure would be fixed in size. In a real-time embedded environment, this would never be dynamically allocated (except maybe the entire memory area needed and then only during startup). One would set up an array of these objects and build a simple library to “allocate” them and “return” them to the pool. This would be a constant order operation. Non-deterministic functions (like malloc) are not a good idea in time sensitive software/firmware. Random-sized dynamic allocations can’t be done deterministically (easily) because any algorithm to traverse the free-list is O(f(n)) and must be protected using mutual exclusion. This is the case in every OS I’ve ever used (and that is a long list).
(as mentioned above)