Current version

v1.10.4 (stable)

Navigation

Main page
Archived news
Downloads
Documentation
   Capture
   Compiling
   Processing
   Crashes
Features
Filters
Plugin SDK
Knowledge base
Contact info
Forum
 
Other projects
   Altirra

Search

Archives

01 Dec - 31 Dec 2013
01 Oct - 31 Oct 2013
01 Aug - 31 Aug 2013
01 May - 31 May 2013
01 Mar - 31 Mar 2013
01 Feb - 29 Feb 2013
01 Dec - 31 Dec 2012
01 Nov - 30 Nov 2012
01 Oct - 31 Oct 2012
01 Sep - 30 Sep 2012
01 Aug - 31 Aug 2012
01 June - 30 June 2012
01 May - 31 May 2012
01 Apr - 30 Apr 2012
01 Dec - 31 Dec 2011
01 Nov - 30 Nov 2011
01 Oct - 31 Oct 2011
01 Sep - 30 Sep 2011
01 Aug - 31 Aug 2011
01 Jul - 31 Jul 2011
01 June - 30 June 2011
01 May - 31 May 2011
01 Apr - 30 Apr 2011
01 Mar - 31 Mar 2011
01 Feb - 29 Feb 2011
01 Jan - 31 Jan 2011
01 Dec - 31 Dec 2010
01 Nov - 30 Nov 2010
01 Oct - 31 Oct 2010
01 Sep - 30 Sep 2010
01 Aug - 31 Aug 2010
01 Jul - 31 Jul 2010
01 June - 30 June 2010
01 May - 31 May 2010
01 Apr - 30 Apr 2010
01 Mar - 31 Mar 2010
01 Feb - 29 Feb 2010
01 Jan - 31 Jan 2010
01 Dec - 31 Dec 2009
01 Nov - 30 Nov 2009
01 Oct - 31 Oct 2009
01 Sep - 30 Sep 2009
01 Aug - 31 Aug 2009
01 Jul - 31 Jul 2009
01 June - 30 June 2009
01 May - 31 May 2009
01 Apr - 30 Apr 2009
01 Mar - 31 Mar 2009
01 Feb - 29 Feb 2009
01 Jan - 31 Jan 2009
01 Dec - 31 Dec 2008
01 Nov - 30 Nov 2008
01 Oct - 31 Oct 2008
01 Sep - 30 Sep 2008
01 Aug - 31 Aug 2008
01 Jul - 31 Jul 2008
01 June - 30 June 2008
01 May - 31 May 2008
01 Apr - 30 Apr 2008
01 Mar - 31 Mar 2008
01 Feb - 29 Feb 2008
01 Jan - 31 Jan 2008
01 Dec - 31 Dec 2007
01 Nov - 30 Nov 2007
01 Oct - 31 Oct 2007
01 Sep - 30 Sep 2007
01 Aug - 31 Aug 2007
01 Jul - 31 Jul 2007
01 June - 30 June 2007
01 May - 31 May 2007
01 Apr - 30 Apr 2007
01 Mar - 31 Mar 2007
01 Feb - 29 Feb 2007
01 Jan - 31 Jan 2007
01 Dec - 31 Dec 2006
01 Nov - 30 Nov 2006
01 Oct - 31 Oct 2006
01 Sep - 30 Sep 2006
01 Aug - 31 Aug 2006
01 Jul - 31 Jul 2006
01 June - 30 June 2006
01 May - 31 May 2006
01 Apr - 30 Apr 2006
01 Mar - 31 Mar 2006
01 Feb - 29 Feb 2006
01 Jan - 31 Jan 2006
01 Dec - 31 Dec 2005
01 Nov - 30 Nov 2005
01 Oct - 31 Oct 2005
01 Sep - 30 Sep 2005
01 Aug - 31 Aug 2005
01 Jul - 31 Jul 2005
01 June - 30 June 2005
01 May - 31 May 2005
01 Apr - 30 Apr 2005
01 Mar - 31 Mar 2005
01 Feb - 29 Feb 2005
01 Jan - 31 Jan 2005
01 Dec - 31 Dec 2004
01 Nov - 30 Nov 2004
01 Oct - 31 Oct 2004
01 Sep - 30 Sep 2004
01 Aug - 31 Aug 2004

Stuff

Powered by Pivot  
XML: RSS feed 
XML: Atom feed 

§ Template madness

Templates are a feature in C++ where you can create functions and class types that are parameterized on other types and values. An example is the min() function. Without templates, your choices in C++ would be a macro, which has problems with side effects; a single function, which locks you down to a single type; or multiple overloads, which drives you nuts. Templates allow you to declare a min() that works with any type that has a less-than predicate without having to write all of the variants explicitly.

The problem with templates is that they're (a) awful to use and (b) very powerful. The C++ template syntax is horrible, with all sorts of notorious problems with angle brackets and typename and other issues, and anyone who used VC6 still shudders at the mention of STL errors. The thing is, I still like templates, because they're compile-time and extremely versatile. The last time I had to use generics in C#, I ran into so many limitations that I really wished I'd had templates instead. C# generics are a mixture of both compile-time and run-time instantiation, which means they're more constrained. In particular, the inability to use constructors with parameters or to cast to the generic type is crippling, especially if you're working with enums. In C++, you can pretty much do anything with T that you could with using an explicit type.

Function template instantiation is one of the areas that I have the most problem with. The idea is simple: you specify the function you want, and the compiler finds the best template to fit. In reality, you're in a role-playing game where you wish for the function you want and the compiler GM does whatever it can to do precisely what you ask and still screw you, like implicitly convert a double through type bool. I got burned by this tonight when I tried to port VirtualDub to Visual Studio 2010 beta 1. I had expected this to be quick since everything just worked in the CTP, but with beta 1 it took hours due to several nasty bugs in the project system. The first time I was able to run the program it asserted before it even opened the main window. The problem was in this code:

int nItems = std::min<int>(mMaxCount, s.length());

mMaxCount was 4, s.length() was 2, and I ended up with min(4, 2) == 4. WTF?

First, I should note the reason for the explicit call. I often end up with situations where I need to do a min() or a max() against mixed signed and unsigned types, and usually I know that the value ranges are such that it's OK to force to one type, such as if I've already done some clamping. To do this, I force the template type. Well, it turns out that specifying min<int>() doesn't do what I had expected. It doesn't force a call to the version of min() with one template parameter of type int -- it forces a call to any template with int as the first type parameter. This used to be OK because std::min() only had one overload that took two parameters, so no other template could match. However, VS2010 beta 1 adds this evil overload:

template<class T, class Pred>
inline const T& min(const T&, Pred);

Why you would ever want a min() that takes a single value and a predicate is beyond me. However, since I was calling min() with an int and an unsigned int, the compiler decided that min<int, unsigned>(int, unsigned) was a better match than min<int>(int, int). The odd result is that 2 got turned into an ignored predicate and min(2, 4) == 4. Joy. I hacked the build into working by writing my own min() and max() and doing a massive Replace In Files.

I love templates, but I wish they didn't have so many gotchas.

Comments

Comments posted:


Correct me if I'm wrong, but I thought casting the unsigned value to an int and then passing to the min function would instantiate the function. So
int a = 2;
unsigned int b = 4;
min(a, static_cast(b));

But if you already did a mass replace in files, I guess it's not worth going back to try this. =)

George Slavov - 23 05 09 - 07:28


Hmmm, somehow my templates got removed by the blog. I hope it still makes sense. I don't know to force it to display 'less-than' min 'greater-than'.

George Slavov - 23 05 09 - 07:29


IMO, this isn't a template issue; it's a "dangerous overload" issue that happens to involve a template.

Hmm, though I guess an unsigned int isn't a valid Pred and the code only compiles because the template doesn't use Pred and will bind absolutely anything to it. So I guess it is a template issue if you look at it like that. Still, there are loads of cases where similar overload do bind to their arguments and still compile, yet are completely unexpected.

I wonder why the one-item min is there? Have they added lots of other mins for N items? Is there a zero-item min, which just takes an unused Pred, as well? (That'd be pretty "special" when the Pred argument in the other cases is defaulted.)

Leo Davidson (link) - 23 05 09 - 08:26


STL doesn't actually define a min() like that, right? This just sounds like VC polluting the namespace and breaking things.

Syntax is the smallest issue of templates.

- They tend to bloat the living hell out of code. Sometimes it's nice to write a whole algorithm as a template, like when you want to do the same thing to 8-bit fixed, 16-bit fixed, floats and doubles, but the result will be four complete copies of the code.
- Even for simpler code, compilers will rarely coalesce anything. When you have many container types on many different data types and pointer types, a lot of that generated code will end up the same. The allocation support code for vector and vector is going to be identical--shifting around arrays of 4 byte items--but compilers usually won't figure that out. If you have map containers, it couldn't even theoretically combine them. Output size bloats quickly.
- They tend to explode code dependencies: unless you wrap everything in an interface class (severely limiting the use of the class), you have to make the entire thing a header.

crypto++ is a collection of some of the worst C++ code I've ever seen: written almost completely as nested templates. The code is an evil maze, and it compiles to over a megabyte, even when all I need is simple RSA crypto and signing. I replaced it with tomcrypt, which is much cleaner and results in much less bloated code.

I like templates when used carefully, but they can easily turn evil.

Glenn Maynard - 23 05 09 - 13:34


Yes, casting the parameters directly would do the trick. (I personally dislike using static_cast myself for numbers -- there's nothing unsafe about using a C cast here and it's a lot more concise.) However, the new overload makes it a lot harder to see when this is necessary, because you'd no longer get the ambiguity error that previously would trip the arguments didn't match and the type weren't forced.

As for why the overload exists, the library source has it wrapped in _HAS_CPP0X, but that's all I know about it. I suspected it might have been an early inclusion from the C++0x standard library but I couldn't find that particular overload in the draft standard. I can't check at the moment, but I believe they added min/max(T), min/max(T, Pred), min/max(T, T, T), and min/max(T, T, T, Pred). It's filed on Connect, so we'll see what happens next.

Dependencies are indeed a huge problem of templates that I forgot to mention. Careless use of templates can easily destroy build speed due to .obj bloat.

The changes I did to get VirtualDub building were all done in a side branch, so they're trivial for me to revert. It turns out there was one genuine bug on my end that I had to fix, which is that the new STL requires allocators to implement the cross-type copy constructor.

Phaeron - 23 05 09 - 15:05


What do you mean by "inability to use constructors with parameters" in C# ?

You can certainly do this:

class MyClass
{
public MyClass() { }
public MyClass(int value) { } // (used even if T is int)
public MyClass(T value) { }
}

Lucas - 23 05 09 - 15:17


err... I meant class MyClass{T} (replace with angle brackets), or in VB syntax (yuck), Class MyClass(Of T).

Anyway, I realised maybe you meant that the constructor itself can't have generic type parameters (which is true). Was that it?

Lucas - 23 05 09 - 15:20


You can't pass parameters when constructing a generic parameter type. C# only allows you to declare the parameterless new constraint, i.e. where T: new().

Phaeron - 23 05 09 - 15:23


unfortunately that true but an easy workaround would be a factory:

static void Abc(Func factory)
{
factory("param").LaunchMissiles();
}

in exchange for the additional restrictions you also gain many advantages. one thing that is lost however is being able to write an algorithm for all numeric types at the same time because there is no INumeric and the template type would have to be statically known that it has numeric operators. a workaround for that is ugly:

interface IMathProvider { T Add(T a, T b); }
struct MathProvider : IMathProvider
{
...
}

static T Add(MathProvider provider, T a, T b)
{
return provider.Add(a, b);
}

because MathProvider is a struct, the implementation of Add will be inlined and the code will be nearly as fast as with direct integers.

Tobias - 23 05 09 - 17:54


@Phaeron

You can always hack around that particular problem, too. Late-bind to the constructor you want, using reflection.

Chris (link) - 23 05 09 - 17:56


C++0x has templates that can take a variable number of arguments. I expect the min(const T&, Pred) is the singleton case for a version of min that can take an arbitrary number of arguments followed by a predicate so you can say min(a, c, t, tastiest) or min(-1, 4, 18, 34, 12, negate).

Neil Hodgson - 23 05 09 - 18:38


I'm with Leo Davidson -- that's not a template problem, that's a bug with an evil overload that shouldn't be there.

The real gotcha with templates is that, in that declaration, "Pred" doesn't mean anything, any more than "T" does -- it's just an arbitrary typename, and could be anything. And so that template will match any call where the typenames differ.

The fact that VS2010 is still in beta means that this isn't necessarily final behavior. PLEASE file it as a bug with Microsoft, so they can fix it!

Brooks Moses - 23 05 09 - 20:22


Have you seen how neat templates are in the D programming language?

kL (link) - 24 05 09 - 10:27


I did file a bug on this: 456631. No response yet because it's the weekend.

Templates are strongly implicated, since no one would write an explicitly typed version of min() that accepted an unsigned int as a predicate type.

Reflection will work wrt. the C# issues, but it's slower and a refactoring hazard -- nothing like using a refactor command to rename a symbol or confirm unused code before removal, only to run into a runtime error later because someone accessed the old name by reflection. And as for the factory pattern, I was trying to use generics to generate factories....

D templates do look significantly more powerful, especially with the static if construct. However, I think some of the syntactic comparisons are unfair, as you can declare integral types as inline static const class members in C++.

Phaeron - 24 05 09 - 21:23


I wonder, given that you would have those 2, is there any way to reliably select the min, without casting the parameters? And if not, I'm trying to think what this means, e.g. what you just had: anyone adding a min template anywhere in the headers you happen to pull in, will be able to replace the min you (tried to) explictly select, without any warnings anywhere.

Arnt - 26 05 09 - 17:26


> I wonder, given that you would have those 2, is there any way to reliably select the min, without casting the parameters?

No, and the new overload significantly raises the risk. Previously, if you happen to accidentally call min() with mismatched signedness, you would get a ambiguous call error to flag that you need to explicitly choose the desired behavior. Now you just get a bogus result, instead.

Someone adding a min template is less of an issue if you are explicitly calling the standard library version, because there are serious restrictions on what user code can inject into namespace std -- I believe it's something like you're only allowed to specialize certain templates. The library implementor, however, has much more leeway to screw you.

I hate the way that min() and max() are generally implemented. CPUs frequently have one or two instruction ways to do a min/max operation, but instead you get branching because the implementation doesn't expose the optimized path.

Phaeron - 26 05 09 - 17:42


Any change like this should count the damage versus the advantage. If Neil is correct, then the advantage here is min(1,2,3,pred) vs (for instance) min_pred(1,2,3,pred). I can only guess the damage is gigantic. It seems strange to me that the VC Compiler guys don't have other MSFT people screaming at them for this, although that begs the question of how much VC uses STL itself (my illiterate uninformed guess is 0%)... I personally avoid the STL, in part because of things like this.

Ben Harper - 27 05 09 - 16:58


Note that the current C++ standard already overloads min() with both predicate and non-predicate versions, so there is precedent.

I think the reason that this wasn't caught is that you practically have to be forcing at least one of the template parameters to trigger this. Otherwise, you would have had to have the types already matched in order for it to work previously, and then it would pick the correct override in VS2010 beta 1. Therefore, unless you use min/max the way I do, this falls into the class of "giant hidden bear trap" instead of "breaks existing code."

Phaeron - 28 05 09 - 15:48


I such cases I usually hack & slash the header files to make them sane rather than doing what you did.

Igor Levicki (link) - 17 06 09 - 11:53

Comment form


Please keep comments on-topic for this entry. If you have unrelated comments about VirtualDub, the forum is a better place to post them.
Name:  
Remember personal info?

Email (Optional):
Your email address is only revealed to the blog owner and is not shown to the public.
URL (Optional):
Comment: /

An authentication dialog may appear when you click Post Comment. Simply type in "post" as the user and "now" as the password. I have had to do this to stop automated comment spam.



Small print: All html tags except <b> and <i> will be removed from your comment. You can make links by just typing the url or mail-address.