3 ms·

Do compilers really can never call `free()`? Simple compiler probably can. Most complex probably cannot (I don't want to imagine a Rust compiler without freein

Do compilers really can never call `free()`? Simple compiler probably can. Most complex probably cannot (I don't want to imagine a Rust compiler without freeing memory: it has 7 layers of lowering (source code->tokens->ast->HIR->THIR->MIR->monomorphized MIR, excluding the final LLVM IR) and also allocates a lot while type-checking or borrow-checking). What is most interesting to me is the average compiler. Does somebody have statistics on the average amount compilers allocate and free?

com2kid 4y ago
> Do compilers really can never call `free()`? I worked on, one of the many, Microsoft compiler teams, though as a software engineer in test not directly on the compiler itself, and I believe the lead dev told me they don't free any memory, though I could be misremembering since it was my first job out of college. Remember C compilers are often one file at a time (and a LOLWTF # of includes), and the majority of work goes into making a single output file, and then you are done. Freeing memory would just take time, better to just hand it all back to the OS. Also compilers are obsessed with correctness, generating incorrect code is to be avoided at all costs. Dealing with memory management is just one more place where things can go wrong. So why bother? I do remember running out of memory using link time code gen though, back when everything was 32bit. Related, I miss the insane dedication to quality that team had. Every single bug had a regression test created for it. We had regression tests 10-15 years old that would find a bug that would have otherwise slipped through. It was a great way to start my career off, just sad I haven't seen testing done at that level since then!
- kaba0 4y ago
  Bootstrapping aside, a compiler written in a GCd language would make perfect sense. It really doesn’t have any reason to go lower level than that (other than of course, if one wants to bootstrap it in the same language that happens to be a low-level one)
  - com2kid 4y ago
    There is no reason to free memory. Your process is going to hard exit after a set workload. If you wrote a compiler in a GCd language, you'd want to disable the collector because that just takes time, and compilers are slow enough as it is!
    - kaba0 4y ago
      A good GC will not really increase the execution time at all -- they turn on only after a significant "headroom" of allocations. For short runs they will hardly do any work. Also, most of the work will be done in parallel, and I really wouldn't put aside that a generational GC's improved cache effect (moving still used objects close) might even improve performance (all other things being equal, but they are never of course). All in all, do not assume that just because a runtime has a GC it will necessarily be slower, that's a myth.
- Arnavion 4y ago
  >Related, I miss the insane dedication to quality that team had. Every single bug had a regression test created for it. Compilers in particular are usually easy to have rigorous regression testing for. Investigating any issue usually forces you to produce a minimal repro because of how complicated a compiler is. Also, all the inputs and outputs are known. Then it's just a one tiny extra step of putting that all together into a checked-in test.
IshKebab 4y ago
I presume he means that compilers could be written to never call `free()`. I'm sure that most of them are not written like that, though they do tend to be very leaky and just `exit()` at the end rather than clean everything up neatly (partly because it's faster).
woodruffw 4y ago
LLVM uses a mixed strategy: there's both RAII and lots of globally allocated context that only gets destroyed at program cleanup. I believe GCC is the same. Rustc is written entirely in Rust, so I would assume that it doesn't do that.
- notriddle 4y ago
  The headline feature of rustc memory management is the use of arenas: https://github.com/rust-lang/rust/blob/10f4ce324baf7cfb7ce2b2096662b82b79204944/compiler/rustc_arena/src/lib.rs https://github.com/rust-lang/rust/blob/10f4ce324baf7cfb7ce2b... //! The arena, a fast but limited type of allocator. //! //! Arenas are a type of allocator that destroy the objects within, all at //! once, once the arena itself is destroyed. They do not support deallocation //! of individual objects while the arena itself is still alive. The benefit //! of an arena is very fast allocation; just a pointer bump. The other thing (not specifically mentioned in this comment, but mentioned elsewhere, and important to understanding why it work the way it does) is that if everything in the arena gets freed at once, it implies that you can soundly treat everything in the arena as having exactly the same lifetime. You can see an example of how every ty::Ty<'tcx> in rustc winds up with the same lifetime, and an entry point for understanding it more, here in the dev guide: https://rustc-dev-guide.rust-lang.org/memory.html https://rustc-dev-guide.rust-lang.org/memory.html However, arena allocation doesn't cover all of the dynamic allocation in rustc. Rustc uses a mixed strategy: there's both RAII and lots of arena allocated context that only gets destroyed at the end of a particular phase.
  - woodruffw 4y ago
    Yep -- arenas compose very nicely with lifetimes, and basically accomplish the same thing as global allocation (in effect, a 'static arena) but with more control.
  - zRedShift 4y ago
    For further reading, I recommend Niko's latest blog, tangentially related to rustc internals (and arena allocation): https://smallcultfollowing.com/babysteps/blog/2022/06/15/what-it-feels-like-when-rust-saves-your-bacon/#how-to-fix-it https://smallcultfollowing.com/babysteps/blog/2022/06/15/wha...
TazeTSchnitzel 4y ago
> Do compilers really can never call `free()`? If a compiler has to be run multiple times in the same process, it may use an area allocator to track all memory, so you can free it all in one go once you're done with compilation. Delaying all freeing until the end effectively eliminates temporal memory issues.
MaxBarraclough 4y ago
I imagine plenty of compilers do call free, but here's a 2013 article by Walter Bright on modifying the dmd compiler to never free, and to use a simple pointer-bump allocator (rather than a proper malloc) resulting in a tremendous improvement in performance. [0] (I can't speak to how many layers dmd has, or had at the time.) The never-free pattern isn't just for compilers of course, it's also been used in missile-guidance code. [0] https://web.archive.org/web/20190126213344/https://www.drdobbs.com/cpp/increasing-compiler-speed-by-over-75/240158941 https://web.archive.org/web/20190126213344/https://www.drdob...
- pjmlp 4y ago
  Which is why dmd just dies on code that overdoes metaprogramming, after gobbling GB of data.

com2kid 4y ago

> Do compilers really can never call `free()`? I worked on, one of the many, Microsoft compiler teams, though as a software engineer in test not directly on the compiler itself, and I believe the lead dev told me they don't free any memory, though I could be misremembering since it was my first job out of college. Remember C compilers are often one file at a time (and a LOLWTF # of includes), and the majority of work goes into making a single output file, and then you are done. Freeing memory would just take time, better to just hand it all back to the OS. Also compilers are obsessed with correctness, generating incorrect code is to be avoided at all costs. Dealing with memory management is just one more place where things can go wrong. So why bother? I do remember running out of memory using link time code gen though, back when everything was 32bit. Related, I miss the insane dedication to quality that team had. Every single bug had a regression test created for it. We had regression tests 10-15 years old that would find a bug that would have otherwise slipped through. It was a great way to start my career off, just sad I haven't seen testing done at that level since then!

kaba0 4y ago
Bootstrapping aside, a compiler written in a GCd language would make perfect sense. It really doesn’t have any reason to go lower level than that (other than of course, if one wants to bootstrap it in the same language that happens to be a low-level one)
- com2kid 4y ago
  There is no reason to free memory. Your process is going to hard exit after a set workload. If you wrote a compiler in a GCd language, you'd want to disable the collector because that just takes time, and compilers are slow enough as it is!
  - kaba0 4y ago
    A good GC will not really increase the execution time at all -- they turn on only after a significant "headroom" of allocations. For short runs they will hardly do any work. Also, most of the work will be done in parallel, and I really wouldn't put aside that a generational GC's improved cache effect (moving still used objects close) might even improve performance (all other things being equal, but they are never of course). All in all, do not assume that just because a runtime has a GC it will necessarily be slower, that's a myth.
Arnavion 4y ago
>Related, I miss the insane dedication to quality that team had. Every single bug had a regression test created for it. Compilers in particular are usually easy to have rigorous regression testing for. Investigating any issue usually forces you to produce a minimal repro because of how complicated a compiler is. Also, all the inputs and outputs are known. Then it's just a one tiny extra step of putting that all together into a checked-in test.

IshKebab 4y ago

I presume he means that compilers could be written to never call `free()`. I'm sure that most of them are not written like that, though they do tend to be very leaky and just `exit()` at the end rather than clean everything up neatly (partly because it's faster).

woodruffw 4y ago

LLVM uses a mixed strategy: there's both RAII and lots of globally allocated context that only gets destroyed at program cleanup. I believe GCC is the same. Rustc is written entirely in Rust, so I would assume that it doesn't do that.

notriddle 4y ago
The headline feature of rustc memory management is the use of arenas: https://github.com/rust-lang/rust/blob/10f4ce324baf7cfb7ce2b2096662b82b79204944/compiler/rustc_arena/src/lib.rs https://github.com/rust-lang/rust/blob/10f4ce324baf7cfb7ce2b... //! The arena, a fast but limited type of allocator. //! //! Arenas are a type of allocator that destroy the objects within, all at //! once, once the arena itself is destroyed. They do not support deallocation //! of individual objects while the arena itself is still alive. The benefit //! of an arena is very fast allocation; just a pointer bump. The other thing (not specifically mentioned in this comment, but mentioned elsewhere, and important to understanding why it work the way it does) is that if everything in the arena gets freed at once, it implies that you can soundly treat everything in the arena as having exactly the same lifetime. You can see an example of how every ty::Ty<'tcx> in rustc winds up with the same lifetime, and an entry point for understanding it more, here in the dev guide: https://rustc-dev-guide.rust-lang.org/memory.html https://rustc-dev-guide.rust-lang.org/memory.html However, arena allocation doesn't cover all of the dynamic allocation in rustc. Rustc uses a mixed strategy: there's both RAII and lots of arena allocated context that only gets destroyed at the end of a particular phase.
- woodruffw 4y ago
  Yep -- arenas compose very nicely with lifetimes, and basically accomplish the same thing as global allocation (in effect, a 'static arena) but with more control.
- zRedShift 4y ago
  For further reading, I recommend Niko's latest blog, tangentially related to rustc internals (and arena allocation): https://smallcultfollowing.com/babysteps/blog/2022/06/15/what-it-feels-like-when-rust-saves-your-bacon/#how-to-fix-it https://smallcultfollowing.com/babysteps/blog/2022/06/15/wha...

TazeTSchnitzel 4y ago

> Do compilers really can never call `free()`? If a compiler has to be run multiple times in the same process, it may use an area allocator to track all memory, so you can free it all in one go once you're done with compilation. Delaying all freeing until the end effectively eliminates temporal memory issues.

MaxBarraclough 4y ago

I imagine plenty of compilers do call free, but here's a 2013 article by Walter Bright on modifying the dmd compiler to never free, and to use a simple pointer-bump allocator (rather than a proper malloc) resulting in a tremendous improvement in performance. [0] (I can't speak to how many layers dmd has, or had at the time.) The never-free pattern isn't just for compilers of course, it's also been used in missile-guidance code. [0] https://web.archive.org/web/20190126213344/https://www.drdobbs.com/cpp/increasing-compiler-speed-by-over-75/240158941 https://web.archive.org/web/20190126213344/https://www.drdob...

pjmlp 4y ago
Which is why dmd just dies on code that overdoes metaprogramming, after gobbling GB of data.