Want Malloc on FIRST?

[CrazyNorman]

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.

[Jon Stratis]

Originally Posted by CrazyNorman

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.

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.

[Salik Syed]

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.

[wireties]

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

HTH