StackThreads/MP: version 0.77 User's Guide

9.3: Where should you insert ST_POLLING?

The final topic is where to insert ST_POLLING. Recall that ST_POLLING serves two purposes.

• Thread migration: Pick up, if any, request form an idle worker.
• Stack management: Free dead frames on top of the stack.

The constraint is that you must put enough ST_POLLING to make them work. Another constraint is that you want to minimize ST_POLLING to save your coding time (and to save some overheads, but the overhead is not large (like 10 instructions). When you are not sure, play safe; put it).

Here are rules as to where you should insert ST_POLLING to make thread migration and stack management work. Each imposes a similar but different constraints, but the total result is as follows:

1. When you have a non-leaf procedure (a procedure that may call another procedure) F, insert one at anywhere between the head of F and the first procedure call performed in F.
2. When you have a non-leaf procedure F, insert one at anywhere between the last procedure call in F and the end of F.
3. (Very strictly speaking) When you have a non-leaf procedure F, insert one at anywhere between two procedure calls performed in F (e.g., just after each procedure call). You can forget it in practice.
4. When you have a loop, insert one at anywhere in the body, so that each iteration calls it.

In the last case, you do not have to do it when you know the loop is very small (and therefore never spends a long time).

For example, in pfib, the original code without ST_POLLING is structured like this:

pfib (...)
{
@  ... (a) ...
@  if (...) { ... (b) ... return; }
@  else {
@    ... (c) ...
@    pfib (...);
@    pfib (...);
@    ... (d) ...
@  }
}

According to the rule 1, you insert ST_POLLING to: (a) or (c). We advise (c), because no procedure calls are made along the path (a)->(b)->return. This saves the overhead of ST_POLLING at leaves. According to the rule 2, you insert ST_POLLING to (d).

Do you want to know why? Let me describe constraints more precisely for thread migration and stack management.

First, for thread migration, you must ensure that ST_POLLING is called often enough so that each worker is responsive to requests from idle workers. Following the above rules, the maximum interval in which no ST_POLLINGs are called is bounded (in terms of instruction counts), regardless of input to the program. If the first rule would not be followed, a recursive function may create an arbitrary long polling-free interval. For example,

f(int n)
{
  ...;
  f(n - 1);
}

If there would be no ST_POLLINGs in ..., the length of a polling-free interval is proportional to N, which is not constant across all inputs.

If the second rule would not be followed, a similar situation occurs during a chain of recursive calls are shrinking. For example,

f(int n)
{

  f(n - 1);
  ...;
}

If there would be no ST_POLLINGs in ..., the length of a polling-free interval is proportional to N, which is not constant across all inputs.

The third rule is irrelevant for thread migration.

The fourth rule will be obvious. In practice, you might want to save overhead of calling ST_POLLING, if the body of the rule is very small. If you know the entire loop does not take a long time, you may skip it.

For stack management, you must ensure that you do not miss a point where the entire space above the current frame (upto stack pointer) is free. Notice that a new frame is always allocated on top of stack pointer. Therefore, if you do not call ST_POLLING at such a point and make another procedure call, these frames do not reuse space that is otherwise reusable. In the worst case, this will result in stack overflow that can otherwise be avoided.

A frame becomes dead only when a procedure returns, thus it suffices to call ST_POLLING just after a procedure returns. This is where the third rule comes from. Strictly speaking, all you need for stack management is this rule, but it may seem impractical when manually inserted by the programmer. As a rough approximation, the second rule is in practice OK. This is because, in common programming styles, a procedure F finishes only if all its decedent have finished. When this is the case, it is guaranteed that, if procedure F performs the last ST_POLLING and returns, free space left on top of the stack is none or the frame of F, because all descendent of F have also been finished.