4 ms·

> computed goto I did a deep dive into this topic lately when exploring whether to add a language feature to zig for this purpose. I found that, although finni

> computed goto I did a deep dive into this topic lately when exploring whether to add a language feature to zig for this purpose. I found that, although finnicky, LLVM is able to generate the desired machine code if you give it a simple enough while loop continue expression[1]. So I think it's reasonable to not have a computed goto language feature. More details here, with lots of fun godbolt links: https://github.com/ziglang/zig/issues/8220 https://github.com/ziglang/zig/issues/8220 [1]: https://godbolt.org/z/T3v881 https://godbolt.org/z/T3v881

tiddles 6y ago
Thank you for doing the research and not just mindlessly adding features other languages have :)
anonymoushn 6y ago
Oh, that's great. I write interpreters off and on and I love Zig, so it's nice to hear I can get the best code gen while keeping the language small
celeritascelery 6y ago
Really cool investigation. I wonder if this applies to rust as well. As you said though, this is finicky, and if you need this optimization for performance then you don’t want to rely on compiler heuristics.
- Measter 6y ago
  Rust's output[0] is basically the same as Zig in this case. The unsafe is needed here because it's calling extern functions. However, in this specific instance at least, this isn't as optimal as it could be. What this is basically doing is creating a jump table to find out which branch it should go down. But, because all the functions have the same signature, and each branch does the same thing, what it could have done instead is create a jump table for the function to call. At that point, all it would need to do is use the Inst's discriminant to index into the jump table. I'm not sure what it would look like in Zig, but it's not that hard to get that from Rust[1]. The drawback of doing it this way is that it now comes with the maintenance overhead of ensuring the order and length of the jump table exactly matches the enum, otherwise you get the wrong function being called, or an out-of-bounds panic. You also need to explicitly handle the End variant anyway because the called function can't return for its parent. I don't know Zig, but from what I understand it has some pretty nice code generation, so maybe that could help with keeping the array and enum in step here? [0] https://godbolt.org/z/sa6fGq https://godbolt.org/z/sa6fGq [1] https://godbolt.org/z/P3cj31 https://godbolt.org/z/P3cj31
eru 6y ago
Somewhat off-topic: I just looked into zig, because you mentioned it. > C++, D, and Go have throw/catch exceptions, so foo() might throw an exception, and prevent bar() from being called. (Of course, even in Zig foo() could deadlock and prevent bar() from being called, but that can happen in any Turing-complete language.) Well, you could bite the bullet and carefully make Zig non-Turing complete. (Or at least put Turing-completeness behind an escape hatch marked 'unsafe'.) That's how Idris and Agda etc do it.
- skybrian 6y ago
  With respect to deadlocks, there’s little practical difference between an infinite loop and a loop that holds the lock for a very long time. Languages like Idris and Agda are different because sometimes code isn’t executed at all. A proof may depend on knowing that some code will terminate without running it.
  - eru 6y ago
    > Languages like Idris and Agda are different because sometimes code isn’t executed at all. A proof may depend on knowing that some code will terminate without running it. Yes. They are rather different in other respects as well. Though you can produce executable code from Idris and Agda, of course. > With respect to deadlocks, there’s little practical difference between an infinite loop and a loop that holds the lock for a very long time. Yes, that's true. Though as a practical matter, I have heard that it's much harder to produce the latter by accident, even though only the former is forbidden. For perhaps a more practical example, have a look at https://dhall-lang.org/ https://dhall-lang.org/ which also terminates, but doesn't have nearly as much involved proving.

tiddles 6y ago

Thank you for doing the research and not just mindlessly adding features other languages have :)

anonymoushn 6y ago

Oh, that's great. I write interpreters off and on and I love Zig, so it's nice to hear I can get the best code gen while keeping the language small

celeritascelery 6y ago

Really cool investigation. I wonder if this applies to rust as well. As you said though, this is finicky, and if you need this optimization for performance then you don’t want to rely on compiler heuristics.

Measter 6y ago
Rust's output[0] is basically the same as Zig in this case. The unsafe is needed here because it's calling extern functions. However, in this specific instance at least, this isn't as optimal as it could be. What this is basically doing is creating a jump table to find out which branch it should go down. But, because all the functions have the same signature, and each branch does the same thing, what it could have done instead is create a jump table for the function to call. At that point, all it would need to do is use the Inst's discriminant to index into the jump table. I'm not sure what it would look like in Zig, but it's not that hard to get that from Rust[1]. The drawback of doing it this way is that it now comes with the maintenance overhead of ensuring the order and length of the jump table exactly matches the enum, otherwise you get the wrong function being called, or an out-of-bounds panic. You also need to explicitly handle the End variant anyway because the called function can't return for its parent. I don't know Zig, but from what I understand it has some pretty nice code generation, so maybe that could help with keeping the array and enum in step here? [0] https://godbolt.org/z/sa6fGq https://godbolt.org/z/sa6fGq [1] https://godbolt.org/z/P3cj31 https://godbolt.org/z/P3cj31

eru 6y ago

Somewhat off-topic: I just looked into zig, because you mentioned it. > C++, D, and Go have throw/catch exceptions, so foo() might throw an exception, and prevent bar() from being called. (Of course, even in Zig foo() could deadlock and prevent bar() from being called, but that can happen in any Turing-complete language.) Well, you could bite the bullet and carefully make Zig non-Turing complete. (Or at least put Turing-completeness behind an escape hatch marked 'unsafe'.) That's how Idris and Agda etc do it.

skybrian 6y ago
With respect to deadlocks, there’s little practical difference between an infinite loop and a loop that holds the lock for a very long time. Languages like Idris and Agda are different because sometimes code isn’t executed at all. A proof may depend on knowing that some code will terminate without running it.
- eru 6y ago
  > Languages like Idris and Agda are different because sometimes code isn’t executed at all. A proof may depend on knowing that some code will terminate without running it. Yes. They are rather different in other respects as well. Though you can produce executable code from Idris and Agda, of course. > With respect to deadlocks, there’s little practical difference between an infinite loop and a loop that holds the lock for a very long time. Yes, that's true. Though as a practical matter, I have heard that it's much harder to produce the latter by accident, even though only the former is forbidden. For perhaps a more practical example, have a look at https://dhall-lang.org/ https://dhall-lang.org/ which also terminates, but doesn't have nearly as much involved proving.