What's the difference, part one: Generics are not templates
Because I'm a geek, I enjoy learning about the sometimes-subtle differences between easily-confused things. For example:
- I'm still not super-clear in my head on the differences between a hub, router and switch and how it relates to the gnomes that live inside of each.
- Hunks of minerals found in nature are rocks; as soon as you put them in a garden or build a bridge out of them, suddenly they become stones.
- When a pig hits 120 pounds, it's a hog.
I thought I might do an occasional series on easily confounded concepts in programming language design.
Here’s a question I get fairly often:
public class C
{
public static void DoIt<T>(T t)
{
ReallyDoIt(t);
}
private static void ReallyDoIt(string s)
{
System.Console.WriteLine("string");
}
private static void ReallyDoIt<T>(T t)
{
System.Console.WriteLine("everything else");
}
}
What happens when you call C.DoIt<string>? Many people expected that “string” is printed, when in fact “everything else” is always printed, no matter what T is.
The C# specification says that when you have a choice between calling ReallyDoIt<string>(string) and ReallyDoIt(string) – that is, when the choice is between two methods that have identical signatures, but one gets that signature via generic substitution – then we pick the “natural” signature over the “substituted” signature. Why don’t we do that in this case?
Because that’s not the choice that is presented. If you had said
ReallyDoIt("hello world");
then we would pick the “natural” version. But you didn’t pass something known to the compiler to be a string. You passed something known to be a T, an unconstrained type parameter, and hence it could be anything. So, the overload resolution algorithm reasons, is there a method that can always take anything? Yes, there is.
This illustrates that generics in C# are not like templates in C++. You can think of templates as a fancy-pants search-and-replace mechanism. When you say DoIt<string> in a template, the compiler conceptually searches out all uses of “T”, replaces them with “string”, and then compiles the resulting source code. Overload resolution proceeds with the substituted type arguments known, and the generated code then reflects the results of that overload resolution.
That’s not how generic types work; generic types are, well, generic. We do the overload resolution once and bake in the result. We do not change it at runtime when someone, possibly in an entirely different assembly, uses string as a type argument to the method. The IL we’ve generated for the generic type already has the method its going to call picked out. The jitter does not say “well, I happen to know that if we asked the C# compiler to execute right now with this additional information then it would have picked a different overload. Let me rewrite the generated code to ignore the code that the C# compiler originally generated...” The jitter knows nothing about the rules of C#.
Essentially, the case above is no different from this:
public class C
{
public static void DoIt(object t)
{
ReallyDoIt(t);
}
private static void ReallyDoIt(string s)
{
System.Console.WriteLine("string");
}
private static void ReallyDoIt(object t)
{
System.Console.WriteLine("everything else");
}
}
When the compiler generates the code for the call to ReallyDoIt, it picks the object version because that’s the best it can do. If someone calls this with a string, then it still goes to the object version.
Now, if you do want overload resolution to be re-executed at runtime based on the runtime types of the arguments, we can do that for you; that’s what the new “dynamic” feature does in C# 4.0. Just replace “object” with “dynamic” and when you make a call involving that object, we’ll run the overload resolution algorithm at runtime and dynamically spit code that calls the method that the compiler would have picked, had it known all the runtime types at compile time.
Comments
Anonymous
July 30, 2009
Ethernet used to consist of a single piece of cable trailing round the building with each computer attached to it by a short piece of cable. So only one computer could (usefully) transmit at a time. A hub replaces the long cable. Each computer connects to the hub using twisted pair cable. A switch is a smart hub that allows different pairs of computers to communicate at the same time. A router routes packets between networks. This doesn't tell the whole story (e.g. hubs can be arranged in a tree). And yes, it has nothing to do with the point you were making.Anonymous
July 30, 2009
Using dynamic in this way is how I now choose to implement the C# equivalent of partial specialization. Prior to dynamic, the only alternatives were to use extension methods (which was fragile and confusing) or implement your own dynamic dispatch using delegates.Anonymous
July 30, 2009
What happens if you have a type constraint applied to T? Such as: public static void DoIt<T>(T t) where T : String
... bad example constraining to the type string (since string is sealed it makes for a very specific constraint), but you get the idea. Such a constraint is illegal. If you wanted T to be only string then why would you make it generic in the first place? -- EricAnonymous
July 30, 2009
The comment has been removedAnonymous
July 30, 2009
eric - why do these posts not appear simultaneously in your RSS feed?Anonymous
July 30, 2009
A hub is an indiscrete gossip that repeats everything it hears on one port to all its other ports. A switch is a discrete messenger which delivers anything it hears on any port only to those ports that need to know. a router is an awkward post master that won't deliver anything if it isn't properly addressed.Anonymous
July 30, 2009
David Morton actually had a great blog post about how it will be different in C# 4.0 using the dynamic keyword (what Eric mentioned at the end of his post). See it here: http://blog.davemorton.net/2009/05/dynamic-type-and-runtime-overload.htmlAnonymous
July 30, 2009
Just a "reminder" to everyone... dynamic will NOT come close to duplicating what C++ template do....it is something completely different [not better or worse...but very different] C++ templates do ALL of their work at compile time. There are NO runtime decisions made. So from a performance perspective, templares and (pre-dynamic) generics have very similar performance characteristics. When dynamic is used, all of the work gets moved into the runtime. Of course much will depend on the internals of C#/CLR and other aspects will depend on usage; but just consider what would happen (to performance) if a person writes image procesing code there each pixel gets passed to a method as a parameter that is "dynamic"..... I am just waiting until we see an "explosion" of places where dynamic is used because it "seemed like a good idea", and the application suffers enough that my company gets called in to address "performance issues".Anonymous
July 30, 2009
TheCPUWizard said: So from a performance perspective, templares and (pre-dynamic) generics have very similar performance characteristics. This is definitely not true. An array type meets the constraints for IEnumerable. If I write a foreach loop against a type parameter (constrained to IEnumerable), the behavior is very different. With templates, I get efficient array iteration with no bounds checking. With generics, I get virtual calls to MoveNext and Current. If the template wants to do something special for arrays and std::vector (because it knows the data are stored contiguously) it can. Generics can't. .NET manages to do spot optimization of generics only when working with type parameters which are value types, otherwise the optimizer is pretty much helpless. And this doesn't even begin to address the things that parameters that aren't types enable for templates... many of which are huge perf wins. Of course, templates being fully instantiated at compile-time, don't provide any mechanism for extensibility. Dynamic does (at a price of course).Anonymous
July 30, 2009
Oh, and for the other matter: Hubs repeat all incoming traffic to all other ports. Bridging hubs are a little better, they work on a packet level and can queue up traffic when there's a collision instead of discarding it (needed for say translating between segments with different speeds). Switches look at the layer 2 (ethernet, typically) destination address to decide which port to forward a packet through. Usually the list of addresses reachable via each port is learned automatically by observing traffic. Packets where the connectivity of the destination isn't known are flooded to all ports, like the hub. Routers look at the layer 3 (IP, typically) destination address to decide which port to forward a packet through. The list of addresses (grouped into binary blocks) reachable via each port is managed either through manual configuration or exchange with peer routers. Packets where the connectivity of the destination isn't known are dropped.Anonymous
July 30, 2009
Hi Eric. Great Post (as usual). I'd really appreciate it if you could do a post on this (if you haven’t already).
using System; namespace OhDear { class Program { static void Main() { Do(() => { }, question => { }); Do(() => { throw new Exception("test"); }, question => { }); Do(() => { }, (Exception question) => { }); Do(() => { throw new Exception("test"); }, (Exception question) => { }); } static void Do(Action action, Action<Exception> errorHandler) { Console.WriteLine("ONE"); } static void Do<T>(Func<T> action, Action<T> callBack) { Console.WriteLine("TWO"); } } } Expected output; ONE ONE ONE ONE Actual output; ONE ONE ONE TWO
Anonymous
July 30, 2009
"This illustrates that generics in C# are not like templates in C++." So was the choice to give them a syntax very much like templates in C++ done out of a desire to deliberately confuse programmers? Something I've picked up in my years as a developer is to not create something, e.g. an API, that looks and feels a lot like an existing something else which is similar (call it "A"), but whose use cases and/or implementation is actually different in subtle and confusing ways. Either make it so the implementation is not different from "A" at all, or make it so that the implementation notices and squawks loudly if you try to use it as if it were an "A", or if none of those are possible make it so that it looks as different from "A" as you possibly can. Has anyone else found this?Anonymous
July 30, 2009
"So was the choice to give them a syntax very much like templates in C++ done out of a desire to deliberately confuse programmers?" C# has other confusing areas. For instance, C# uses the C++ ~destructor syntax, but the behavior is (as we know) very different. This is very confusing for C++ programmers.Anonymous
July 30, 2009
The comment has been removedAnonymous
July 30, 2009
The comment has been removedAnonymous
July 30, 2009
'Why not: "C++ has other confusing areas. For instance, C++ uses the C# ~destructor syntax, but the behavior is (as we know) very different. This is very confusing for C# programmers."' Uh, because C++ was written first, and C#'s syntax was clearly based on C++, not vice-versa. C++ could not have been written differently in order to avoid confusion with C#, as C# syntax had not been invented yet. It has something to do with the linearity of time, cause and effect, and other related concepts.Anonymous
July 30, 2009
The comment has been removedAnonymous
July 31, 2009
The comment has been removedAnonymous
July 31, 2009
The comment has been removedAnonymous
July 31, 2009
@James Miles - That's interesting (to me, anyway). I've boiled it down to: static void Main() { Do(() => { throw new Exception(); }); } static void Do(Action a) { Console.WriteLine("Expected"); } static void Do(Func<string> d) { Console.WriteLine("Unexpected (but actual)"); } In other words, a lambda has a throw making the end unreachable, and that makes it match Func<ANYTHING> better than Action, which does seem strange. Even more strangely, you can get your expected behaviour by sticking a 'return;' at the end of the lambda: Do(() => { throw new Exception(); return; }); Though I bet Eric will tell us that there's some other situation where we'd be amazed if it didn't behave like this! :)Anonymous
July 31, 2009
The comment has been removedAnonymous
August 02, 2009
"Even more strangely, you can get your expected behaviour by sticking a 'return;'" Daniel Earwicker - Yes it is strange isn't it ;)Anonymous
August 03, 2009
I think you've missed the core difference between a template and a generic -- at least for C++ people. The parameter of a template can be anything -- a number, a type, a global variable, etc. And it can apply to a free function or a class. This allows us to do computations at compile time. See boost and loki for examples of the power this allows us -- inline LL parsers, simple lambda functions, and precompiled regular expressions for just a few examples. These things are not possible using generics -- they require other language features. They aren't necessarily better in all cases, but they are certainly different at a more fundamental level than pointed out in the article.Anonymous
August 03, 2009
The comment has been removedAnonymous
August 03, 2009
The comment has been removedAnonymous
August 03, 2009
The comment has been removedAnonymous
August 05, 2009
@ Daniel He does say that, but completely misses the major implications of it. The template is fundamentally more powerful than the C# generic, but at the same time, it cannot be used cross-language. It isn't better or worse. Furthermore, shared_ptr is more suitable for C++ applications than mark and sweep garbage collection since it is completely synchronous. The lifetime of every scope-bound object in the system has a predictable lifetime, and when it goes out of scope or gets deleted clean up is done immediately. While this may not be quite as efficient overall as the C# model, for many applications it is preferable to be predictable. Real time apps and OS's come to mind. Shared_ptr is a compromise in this direction, and certainly has its place. Again, for some apps, better, for others worse. That's why we like .NET. It allows us to use the paradigms we need to get the job done.Anonymous
August 07, 2009
"C# generics have the same syntax as Java generics, which work similarly." - uh? Java generics and C# generics work completely differently! Java generics are purely a compile time illusion: there is no such thing, at runtime, as an ArrayList<String> - just an ArrayList. The compiler keeps track of the compile time types and gives you some helpful error messages if you bypass type-safety, but you can bypass the error messages - eg by casting your ArrayList<String> to an ArrayList and then to an ArrayList<Object>, and put in something other than strings - and they will be accepted at runtime because the runtime isn't even aware that ArrayList was generic in the first place! Also, Java allows types to be partially unbound, so ArrayList<?> is also a legal type which you can have instances of and perform operations on. C# does not have any concept of List<?> at compiletime except as an argument to typeof(). Not only that, but it doesn't have a concept of List<?> at runtime, either. Any given instance of List<T> has a particular T that it applies to. Attempting to cast that list to a List of a different<T> would fail. Attempting to put other kinds of object other than String into a List<String> would be impossible (because to do so you'd have to write code that would fail with a class cast exception before it even got to the Add() call). Java and C# generics are just as different as C# generics are from C++ templates. They use the same syntax because they have more in common than different. And that's as it should be. Sure, it's confusing when you encounter one of the comparatively obscure things that they do differently. But that's outweighed by the fact that you can get a general sense of the code based on what they are doing the same. A halfway decent programmer learns a new language, initially, by learning how to map its syntax to concepts he or she is familiar with from other languages, ANYWAY. Even if C# had decided to say that generics should be expressed as List~T~, C++ programmers coming to C# would still mentally map that to List<T> to start with to be able to get the basic idea of what it's for. And only AFTER that get a deep enough understanding to grasp the subtle differences.Anonymous
August 09, 2009
"They were creating a new language, period, and any resemblance to any other language is purely coincidental." Come on. We all know other C-style languages influenced C#. They could've chosen the VB syntax for generics, but they didn't. It's not purely coincidental, if it were C# wouldn't look like it did.Anonymous
August 24, 2009
@author: Templates like in C++ are a bit more than fancy-pants search&replace you know :) I'm just writing to ask you: What have stopped the C#/CLR designer from actually allowing to specialize the generic methods? Having: method<T>(T arg), method(string arg), method(int arg) a compiler knows about ALL possible overloads. Easiest way would be to emit a prologue for method<T>(T) that checks "if arg is string" "if arg is int" and thus call the appropriate 'overload' at runtime even if someone calls method((object)string). Now the programmers must do that all the time by hand if they want to have any specialization-like features :/ IMHO, not the C# compiler shall, but rather the CLR should perform such lookup and choose the right, tightest match at runtime, but with all other languages on the platform, I can understand the option taken there. But why not in C#? Rarely you have more than 1-6 specializations, so not that big performance hit at all. @ComeOn Aggreed with that. It's very name and symbol claims that. Early marketing joke was, that C# is actually C++++ (two rows with ++). The evolution of the language shows heavy impact of changes made to independently evolving C++ and Java. heh, I ven remember that when C# was born, it was claimed that it is being created in a such way, that existing C++ and Java programmers will not notice much difference and can start coding in C# right away with little fuss. Maybe it's still written somewhere on Microsoft's pages?Anonymous
August 28, 2009
@Joel Redman - this is now off topic and probably too late for you to read it, but I gotta take issue with this: "Furthermore, shared_ptr is more suitable for C++ applications than mark and sweep garbage collection since it is completely synchronous. The lifetime of every scope-bound object in the system has a predictable lifetime, and when it goes out of scope or gets deleted clean up is done immediately." I hear/read that a lot, and I don't agree. When you use shared_ptr (or any kind of ref-counting smart ptr) you're doing so because you don't know locally whether it is time to destroy the object. Therefore when the program exits the scope of the shared_ptr, you don't know for sure that the object has been destroyed. So in practise there's nothing deterministic about it. It may happen sooner than it would with real GC, but it's no more deterministic in reality. If you want to know for sure that an object is definitely destroyed when you exit a specific scope, then use a normal variable or auto_ptr. Don't use shared_ptr. C++/CLI is a great resource for clarifying the distinction and integration point between RAII and GC, because it quite beautifully combines the two in a way that makes me rather envious. I wish C# could write Dispose methods for me! So far it only has the 'using' statement to make it easy to consume disposable objects, but nothing much to assist with implementing them.Anonymous
August 29, 2009
whoa. where do you see sensible RAII in C# ? in using/Dispose? 'dispose' thing is a patch for nonexistence of destructors, and using - for of deterministic cleanup, and it doesnt more than calling dispose anyways.. i lately heard a lot from other programmers that using-this using-that, use-using-dont-call-dispose-manually, they really think that using() is doing some cleanup and frees memory.. please, finally stop publishing this rubbish, people really can start believing in it