4 ms·

We'll just have to put Rust up against MLton and see if tail calls really are so expensive.

larsberg 14y ago
If I understand it correctly, the Rust issue is that tail calls are expensive in the context of LLVM and the calling convention that they are using. MLton (like Manticore, which I work on) uses a different code generation backend and calling convention entirely. And neither of us worry about "destructors" or, in general, things that happen at every return point. Though, interestingly, in the context of a CPS-converted program, destructors would just be the next continuation called on the way to calling the procedure previously "returned to." Under our (Manticore) calling convention, we would just jump to each of those continuations and wouldn't have to grow stack (though in our case, it's keeping around heap frames, as we're not stack-based), and would have the same next allocation and instruction-level behavior as a tail call. That said, if you think tail calls are hard to debug, CPS-converted programs would destroy most people's will to live. No stack backtraces, except in debug modes, with 5-10x performance penalties.
- Rickasaurus 14y ago
  I never thought tail calls were hard to debug, but can you can keep text offsets to the original tokens through the CPS transform? Usually with typed languages that's enough information to figure out what went wrong or at least what to log. Also, I'm not sure why the entire library needs the same calling convention when it's such bad form to expose all of your functions anyway.
  - larsberg 14y ago
    You can keep the original tokens. The challenge with debugging such programs is really the integration with the rest of the optimizations. CPS transformation turns your program into a ton of tiny functions. Then, any reasonable optimizer will do a huge amount of inlining. Attempting to do trace-based debugging bounces you from one subexpression in one function to another and so forth. Especially when you consider that Manticore (like MLton) is a whole-program optimizing compiler, you also get little chunks of library functions we've duplicated like map, foldr, etc. Worse, we liberally remove dead code, including unused arguments, branches of conditionals we can guarantee are never called, etc. And since it's a research compiler, there isn't really a "-O0". You can turn off individual optimization passes, but guessing what combination lead to something getting inlined or not requires some careful study. As to why they've chosen what they have with LLVM, I don't know enough to judge. Doing something like ML compilers do with a custom calling convention internally and then a C convention externally is pretty expensive, and ends up putting a massive penalty on C calls (oh, you want to call C? let me move the GC pointer out of the way, set up a fake stack frame for you, etc.). Further, doing it makes register allocation more of a challenge. Many ML compilers like to "pin" certain registers with their own values (e.g., the GC local heap limit pointer) so that we can write custom little blobs of assembly that get emitted in the right places without worrying about substituting in what the _real_ heap limit pointer is, etc. That pinning interacts badly with LLVM, as you can see from the Haskell/LLVM master's paper - they basically had to give up on it and just add their pinned values as extra arguments and then stop emitting code that relied on it being in a sane, typical place. Hope that helps! I've been thinking about these problems and talking only with other people who do the same for so many years I'm starting to forget which parts are and aren't obvious (or even published/documented).
    - Rickasaurus 14y ago
      Very helpful, thank you! I guess another problem would be that people often complain about how slow these kinds of compilers can be, and if you keep around enough to reconstruct good error messages it would probably make it that much slower.
      - larsberg 14y ago
        Most of the time in whole-program compilers such at Manticore and MLton (> 60%, though it depends on the particular program) is spent in the combination of parsing the input source files and running GCC over the generated assembly to produce the binary. Many compilers (including ours) did not keep around that extra information because even in 2007 (when we started) RAM was a bit scarce. The cost associated with keeping that info around between phases is primarily in the extra working set hit and the resulting GC and especially memory paging issues. Given that it's not unreasonable to expect people to have > 1GB of available physical RAM for the compilation process these days, that's something we should consider changing. Though at this point threading that info through the compiler is probably a couple weeks of dedicated effort to get working correctly.
- cwzwarich 14y ago
  If you don't have any interesting control operators like call/cc, prompt/control, etc. then it should be possible to track stack-like control patterns after CPS conversion through the compiler and through DWARF (or a custom debugging format). Unless I am missing something it seems that the control operators are the problem, not CPS.
  - larsberg 14y ago
    Certainly, that's true! As I mentioned in my other far-too-wordy response, though, if you just CPS convert and run a program, it will be far too slow (5x the funcalls != 5x the fun...). So, it's the combination of CPS conversion and later optimizations --- paired with whole-program compilation --- that make it so hard to debug.
- burntsushi 14y ago
  > (like Manticore, which I work on) Nice! I have had envious eyes for Manticore as a modern replacement for Concurrent ML. Are you guys intending for it to be available for general use or more of a research language?
  - larsberg 14y ago
    It's still a research language today. Honestly, we would need to make a fairly major push --- which would freeze all resarch work and publications --- to get to a point where it is ready for general use. We're working on some grant proposals along those lines, because frankly without NSF support (in the context of making it ready for wider use in classes such as CMU's new intro curriculum), it's unlikely we can justify the massive amount of work required to take it from something that PL experts to use to something that, say, MLton or SML/NJ users could pick up and use. I hate to sound mercenary, but frankly if we can't significantly increase the project from the current number of developers (myself and two part-time undergrads), it's difficult to see how we can make it more generally available. Especially when I lose a couple of months of work every time we double the number of processors in a server-class machine, as there's always either a GC bug or some scalability issue still lurking in the runtime...

If I understand it correctly, the Rust issue is that tail calls are expensive in the context of LLVM and the calling convention that they are using. MLton (like Manticore, which I work on) uses a different code generation backend and calling convention entirely. And neither of us worry about "destructors" or, in general, things that happen at every return point. Though, interestingly, in the context of a CPS-converted program, destructors would just be the next continuation called on the way to calling the procedure previously "returned to." Under our (Manticore) calling convention, we would just jump to each of those continuations and wouldn't have to grow stack (though in our case, it's keeping around heap frames, as we're not stack-based), and would have the same next allocation and instruction-level behavior as a tail call. That said, if you think tail calls are hard to debug, CPS-converted programs would destroy most people's will to live. No stack backtraces, except in debug modes, with 5-10x performance penalties.

Rickasaurus 14y ago
I never thought tail calls were hard to debug, but can you can keep text offsets to the original tokens through the CPS transform? Usually with typed languages that's enough information to figure out what went wrong or at least what to log. Also, I'm not sure why the entire library needs the same calling convention when it's such bad form to expose all of your functions anyway.
- larsberg 14y ago
  You can keep the original tokens. The challenge with debugging such programs is really the integration with the rest of the optimizations. CPS transformation turns your program into a ton of tiny functions. Then, any reasonable optimizer will do a huge amount of inlining. Attempting to do trace-based debugging bounces you from one subexpression in one function to another and so forth. Especially when you consider that Manticore (like MLton) is a whole-program optimizing compiler, you also get little chunks of library functions we've duplicated like map, foldr, etc. Worse, we liberally remove dead code, including unused arguments, branches of conditionals we can guarantee are never called, etc. And since it's a research compiler, there isn't really a "-O0". You can turn off individual optimization passes, but guessing what combination lead to something getting inlined or not requires some careful study. As to why they've chosen what they have with LLVM, I don't know enough to judge. Doing something like ML compilers do with a custom calling convention internally and then a C convention externally is pretty expensive, and ends up putting a massive penalty on C calls (oh, you want to call C? let me move the GC pointer out of the way, set up a fake stack frame for you, etc.). Further, doing it makes register allocation more of a challenge. Many ML compilers like to "pin" certain registers with their own values (e.g., the GC local heap limit pointer) so that we can write custom little blobs of assembly that get emitted in the right places without worrying about substituting in what the _real_ heap limit pointer is, etc. That pinning interacts badly with LLVM, as you can see from the Haskell/LLVM master's paper - they basically had to give up on it and just add their pinned values as extra arguments and then stop emitting code that relied on it being in a sane, typical place. Hope that helps! I've been thinking about these problems and talking only with other people who do the same for so many years I'm starting to forget which parts are and aren't obvious (or even published/documented).
  - Rickasaurus 14y ago
    Very helpful, thank you! I guess another problem would be that people often complain about how slow these kinds of compilers can be, and if you keep around enough to reconstruct good error messages it would probably make it that much slower.
    - larsberg 14y ago
      Most of the time in whole-program compilers such at Manticore and MLton (> 60%, though it depends on the particular program) is spent in the combination of parsing the input source files and running GCC over the generated assembly to produce the binary. Many compilers (including ours) did not keep around that extra information because even in 2007 (when we started) RAM was a bit scarce. The cost associated with keeping that info around between phases is primarily in the extra working set hit and the resulting GC and especially memory paging issues. Given that it's not unreasonable to expect people to have > 1GB of available physical RAM for the compilation process these days, that's something we should consider changing. Though at this point threading that info through the compiler is probably a couple weeks of dedicated effort to get working correctly.
cwzwarich 14y ago
If you don't have any interesting control operators like call/cc, prompt/control, etc. then it should be possible to track stack-like control patterns after CPS conversion through the compiler and through DWARF (or a custom debugging format). Unless I am missing something it seems that the control operators are the problem, not CPS.
- larsberg 14y ago
  Certainly, that's true! As I mentioned in my other far-too-wordy response, though, if you just CPS convert and run a program, it will be far too slow (5x the funcalls != 5x the fun...). So, it's the combination of CPS conversion and later optimizations --- paired with whole-program compilation --- that make it so hard to debug.
burntsushi 14y ago
> (like Manticore, which I work on) Nice! I have had envious eyes for Manticore as a modern replacement for Concurrent ML. Are you guys intending for it to be available for general use or more of a research language?
- larsberg 14y ago
  It's still a research language today. Honestly, we would need to make a fairly major push --- which would freeze all resarch work and publications --- to get to a point where it is ready for general use. We're working on some grant proposals along those lines, because frankly without NSF support (in the context of making it ready for wider use in classes such as CMU's new intro curriculum), it's unlikely we can justify the massive amount of work required to take it from something that PL experts to use to something that, say, MLton or SML/NJ users could pick up and use. I hate to sound mercenary, but frankly if we can't significantly increase the project from the current number of developers (myself and two part-time undergrads), it's difficult to see how we can make it more generally available. Especially when I lose a couple of months of work every time we double the number of processors in a server-class machine, as there's always either a GC bug or some scalability issue still lurking in the runtime...