Is it possible to define branches which, once taken once, will become the default forever?
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:


Most switch statements aren't executed enough to be computationally significant.
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:


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.

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.