Menu
Template metaprogramming can be used for computing things like factorial at compile time instead of during runtime. I've heard that some programming contests have introduced limitations on compilation time exactly to weed out template metaprogramming abuse.
Is there any innocent looking example of using templates that takes some really-really long time (like several hours) to compile?
676
Because we're adding more templated member functions! Each empty template member function costs about 0.000030 seconds to compile, and that's before it has any code code in it. By moving code out of one function and into another, we actually end up adding time.
The use of templates can be thought of as compile-time polymorphism. The technique is used by a number of languages, the best-known being C++, but also Curl, D, Nim, and XL.
Compared to hand-written code written precisely for that scenario, there is zero difference. So the nice thing about templates isn't that they are "faster" than what you could do otherwise, but that they are "as fast" as hand-written code, while also being generic and reusable.
Templates are slow (to build) Templates reduce the number of lines of code in our programs. They are harder to understand when reading them later, but the bigger disadvantage is that they slow down build time.
The template mechanism is Turing-complete. This means that in theory at least, any computation that can be done can be done at compile time this way (In practice you may run into hard limits on template depth etc. fairly quickly but this is compiler dependent).
Whether or not you'd want to do this is a separate question. You can trivially match your criterion of "hours to compile" by using an expensive algorithm. But there are also more practical codes like this one implementing an FFT; give that a large enough data set and it will take a while...
142
I've heard that the International Olympiad in Informatics (one such programming contest) first introduced compile time limits after a contestant created a 7 dimensional vector using a technique much like this. His code had to be left compiling overnight it was so bad. I think this occured some time in the late 90's.
27
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
