3 ms·

Conversely, more sophisticated algorithms, and particularly monomorphization, may bloat the code size, causing icache, L2/L3 cache, and TLB misses. (Also slows

Conversely, more sophisticated algorithms, and particularly monomorphization, may bloat the code size, causing icache, L2/L3 cache, and TLB misses. (Also slows compilation.) I think this is under-appreciated because it doesn't show in microbenchmarks. (I wish I knew of an easy way to measure how much cache pressure you're causing from a microbenchmark.) I suspect for this reason it'd be better in Rust to use a Go-like hash map implementation [1] that keeps all the key/value information (size, Hash and Eq implementations) in a vtable-like form rather than be monomorphized, except in really hot inner loops where the specialization is worth it. There was an interesting article and discussion on reddit relating to this [2] where someone made a toy type-erased map (though not as nice as Go's) to measure the difference in compilation times. Maybe some day I'll make a more production-ready attempt... [1] https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics https://dave.cheney.net/2018/05/29/how-the-go-runtime-implem... [2] https://www.reddit.com/r/rust/comments/g1skz4/an_experiment_with_typeerased_datastructures/ https://www.reddit.com/r/rust/comments/g1skz4/an_experiment_...

pbadenski 6y ago
Thank you for mentioning monomorphization - I wasn't aware of this concept. Would you maybe if there's any source discussing how this is solved in different languages and performance consequences of it?
- bicolao 6y ago
  Not really answering your questions, but regarding monomorphization, you can see a comparison of code size and compilation speed between printf, std::format and C++ iostream. The last one is monomophization, I believe. https://github.com/fmtlib/fmt#compile-time-and-code-bloat https://github.com/fmtlib/fmt#compile-time-and-code-bloat
- scottlamb 6y ago
  I'm not aware of a high-quality source discussing this. I'd be interested in seeing one. Off the top of my head: * In many languages, monomorphization is impractical. Eg, in C it requires macros or external code generators. Java and Go don't even have macros. So it's rarely done. Instead, stuff uses type erasure, dynamic dispatch, more heap allocations, and tables like the ones described in that dave.cheney.net link. Maybe some JITs or even some ahead-of-time compilers do monomorphization internally in some cases, but I'm speculating rather than speaking from knowledge. * In C++ and Rust, monomorphization is easy. You don't have to do it, but it's easy, so many people do. The containers in the standard library are monomorphized. This code can perform very well in any particular case, but in aggregate it's large enough that I have doubts about whether it's always worth it for the whole program.

pbadenski 6y ago

Thank you for mentioning monomorphization - I wasn't aware of this concept. Would you maybe if there's any source discussing how this is solved in different languages and performance consequences of it?

bicolao 6y ago
Not really answering your questions, but regarding monomorphization, you can see a comparison of code size and compilation speed between printf, std::format and C++ iostream. The last one is monomophization, I believe. https://github.com/fmtlib/fmt#compile-time-and-code-bloat https://github.com/fmtlib/fmt#compile-time-and-code-bloat
scottlamb 6y ago
I'm not aware of a high-quality source discussing this. I'd be interested in seeing one. Off the top of my head: * In many languages, monomorphization is impractical. Eg, in C it requires macros or external code generators. Java and Go don't even have macros. So it's rarely done. Instead, stuff uses type erasure, dynamic dispatch, more heap allocations, and tables like the ones described in that dave.cheney.net link. Maybe some JITs or even some ahead-of-time compilers do monomorphization internally in some cases, but I'm speculating rather than speaking from knowledge. * In C++ and Rust, monomorphization is easy. You don't have to do it, but it's easy, so many people do. The containers in the standard library are monomorphized. This code can perform very well in any particular case, but in aggregate it's large enough that I have doubts about whether it's always worth it for the whole program.