Computed gotos on Reddit

[Dmitry Olshansky]

On 24-Jul-12 02:06, Walter Bright wrote:
> On 7/23/2012 2:25 PM, bearophile wrote:
>> Walter Bright:
>>
>>> D already has it: http://dlang.org/statement.html#FinalSwitchStatement
>>
>> Do you have a proof? (Show me asm code)
>
> Since the final switch does not allow a 'default' case, the check can be
> omitted, and the generated code is a simple index-jump, just like the
> computed goto example.
>

Bounds check is actually not that important.

> dmd currently doesn't do that, but that's not the language's fault, it's
> a quality of implementation issue.
>
> The point is, computed goto offers nothing that final switch doesn't.
>


Sorry, but it's just wrong. The trick is that there is no need for jump 
table at all. That saves one memory access to read jump table entry and 
saves on cache (need only one "table" - bytecode itself).

Now to the heart of it all - threaded interpreter looks like this (I'll 
use switches for clarity):

switch(opcode){
case OP1:
	... //do instruction 1
	//+ decode next
	opcode = code[pc++];
	switch(opcode){
	case OP1:
		// jump to case OP1 above
	... etc.
	}
//no break as it will jump away
case OP2:
	... //do instruction 2
	//+ decode next
	opcode = code[pc++];
	switch(opcode){
	case OP1:
		// jump to case OP1 above e.g. by planting label on it
	... etc.
	}
....
}

Now if I use final switches there is still:

A) jump table per switch, or maybe less but there is no guarantees
  (= depend on another optimization that's not here)
B) it's an ugly and a roundabout way to do this

However I think that always requiring tail call optimization or 
providing syntax to enforce it would work:

void op_1()
{
	...//some code for instruction 1
	opcode = cast(function void ())code[pc++];
	goto opcode(); //opcode is pointer to function op_xx
}
//can do without goto fn() iff tail call is GUARANTEED

-- 
Dmitry Olshansky