Do not store computation results of pure nodes

[nkrkv]

Rationale

Currently, every node’s output values are stored in global C++ variables. They permanently consume the RAM required to hold them. For pure functional nodes like not, add, etc this is equivalent to holding intermediate computation results forever.

 button1     button2
   |           |
  not         not
   |           |
  not         not
   |           |
  not         not
   |           |
  not         not
   |           |
  led1        led2

In the image above the results of not nodes are put in the global scope and thus consume 4 nots × 2 cols × 1 bool-byte = 8 bytes at all times. However, when nothing happens, storing a result of an intermediate not makes a little sense. When one of the buttons is pressed, only the branch related to that particular button might be evaluated and the second one left intact. The peak consumption, in this case, will be 4 bytes. The more independent branches of pure nodes in the program, the more dramatic the difference is.

Also, referring to the global scope while preparing and reading pure nodes Context stops GCC from applying many optimizations: compile-time expression evaluation, common subexpression elimination, etc.

Solution

We can move pure nodes evaluation to the stack making all their intermediate results transient. If a node is pure, the generated code might have a function like the following:

// Output is a generated struct containing all output values
// node4 is the node ID
xod__core__not::Output evaluate_node4() {
    // Input is a generated struct containing all input values
    xod__core__not::Input inp;

    // The input values are taken from the global scope as they do now...
    inp.input_IN = output_node_button;
    // or it can be a result of another pure evaluation
    //inp.input_IN = evaluate_node3().output_OUT;

    // The evaluate function have to have a different signature in
    // the case of pure nodes
    return xod__core__not::evaluate(inp);
}

Then any downstream node can take its input as evaluate_nodeN().output_XXX.

One negative impact is re-evaluation in cases of converging branches:

 button1 button2
    |      |
   not    not
    |      |
   not    not
    \     /
     \   /
      and
       |
      led

Regardless of why led should update, this transaction has to re-evaluate the and and four nots at the current transaction. But taking into account that the RAM is the most precious resource and not the computation time, the effect seems acceptable.

Proof of concept

For example, in the following snippet which structurally resembles XOD-generated code, GCC is smart enough to optimize the not sequence to a single (odd number) negation or no-op (even number) making the consumed Flash and RAM size constant regardless of the number of the not nodes.

#include <Arduino.h>

bool output_node_button;

namespace xod__core__not {

struct Input { bool input_IN; };
struct Output { bool output_OUT; };

Output evaluate(Input inp) {
    Output result;
    result.output_OUT = inp.input_IN;
    return result;
}

} // namespace

void setup() {
    pinMode(13, OUTPUT);
}

xod__core__not::Output evaluate_node4() {
    xod__core__not::Input inp;
    inp.input_IN = output_node_button;
    return xod__core__not::evaluate(inp);
}

xod__core__not::Output evaluate_node3() {
    xod__core__not::Input inp;
    inp.input_IN = evaluate_node4().output_OUT;
    return xod__core__not::evaluate(inp);
}

xod__core__not::Output evaluate_node2() {
    xod__core__not::Input inp;
    inp.input_IN = evaluate_node3().output_OUT;
    return xod__core__not::evaluate(inp);
}

xod__core__not::Output evaluate_node1() {
    xod__core__not::Input inp;
    inp.input_IN = evaluate_node2().output_OUT;
    return xod__core__not::evaluate(inp);
}

void loop() {
    output_node_button = digitalRead(4);
    auto output = evaluate_node1();
    digitalWrite(13, output.output_OUT);
}

Pure marker

A xoder should define somehow that a C++ node he is writing is a pure node. Let it be a xod/patch-nodes/pure marker node. The xoder places the marker on his patch and implements the node using the alternative pure evaluate signature.

The marker is a promise allowed only on C++ nodes. Making a patch node out of impure nodes and then marking the outcome as pure makes no sense. So if the marker is put on a patch without the not-implemented-in-xod node, it should be marked with an error.

Acceptance criteria

• [ ] I can put the pure marker on my patch
• [ ] If there’s no not-implemeted-in-xod marker on the patch, the pure marker shows an error¹
• [ ] Pure nodes project to functions in the generated C++ as shown above
• [ ] Given the example of not node sequence, adding or removing a couple of nots in the chain has zero effect on compiled hex contents (i.e., ensure evaluates in compile-time)
• [ ] Adding a pure node to the program can only raise Flash consumption and must not affect RAM

¹

**Pure marker on impure node**
@/foo -> @/bar: |A `pure` marker node is only allowed on a patch implemented in
C++.| Purity of a composite patch node is inferred automatically from the purity of
nodes contained within.
Try deleting the `pure` marker or adding a `not-implemented-in-xod` node.

How to test

• Make a fixture with two nots in a row and another with much more. Check whether they compile to equivalent hex.
• Make a fixture with two nots in a row and another involving and, or, xor. Check whether they compile to a hex with equal RAM consumption.