3 ms·

+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 ago
OTOH 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 ago
  I 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 ago
  FWIW, 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."
- heavenlyblue 6y ago
  Shouldn’t that be pretty easy to automate in the compiler?

pornel 6y ago

OTOH 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 ago
I 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 ago
FWIW, 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."
heavenlyblue 6y ago
Shouldn’t that be pretty easy to automate in the compiler?