1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm not really sure what you're asking. It's certainly possible, in the sense that you could certainly program a computer to do this, so you could certainly include it in a language. $\endgroup$ – David Richerby May 30 '17 at 0:45
  • $\begingroup$ b) For dynamic environments you may hotswap the switch statement and surrounding code with new one. If this is in a function you may just assign new function without switch statement. Taking optimization as the permanent change to control flow, yes, for hotspotting vm's it will be included if the control variable is in the scope, not more changes possible, jitc will treat is as constant, so if decision to compile is after the first execution it will vanish. Otherwise it is per VM / per code / per recompile possibility. $\endgroup$ – Evil May 30 '17 at 2:30
5
$\begingroup$

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.

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.

$\endgroup$
  • $\begingroup$ I'm not concerned so much about switch statement being ineficient as I am by the fact that the switch statement exists at all. In the example you gave: var selectedBranch = switchBranches[x]; ... this operation is very resource light but if it happens at a very "hot" point in the program (e.g. each time you append an element to a vector) it will still probably cost you quite a lot of resources on a modern architecture in a real program. $\endgroup$ – George May 30 '17 at 8:39
  • $\begingroup$ The same problem will be exhibited with a splay tree as well since you still have to do my_tree[x] or at least my_tree.root() to pick the branch that's going to run and in that case which means: a) I have to occupy precious space in L1 while executing the instruction and b) I can't actually load code as efficiently in the cache since the path its going to take it unpredictable. Hence why I was asking if there's a way to write the code such that once a branch is taken the control statement is invalidated and the code becomes linear. $\endgroup$ – George May 30 '17 at 8:41
  • $\begingroup$ @George Branch prediction, or just plain currying? First one assumes a path but can backtrack if wrong, the second loses the other paths. $\endgroup$ – Nat May 30 '17 at 10:07
  • $\begingroup$ @George Actually, pretty sure currying's what you want. Heh, that's good for me, too - I'm selling something that does exactly what you want. =P $\endgroup$ – Nat May 30 '17 at 10:36
2
$\begingroup$

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
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.