Is it possible to define branches which, once taken once, will become the default forever?

Question

Assuming I have a very simple branching:

switch on var:
  1 => branch1
  2 => branch2
  default => branch3

And I wish to implement a program that will forever take "branch2" when entering this sequence of instructions once branch2 is taken.

This is quite easy to do by adding an additional variable and setting it when branch2 is entered, however, this will keep the overhead of having to execute the control statement, I'm wondering if there is a way to remove that overhead or diminish it.

I'd be interested in knowing if:

a) This sort of optimization exists in theory ?

b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?\

Edit:

Just to clarify, what I'm asking is if its possible that, once branch-x is taken once, for the instructions executed by the cpu to become:

//Code
//Instructions of branch x
//Code

rather than what we had before which was:

//Code
//Control Statement
//Code

That is in order to "skip" the overhead of having to select branch x to being with, not to optimize how that selection is done.

Answer 1

Update

Based on your comment,

I'm not concerned so much about switch statement being inefficient as I am by the fact that the switch statement exists at all.

, I think that I understand the question better now. And the answer is that you want currying to be applied on the first execution.

As a quick explanation of currying, consider a mathematical function $$f\left(x,y,z\right)=x+y+z,$$ but you know that $x=y=z=1$, such that this could be reduced down to $$f\left(\right)=3.$$ You want this, except in your case you want to reduce a switch function down to a single one of its branches.

This is entirely possible - you basically just need to recompile the code for that function. Or, if you're working in an interpreted language (e.g., JavaScript), you can simply define the switch function as its branch to replace it.

In practice, you won't need to worry about it too much in typical cases because:

1. Most switch statements aren't executed enough to be computationally significant.

2. When switch statements are executed enough to be computationally significant, but continue to resolve to the same branch each time (as you're asking about), the CPU will tend to use branch prediction to optimize it away automatically.

   • Example: StackOverflow: "Why is it faster to process a sorted array than an unsorted array?" is about a dramatic example of branch prediction at work. The tl;dr there is that sorting a list caused branches to tend to evaluate the same way over time (as you're interested in), resulting in a dramatic speedup.

Still, if the switch statement's proving to be a major bottleneck or you just want to do this anyway for fun (which is a very under-valued rationale - where would we be today if people just didn't do stuff for the heck of it?!), then you have a few options:

1. Split up the method that calls the switch statement into several variants, each of which does a different branch.

   • Perform this split just high enough to be outside of the critical section.

   • In effect, this will be like having pre-compiled (and optimized!) versions of the code for each of the possibilities.

   • For a jargon description, you'd be hoisting the switch nodal point outside of the performance-critical code region.

2. Actually curry-and-recompile the method at runtime.

   • Depending on your platform, this can have some technical barriers.

   • When you recompile, you have to figure out what part of the program to recompile. If you do the entire thing, then it could take a while, etc.. But if you do only the switch statement, then optimizations around that area in the code will become prohibited, plus your program will need an extra function-call step to call the switch statement and its ultimate reduction.

   • As with Option (1), the optimal choice here is probably to recompile the critical section, as opposed to just the switch statement or the entire program.

Specific answers

a) This sort of optimization exists in theory ?

Sure, you're talking about splaying, such as implemented in a splay tree.

Obviously you can't implement this sort of optimization in rigid control structures like a switch statement in C/C++, so it'll take making your own implementation of something like a a splay tree that has methods as terminal nodes.

According to your description, you may want the reorganization process to stop after order's been changed once. If so, that's a modification you can add into the splay tree's logic. You can even instruct it to recompile itself in a more rigid, switch-like structure once the structure's determined and the splay logic's no longer needed.

b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

Perhaps in some. It's an implementation detail, so it may be implemented in some implementations but not others.

c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?

Yeah, definitely! You need to statically compile the methods, but you can have a splay tree that resolves method pointers, then run those.

Comments

Just in case there was any confusion, switch statements don't normally need to check cases one-by-one.

For example, consider:

switch (x)
{
    case 0:    foo_0();    break;
    case 1:    foo_1();    break;
    case 2:    foo_2();    break;
    case 3:    foo_3();    break;
}

I'd expect a good compiler to implement this more like:

function[] switchBranches = { foo_0, foo_1, foo_2, foo_3 };
var selectedBranch = switchBranches[x];
selectedBranch();

than as:

if      (x == 0) { foo_0(); }
else if (x == 1) { foo_1(); }
else if (x == 2) { foo_2(); }
else if (x == 3) { foo_3(); }

So if you're doing something like this, you don't really need to worry about the compiler reordering the switch statement's cases since it's already a constant-time lookup.

In more general cases, where a deterministic index isn't practical, dictionary-lookup logic can be applied.

Answer 2

Unroll the loop. Instead of

while true:
  switch on var:
    1 => branch1
    2 => branch2
    default => branch3

replace that with an unrolled version:

while true:
  switch on var:
    1 => branch1
    2 => goto loop2
    default => branch3
return

loop2:
while true:
  branch2

Or, if you prefer:

while true:
  switch on var:
    1 => branch1
    2 => while true:
           branch2
         break
    default => branch3

Answer 3

It is reasonably common nowadays that code is recompiled on occasion. For example, a JVM compiler will initially assume that some function call is not virtual (but can be proved wrong). It will then for a virtual function call generate code like "if (function implementation is what I thought it would be) then (call that implementation) else (recompile this code without that assumption and run it again)". So technically no problem.

However: What on earth are you actually trying to achieve here? You say "the default should be branch2". So you want to change the code from

switch on var:
  1 => branch1
  2 => branch2
  default => branch3

to

switch on var:
  1 => branch1
  2 => branch2
  default => branch2

or at least that's what you say. As a feature of a programming language, the value of this is less than zero. I cannot see any application for this whatsoever. It is so out of the norm that nobody in their right mind will ever use it. If someone else uses it, everyone reading the code will be forever confused what this is doing.

On the other hand, something similar is actually used. Either explicitly as a function (for example dispatch_once or pthread_once) or hidden in the language (static variables in C++, C#, Swift etc.) people want code that is executed only once. With a thread safety guarantee, which means that if one thread is running this code to be run once, all other threads wait if they reach this code.

It turns out that any compiler optimisation there is of very little value. All that needs doing is checking the value of a variable and branching accordingly, which due to branch prediction has a cost of approximately zero.