28 ms·

How to speed up the Rust compiler

185 points by nnethercote 10y ago

acqq 10y ago
As far as I know, the Rust compiler is written in Rust? That should mean that if the features of the language are used, a lot of "small" allocations shouldn't happen at all, instead, the language is supposed to allow that the short lived variables (and objects) exist only on the stack, costing effectively nothing to allocate them? Moreover, the compilers in general have an advantage to know that most of the objects are needed only during specific times, allowing optimized allocation and bundled deallocation. I see "a lot" of "arena" allocators are mentioned, so it seems there is something like that, just maybe too fine grained? In short, there's no need for the Rust compiler to have any measurable overhead due to the allocations. Then only the changes in the compiling algorithms and the underlying data structures (how often is what traversed and why, is something kept or recalculated, sometimes it's even more expensive to produce too much data to be kept in memory, and sometimes the data structures aren't optimal for the most of the uses) should have the potential of changing the compilation speed.
- Chirono 10y ago
  Don't know why you are being down voted. Even if you are incorrect, it would be interesting to hear why. Anyone care to comment?
  - __s 10y ago
    Compilers spend a lot of time with hashtables, which exist on the heap. Rust isn't some magical language that makes the heap some unnecessary entity. One still has objects whose lifetime do not fit the stack model or whose size is dynamic Their comment went on to claim that given their hypothesis, allocation optimization shouldn't be impactful. Yet this post demonstrates otherwise, perhaps showing that therefore their hypothesis is false (if a then b, b is false, therefore a is false) One of the post's optimizations was to use Cow<str> over String tho, which is an example of reducing allocations with borrows Additionally it's oft mentioned that a weak point in Rust's compile time is LLVM. This has to do with various things, some of which are Rust's fault (it could generate less IR), but it points out that there's a lot of time being spent in C++ code. LLVM's great, but it's guidelines essentially suggest 'if you want to make llvm play nice, generate IR like clang'
    - acqq 10y ago
      > Their comment went on to claim that given their hypothesis, allocation optimization shouldn't be impactful. And what was the hypothesis? That the code for the compiler itself should use the features imagined to be used by the language, just like your example: > One of the post's optimizations was to use Cow<str> over String Then: > allocation optimization shouldn't be impactful. Yet this post demonstrates otherwise "not impactful": It looks to me like that: 36.526s vs 32.373s for the longest compile tested. It is measurable, but not something that I as the programmer will be able to notice. My definition of impactful for the compilation times is "at least a factor of 2" not 1.1. And the claim is, once the language possibilities are actually used. If the code is written differently, of course not much is expected. The result of a moderate speedup exactly shows that the language possibilities weren't always used in a way to minimize allocations, but the difference is still not, for my perception, significant (10% is hard to recognize unless measured or the actual compilations last hours and not seconds). But I still claim that much bigger potential gains are the actual changes in the algorithms and the data structures. The data structures especially can hugely change the result if they are made to be really cache friendly, and together with the changes in algorithms such modifications have the potential to make an order of magnitude speedups, if they are actually possible.
  - valarauca1 10y ago
    Because the parent poster's thesis >>Moreover, the compilers in general have an advantage to know that most of the objects are needed only during specific times, allowing optimized allocation and bundled deallocation Is flawed. Compiler can know this. Most the time they don't. In Turing complete languages you can't reason about how much space/time a program will need to run. When you do know that and object, or objects will be determanstically allocated/de-allocated together. Then you need to know how large they'll grow too over their their lifetimes. Which again may hit a Turing Tarpit, and you lose this ability. Here is an incredibly simple example fn read_file(path: &str) -> String; fn get_tokens<'a>(s: &'a str, r: &Regex) -> HashMap<&'a str, &'str> fn main() { let my_regex = //something let file_data = read_file(&arg[1]); let tokens = get_tokens( &file_data, &my_regex); } On can see the String that will contain the file's data, and Hashmap can be allocated together. But one cannot reason about how large either will be head of time to pre-size these on the heap. Lastly, address randomization is a good thing. Knowing ahead of time which allocations will determanstically be in relation to each other is a security vulnerability.
    - acqq 10y ago
      My claim about "the compilers in general have an advantage to know that most of the objects are needed only during specific times" is directed to the construction of the compiler, like the Rust compiler written in Rust, not that there's any magic. That means, the writer of the compiler can write the compiler knowing much more about the lifetime of the objects used in the compilation than most of the software. When you write a server, you don't know who much which pieces of the database should be in the memory. When you write a compiler, you know that everything goes away after the compilation is done. It allows extremely speedy compilers (considering the number of their malloc calls), which seldom allocate memory blocks and seldom deallocate. That means that even for the stuff that you allocate "on the heap" you don't have to allocate objects one-by-one, but allocate big chunks of memory and then just deliver the small pieces of it as the memory for "objects." The same way, for the deallocation, instead of deallocation many small objects, you can deallocate a lot at once. I've personally made the compiler that made only a few malloc calls for the whole compilation process, even if it internally "created" tens of thousand of "objects." I've done it in C, and Rust is made to allow the speed of C with the higher safety, so the equivalent strategies should be possible. The mention of "arenas" suggests to me that the writers actually think in that direction.
  - Zarathustra30 10y ago
    > ...if the features of the language are used... The Rust compiler uses Rust's features terribly, just because Rust's features were a moving target for the majority of the compiler's lifetime.
keyle 10y ago
I've never used rust but seeing it's so oriented towards correctness and type checking, I'm not surprised it's a little slow to compile! From someone stuck with dynamic languages, mark my words, it's best for your compiler to be a bit slow, than your brain being the compiler! :-)
- vintagedave 10y ago
  Why? You can have both fast compilers and safe languages. Take Delphi for example: statically typed, strong type correctness, you have to work to avoid type safety. Compiles a million lines of code in 4 seconds (including linking.) * https://www.youtube.com/watch?v=Yq2mNUzcpE0 https://www.youtube.com/watch?v=Yq2mNUzcpE0 (1 million lines, 4 seconds) * https://www.youtube.com/watch?v=kvuxeaMDmMc https://www.youtube.com/watch?v=kvuxeaMDmMc (277,000 lines of much more complex code (the most complex, compiler-stressing library Delphi has) in 16 seconds counting linking.
  - adrianN 10y ago
    I think the correctness guarantees that Rust provides are a little stronger than what Delphi provides.
    - bryanlarsen 10y ago
      Perhaps more significantly, the checking that Delphi provides is both explicit and local. Rust does a lot more inferential checks and at the crate level rather than at the line level.
      - Rusky 10y ago
        Rust's inference and checks are actively limited to function level, not crate level- function types are not inferred, generics are type-checked before instantiation, the borrow checker works on individual functions, etc.
  - krylon 10y ago
    At work, I am stuck doin maintenance on an in-house application our accounting department uses, which is written in Delphi. It's small (~10k lines of code), but it compiles so fast I sometimes wonder if I clicked the wrong button / hit the wrong key.
pjmlp 10y ago
In conclusion, allocating memory is expensive, regardless how it is done. :)
- kzrdude 10y ago
  The allocation fixes are scratching on the surface of the compiler. It must be something more fundamental underlying the long compilation time.
  - Manishearth 10y ago
    One of the main slow bits is just LLVM. Rust produces LLVM IR which LLVM takes a long time to optimize. Since MIR has landed, IIRC work on doing MIR optimizations and LLVM IR simplifications is the next step here.
    - kzrdude 10y ago
      Rustc is of course responsible for what it's feeding llvm, and being smarter about that sounds exciting.
  - gribbly 10y ago
    Not sure how much is due to this, but LLVM has gotten much slower in recent releases, probably due to improved optimizations. I would not be surprised if down the line, the Rust devs decided to write their own Rust backend rather than relying on LLVM.
    - qznc 10y ago
      At least for development a custom fast backend would be great. For production code you still want all the optimizations you can get, which means LLVM.
    - wyldfire 10y ago
      Writing different backends for each supported target would either be taking on a lot of work or shedding some targets.
nickpsecurity 10y ago
I still think they should investigate doing the LISP solution to the problem where you combine several options: 1. Interpreter (eg REPL) that executes it instantly with dynamic checks for rapid prototyping of logic. 2. Fast, non-optimizing compile that at least does the safety checks. 3. Fully-optimizing compile that can be done in background or overnight while programmer works on other things like tests or documentation. 4. Incremental, per-function version of 2 or 3 for added boost. Rust is already adding something like that. This combo maximizes mental flow of programmer, lets them tinker around with algorithms, quickly produces executables for test deployments, and will often do full compiles without interrupting flow with wait times. It's the workflow available in a good LISP. It doesn't have to be exclusive to LISP. Other languages should copy it. I'll go further to say they should even design the language and compiler to make it easy to pull that off.
- qwertyuiop924 10y ago
  In CLs, anyways. In Schemes, we usually only have 1 and 3. Maybe 2 and four, but only sometimes.
  - nickpsecurity 10y ago
    The Scheme I was thinking of using to re-learn LISP and Scheme was Racket. Its environment + How to Design Programs looked like a strong combo. Do you know how it fares on this list?
    - dleslie 10y ago
      FWIW, Racket explicitly dropped Scheme from its branding because the language designers disagreed with the direction of Scheme and wanted to go their own way; and they have, to a great extent. Racket has scheme in its syntax, but as does C++ has C.
      - nickpsecurity 10y ago
        Ahh. So probably best to think of it as its own, Scheme-like language.
eridius 10y ago
> malloc and free are still the two hottest functions in most benchmarks. Avoiding heap allocations can be a win. This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. But it does not mean that you should try to reduce calls to that function elsewhere (unless you can cut out a lot in one go). As a trivial example, if you have a super-fast function that cannot be optimized any further, but it's called millions of times, that function may appear hot, but any individual invocation of the function might be taking just a few microseconds. Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good. I guess another way of saying this is, if you're trying to optimize a hot function by reducing the number of times it's called, you need to reduce it by a significant percentage of the total calls rather than reducing it by a specific number of times. No matter how many times it's called, if you reduce the number of calls by 50%, the overall time taken by the function drops by 50%. But if you reduce the number of calls by 50, then whether that's meaningful or not depends entirely on how long each individual call to the function takes. Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why.
- MaulingMonkey 10y ago
  > Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why. Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite. > This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. This is just as much of a "non-sequitur" - maybe you can optimize that function further, but if it's reached the point of diminishing returns it may not be worth it even if it's technically possible. In-context, there has already been a lot of optimization work put into malloc and free, lots of low hanging fruit is gone. Further, malloc and free are very generic allocation strategies that generally do a lot of work to try and handle many different cases with OK efficiency. I challenge you to make them as fast as, say, stack allocation - go ahead, I'll wait. Sure, you can't replace all use of a heap with a stack, but most programs I've seen have at least some cases where you could. And there is actually a way to make malloc and free as fast as a stack - turn your malloc implementation into a pointer increment, and free into a noop. Not appropriate for all tools, but a short lived compiler pass might be able to get away with it! Although it'd possibly cause problems for large 32-bit builds. Regardless - this is also technically no longer a heap. As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO. > Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good. An important note here: Cutting the number of calls in half could, in theory, involve eliminating one call site (because e.g. the calling code itself is very hot) although this probably isn't the case in the Rust codebase or it'd have been optimized already. Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site.

185 points by nnethercote 10y ago

acqq 10y ago

As far as I know, the Rust compiler is written in Rust? That should mean that if the features of the language are used, a lot of "small" allocations shouldn't happen at all, instead, the language is supposed to allow that the short lived variables (and objects) exist only on the stack, costing effectively nothing to allocate them? Moreover, the compilers in general have an advantage to know that most of the objects are needed only during specific times, allowing optimized allocation and bundled deallocation. I see "a lot" of "arena" allocators are mentioned, so it seems there is something like that, just maybe too fine grained? In short, there's no need for the Rust compiler to have any measurable overhead due to the allocations. Then only the changes in the compiling algorithms and the underlying data structures (how often is what traversed and why, is something kept or recalculated, sometimes it's even more expensive to produce too much data to be kept in memory, and sometimes the data structures aren't optimal for the most of the uses) should have the potential of changing the compilation speed.

Chirono 10y ago
Don't know why you are being down voted. Even if you are incorrect, it would be interesting to hear why. Anyone care to comment?
- __s 10y ago
  Compilers spend a lot of time with hashtables, which exist on the heap. Rust isn't some magical language that makes the heap some unnecessary entity. One still has objects whose lifetime do not fit the stack model or whose size is dynamic Their comment went on to claim that given their hypothesis, allocation optimization shouldn't be impactful. Yet this post demonstrates otherwise, perhaps showing that therefore their hypothesis is false (if a then b, b is false, therefore a is false) One of the post's optimizations was to use Cow<str> over String tho, which is an example of reducing allocations with borrows Additionally it's oft mentioned that a weak point in Rust's compile time is LLVM. This has to do with various things, some of which are Rust's fault (it could generate less IR), but it points out that there's a lot of time being spent in C++ code. LLVM's great, but it's guidelines essentially suggest 'if you want to make llvm play nice, generate IR like clang'
  - acqq 10y ago
    > Their comment went on to claim that given their hypothesis, allocation optimization shouldn't be impactful. And what was the hypothesis? That the code for the compiler itself should use the features imagined to be used by the language, just like your example: > One of the post's optimizations was to use Cow<str> over String Then: > allocation optimization shouldn't be impactful. Yet this post demonstrates otherwise "not impactful": It looks to me like that: 36.526s vs 32.373s for the longest compile tested. It is measurable, but not something that I as the programmer will be able to notice. My definition of impactful for the compilation times is "at least a factor of 2" not 1.1. And the claim is, once the language possibilities are actually used. If the code is written differently, of course not much is expected. The result of a moderate speedup exactly shows that the language possibilities weren't always used in a way to minimize allocations, but the difference is still not, for my perception, significant (10% is hard to recognize unless measured or the actual compilations last hours and not seconds). But I still claim that much bigger potential gains are the actual changes in the algorithms and the data structures. The data structures especially can hugely change the result if they are made to be really cache friendly, and together with the changes in algorithms such modifications have the potential to make an order of magnitude speedups, if they are actually possible.
- valarauca1 10y ago
  Because the parent poster's thesis >>Moreover, the compilers in general have an advantage to know that most of the objects are needed only during specific times, allowing optimized allocation and bundled deallocation Is flawed. Compiler can know this. Most the time they don't. In Turing complete languages you can't reason about how much space/time a program will need to run. When you do know that and object, or objects will be determanstically allocated/de-allocated together. Then you need to know how large they'll grow too over their their lifetimes. Which again may hit a Turing Tarpit, and you lose this ability. Here is an incredibly simple example fn read_file(path: &str) -> String; fn get_tokens<'a>(s: &'a str, r: &Regex) -> HashMap<&'a str, &'str> fn main() { let my_regex = //something let file_data = read_file(&arg[1]); let tokens = get_tokens( &file_data, &my_regex); } On can see the String that will contain the file's data, and Hashmap can be allocated together. But one cannot reason about how large either will be head of time to pre-size these on the heap. Lastly, address randomization is a good thing. Knowing ahead of time which allocations will determanstically be in relation to each other is a security vulnerability.
  - acqq 10y ago
    My claim about "the compilers in general have an advantage to know that most of the objects are needed only during specific times" is directed to the construction of the compiler, like the Rust compiler written in Rust, not that there's any magic. That means, the writer of the compiler can write the compiler knowing much more about the lifetime of the objects used in the compilation than most of the software. When you write a server, you don't know who much which pieces of the database should be in the memory. When you write a compiler, you know that everything goes away after the compilation is done. It allows extremely speedy compilers (considering the number of their malloc calls), which seldom allocate memory blocks and seldom deallocate. That means that even for the stuff that you allocate "on the heap" you don't have to allocate objects one-by-one, but allocate big chunks of memory and then just deliver the small pieces of it as the memory for "objects." The same way, for the deallocation, instead of deallocation many small objects, you can deallocate a lot at once. I've personally made the compiler that made only a few malloc calls for the whole compilation process, even if it internally "created" tens of thousand of "objects." I've done it in C, and Rust is made to allow the speed of C with the higher safety, so the equivalent strategies should be possible. The mention of "arenas" suggests to me that the writers actually think in that direction.
- Zarathustra30 10y ago
  > ...if the features of the language are used... The Rust compiler uses Rust's features terribly, just because Rust's features were a moving target for the majority of the compiler's lifetime.

keyle 10y ago

I've never used rust but seeing it's so oriented towards correctness and type checking, I'm not surprised it's a little slow to compile! From someone stuck with dynamic languages, mark my words, it's best for your compiler to be a bit slow, than your brain being the compiler! :-)

vintagedave 10y ago
Why? You can have both fast compilers and safe languages. Take Delphi for example: statically typed, strong type correctness, you have to work to avoid type safety. Compiles a million lines of code in 4 seconds (including linking.) * https://www.youtube.com/watch?v=Yq2mNUzcpE0 https://www.youtube.com/watch?v=Yq2mNUzcpE0 (1 million lines, 4 seconds) * https://www.youtube.com/watch?v=kvuxeaMDmMc https://www.youtube.com/watch?v=kvuxeaMDmMc (277,000 lines of much more complex code (the most complex, compiler-stressing library Delphi has) in 16 seconds counting linking.
- adrianN 10y ago
  I think the correctness guarantees that Rust provides are a little stronger than what Delphi provides.
  - bryanlarsen 10y ago
    Perhaps more significantly, the checking that Delphi provides is both explicit and local. Rust does a lot more inferential checks and at the crate level rather than at the line level.
    - Rusky 10y ago
      Rust's inference and checks are actively limited to function level, not crate level- function types are not inferred, generics are type-checked before instantiation, the borrow checker works on individual functions, etc.
- krylon 10y ago
  At work, I am stuck doin maintenance on an in-house application our accounting department uses, which is written in Delphi. It's small (~10k lines of code), but it compiles so fast I sometimes wonder if I clicked the wrong button / hit the wrong key.

pjmlp 10y ago

In conclusion, allocating memory is expensive, regardless how it is done. :)

kzrdude 10y ago
The allocation fixes are scratching on the surface of the compiler. It must be something more fundamental underlying the long compilation time.
- Manishearth 10y ago
  One of the main slow bits is just LLVM. Rust produces LLVM IR which LLVM takes a long time to optimize. Since MIR has landed, IIRC work on doing MIR optimizations and LLVM IR simplifications is the next step here.
  - kzrdude 10y ago
    Rustc is of course responsible for what it's feeding llvm, and being smarter about that sounds exciting.
- gribbly 10y ago
  Not sure how much is due to this, but LLVM has gotten much slower in recent releases, probably due to improved optimizations. I would not be surprised if down the line, the Rust devs decided to write their own Rust backend rather than relying on LLVM.
  - qznc 10y ago
    At least for development a custom fast backend would be great. For production code you still want all the optimizations you can get, which means LLVM.
  - wyldfire 10y ago
    Writing different backends for each supported target would either be taking on a lot of work or shedding some targets.

nickpsecurity 10y ago

I still think they should investigate doing the LISP solution to the problem where you combine several options: 1. Interpreter (eg REPL) that executes it instantly with dynamic checks for rapid prototyping of logic. 2. Fast, non-optimizing compile that at least does the safety checks. 3. Fully-optimizing compile that can be done in background or overnight while programmer works on other things like tests or documentation. 4. Incremental, per-function version of 2 or 3 for added boost. Rust is already adding something like that. This combo maximizes mental flow of programmer, lets them tinker around with algorithms, quickly produces executables for test deployments, and will often do full compiles without interrupting flow with wait times. It's the workflow available in a good LISP. It doesn't have to be exclusive to LISP. Other languages should copy it. I'll go further to say they should even design the language and compiler to make it easy to pull that off.

qwertyuiop924 10y ago
In CLs, anyways. In Schemes, we usually only have 1 and 3. Maybe 2 and four, but only sometimes.
- nickpsecurity 10y ago
  The Scheme I was thinking of using to re-learn LISP and Scheme was Racket. Its environment + How to Design Programs looked like a strong combo. Do you know how it fares on this list?
  - dleslie 10y ago
    FWIW, Racket explicitly dropped Scheme from its branding because the language designers disagreed with the direction of Scheme and wanted to go their own way; and they have, to a great extent. Racket has scheme in its syntax, but as does C++ has C.
    - nickpsecurity 10y ago
      Ahh. So probably best to think of it as its own, Scheme-like language.

eridius 10y ago

> malloc and free are still the two hottest functions in most benchmarks. Avoiding heap allocations can be a win. This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. But it does not mean that you should try to reduce calls to that function elsewhere (unless you can cut out a lot in one go). As a trivial example, if you have a super-fast function that cannot be optimized any further, but it's called millions of times, that function may appear hot, but any individual invocation of the function might be taking just a few microseconds. Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good. I guess another way of saying this is, if you're trying to optimize a hot function by reducing the number of times it's called, you need to reduce it by a significant percentage of the total calls rather than reducing it by a specific number of times. No matter how many times it's called, if you reduce the number of calls by 50%, the overall time taken by the function drops by 50%. But if you reduce the number of calls by 50, then whether that's meaningful or not depends entirely on how long each individual call to the function takes. Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why.

MaulingMonkey 10y ago
> Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why. Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite. > This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. This is just as much of a "non-sequitur" - maybe you can optimize that function further, but if it's reached the point of diminishing returns it may not be worth it even if it's technically possible. In-context, there has already been a lot of optimization work put into malloc and free, lots of low hanging fruit is gone. Further, malloc and free are very generic allocation strategies that generally do a lot of work to try and handle many different cases with OK efficiency. I challenge you to make them as fast as, say, stack allocation - go ahead, I'll wait. Sure, you can't replace all use of a heap with a stack, but most programs I've seen have at least some cases where you could. And there is actually a way to make malloc and free as fast as a stack - turn your malloc implementation into a pointer increment, and free into a noop. Not appropriate for all tools, but a short lived compiler pass might be able to get away with it! Although it'd possibly cause problems for large 32-bit builds. Regardless - this is also technically no longer a heap. As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO. > Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good. An important note here: Cutting the number of calls in half could, in theory, involve eliminating one call site (because e.g. the calling code itself is very hot) although this probably isn't the case in the Rust codebase or it'd have been optimized already. Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site.