News for hackers. Stuff that matters.
Re:Things Rust shipped without by IvyMike on Friday July 03, 2015 @02:50PM (#9827276)
> goto (not even as a reserved word)

I haven't done this for a while, but once upon a graduate program I wrote a compiler from a made-up-language (MUP) to C. MUP had some strange control structures, and if C did not have "goto", it would have been a lot more difficult to implement those structures. Since then, I have always thought languages should have a "goto" statement that human-written code is not allowed to use. :)

Re:Things Rust shipped without by pcwalton on Friday July 03, 2015 @02:55PM (#9827305)
It often simplifies a lot of the compiler implementation if you only have reducible control flow. LLVM is fine with irreducible control flow, because it has to handle C, but rustc uses a CFG for the borrow checker, which is flow-sensitive. You can convert irreducible control flow to reducible control flow, but it can explode the size of the graph in pathological cases.

(I don't recall whether the borrow checker actually depends on the control flow being reducible, but some of the possible future improvements we've talked about with "non-lexical lifetimes" definitely do. There are also nasty interactions between RAII and irreducible control flow…)

Re:Things Rust shipped without by cwzwarich on Friday July 03, 2015 @03:48PM (#9827582)
Non-lexical lifetimes don't depend on reducibility. The RFC I wrote works fine for irreducible CFGs:

https://github.com/rust-lang/rfcs/pull/396

It does have the effect of picking a single dominating entry point for a loop with multiple entry points, but if you want a single-entry region that's necessarily true. Multiple-entry regions are probably possible, but they could be counterintuitive and produce even stranger error messages than the current region system.

The borrow checker is based on dataflow analyses that should work on arbitrary CFGs, assuming an appropriately generalized notion of region.

Re:Things Rust shipped without by EugeneOZ on Saturday July 04, 2015 @01:11AM (#9829309)
I think the point of parent comment is "it's ok to don't have goto in Rust, but it's not the reason to be proud of just not having goto". Goto is important enough operator and doesn't deserve blind hate.
Re:Things Rust shipped without by tracker1 on Saturday July 04, 2015 @01:30AM (#9829347)
Agreed... I honestly tend to break code into a lot of discrete functions, and combine for workflows, but sometimes you just need to easily jump back a few places, and where goto is available it's not always a bad option. Just one that should be used sparingly... once in a complex workflow is fine.. more than twenty times in a few thousand line method, not so much.
Re:Things Rust shipped without by mcguire on Saturday July 04, 2015 @12:24PM (#9830611)
Don Knuth, "Structured Programming with go to Statements":

"Just recently, however, Hoare has shown that there is, in fact, a rather simple way to give an axiomatic definition of go to statements; indeed, he wishes quite frankly that it hadn't been quite so simple....

"Informally, α(L) represents the desired state of affairs at label L; this definition says essentially that a program is correct if α(L) holds at L and before all "go to L" statements, and that control never "falls through" a go to statement to the following text. Stating the assertions α(L) is analogous to formulating loop invariants. Thus, it is not difficult to deal formally with tortuous program structure if it turns out to be necessary; all we need to know is the "meaning" of each label."

Re:Things Rust shipped without by gsg on Friday July 03, 2015 @03:24PM (#9827483)
Yeah. Even basic things like building SSA can be done more simply on "structured" CFGs.

The benefits are enough that data structure and algorithm designs in the JVM compiler world often take advantage of assuming reducible control flow even though Java bytecode can express irreducible CFGs. Instead, such programs are left to the interpreter.

Re:Things Rust shipped without by cwzwarich on Friday July 03, 2015 @03:54PM (#9827605)
Rust's CFGs are reducible with unbounded treewidth, not structured, because Rust has named exits from loops that nest arbitrarily.

Most problems on reducible graphs are not easier than for general graphs, because you can always compute a loop forest (for generalized loops, not natural loops with a single entry point) and just consider a derived acyclic graph.

Re:Things Rust shipped without by gsg on Saturday July 04, 2015 @12:31AM (#9829212)
The structured SSA building algorithm I had in mind has a fairly simple extension that covers break, continue, and early return. It's more complicated, but still way simpler than iterated dominance frontiers.

> you can always compute a loop forest

It's easier to not have to.

Re:Things Rust shipped without by cwzwarich on Saturday July 04, 2015 @02:59AM (#9829497)
Technically speaking, break / continue / early return are unstructured by the classical definition. The algorithm you are likely thinking of can easily be extended to handle arbitrary control-flow:

https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun...

In the case of irreducible control-flow it may produce redundant cyclic phis, but those can be eliminated with a pretty simple post-pass.

Re:Things Rust shipped without by haberman on Friday July 03, 2015 @04:27PM (#9827753)
At least reserve the word, in case you change your mind in the future? I guess it's too late now...
Re:Things Rust shipped without by Maken on Friday July 03, 2015 @04:56PM (#9827912)
Burn the boats and never look back, I guess.
Re:Things Rust shipped without by GFK_of_xmaspast on Friday July 03, 2015 @05:44PM (#9828114)
Since when does rust care about breaking changes to the language.
Re:Things Rust shipped without by steveklabnik on Friday July 03, 2015 @05:45PM (#9828117)
Seven weeks ago today.
Re:Things Rust shipped without by mcguire on Saturday July 04, 2015 @12:25PM (#9830616)
For version 1? Can we break on 2.0?
Re:Things Rust shipped without by steveklabnik on Saturday July 04, 2015 @12:27PM (#9830620)
Re:Things Rust shipped without by azakai on Friday July 03, 2015 @04:06PM (#9827658)
> You can convert irreducible control flow to reducible control flow, but it can explode the size of the graph in pathological cases.

True, but only in node-splitting approaches. If you use a label threading variable (as emscripten's relooper does), there is a guaranteed reasonable limit on code size increase (at the cost of performance).

Re:Things Rust shipped without by chjj on Friday July 03, 2015 @06:54PM (#9828348)
I've always defended goto and gotten a lot of flak for it. As soon as I say, "I wish I had X-language had gotos", I see jaws drop. Response: "Wow, haven't you heard the news?! GOTOs are considered harmful!"

I think goto should be in almost every language. It's one of the most primitive instructions, why shouldn't it be available when needed? Yes, it can be misused, just like any other feature in the language, but it can also be used to great benefit. State machines, for example, can make good use of gotos.

Hell, look at any unix library your machine uses every day. The ones you don't even think about. Start with libncurses: I promise there's a few gotos where needed.

    $ find ~/ncurses-5.9 -name '*.c' -print0 | xargs -0 grep goto | wc -l
    70
Raise your hand if you plan to stop using ncurses because of how opposed to how "harmful" goto statements are.

Oh, here's tmux, if you're interested (one of the most beautifully written C programs): https://github.com/tmux/tmux/search?utf8=%E2%9C%93&q=goto

Re:Things Rust shipped without by geofft on Saturday July 04, 2015 @12:14AM (#9829162)
Rust is not a language that looks favorably on things that are easy to misuse and hard to use correctly. You can make the same argument about, say, untagged / C-style unions, which are much more common in C, but Rust doesn't have those either.

I don't plan to stop using ncurses in particular, but one of the reasons I am supportive of Rust is that I would like to stop using all C software sometime in my lifetime.

Re:Things Rust shipped without by milspec on Saturday July 04, 2015 @02:02AM (#9829390)
Rust should have untagged unions. Obviously, ones that allow pointer abuse would be restricted to code marked unsafe.

Note that a union of two pointer-containing structs is safe as long as the pointers line up, having the same type and offset in each struct.

Re:Things Rust shipped without by comex on Saturday July 04, 2015 @07:10AM (#9829847)
They've been proposed:

https://github.com/rust-lang/rfcs/pull/724

If you really need them, you can implement them in a library by declaring a suitably sized byte array and having methods that return casted pointers to it. This would be illegal in C due to strict aliasing, but IIRC Rust does not have a strict aliasing rule (because almost all pointers being the equivalent of 'restrict' drastically reduces the benefit).

There are issues with size_of not being a constant expression and such (at least in stable), but those are definitely going to be fixed.

Re:Things Rust shipped without by jroesch on Saturday July 04, 2015 @03:48AM (#9829577)
Do you have a compelling use case? I can't imagine a use for untagged unions in Rust that isn't subsumed by other features in the language.
Re:Things Rust shipped without by mbrubeck on Saturday July 04, 2015 @11:33AM (#9830433)
The most common use case would be interop with C libraries that use untagged unions. This is a significant hassle when writing C bindings in Rust today.
Re:Things Rust shipped without by Jweb_Guru on Saturday July 04, 2015 @01:43PM (#9830891)
I can think of many, mostly revolving around cases where the tag is not stored inline with the structure in question. Where space efficiency is important this is quite common. C interoperability is obviously another important use case (the current solution of passing around [u8] arrays is pretty atrocious).
Re:Things Rust shipped without by jxf on Friday July 03, 2015 @08:06PM (#9828572)
> It's one of the most primitive instructions, why shouldn't it be available when needed?

I see what you're saying, though I don't find this a compelling argument. By this logic, why not allow direct register access in all languages?

Just because something is a primitive operation doesn't mean you want to include it, especially not if it's more difficult to enforce guarantees your language would like to make about valid programs.

Re:Things Rust shipped without by pcwalton on Friday July 03, 2015 @10:40PM (#9828914)
All of the gotos I see on that page are simulations of RAII or labeled break/continue.
Re:Things Rust shipped without by mercurial on Saturday July 04, 2015 @02:48AM (#9829476)
The kernel has plenty of goto, mostly (as far as I know) to handle errors and safe resource deallocation. There is no reason to keep using GOTO if you have better mechanisms to handle these things.
Re:Things Rust shipped without by Retra on Saturday July 04, 2015 @05:44PM (#9831708)
The target of a goto statement is a specific place in code. It is not code that refers to the task you are trying to perform.

The main advantage of using higher-level languages is that you can talk about manipulations of data. Goto doesn't manipulate data, it manipulates the machine. And if you want to _really_ manipulate the machine, you're going to want more than just goto.

>Raise your hand if you plan to stop using ncurses because of how opposed to how "harmful" goto statements are.

Goto statements are not harmful to computers or to code. Ncurses isn't what is harmed by goto, nor does "using ncurses" imply any interaction with goto at all.

Muhammad Ali was a good boxer. He was Muslim. Am I to conclude that one must be Muslim to be a good boxer, now?

Yes, ncurses is a good program. Yes it uses goto. But that doesn't imply that goto is necessary to it being a good program. Or that it is even a mildy efficient way of doing well. (Especially not when there is a whole universe of alternatives.)

If you're going to defend goto (and there are reasons to do this) you should probably do so without employing such blatant logical fallacies. It's irresponsible and detracts from your point.

Re:Things Rust shipped without by adynatos on Saturday July 04, 2015 @05:04AM (#9829683)
C's goto has a bad rep it only partially deserves, however I can't agree that it should be in every language. I use it fairly frequently, but virtually all the uses are about cleanup after error. I like that it requires unique label for identification, as it allows for language-enforced documentation. But my gotos always go "down" the source code, never "up. Through goto I can basically setup an error-condition code flow for every function, with multiple conditional entry points into that flow and if there was another language feature that allowed just this particular usage in cleanup, without multiple nested scopes and with clear labelling, then I would see no reason for keeping goto. Throughout the years we developed a way to neatly use an unsafe feature, but it's always better to have such things enforced by language, not by tradition.
Re:Things Rust shipped without by istvan__ on Friday July 03, 2015 @10:44PM (#9828927)
I do not use goto in my code. What do I do wrong? :) Ok, I have to admit that I used it on C64 in the 80s.

Anyways, exceptions are sort of gotos or at least they can behave that way.

Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @06:43AM (#9829816)
If you're not implementing fast FSMs, fast bytecode interpreters (and dynamic dispatchers in general), and you're not using metaprogrming to the full power, not implementing multiple embedded DSLs - then you can live without a goto. Otherwise it is essential.
Re:Things Rust shipped without by pjmlp on Saturday July 04, 2015 @08:48AM (#9829993)
Metaprogramming to the full power sounds like Lisp. It doesn't have goto.
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @10:07AM (#9830174)
> Metaprogramming to the full power sounds like Lisp.

It does, yes, although many Lisps got a pretty limited backend for this sort of things. My preferred metaprogramming environment must have a fallthrough mode for allowing generating low-level code where Lisp semantics is not sufficient. Rust seems like a very good target platform in this sense, so the lack of goto really hurts.

> It doesn't have goto.

Of course they do (tagbody in Common Lisp, for example). And when they don't, it's often relatively easy to add one.

Re:Things Rust shipped without by pjmlp on Monday July 06, 2015 @06:52AM (#9838124)
> Of course they do (tagbody in Common Lisp, for example). And when they don't, it's often relatively easy to add one.

I was wrong, however it is much more limited than the goto everywhere from C, as where the labels are located is clearly defined in the tagbody and not in every possible statement.

Re:Things Rust shipped without by EugeneOZ on Saturday July 04, 2015 @01:15AM (#9829314)
No, exceptions are incomparable much harmful because they don't have destination, they just hysterically run, crashing everything on their way.
Re:Things Rust shipped without by istvan__ on Saturday July 04, 2015 @03:46AM (#9829574)
I said "sort of"...
Re:Things Rust shipped without by MaulingMonkey on Friday July 03, 2015 @08:52PM (#9828681)
> Raise your hand if you plan to stop using ncurses because of how opposed to how "harmful" goto statements are.

What if I just avoid contributing to the ncurses codebase? I've used plenty of useful tools with absolutely horrific codebases that I'd never want to touch in a million years. Not sure if ncurses is one of them.

The whole "it gets used, ergo it must be a good idea" argument doesn't hold much traction with me - even if I think using it when in C, to enforce single exit style, to work around the lack of RAII constructs, goto is the lesser evil.

I started with GOTO in BASIC. I used it a lot. It structured my initial reasoning about control flow. Despite this, in the past few years, I've used a naked goto maybe once or twice, and in all cases later rewrote it without the goto, which in my opinion increased it's readability. (I generally always have the option of C++ over C, and choose it, rendering single exit style 'useless'.)

> Oh, here's tmux, if you're interested (one of the most beautifully written C programs): https://github.com/tmux/tmux/search?utf8=%E2%9C%93&q=goto

Most of those are single exit style gotos. Those that aren't, do cause some concern, despite being "one of the most beautifully written C programs", even to their original author from the looks of it:

  if (errno == ENOMEM)
    goto retry; /* possible infinite loop? */
For what it's worth, it seems unlikely to be an infinite loop, short of encountering a bug in sysctl, or another process/thread constantly adding data. I had to google the header path to find an appropriate manpage (i.e. not _sysctl, not sysctl the program) to figure this out...

I've encountered worse edge cases before, however, and I'd really prefer my programs crash properly, instead of hanging when they do.

> State machines, for example, can make good use of gotos.

The performance complaints about an additional branch misprediction when using the "for(;;) switch(...)" style without gotos, is one of the few arguments that moves me, if only slightly. That seems like a case your standard optimizing compiler really should be able to handle, however. I'll assume they don't, as I'm too lazy to test if this is merely hearsay...

That said, I'll even use "goto case" in C# on occasion where I'd use case fallthrough in C++, if I'm feeling particularly lazy and don't want to turn things into proper method calls that can simply call each other just yet. I usually clean it up before I start to confuse myself.

It's not something I'd miss if it were gone, however. It's something I use only rarely, and only as a crutch to stave off cleanup. Not exactly a ringing endorsement.

EDIT: Code formatting, proper insertion of subject...

Re:Things Rust shipped without by sunfish on Friday July 03, 2015 @03:17PM (#9827437)
I wish C/C++ had a labeled break construct, like JavaScript, Java, Rust, and other languages have. It's surprisingly powerful, while still remaining structured. I personally have enjoyed learning about it, and about just how rarely an actual goto is really needed.
Re:Things Rust shipped without by api on Friday July 03, 2015 @03:21PM (#9827462)
I've never had to use 'goto' in C++ except to break from a nested loop. In C++ labeled breaks would make 'goto' completely obsolete.

In C it would still have use in the implementation of orderly error handling -- the pattern where you hand-implement exception handling in C by putting an on_error: label at the end of the function that is goto'd on error. The addition of some orderly construct for this in C would eliminate that case, leaving no real role for goto there either.

Re:Things Rust shipped without by frivoal on Friday July 03, 2015 @04:26PM (#9827749)
A bitecode interpreter is another place where it's nice to have gotos.

Here's the base code without gotos:

  typedef enum { ADD, MUL, ..., END } opcode;

  void run() {
    opcode ins;

    while (1) {
      ins = fetch_next_inst();
      switch (ins) {
        case ADD:
          perform_addition();
          break;
        case MUL:
          perform_multiplication();
          break;
        ...
        case END:
          wrap_up();
          return;
      }
    }
  }
You have 3 jumps on each loop. From the break to the end of the loop, then from the end to the top, and one from the switch to the right case. The first one might be optimized away, but let's remove it explicitly.

  typedef enum { ADD, MUL, ..., END } opcode;

  void run() {
    opcode ins;

    start:
    ins = fetch_next_inst();
    switch (ins) {
      case ADD:
        perform_addition();
        goto start;
      case MUL:
        perform_multiplication();
        goto start;
      ...
      case END:
        wrap_up();
        return;
    }
  }
Assuming a non lousy compiler, we haven't improved anything yet. But now the fun starts. We can go down to one jump for each iteration.

  typedef enum { ADD, MUL, ..., END } opcode;

  #define NEXT() \
  do { \
    ins = fetch_next_inst(); \
    goto *jump_table[ins]; \
  } while(0)

  void run() {
    opcode ins;
    static void *jump_table[] = { &&add_l, &&mul_l, ..., &&end_l };

    NEXT();
    add_l:
      perform_addition();
      NEXT();
    mul_l:
      perform_multiplication();
      NEXT();
    ...
    end_l:
      wrap_up();
      return;
  }
Voila! a single jump every time around. Now, depending on what kind of architecture you're running on, the size of the cache, etc, this may or may not be faster.

Granted, this is not the kind of code you write everyday. But sometimes speed matters, and good luck writing this without gotos.

Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @04:14AM (#9829613)
I really dislike 'clever' code like this, even when speed is paramount you will find that by obscuring the flow you make it harder, not easier to really optimize the code.

Over time it tends to evolve into ever messier and harder to understand versions of the initial run after which a future maintainer will end up losing sleep and or hair chasing some production bug.

Consider this (slower!) much clearer alternative, and consider too that if you need to eliminate one goto for speed reasons that you're most likely doing something wrong:

  typedef enum { ADD, MUL, ..., END } opcode;

  int process_instruction(opcode ins) {

      switch (ins) {
        case ADD:
          perform_addition();
          break;

        case MUL:
          perform_multiplication();
          break;
        ...
        case END:
          return FALSE;
      }

      return TRUE;
  }

  void run() {

    do {
    } while (process_instruction(fetch_next_instruction());

    wrap_up();
  }
That's a whole function call overhead (but you can eliminate that with an 'inline'), it's easier to test and much easier to follow what it does.

It would be interesting to see what the actual difference is in speed when comparing those two versions, I suspect that the contents of 'perform_addition' and 'perform_multiplication' are going to be the key here, not whether or not the loop uses a short-cut or an instruction (or two) less. Oh, and you could have eliminated that 'ins' variable.

Re:Things Rust shipped without by obastani on Saturday July 04, 2015 @08:41AM (#9829980)
I imagine that if you have more instructions (a few hundred) the overhead of the switch starts to become significant. At 256 opcodes you need 8 jumps, and hence 8 CPU cycles. That's non-trivial, especially if most of the opcodes can be implemented more quickly than this. For example, a quick Google search says that for an Intel CPU, addition is 1 cycle and multiplication is 3 cycles.
Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @09:22AM (#9830065)
Switches over enums are usually compiled to jump tables. What you see in source and what you get after the optimizer is done with it are sometimes very far apart. Looking at the output of gcc -S can be very enlightening at various levels of optimization.
Re:Things Rust shipped without by ectoplasm on Sunday July 05, 2015 @01:58AM (#9832633)
Since you asked, there's an assembly comparison on pages 5-6 of http://www.jilp.org/vol5/v5paper12.pdf and a performance comparison on page 12 of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.... . Note that the "inline threading" in the second paper is a further optimization that hasn't been brought up here yet.

In summary, the assembly of the goto version is much shorter and there's a 10% speedup over SPEC JVM98. The optimization works out because: a) instruction bodies are often short; b) instruction dispatch is the hottest code path of any interpreter; c) it's orthogonal to all or almost all other optimizations.

Re:Things Rust shipped without by jacquesm on Sunday July 05, 2015 @05:20AM (#9833008)
That's about what I expected, contrary to the 2-4x times speedup mentioned above. Still, I can imagine in isolated cases you really would get a better number than that 10%. So, for code where performance is super important and where the effort of the optimization and lack of transparency is outweighed by the performance boost this makes sense.
Re:Things Rust shipped without by ectoplasm on Sunday July 05, 2015 @05:12PM (#9835012)
Yes, that 10% is an average over seven benchmarks. The numerical one gets a 25% speedup, the one with a bunch of exceptions doesn't benefit at all. The funny thing is, if you're interested in performance, you're probably going to be writing a JIT, so this optimization is really just a stop-gap measure. In fact, the inline threading I mentioned is a kind of cheap JIT: it copies the in-memory executable code from the instructions at these goto labels to form basic blocks in an executable CFG. That gets you 1.6x speedup on those benchmarks, but it's a lot more work.
Re:Things Rust shipped without by jacquesm on Monday July 06, 2015 @06:12AM (#9837992)
> The funny thing is, if you're interested in performance, you're probably going to be writing a JIT, so this optimization is really just a stop-gap measure.

Exactly. And stop-gap measures are fine if and when they're followed up by a proper solution. Unfortunately stop-gap measures tend to be a lot more permanent than originally intended in practice.

Re:Things Rust shipped without by unholiness on Friday July 03, 2015 @10:47PM (#9828935)
Okay, but a much more readable and maintainable way to achieve this same optimization is with function pointers.

In your example:

  void (*[10])() function_table = {
      &perform_addition, 
      &perform_multiplication,
      ...
  }
  
  while(1) {
      ins = fetch_next_inst();
      *(function_table[ins])();  
  }
Edit: Seeing it written like this now, it's clear you could save yet another jump by defining a macro for what's in the while loop and putting it at the end of every function call.
Re:Things Rust shipped without by TheLoneWolfling on Friday July 03, 2015 @10:52PM (#9828955)
That's an additional pointer-chase per loop. And more function prefix / suffix work. In actuality, I suspect that it'd be optimized out - but you cannot say "you cannot do X because it relies on compiler optimizations" and replace that with Y that relies on compiler optimizations.
Re:Things Rust shipped without by unholiness on Saturday July 04, 2015 @09:45AM (#9830114)
A function call is nothing more than putting your return address and parameters on the stack and jumping to the address of the function. By referring directly to the function's address, there's no "additional pointer chase", since calling the function already does exactly that.

If you were to inline all of the perform functions in the GOTO version vs putting a macro at the end of each function, you're right that there's some function overhead, but I think it's as small as a single instruction to put the return address on the stack. Maybe that would be optimized away, maybe not.

To your point: My argument isn't that you can't do the GOTO version. With optimizations, it's essentially identical. My point is, that is a lot more hard-to-grok code to maintain for something that can be achieved in a simpler way.

Re:Things Rust shipped without by TheLoneWolfling on Saturday July 04, 2015 @06:32PM (#9831804)
You're forgetting the overhead of popping / pushing registers. Both in terms of direct instruction overhead, and indirectly through code size and working set bloat. Which, especially for smaller functions, can be significant. It's one of the problems with a register-oriented architecture.

Sometimes this can be optimized away, but not always.

Re:Things Rust shipped without by zem on Friday July 03, 2015 @04:56PM (#9827911)
~20 years of using various combinations of C and C++, and i never knew you could take the address of a label! reminds me of computed GOSUBs from my basic days :)
Re:Things Rust shipped without by banthar on Friday July 03, 2015 @05:06PM (#9827953)
Re:Things Rust shipped without by arcticbull on Friday July 03, 2015 @05:43PM (#9828111)
There is actually a neat feature where you can take the address of the thing you're assigning in a static context:

static void* address = &address;

This is helpful for things that take void* context pointers that you want to match with logical equality.

Re:Things Rust shipped without by frivoal on Friday July 03, 2015 @04:58PM (#9827919)
And they say C is a simple language... :)

To be fair, I've seen code like this exactly once.

Re:Things Rust shipped without by tjradcliffe on Friday July 03, 2015 @09:13PM (#9828738)
They say C is a low level language. That is not the same as simple.
Re:Things Rust shipped without by jcoffland on Friday July 03, 2015 @05:49PM (#9828131)
Who says that?
Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @04:16AM (#9829619)
Before you use such constructs make sure your team lead or boss is ok with it, it's incompatible with many compilers and ugly to boot. This is the kind of code that gives C its bad reputation.
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @06:46AM (#9829818)
This is the kind of code which makes OCaml the fastest bytecode interpreter out there, and selection between an ad hoc switch and a comuted goto is done transparently with a single ifdef.
Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @09:35AM (#9830096)
Yes, there may be exceptions when this kind of code is preferable. But it's definitely not the rule and the speed difference between the one and the other is so small that only a profiler can guide you to optimizations like these.
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @10:01AM (#9830159)
> Yes, there may be exceptions when this kind of code is preferable.

In my practice these exceptions are ubiquitous. Multiple tiny interpreted DSLs (which cannot be compiled more efficiently for the latency reasons), efficient protocols, all that stuff. System programming, in other words, and it's exactly the stuff Rust was supposed to be designed for.

> But it's definitely not the rule and the speed difference between the one and the other is so small

2-4 times difference is not "small" in system-level programming.

Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @10:41AM (#9830283)
2-4 times is a spectacular speed-up, of course the inner loop of an interpreter is important but you're implying the rest of the code-path is only 3-4 instructions long (otherwise you can't get that kind of speed-up) which I find hard to believe. Even the inner loop of an interpreter usually calls routines that are longer than the inner loop itself. Is there a particular benchmark you have in mind for that 2-4 number?
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @02:25PM (#9831064)
Take a look at the OCaml bytecode interpreter: case bodies are all very small there, so the instruction dispatch time really counts. I got this 2x times difference when comparing this bytecode interpreter built with and without computed goto, but I don't remember any other details at the moment. In my own bytecode interpreters the difference was up to 4x, again, because each bytecode instruction implementation was tiny and trivial (like, move something from one register to another, or perform an arithmetic operation).

> Even the inner loop of an interpreter usually calls routines

These are too high level interpreters for the too dynamic languages, they're beyond any hope in terms of performance, by design. I'm talking about some simpler and better designed things (like OCaml, for example).

Re:Things Rust shipped without by sklogic on Friday July 03, 2015 @06:56PM (#9828356)
There is one next step - eliminate jump_table and rewrite your bytecode before executing it, replacing opcodes with the jump addresses.
Re:Things Rust shipped without by api on Friday July 03, 2015 @04:31PM (#9827780)
That's pretty nifty, but it seems like something a really good compiler could achieve automatically. Of course I'm not sure if any compilers actually are that good.
Re:Things Rust shipped without by sklogic on Friday July 03, 2015 @06:55PM (#9828352)
This is not exactly how fast bytecode interpreters are implemented. There is one next step - pre-caching the jump table straight into the bytecode. And there is absolutely no way compiler can transform your ad hoc switch-based interpreter into a threaded code interpreter automatically - it is not allowed to rewrite your data willy-nilly.
Re:Things Rust shipped without by frivoal on Saturday July 04, 2015 @04:42PM (#9831542)
Hadn't thought of that, but it sounds interesting. I guess this means that opcodes in your bytecode need to be large enough to store a pointer, this could involve some tradeoffs in terms of minimizing instructions vs fitting in the cache, but I suppose it could fall on the right side of things often enough.
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @04:53PM (#9831593)
32-bit opcodes are ok, even on 64-bit architectures, if you add a constant offset - see how it's done in OCaml.
Re:Things Rust shipped without by frivoal on Saturday July 04, 2015 @05:59PM (#9831730)
An offset from the first label, or some nearby alignment point? Makes sense.

Do you have a pointer to the relevant part of OCaml's source? The whole thing is probably worth a read, but don't think I can set aside enough time for that soon, and it could take me a while to find the right part.

Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @06:10PM (#9831762)
Re:Things Rust shipped without by frivoal on Sunday July 05, 2015 @03:06AM (#9832787)
Nice. Simple and efficient. I am going to read more from that code base. Looks like this might be a nice read as well: https://ocaml.org/docs/papers.html#BytecodeCompilerandByteco...
Re:Things Rust shipped without by Redoubts on Friday July 03, 2015 @06:47PM (#9828330)
Well, this is what is going into Python 2.7.11 for a 15% speed up, so apparently compilers aren't that good yet.

https://lwn.net/Articles/646888/

Re:Things Rust shipped without by frivoal on Friday July 03, 2015 @04:38PM (#9827822)
This is a fairly mechanical conversion, so suppose a sufficiently smart compiler could do that.

But assuming a sufficiently smart compiler when you depend on your code being fast tends to cause issues. Especially if you expect it to run on a bunch of platforms with compilers of varying qualities. Last time I saw code last this, we certainly couldn't rely on compilers being particularly smart, and we did care about speed.

Re:Things Rust shipped without by jasode on Friday July 03, 2015 @03:51PM (#9827594)
>In C++ labeled breaks would make 'goto' completely obsolete.

In 20 years of using C/C++, I've found one use for "goto" that's hard to substitute: simulating coroutines that yield to an outer context. (Similar to C# yield return).

A "break label" gets you out of a loop. I needed to use "goto" to jump back into the middle of a loop to resume where the "coroutine" previously left off. The keywords "break/setjmp/longjmp" wouldn't have been substitutes for this particular use case.

Re:Things Rust shipped without by prutschman on Friday July 03, 2015 @04:22PM (#9827732)
I've used a switch statement essentially as a jump table for this purpose. I'm curious whether that would have worked, or if you were doing something different enough that you needed a goto.
Re:Things Rust shipped without by IsTom on Friday July 03, 2015 @06:54PM (#9828346)
I don't quite understand how it's not a setjmp/longjmp usecase. Isn't this exactly what longjmp is for?
Re:Things Rust shipped without by Niten on Friday July 03, 2015 @06:05PM (#9828186)
> The addition of some orderly construct for this in C would eliminate that case, leaving no real role for goto there either.

I like the way this is handled in Go with the defer keyword: https://blog.golang.org/defer-panic-and-recover

This construct gives you most of the power of C++ RAII without the overhead. Except that you can't use it to cleanup resources after exiting an anonymous block—it strictly defers to function exit.

Re:Things Rust shipped without by danieldk on Saturday July 04, 2015 @02:48AM (#9829477)
This construct gives you most of the power of C++ RAII without the overhead.

But it leaves out the most useful part: in C++ releasing the resources is completely implicit:

    {
        std::ifstream in(fn);
        // Do something with 'in'
    } // Released
while with Go defer, you have to call explicitly for the method that you want to call. If you forget this, you still have a resource leak.

Sure, it's an improvement over languages where you have to cover every possible scope exit, but it definitely doesn't give you 'most of the power' of C++ RAII.

Re:Things Rust shipped without by pcwalton on Friday July 03, 2015 @06:50PM (#9828339)
defer has unavoidable runtime overhead due to its dynamic semantics. It's strictly slower than RAII as implemented in C++ or Rust.
Re:Things Rust shipped without by giovannibajo1 on Friday July 03, 2015 @07:39PM (#9828492)
That's not true. The only case where the runtime overhead is unavoidable is calling defer in a loop, because it might require allocating the defer chain in the heap; in all other cases, it's just a metter of writing the correct optimization passes in the compiler.
Re:Things Rust shipped without by pcwalton on Friday July 03, 2015 @08:44PM (#9828663)
Yes, that's what I meant by "strictly slower". At best, it can be optimized to something similar to what RAII can give you. RAII never has the overhead of the bad case.
Re:Things Rust shipped without by giovannibajo1 on Friday July 03, 2015 @08:56PM (#9828693)
I don't want to be excessively picky, but you said that is has "unavoidable runtime overhead", and that's true only in its rarest form (defer within a loop), which is a feature which you can't implement in RAII. IOW, defer is a superset of RAII.

In all other cases (which is almost all usages), it is semantically equivalent to RAII, so the language doesn't force any runtime overhead. The only difference is that the compiler is less mature than an average C++ compiler, but this is an implementation problem, not a design problem.

RAII has no overhead because it is a pattern designed within the context of a zero-overhead language. defer allows you to implement a superset of cases that RAII handles, including those with runtime overhead.

Re:Things Rust shipped without by pcwalton on Friday July 03, 2015 @10:29PM (#9828888)
defer isn't a superset of RAII. defer is function-scoped. RAII is block-scoped. If you want to run code at the end of a block, you can do that with RAII and you can't do that with defer—and note that this is what causes all the codegen issues with defer.
Re:Things Rust shipped without by Niten on Friday July 03, 2015 @08:46PM (#9828670)
To clarify, I meant the "overhead" of defining and instantiating a container class for RAII purposes.

I hadn't considered the type of overhead you're talking about, which is admittedly more important for the kind of software that tends to get written in C.

Re:Things Rust shipped without by pcwalton on Friday July 03, 2015 @08:55PM (#9828691)
There was such a thing (std::finally), but it was removed due to lack of use and maintenance. When your standard library is completely built on RAII, you rarely need it.
Re:Things Rust shipped without by Animats on Friday July 03, 2015 @03:53PM (#9827598)
I don't think I've written a goto since the 1970s, and I've written a lot of code since then. If you need to bail out of something in the middle, make it a function.
Re:Things Rust shipped without by bluecalm on Friday July 03, 2015 @04:52PM (#9827897)
As mentioned above, in C goto is often useful for error handling (where you need to free some resources before exiting the function). It's way more convenient and readable to write freeing code once and jump to it instead of having multiple return exits and duplicate the code before every single one of them.
Re:Things Rust shipped without by derf_ on Friday July 03, 2015 @05:31PM (#9828068)
What the parent said still applies in your case. You just make a wrapper function that does the cleanup. I have used this pattern many times:

  static int foo_impl(int arg, int **resource1, int **resource2) {
    *resource1 = (int *)malloc(sizeof(**resource1));
    if (*resource1 == NULL) return EXIT_FAILURE;
    /* Do something with resource1 (omitted)... */
    *resource2 = (int *)malloc(sizeof(**resource2));
    if (*resource2 == NULL) return EXIT_FAILURE;
    /* Do something with resource1 and resource2 (e.g.,
       stick them in a global hash table as key/value pairs,
       or whatever, omitted)... */
    return EXIT_SUCCESS;
  }

  int foo(int arg) {
    int *resource1;
    int *resource2;
    int ret;
    resource1 = resource2 = NULL;
    ret = foo_impl(arg, &resource1, &resource2);
    if (ret != EXIT_SUCCESS) {
      free(resource2);
      free(resource1);
    }
    return ret;
  }
The advantages are that it makes it very explicit which resources need to be cleaned up (making it easier to review to be sure you haven't forgotten one, or forgotten to initialize one, because they're in a nice list), and it's harder to screw up the control flow. You can't get out of the function without passing by the clean-up code, and you can't accidentally fall into the clean-up code without explicitly returning an error.
Re:Things Rust shipped without by luso_brazilian on Friday July 03, 2015 @05:50PM (#9828133)
I know it is just an example to illustrate the point but this seems to have a bug in it: resource2 won't be initialized if the function fail to allocate resource1 so resource2 will be null when the code enters the deallocation condition.

A way to fix it would be to return different failures for every allocation and to use a switch without a break to clean up, something like:

    switch (ret) {
      case EXIT_SUCCESS:
        free(resource2);
      case EXIT_FAILURE2: 
        free(resource1);
      case EXIT_FAILURE1:
        break;
    }
EDIT: added potential fix to the code. Sorry if there is any bug in the fix, my C is a little bit ... rusty.

EDIT2: fixed a bug in the fix. C is hard, let's go shopping.

EDIT3: the explanation for the bug was also wrong. It is not a memory leak for but freeing a null pointer. Fixed too.

Re:Things Rust shipped without by protopete on Friday July 03, 2015 @07:34PM (#9828479)
Passing a null pointer to free() is perfectly safe, and in this case simplifies the cleanup code.

Although the concern of a memory leak is valid. I would have expected the resources to be free'd regardless of the result.

Re:Things Rust shipped without by luso_brazilian on Friday July 03, 2015 @07:59PM (#9828550)
Of course, you are right. I seem to have carried the belief that freeing a null pointer was as bad as freeing one twice. And now I know.

Seems to be a common misconception [1], thanks for pointing out, that makes the GGP code correct in all counts and my switch redundant.

[1] https://news.ycombinator.com/item?id=8844031

Re:Things Rust shipped without by malka on Friday July 03, 2015 @09:28PM (#9828774)
Or you could simply free resource1 and resource2 even if the allocation failed. free(NULL) is defined to do nothing.
Re:Things Rust shipped without by TheLoneWolfling on Friday July 03, 2015 @09:23PM (#9828764)
Except of course that many languages seem to be trying to remove fallthroughs from switches too...
Re:Things Rust shipped without by Gibbon1 on Saturday July 04, 2015 @02:26AM (#9829441)
I find myself often having the issue where the code digging through what can and often is, garbage. At some point you find it's pointless to continue. You are done. Fin. Goto error; in that case makes absolutely perfect sense.

Two things about goto and jmp instructions. Most people have no idea how badly they were abused back in old days. For instance to jump into the middle of a subroutine. Yay just saved 9!!! words of core memory!!! And most people forget that old computer scientists were obsessed with creating grammars that you could write formal proofs for.

Re:Things Rust shipped without by contravariant on Friday July 03, 2015 @09:37PM (#9828793)
I'm pretty sure Dijkstra would also have been against using 'return' instead of a goto.
Re:Things Rust shipped without by justincormack on Friday July 03, 2015 @03:21PM (#9827471)
Lua introduced goto in a recent release, to some surprise, but it is useful especially for code geneation and interpreters.
Re:Things Rust shipped without by CyberDildonics on Friday July 03, 2015 @03:08PM (#9827383)
I've used goto in very specific cases which basically boils down to breaking from inner loops to the outside of the outer loop. Thankfully Rust actually has labeled break and continue statements, so this case of using goto is taken care of.
Re:Things Rust shipped without by kazinator on Friday July 03, 2015 @05:47PM (#9828122)
> Since then, I have always thought languages should have a "goto" statement that human-written code is not allowed to use.

It's an interesting idea.

The problem I see is that users can get around it by wrapping goto in the simplest possible macro. Then the idea has backfired: we now have goto under as many names as there are goto-using programmers. :)

Re:Things Rust shipped without by vezzy-fnord on Friday July 03, 2015 @02:54PM (#9827294)
All control flow is ultimately derived from goto (or JMP).
Re:Things Rust shipped without by pjmlp on Saturday July 04, 2015 @08:52AM (#9830004)
I only used goto in ZX Spectrum Basic, GW Basic and several Assembly flavours.

All its use cases are better served by other language constructs.

Then again, C is a portable macro assembler.