View mode: basic / threaded / horizontal-split · Log in · Help
July 22, 2012
Computed gotos on Reddit
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
July 23, 2012
Re: Computed gotos on Reddit
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.
July 23, 2012
Re: Computed gotos on Reddit
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
July 23, 2012
Re: Computed gotos on Reddit
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
July 23, 2012
Re: Computed gotos on Reddit
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
July 23, 2012
Re: Computed gotos on Reddit
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
July 23, 2012
Re: Computed gotos on Reddit
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
July 23, 2012
Re: Computed gotos on Reddit
Walter Bright:

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

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

Bye,
bearophile
July 23, 2012
Re: Computed gotos on Reddit
> 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
July 23, 2012
Re: Computed gotos on Reddit
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.
« First   ‹ Prev
1 2 3 4 5
Top | Discussion index | About this forum | D home