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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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.
|
July 23, 2012 Re: Computed gotos on Reddit | ||||
---|---|---|---|---|
| ||||
Posted in reply to deadalnix | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to deadalnix | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to deadalnix | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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 |
July 23, 2012 Re: Computed gotos on Reddit | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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 |
July 23, 2012 Re: Computed gotos on Reddit | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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.
|
Copyright © 1999-2021 by the D Language Foundation