[Proposal]: switch for Duff's Device

[jrmoserbaltimore]

Duff's Device

• Proposed
• Prototype: Not Started
• Implementation: Not Started
• Specification: Not Started

Summary

[summary]: Implement the Duff's Device as a language feature.

A Duff's Device allows entry into a loop partway into the loop. Duff's Device relies on fall-through case switching.

// Sum all but the final number in this list
switch (true) foreach (int x in intList)
{
  int last;
  foo += last;
  case true:
  last = x;
}

Motivation

[motivation]: Keeps happening

It's infrequent, but from time to time I find myself writing code in the form:

some_code_X;

while (condition)
{
    some_other_code;
    some_code_X;
}

These are conditions where some_code_X has to execute in the initial state before some_other_code is valid; but some_other_code is not valid after the final execution of some_code_X, therefor no ordering of the code inside a loop works. The answer is to violate the DRY principle, copying the same code twice and maintaining both bodies of code when they change.

These chicken-and-egg problems are frequent enough to be a memorable annoyance, but not so frequent as to draw real-world examples to mind easily. That's the sweet spot where a problem gets ignored even if it's a problem.

Detailed design

[design]: Just a Duff's Device

This would involve some manner of switching into a for, foreach, while, or do loop based on a condition at entry. No further evaluation would be carried out: at the loop's entry point, the entry condition is evaluated, and a case label is selected as the entry point of the first iteration only.

Drawbacks

It would be perhaps problematic, perhaps not, to modify the general switch statement to automatically fall through (as in C), much less to allow it to envelope a loop. It would also be odd and cluttered code.

This means a new type of switch would be necessary, which may then cause confusion about the old type of switch. Within the device, the break command is not valid in terms of the switch: break exits the loop, which is the immediate scope.

Alternatives

A new keyword prefixed to a loop is an alternative. Possibilities are entry, from, or duff (after the original Duff's Device). The form would be:

from (caseSwitch) while (a>0)
{
  default:
  ...
  5:
  ...
  11:
  ...
}

The keyword would need to precede the for, foreach, do, or while statement, since a statement immediately following any of these is interpreted as the statement on which the execution is conditioned.

Unresolved questions

It is perhaps nonsense to support this for both do and while, as do is equivalent to a Duff's Device that switches into the first execution of a while loop without testing the condition.

[benaadams]

Can switch to gotos; which gives much the same effect? Then loop around that

    switch (i)
    {
        case 0: goto pos0;
        case 1: goto pos1;
        case 2: goto pos2;
        case 3: goto pos3;
        case 4: goto pos4;
        case 5: goto pos5;
        case 6: goto pos6;
        case 7: goto pos7;
    }

pos0:
    ;
pos1:
    ;
pos2:
    ;
pos3:
    ;
pos4:
    ;
pos5:
    ;
pos6:
    ;
pos7:
    ;

[333fred]

In the future, please submit this type of proposal as a discussion, rather than an issue. We would like to reserve new issues for fully-specified proposals that have had discussion with members of the team and the community about the benefits and drawbacks, and the format of issues does not make it easy to have such a discussion.

[ber-sma]

The wish for something like "start in the middle" of a loop occurred to me as well, but not in a frequent or bothering way. I think what I usually do is one of the following:

while (true) {
    some_code_X;
    if (!condition) {
        break; // if you can live with a break (I usually cannot)
    }
    some_other_code;
}

do {
    some_code_X;
    if (condition) {
        some_other_code;
    }
} while (condition) // if your condition is side-effect free (which I strongly recommend anyway)

TLDR: Don't DRY. If all else fails, at least extract a (possibly local) method for the repeated code block - and then why not use that opportunity to give it meaningful name.

[benaadams]

More specifically, jumping into the middle of a loop creates irreducible control flow graphs https://en.wikipedia.org/wiki/Control-flow_graph which makes it hard for a compiler to optimize (and why gotos got a bad name)

[jrmoserbaltimore]

That's interesting. Is this an irreducible control-flow graph:

bool init = true;
while (condition)
{
  if (!init || entry == 0)
  {
    body_1();
    init = 0;
  }
  if (!init || entry == 1)
  {
    body_2();
    init = 0;
  }
  body_3();
  init = 0;
}

[benaadams]

No; because there is only one way to enter the loop. It becomes irreducible when the control flow crosses; e.g. you have more than one loop entry point, which Duffs Device does

    register n = (count + 7) / 8;  // gives the number of iterations
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
            } while (--n > 0);
    }

As the switch makes 8 different ways of entering the do loop

[jrmoserbaltimore]

The two seem equivalent to me in a mathematical sense: if on the first iteration, based on each of these conditions, don't perform all portions of the body of the loop prior to this portion.

That being the case, given the irreducible form, can it be transformed into the reducible form; and if so, is it really irreducible?

[benaadams]

The transform is changing the operations performed (as now it's doing many if checks per loop iteration); so it's a deoptimisation?