FrameMark in C++

The FrameMark (defined in sched/FrameMark.h) marks the unit's frame at the start of the loop, to fork there the rowops for the next iterations of the loop. It's pretty simple:

FrameMark(const string &name);

The constructor that gives the mark a name. A FrameMark is an Starget, so it's reference-counted and may be used only in one thread.

const string &getName() const;

Read back the name.

Unit *getUnit() const;

This method is different from getUnit() on most of the other classes. It returns the pointer to the unit, on which it has been set. A freshly created FrameMark would return NULL. Internally a FrameMark doesn't keep a reference to the unit, it's just a pointer, and a way for the Unit to check in loopAt() that the mark has been indeed set on this unit. And you can use it for the entertainment purposes too. Normally when the frame marked with this mark gets popped from the Unit's stack, the mark becomes unset, and its getUnit() will return NULL.

All the actions on the FrameMark are done by passing it to the appropriate methods of the Unit. When a mark is set on a frame, the frame has a reference to it, so the mark won't be destroyed until the frame is freed.

Fork revisited

I've been working on the streaming functions, and that gave me an idea for a change in scheduling. Sorry that this description is a little dense, you'd need to get the context of the old ways from the manual for the description of the changes to make sense.

If you'd want to look up the section on Basic scheduling http://triceps.sourceforge.net/docs-1.0.1/guide.html#sc_sched_basic, and the section on Loop scheduling http://triceps.sourceforge.net/docs-1.0.1/guide.html#sc_sched_loop, I've been saying that the loop logic could use some simplification, and the forking of the rowops is getting deprecated. Now I've come up with a solution for them both.

The loops required a separate label at the beginning of the loop to put a mark on its queue frame. When the loop's body unwinds and the next iteration starts, it has to avoid pushing more frames with each iteration. So it has to put the rowop for the next iteration into that beginning frame (like fork but farther up the stack), and then unwind the whole body before the beginning label picks the next rowop from its frame and runs the loop body for the next iteration.

But now one little change in the execution of the forked rowops from the frame fixes things: rather than doing a proper call and pushing a new frame for each of them, just execute them using the parent's frame. This muddles up the precise forking sequence a little (where the rowops forked by a label were guaranteed to execute before any other rowops forked by its parent). But this precision doesn't matter much: first, forking is not used much anyway, and second, the forked labels can't have an expectation that the model won't change between them being forked and executed. However this little change is very convenient for the loops.

In a loop the first label of the loop can now put the mark directly on its frame. This mark will stay there until the loop completes, executing every iteration from that point.

If we review the example from the section on Loop scheduling, with the topology

X -> A -> B -> C -> Y
     ^         |
     +---------+

Then the sequence will look like this:

Rowop X1 scheduled  on the outer frame:

[X1]

Rowop X1 executes:

[ ] ~X1
[ ]

Label X calls the first label of the loop, A, with rowop A1:

[ ] ~A1
[ ] ~X1
[ ]

The label A calls setMark() and puts the mark M on itself:

[ ] ~A1, mark M
[ ] ~X1
[ ]


The label A then calls the rowop B1 with calls the rowop C1:


[ ] ~C1

[ ] ~B1

[ ] ~A1, mark M

[ ] ~X1
[ ]


The label C loops the rowop A2 (for the second iteration of the loop) at mark M, thus placing A2 into the A1's frame.

[ ] ~C1

[ ] ~B1

[A2] ~A1, mark M

[ ] ~X1
[ ]


Then the label C returns, label B returns, and label A returns. But A1's frame is not empty yet (* shows that A1 has completed and now it's a frame without a rowop as such).

[A2] *, mark M

[ ] ~X1
[ ]


Then A2 gets taken from the frame and executed with the context of the same frame:

[ ] ~A2, mark M

[ ] ~X1
[ ]


The label A again sets the mark M, which marks the same frame, so it's pretty much a no-op (so A doesn't really have to set the mark the second time, it's just easier this way). And then it proceeds to call B and C again:


[ ] ~C2

[ ] ~B2

[ ] ~A2, mark M

[ ] ~X1
[ ]


The label C loops again back to A:


[ ] ~C2

[ ] ~B2

[A3] ~A2, mark M

[ ] ~X1
[ ]


The stack then unrolls, finds the A2's frame not empty, takes A3 from it, and continues in the same way until C decides to not loop to A any more, calling Y instead.

This has pulled with it a few more changes. The first consequence is that the frame draining doesn't happen between executing the label itself and executing its chained labels. Now it has moved to the very end. Now the label runs, then calls whatever labels are chained from it, then the frame draining happens after all the other processing has completed. If the frame is found not empty, the first label from it gets removed from the frame and "semi-called" with the same frame. If the frame is not empty again (because either the original rowop had forked/looped rowops onto it, or because the "semi-called" one did), the next label gets removed and "semi-called", and so on.

The second consequence is that this has changed the traces of the unit tracers, and I've had to add one more TracerWhen constant. Remembering the difficulties with the nesting of the traces, this was a good time to fix that too, so I've added the second TracerWhen constant. Now all of them go nicely in pairs:

TW_BEFORE, // before calling the label's execution as such
TW_AFTER, // after all the execution is done
TW_BEFORE_CHAINED, // after execution, before calling the chained labels (if they are present)
TW_AFTER_CHAINED, // after calling the chained labels (if they were present)
TW_BEFORE_DRAIN, // before draining the label's frame if it's not empty
TW_AFTER_DRAIN, // after draining the label's frame if was not empty

The TW_BEFORE/AFTER_CHAINED trace points now get called only if there actually were any chained labels to call, and TW_BEFORE/AFTER_DRAIN trace points get called only if there were anything to drain. The DRAIN trace points get always called with the original rowop that pushed this frame onto the stack first (so that matching the "before" and "after" is easy).

The full sequence in the correct order now becomes:

TW_BEFORE
TW_BEFORE_CHAINED
TW_AFTER_CHAINED 
TW_AFTER
TW_BEFORE_DRAIN
TW_AFTER_DRAIN 

But since parts of it are optional, the minimal (and most typical) one is only:

TW_BEFORE
TW_AFTER

There also are new methods to check if a particular constant (in its integer form, not as a string) is a "before" or "after". Their typical usage in a trace function, to print an opening or closing brace, looks like:

     if (Triceps::tracerWhenIsBefore($when)) {
        $msg .= " {";
    } elsif (Triceps::tracerWhenIsAfter($when)) {
        $msg .= " }";
    }


More trace points that are neither "before" or "after" could get added in the future, so a good practice is to use an elsif with both conditions rather than a simple if/else with one condition.



The third consequence is that the methods Unit::makeLoopHead() and Unit::makeLoopAround() now return only a pair of values, not a triplet. The "begin" label is not needed any more, so it's not created and not returned.

Execution Unit

After discussing the principles of scheduling in Triceps, let's get down to the nuts and bolts.

An execution unit represents one logical thread of Triceps. In some special cases more that one unit per actual thread may be useful, but never one unit shared between threads.

A unit is created as:

$myUnit = Triceps::Unit->new("name") or die "$!";

The name argument as usual is used for later debugging, and by convention should be the same as the name of the unite variable ("myUnit" in this case). The name can also be changed later:

$myUnit->setName("newName");

It returns no value. Though in practice there is no good reason for it, and this call will likely be removed in the future. The name can be received back:

$name = $myUnit->getName();

Also, as usual, the variable $myName here contains a reference to the actual unit object, and two references can be compared, whether they refer to the same object:

$result = $unit1->same($unit2);

The rowops are enqueued with the calls:

$unit->call($rowop, ...) or die "$!";
$unit->fork($rowop, ...) or die "$!";
$unit->schedule($rowop, ...) or die "$!"; 

Also there is a call that selects the enqueueing mode by argument:

$unit->enqueque($mode, $rowop, ...) or die "$!";

Multiple rowops can be specified as arguments. Calling these functions with multiple arguments produces the same result as doing multiple calls with one argument at a time. Not only rowops but also trays (to be discussed later) of rowops can be used as arguments.

The mode for enqueue() is one of either Triceps constants

&Triceps::EM_CALL
&Triceps::EM_FORK
&Triceps::EM_SCHEDULE

or the matching strings "EM_CALL", "EM_FORK", "EM_SCHEDULE". As usual, the constant form is more efficient. There are calls to convert between the constant and string representations:

$string = &Triceps::emString($value);
$value = &Triceps::stringEm($string);

As usual, if the value can not be translated they return undef.

The frame marks for looping are created as their own class:

$mark = Triceps::FrameMark->new("name") or die "$!";

The name can be received back from the mark:

$name = $mark->getName();

Other than that, the frame marks are completely opaque, and can be used only for the loop scheduling. Not even the same() method is supported for them at the moment, though it probably will be in the future. The mark gets set and used as:

$unit->setMark($mark);
$unit->loopAt($mark, $rowop, ...) or die "$!";

The rowop arguments of the loopAt() are the same as for the other enqueueing functions.

The methods for creation of labels have been already discussed. There also are similar methods for creation of tables and trays that will be discussed later:

$label = $unit->makeDummyLabel($rowType, "name") or die "$!";
$label = $unit->makeLabel($rowType, "name",
  $clearSub, $execSub, @args) or die "$!";
$table = $unit->makeTable($tableType, $endMode, "name") or die "$!";
$tray = $unit->makeTray(@rowops) or die "$!"; 

The unit can be checked for the emptiness of its queues:

$result = $unit->empty();

The functions for execution are:

$unit->callNext();
$unit->drainFrame();

The callNext() takes one label from the top stack frame queue and calls it. If the innermost frame happens to be empty, it does nothing. The drainFrame() calls the rowops from the top stack frame until it becomes empty. This includes any rowops that may be created and enqueued as part of the execution of the previous rowops.

A typical way of processing the incoming rowops in a loop is:

$stop = 0; 
while (!$stop) {
  $rowop = readRowop(); # some user-defined function
  $unit->schedule($rowop);
  $unit->drainFrame();
} 

All the unit's labels get cleared with the call

$unit->clearLabels();

To not forget calling it, a separate clearing trigger object can be created:

my $clearUnit = $unit->makeClearingTrigger();

The variable $clearUnit would normally be a global (in a thread) variable. Don't copy the reference to the other variables! Then when the thread completes and the global variables get destroyed, the trigger object will be also destroyed, and will trigger the clearing of the unit's labels, thus breaking up any reference loops and allowing to destroy the bits and pieces.

The only item left is the tracers, and they will be described in a separate post.

loop scheduling

The easiest way to schedule the loops is to do it procedurally, something like this:

foreach my $row (@rowset) {
  $unit->call($lbA->makeRowop(&Triceps::OP_INSERT, $row)); 
}

However the labels topologically connected into a loop can come handy as well. Some logic may be easier to express this way. Suppose the model contains the labels connected in a loop:

X->A->B->C->Y

   ^     |

   +-----+

Suppose a rowop X1 is scheduled for label X, and causes the loop executed twice, with rowops X1, A2, B3, C4, A5, B6, C7, Y8. If each operation is done as a CALL, the stack grows like this: It starts with X1 scheduled.

[X1]

Which then gets executed, with its own execution frame (marked as such for clarity:

[ ] of X1
[ ]

Which then calls A2:

[ ] of A2
[ ] of X1
[ ]

By the time the execution comes to Y8, the stack looks like:

[ ] of Y8
[ ] of C7
[ ] of B6
[ ] of A5
[ ] of C4
[ ] of B3
[ ] of A2
[ ] of X1
[ ]

The loop has been converted into recursion, and the whole length of execution is the deep of the recursion. If the loop executes a million times, the stack will be two million levels deep. Worse yet, it's not just the Triceps scheduler stack that grows, it's also the process (C++) stack.

Would things be better with FORK instead of CALL used throughout the loop? It starts the  same way:

[X1]

Then X1 executes, gets its own frame and forks A2:

[A2] of X1
[ ]

Then A2 executes, gets its own frame and forks B3:

[B3] of A2
[ ] of X1
[ ]

By the end of the loop the picture becomes exactly the same as with CALL. For a while I've thought that optimizing out the empty stack frames would solve the problem, but no, that doesn't work: the problem is that the C++ process stack keeps growing no matter what. The jump back in the loop needs to be placed into an earlier stack frame.

One way to do it would be to use the SCHEDULE operation in C to jump back to A, placing the rowop A5 back onto the outermost frame. The scheduler stack at the end of C4 would look like:

[ ] of C4
[ ] of B3
[ ] of A2
[ ] of X1
[A5]

Then the stack would unwind back to

[A5]

and the next iteration of the loop will start afresh. The problem here is that if X1 wanted to complete the loop and then do something, it can't. By the time the second iteration of the loop starts, X1 is completely gone. It would be better to be able to enqueue the next execution of the loop at the specific point of the stack.

Here the concept of the frame mark comes in: a frame mark is a token object, completely opaque to the program. It can be used only in two operations:

• setMark() remembers the position in the frame stack, just outside the current frame
• loopAt() enqueues a rowop at the marked frame

Then the loop wold have its mark object M. The label A will execute setMark(M), and the label C will execute loopAt(M, rowop(A)). The rest of the execution can as well use call().

When A2 calls setMark(M), the stack will look like this:

[ ] of A2
[ ] of X1 * mark M
[ ]

The mark M remembers the frame one outer to the current one. The stack at the end of C4, after it has called loopAt(M, A5), is:

[ ] of C4
[ ] of B3
[ ] of A2
[A5] of X1 * mark M
[ ]

The stack then unwinds until A5 starts its execution:

[ ] of A5
[ ] of X1 * mark M
[ ]

Each iteration starts with a fresh stack, and the stack depth is limited to one iteration. The nested loops can also be properly executed.

Now, why does the mark is placed on the frame that is one out from the current one? Suppose that it did remember the current frame. Then at the end of C4 the stack will be:

[ ] of C4
[ ] of B3
[A5] of A2 * mark M
[ ] of X1
[ ]

The stack will unwind until A5. Which would then have its own frame pushed onto the stack, and call setMark(M) again, moving the mark to its own frame:

[ ] of A5 * mark M
[ ] of A2
[ ] of X1
[ ]

So on each iteration of the loop one extra frame will be pushed onto the stack, and the mark moved by one level. A loop executing a million times will push a million frames, which is bad. Marking the next outer frame prevents this.  Another option would have been to put the mark in X, but that would mean that every loop must have a preceding label that just marks the frame (well, and potentially could do the other initializations too), which seems to be too annoying.

However as things are, another problem is that if X does call(A2), when it returns, the loop would not be completed yet, only the first iteration would be completed. To have the whole loop completed, there would have to be another label W, and when W does call(X1), the loop would be completed.

This is still messy, and I'm still thinking about the ways to improve the situation.

What happens after the stack unwinds past the mark? The mark gets unset. When someone calls loopAt() with an unset mark, the rowop is enqueued in the outermost frame, having the same effect as schedule().

rowop sets the condition, it would free that original row and make it continue through the loop.  Eventually the loop will come to the looping point, calling loopAt(). But the original mark will be long unset. Scheduling at the outermost frame seems to be a logical thing to do at this point.

What if setMark() is called when there is only one frame on the stack? Then there is no second frame outer to it. The mark will simply be left unset.