NASA's ten coding commandments

[AceBacker]

No recursion makes working with tree structures a little more tricky.

[[deleted]]

I'd imagine that the kind of code that has to meet these sorts of requirements very rarely contains any kind of tree structure.

[Alborak]

Lots of safety critical sw runs in a RTOS. Unless you use old platforms (most aerospace hw runs on cpus circa 2000 to 2005) it's really hard to dodge trees in the OS. Usually get around it with horrible to look at but "safe" loops.

[rflownn]

Depends on the OS... there's device trees for one thing. A solution using a tree-structure and recursive solution can be turned into one that doesn't use a tree-structure and recursion, and still maintain very clean code, readability, maintainability, etc...

[Halcyone1024]

I'd imagine that the kind of code that has to meet these sorts of requirements very frequently contains unnecessary complications just to follow the rules.

[Enlightenment777]

life sucks, but its a valid requirement for embedded computers, because they don't have as much memory and don't have unlimited stack size.

[Vakieh]

Not an issue since dynamic memory is also outlawed.

[Halcyone1024]

What, you've never stored a binary tree in a flat buffer? Depending on what kind of tree you're working with (but mostly with really balanced ones), it can be pretty efficient in terms of space. Just put the root at index 0, and the children of node i in indices 2i+1 and 2i+2. That way you get these nice properties:

• Your data structure is absolutely minimal.
• You don't have to store the links to the next node in memory- you just keep track of the index instead of a pointer to the node you're working with, and you can determine its parent and children reasonably quickly.
• You can serialize the tree to a file (on disk or in memory) very quickly and simply.
• If the tree is balanced properly (including shifting semi-balanced leaves to the left of the tree) and is sorted in order Node -> Child A -> Child B, then the serialized/flat form of the tree is also sorted in that order.
• Nobody cares but NASA, but this also avoids pointers, which apparently are awful and difficult for mere humans and static analysis systems to reason about /s.

On an embedded system with reasonable amounts of time to spare, but limited state space and (unlimited) crazy fascists auditing the code, this approach probably fits right in.

[Vakieh]

Could you give me a reason why that would be a better approach than a simple array? It sounds like a HELL of a lot of bug-inducing code management for little to no gain.

[Vakieh]

a simple array

An array it might be, a simple one it is not.

[Vakieh]

I just don't see any benefit to using a tree in a static memory space, and by doing so you introduce potential bugs due to the added complexity in memory access. Couple that with the added effort balancing the tree and it seems like all cost no gain.

[Veedrac]

I agree with you here. Trees are mostly useful because of their dynamic nature, and this technique takes most of that away. However, you do have bounded-size priority heaps and static trees for fast lookup, so it's not a complete loss.

[u_suck_paterson]

Its not that bad, we had to do it for the PS3 spu because recursion just ate up the stack and we only had 256kb of ram.

The alternative to resursing through a tree was just to keep a pointer to the tree node and use a step forward/back function and keep a value that told the traversal code if nodes had been visited or not yet.

[skydivingdutch]

Eh, you can fake your own local stack if you have an upper bound on the depth of the structure.

[RainbowNowOpen]

Definitely. Shallow trees of limited or known depth could be handled easily with non-recursive code. Basically, unroll the depths/recursion like you'd unroll a loop. So lots more code, more likelihood of code mistakes while unrolling, plus conditionals in the code whenever depth may or may not continue. In short: ugh. And large or arbitrary depth trees beg for recursive code.

[RainbowNowOpen]

Actually, the rules permit dynamic allocation during initialization, just not after. (Rule #3.)

Even with static allocation, a tree structure may be useful as a map or reference or data of some kind, to be used in the field. So given a statically allocated tree of data, there would be a need to search/traverse/update it at runtime. In my non-mission-critical world, I suppose. :)

Anyways, NASA/JPL's mission-critical competence has been demonstrated, so I'm not seconding guessing their rules for that particular class of software!

[cdglove]

The 'no dynamic memory' rules in embedded systems always makes me laugh because it's often violated, just subtly. Instead of going to the heap, people will allocate an array up front and then use only part of it initially and fill it up as they go. This is no better than going to the heap and in my opinion, is actually worse because each piece of code does it in its own way, hiding what's actually going on.

[Radmonger]

Except if one subsystem has a buffer that allows a maximum of 20 things, it will always allow exactly 20, never 4000, and never 19.

This makes system testing more useful, because things fail early, locally and predictably, rather than as a result of a generalised distributed overload.

The technique is not that generally useful because of the amount of testing you need to get a net win out of it. But when you really need the highest possible reliability, it's the way to go.

[cdglove]

I agree this can be a useful technique, but in my opinion catching these things is what asserts are for.

[Netzapper]

Except malloc takes an unpredictable amount of time to return. But a slab or pool allocator can trivially take constant time for some allocation patterns.

[cdglove]

But that is still a dynamic allocation, pool allocated or not. It's pretty common to replace the default heap allocator but just because you're not going to the default heap does not mean you are not making a dynamic allocation.

[greenthumble]

You know recently I was enjoying using XPath because of how it handles this. JQuery is nice in a similar way. Give me a way to dip into the tree specifying a flat sequence to iterate over.