It's not the complication that bugs me: it's the runtime inefficiency! Used carelessly, C++ templates produce massive code bloat from repetitive instantiations.
Templates are a prime mechanism for achieving efficiency in C++ code and do not produce code-bloat like those early compilers.
http://articles.emptycrate.com/2008/05/06/nobody_understands...
When templates are used to remove indirection, very good efficiency results with zero-overhead, which is a major reason why C++ sort can be quicker than qsort. (http://www.geeksforgeeks.org/c-qsort-vs-c-sort/)
You can use techniques like type erasure to reduce bloat, and compilers and linkers do combine identical code sequences in many cases, but the point remains that templates work by replicating code for each instantiation. If you blindly trust the toolchain to clean up for you (as your first link suggests), you're going to run into problems. Size problems are insidious because they don't show up until they're hard to fix.
I'm not suggesting that you never use templates, but I am insisting that you understand what they do instead of trusting the compiler to sweep everything under the rug.
You mean you actually experience slowness clearly attributable to instruction cache misses? I don't know if I've ever had that. What bugs me is the compile-time inefficiency. A lot of times the same method gets regenerated for every time in the enclosing class even though most if not all of it could just as well be in the base class without the template parameter, to only get instantiated once.
The remaining inefficiency is supposed to go away with the upcoming module system.
That's really not the main goal of the module system. It's more about code hygiene, no matter how much people are hoping it will completely solve the issue with compile times.