Computed gotos on Reddit

[Dmitry Olshansky]

On 25-Jul-12 10:11, Walter Bright wrote:
> On 7/24/2012 10:04 PM, Dmitry Olshansky wrote:
>> BTW Static array for jump table is all
>> good and well but does this trick work with PIC code?
>
> The jump table can be in the code segment, which is not possible for a
> user generated array.
>
OK, so it works - good to know.

>> And last but not least - the jump
>> target has to be _read_ from jump table
>>   and then jumped to it isn't it?
>
> And it has to be read from code[] and jumped to. No difference.

Yes, one read + one jump.

>
>> OK I've taken your comments into account.
>> Now I think I finally got it right:
>>
>> mov ecx, [ebx] ; ecx = code[pc]
>> inc ebx ; pc ++
>> jmp ecx ; goto code[pc], as ecx is already a pointer
>
> Nope, ecx is an opcode, not a pointer. You need another indirection.

Great, I think we finally got to the heart of it.
The trick is that we already pre-processed our bytecode. Now it contains 
real addresses. See my computed goto example again.
(even I myself made a mistake of writing [ecx] previously)

>>
>> vs
>>
>> mov ecx, [ebx] ; ecx = code[pc]
>> inc ebx ; ; inc pc
>> jump jump_table[ecx]; ; switch jump to it
>>
>> or in english, ommiting PC increment:
>> 1.
>> read x from array
>> jump to it
>
> It's
>
>      pc => opcode => address
>
> not
>
>      pc => address
>

It's pc => address because one can first preprocess all of byte code 
doing opcode => address rewrites. But you can't do it unless taking 
address of labels is possible.

> 2 indirections required. You keep skipping one of them!

That's how you make things fast! :)

>>> I see what you mean here, too. Thanks for the explanation. It never
>>> occurred to me that one could write code like that, but I see the point,
>>> and doing jump table merging could be done fairly easily. No new
>>> language feature is required.
>>
>> Superb! I actually tried the code above, generating common things with
>> a help of
>> string mixins, of course currently it only gets slightly slower.
>>
>> Should I file an enhancement request?
>
> For the jump table merging, yes please.

Done:
http://d.puremagic.com/issues/show_bug.cgi?id=8431

-- 
Dmitry Olshansky