3 ms·
My list would be: - Inlining - Common subexpression elimination - Dead code elimination - Monomorphization I get the impression that 2 and 3 come out of an
by fanf2 6y ago
My list would be:
- Inlining
- Common subexpression elimination
- Dead code elimination
- Monomorphization
I get the impression that 2 and 3 come out of an SSA middle end fairly straightforwardly, along with the article’s copy propagation and dead store elimination.
The biggie is monomorphization, which is part of the language in C++. The alternative is uniform representation of generic values,
which implies boxing and indirection instead. I understand Rust does not hide representations enough for the compiler to be able to choose whether or not to monomorphize. Interestingly, the Go generics discussion seems to be heading towards a design where the compiler does have this option.
- davidcuddeback 6y ago> I understand Rust does not hide representations enough for the compiler to be able to choose whether or not to monomorphize. Any chance you could expand on that?
- fanf2 6y agoI don't know enough Rust to explain clearly or give examples :-) But like C++, Rust makes it explicit whether an object is boxed or not and the compiler doesn't get a choice about the memory layout, so it can't switch between monomorphization or uniform representation depending on the optimization level.
- davidcuddeback 6y agoI'm so used to choosing between monomorphization and dynamic dispatch myself that I never thought of the possibility of a compiler being able to choose. Is the point to avoid monomorphization during dev to have faster compile times, and then enable monomorphization for release builds? That's a neat idea. That makes me wonder what Java does these days. I haven't used Java much since about v1.6. Java took a different approach than C++ and Rust. I remember when generics were introduced, they were basically syntactic sugar for type casts (for backwards compatibility). That implies that Java at the time didn't monomorphize generics. I think the language has evolved a lot since those days, so I wonder if it does any monomorphization today.
- kjeetgill 6y agoJava is slightly more complicated. It can make assumptions about the code (even if it can't prove they always hold!) and specialize some things but not others. Generally, the jit can specialize the code making assumptions about the real type under interfaces/polymorphism, which types the generic parameters will be, or even which target virtual dispatch will always hit. But for the objects themselves, it never specializes layout in any way (short of removing an allocation entirely). ... I think. I'm no expert in this, ask chrisseaton.
- necubi 6y agoYeah in Rust it's not up to the compiler whether generic code is monomorphized or dynamic dispatched, it's part of the language. A monomorphized function looks like this: fn f1<T: Display>(v: &T) -> String { format!("{}", v) } A dynamic dispatched function looks like: fn f2(v: &dyn Display) -> String { format!("{}", v) } Note that we've added the dyn keyword, which tells rust to treat this as a trait object and use dynamic dispatch. This is actually separate from boxing (these examples are just using normal unboxed references), although typically you would use trait objects with boxing as unboxed trait objects are awkward to work with. See https://godbolt.org/z/PvM3ox https://godbolt.org/z/PvM3ox for an example of the compilation: we get two versions of f1 specialized for u32 and u64, but just one for f2.
- mshockwave 6y ago+1 for Monomorphization. Though more and more code base try to avoid virtual dispatching by either not using it at all or using template tricks instead
- pornel 6y agoOTOH monomorphisation multiplies amount of code to optimize. For large functions that is problematic. Rust's standard library uses a pattern (written manually) of "hoisting" generic code out of large functions, e.g. fn generic<P: AsRef<Path>>(path: P) { non_generic(path.as_ref()); } fn non_generic(path: &Path) { // lots of code } That's cheaper to compile and reduces binary size compared to having one large generic function monomorphized for every AsRef<Path> type. It'd be great to have this as a compiler optimization to automatically have "half-monomorphic" functions.
- cesarb 6y agoI have seen a similar optimization in GHC, where it's called "worker-wrapper", and used to reduce the cost of Haskell allocating everything on the heap. It splits each function into a "wrapper" which unboxes all arguments and boxes the return value, and a "worker" which actually does all the work on the unboxed values. The "wrapper" can then be inlined, which allows the compiler to remove unnecessary boxing (boxing a value only to immediately unbox it again).
- matt_d 6y agoFWIW, this technique has been known in the C++ community as "hoisting", too (often applied to templates, particularly container class templates, but also smart pointers); cf. "Designing and Coding Reusable C++" by Carroll and Ellis, 1995 (http://cpptips.com/hoisting http://cpptips.com/hoisting). "Given this, what techniques can be used to reduce template instantiation time? One technique is called "hoisting." This is a generalization of the "wrappers for pointer containers" technique that showed up as a tip within the past week or so. The idea is quite simple: when writing a template class, consider each method in turn. If the method does not depend upon the template parameters, split the template class into a non-template base and a template derived class. Move (hoist) these parameter independent methods up into the base class. Note that with experience, you will begin to recognize opportunities for "hoisting" even in cases where methods initially appear to depend upon template parameters." See also "thin template" (demonstrating the technique for containers, together with a Symbian OS adoption example, https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Thin_Template https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Thin_Templ...) as well as "Minimizing Dependencies within Generic Classes for Faster and Smaller Programs", Dan Tsafrir, Robert W. Wisniewski, David F. Bacon, and Bjarne Stroustrup (ACM OOPSLA 2009). https://www.stroustrup.com/SCARY.pdf https://www.stroustrup.com/SCARY.pdf "Reducing bloat by replacing inner classes with aliases can be further generalized to also apply to member methods of generic classes, which, like nested types, might uselessly depend on certain type parameters simply because they reside within a generic class’s scope. (Again, causing the compiler to uselessly generate many identical or nearly-identical instantiations of the same method.) To solve this problem we propose a “generalized hoisting” design paradigm, which decomposes a generic class into a hierarchy that eliminates unneeded dependencies."