A discussion appeared few days ago on Reddit, about computed gotos:

http://www.reddit.com/r/programming/comments/wld04/eli_benderskys_website_computed_goto_for/

http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables/

Computed gotos are useful to write interpreters. Interpreters are a niche but important purpose of system languages like D. Computed gotos are also useful to implement certain finite state machines (like some used in computational biology).

The GCC back-end supports computed gotos very well, and recent versions of LLVM support them decently (but not perfectly). This means implementing those gotos in LDC2 and GDC is probably not too much hard. DMD back-end probably don't support them (and who knows how much work it takes to implement that).

So maybe someday people will add a nonstandard extension to D, for GDC and/or LDC to support computed gotos. I hope they will use the same syntax, but generally nonstandard extension are a portability pain, and some people (purists, language lawyers, etc) seem to hate them.

So I have suggested to define a standard syntax for computed gotos in D, so LDC and GDC will avoid inventing a different syntax, so only DMD is the nonsupporting compiler.

Bye,
bearophile

On 23/07/2012 01:35, bearophile wrote:
> A discussion appeared few days ago on Reddit, about computed gotos:
>
> http://www.reddit.com/r/programming/comments/wld04/eli_benderskys_website_computed_goto_for/
>
>
> http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables/
>


The presented example is insanely unsafe. By giving invalid input, you can basically branch randomly.

The check added by the switch is what is required to make it safe, so it isn't faster at the end.

The case in the article isn't very strong.

On 23-Jul-12 07:05, deadalnix wrote:
> On 23/07/2012 01:35, bearophile wrote:
>> A discussion appeared few days ago on Reddit, about computed gotos:
>>
>> http://www.reddit.com/r/programming/comments/wld04/eli_benderskys_website_computed_goto_for/
>>
>>
>>
>> http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables/
>>
>>
>
>
> The presented example is insanely unsafe. By giving invalid input, you
> can basically branch randomly.
>
> The check added by the switch is what is required to make it safe, so it
> isn't faster at the end.
>
> The case in the article isn't very strong.

The  trick is to check the whole bytecode first then execute. The bulk of time is spent in loops anyway.
But yes it's not particularly safe.

> The case in the article isn't very strong.

From a glance it's a well known case of threaded code interpreters. That is the only fast *portable* interpreters as of now.

So the case is strong but hardly anything new ;)

P.S. sorry for mailing you directly, updated firefox changed interface *again* :)

-- 
Dmitry Olshansky


-- 
Dmitry Olshansky

On 23-07-2012 05:05, deadalnix wrote:
> On 23/07/2012 01:35, bearophile wrote:
>> A discussion appeared few days ago on Reddit, about computed gotos:
>>
>> http://www.reddit.com/r/programming/comments/wld04/eli_benderskys_website_computed_goto_for/
>>
>>
>>
>> http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables/
>>
>>
>
>
> The presented example is insanely unsafe. By giving invalid input, you
> can basically branch randomly.
>
> The check added by the switch is what is required to make it safe, so it
> isn't faster at the end.
>
> The case in the article isn't very strong.

You should always verify your bytecode before executing it anyway.

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org

On Sunday, 22 July 2012 at 23:35:34 UTC, bearophile wrote:
> A discussion appeared few days ago on Reddit, about computed gotos:

For another use case: dotat.at/tmp/gll.pdf

deadalnix:

> The presented example is insanely unsafe. By giving invalid input, you can basically branch randomly.
>
> The check added by the switch is what is required to make it safe, so it isn't faster at the end.
>
> The case in the article isn't very strong.

Thank you for your answer. We have not yet designed how D computed gotos are, both in syntax and semantics. This means that maybe there are ways to make them a little safer, in non-release mode.

Part of the GCC-C code in the article was:

static void* dispatch_table[] = {
        &&do_halt, &&do_inc, &&do_dec, &&do_mul2,
        &&do_div2, &&do_add7, &&do_neg};
#define DISPATCH() goto *dispatch_table[code[pc++]]

In D there are no preprocessor macros and the array bounds are enforced at run-time, this avoids some possible bugs of similar code.

Also, instead of void* maybe a different type can be introduced, so only label addresses of the current function can be put in dispatch_table and pointer variables given to goto. This statically avoids some other possible bugs.

It's true that in the end computed gotos are unsafe, you generally need to validate the bytecode/state transition before feeding them to the computed goto, and in D (unlike GCC-C) you are able to forbid the usage of computed gotos in @safe functions/methods. This doesn't avoid bugs, but helps contain them in delimited places. We have the @safe/@trusted/@system for a purpose.

In D modules like std.reflection suggested by Andrei are useful, because D is usable to write lot of high-level code too, I use a highly functional D style in some little D "scripts". But D is also a system language, and sometimes I desire to use it for tasks where C is used. GCC has computed gotos since many years (and Clang supports them) and as you see in the linked article some very common language interpreters you see around use computed gotos if the C compiler supports them. This is not a must-have feature for D, but dismissing it just because it's not safe is a bad idea.

Bye,
bearophile

On 7/22/2012 4:35 PM, bearophile wrote:
> Computed gotos are useful to write interpreters. Interpreters are a niche but
> important purpose of system languages like D. Computed gotos are also useful to
> implement certain finite state machines (like some used in computational biology).

D already has it: http://dlang.org/statement.html#FinalSwitchStatement

Walter Bright:

> D already has it: http://dlang.org/statement.html#FinalSwitchStatement

Do you have a proof? (Show me asm code)

Bye,
bearophile

> Do you have a proof? (Show me asm code)

Just to be more clear, what I mean is that given a D program equivalent to the C code shown in the article:


int interp_cgoto(unsigned char* code, int initval) {
    static const void* dispatch_table[] = {
        &&do_halt, &&do_inc, &&do_dec, &&do_mul2,
        &&do_div2, &&do_add7, &&do_neg};

    #define DISPATCH() goto *dispatch_table[code[pc++]]

    int pc = 0;
    int val = initval;

    DISPATCH();

    do_halt:
        return val;
    do_inc:
        val++;
        DISPATCH();
    do_dec:
        val--;
        DISPATCH();
    do_mul2:
        val *= 2;
        DISPATCH();
    do_div2:
        val /= 2;
        DISPATCH();
    do_add7:
        val += 7;
        DISPATCH();
    do_neg:
        val = -val;
        DISPATCH();
}

int main() {return 0;}


Is a 32 bit D compiler producing asm (with performance) similar to:


_interp_cgoto:
    movl    4(%esp), %edx
    movzbl  (%edx), %eax
    addl    $1, %edx
    movl    _dispatch_table.1363(,%eax,4), %ecx
    movl    8(%esp), %eax
    jmp *%ecx
    .p2align 4,,7
L3:
    rep
    ret
    .p2align 4,,7
L4:
    movzbl  (%edx), %ecx
    addl    $1, %eax
    movl    _dispatch_table.1363(,%ecx,4), %ecx
    .p2align 4,,7
L5:
    addl    $1, %edx
    jmp *%ecx
    .p2align 4,,7
L6:
    movzbl  (%edx), %ecx
    subl    $1, %eax
    movl    _dispatch_table.1363(,%ecx,4), %ecx
    addl    $1, %edx
    jmp *%ecx
    .p2align 4,,7
L7:
    movzbl  (%edx), %ecx
    addl    %eax, %eax
    movl    _dispatch_table.1363(,%ecx,4), %ecx
    addl    $1, %edx
    jmp *%ecx
    .p2align 4,,7
L8:
    movl    %eax, %ecx
    shrl    $31, %ecx
    addl    %ecx, %eax
    movzbl  (%edx), %ecx
    sarl    %eax
    movl    _dispatch_table.1363(,%ecx,4), %ecx
    addl    $1, %edx
    jmp *%ecx
    .p2align 4,,7
L9:
    movzbl  (%edx), %ecx
    addl    $7, %eax
    movl    _dispatch_table.1363(,%ecx,4), %ecx
    addl    $1, %edx
    jmp *%ecx
    .p2align 4,,7
L10:
    movzbl  (%edx), %ecx
    negl    %eax
    movl    _dispatch_table.1363(,%ecx,4), %ecx
    addl    $1, %edx
    jmp *%ecx

    .section .rdata,"dr"
    .align 4
_dispatch_table.1363:
    .long   L3
    .long   L4
    .long   L6
    .long   L7
    .long   L8
    .long   L9
    .long   L10


Bye,
bearophile

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.

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.