A contravariance conundrum

Suppose we have my usual hierarchy of types, Animal, Giraffe, etc, with the obvious type relationships. An IEqualityComparer<T> is contravariant in its type parameter; if we have a device which can compare two Animals for equality then it can compare two Giraffes for equality as well. So why does this code fail to compile?

IEqualityComparer<Animal> animalComparer = whatever;
IEnumerable<Giraffe> giraffes = whatever;
IEnumerable<Giraffe> distinct = giraffes.Distinct(animalComparer);

This illustrates a subtle and slightly unfortunate design choice in the method type inference algorithm, which of course was designed long before covariance and contravariance were added to the language.

Continue reading

What is the type of the null literal?

The C# 2.0 specification says

The null literal evaluates to the null value, which is used to denote a reference not pointing at any object or array, or the absence of a value. The null type has a single value, which is the null value.

But every version of the specification since then does not contain this language. So what then is the type of the null literal expression?

Continue reading

Why does a foreach loop silently insert an “explicit” conversion?

The C# specification defines

foreach (V v in x) 

as having the same semantics as:

  E e = ((C)(x)).GetEnumerator();
    V v;  // Inside the while in C# 5.
    while (e.MoveNext()) 
      v = (V)e.Current;
    // necessary code to dispose e

(Actually this is not exactly what the spec says; I’ve made one small edit because I don’t want to get into the difference between the element type and the loop variable type in this episode.)

There are a lot of subtleties here that we’ve discussed before; what I want to talk about today is the explicit conversion from e.Current to V. On the face of it this seems very problematic; that’s an explicit conversion. The collection could be a list of longs and V could be int; normally C# would not allow a conversion from long to int without a cast operator appearing in the source code. (Or the long being a constant that fits into an int.) What justifies this odd design choice?

Continue reading

Why not allow double/decimal implicit conversions?

I’ve talked a lot about floating point math over the years in this blog, but a quick refresher is in order for this episode.

A double represents a number of the form +/- (1 + F / 252 ) x 2E-1023, where F is a 52 bit unsigned integer and E is an 11 bit unsigned integer; that makes 63 bits and the remaining bit is the sign, zero for positive, one for negative. You’ll note that there is no way to represent zero in this format, so by convention if F and E are both zero, the value is zero. (And similarly there are other reserved bit patterns for infinities, NaN and denormalized floats which we will not get into today.)

A decimal represents a number in the form +/- V / 10X where V is a 96 bit unsigned integer and X is an integer between 0 and 28.

Both are of course “floating point” because the number of bits of precision in each case is fixed, but the position of the decimal point can effectively vary as the exponent changes.
Continue reading

Ask the Bug Guys

Today on the Coverity Development Testing blog we’ve announced a new recurring feature: Ask the Bug Guys. If you’ve got a question about a strange behavior that caused a bug in a C#, Java, C or C++ program, or an interesting story to share about finding and fixing bugs, consider sending it to TheBugGuys@coverity.com. I’ll be reviewing the C# bugs, and my colleagues Jon and Tim will be looking at the C, C++ and Java submissions.

We of course cannot promise to write up an analysis of all submissions, but we will choose a selection of the most interesting and informative bugs and periodically post an analysis of them on the blog. Including a small, complete example that clearly demonstrates the bug would be helpful.

Why are generic constraints not inherited?

Today’s episode is presented as a dialogue:

Why are generic constraints not inherited?

Members are inherited. Generic constraints are not members of a type.

But generic constraints are inherited on generic methods, right?

That’s true, though what is inherited is the method and the constraint comes along with it. What is a bit odd is: generic constraints on methods are invisibly inherited when overriding, which has always vexed me. My preferred design would have been to require that the constraint be re-stated. That is, when you say:

class B
  public virtual void M<T>() where T : struct { }
class D : B
  public override void M<U>() { }

U in D.M<U> is still constrained to struct, but it is actually illegal in C# to re-state that fact redundantly! This is a bit of a misfeature in my opinion; it works against code clarity for the reader. Particularly since the base class might not even be in source code; it might be in a different assembly entirely.

(Note that I’m emphasizing here that there is no requirement that the type parameters be named the same. Similarly there is no requirement that the formal parameters be named the same either, but it is a good idea to do so. We’ll come back to this point in a moment.)

Continue reading

Benchmarking mistakes, part three

NOTE: I wrote this series of articles for a web site which went out of business soon thereafter. They asked for a beginner-level series on how to benchmark C# programs. I’ve copied the articles as I wrote them below. Part two is here and part four is here.

As I discussed in part one of this series, a C# program actually goes through two compilers before the code runs. First the C# compiler converts the code into “Common Intermediate Language”, or “IL”, which is written into the assembly — the .EXE or .DLL file of the program. Then at runtime, immediately before a method is called for the first time, the aptly-named “just in time” compiler — the jitter, for short — transforms the IL into actual executable machine code. Because computer programmers love to verb words, this process is called “jitting a method”.

The jitter was built to be fast, but it’s not infinitely fast. You should expect that the first time you run a method it will be considerably slower; before it can run for the first time all its IL has to be translated into machine code. And of course, if the methods that it calls in turn are all being called for the first time then they’ve got to be jitted as well.

But wait, it gets worse. Suppose you are calling a method for the first time, and it in turn creates an object from a library. If that library is being used for the first time in this process, not only does the code for the constructor have to be jitted, but before it can be jitted the library has to be found on disk, mapped into virtual memory, analyzed for security problems, and any code in the static constructors of the newly-created object has to be jitted and executed.

In short, calling code for the first time can be massively more expensive than calling it for the second time. So this brings us to…

Mistake #6: Treat the first run as nothing special when measuring average performance.

In order to get a good result out of a benchmark test in a world with potentially expensive startup costs due to jitting code, loading libraries and calling static constructors, you’ve got to apply some careful thought about what you’re actually measuring.

If, for example, you are benchmarking for the specific purpose of analyzing startup costs then you’re going to want to make sure that you measure only the first run. If on the other hand you are benchmarking part of a service that is going to be running millions of times over many days and you wish to know the average time that will be taken in a typical usage then the high cost of the first run is irrelevant and therefore shouldn’t be part of the average. Whether you include the first run in your timings or not is up to you; my point is, you need to be cognizant of the fact that the first run has potentially very different costs than the second.

Let’s illustrate the enormous effect that the jitter can have on the first run of a program by modifying our example from last time. Let’s suppose we’ve written our own implementation of the standard “quicksort” algorithm and we want to benchmark its performance:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

static class Extensions
  public static void Quicksort(this int[] items)
    Quicksort(items, 0, items.Length - 1);
  static void Quicksort(int[] items, int leftBound, int rightBound)
    int left = leftBound;
    int right = rightBound;
    int pivotIndex = leftBound + (rightBound - leftBound) / 2;
    int pivot = items[pivotIndex]; 
    while (left <= right)
      // Find an item greater than the pivot
      while (items[left] < pivot)
        left += 1;
      // Find an item less than the pivot
      while (pivot < items[right])
        right -= 1;

      // Swap them
      if (left <= right)
        Swap(ref items[left], ref items[right]);
        left += 1;
        right -= 1;

    // Everything less than the pivot is now left of the pivot.
    // Sort this portion.
    if (leftBound < right)
      Quicksort(items, leftBound, right);
    // Same for the right.
    if (left < rightBound)
      Quicksort(items, left, rightBound);        
  private static void Swap(ref int x, ref int y)
    int t = x;
    x = y;
    y = t;

That’s a pretty standard implementation of quicksort in C#. Now let’s make some modifications to our benchmark test of last time. Here we’ll make a random list, copy it to an array twice so that we know that both runs will be operating on exactly the same data, and see if we can deduce the cost of jitting those methods the first time they’re called:

class P
  static void Main()
    var original = new List<int>();
    const int size = 1000;
    var random = new Random();
    for(int i = 0; i < size; ++i)

    var arr1 = original.ToArray();
    var arr2 = original.ToArray();

    var stopwatch = new System.Diagnostics.Stopwatch();

When I run this on my laptop (again, remembering to compile into release mode, and running without the debugger attached) a typical result is 3500 microseconds for the first run and 700 microseconds for the second run; in other words, the first run here took roughly five times longer than the second run on average. It must have taken the jitter about 2.8 milliseconds on average to find the IL and translate it into efficient machine code.

Of course, that factor is relative, and I chose the array size somewhat arbitrarily. If we were sorting an array with a million elements then the ~3 millisecond jit cost would be a barely-noticeable bump. If we were sorting an array with twenty elements then the jit cost wouldn’t be five times worse; it could be a hundred times worse.

Moreover, it’s important to note that different jitters give different results on different machines and in different versions of the .NET framework. The time taken to jit can vary greatly, as can the amount of optimization generated in the machine code. The jit compilers on the Windows 32 bit desktop, Windows 64 bit desktop, Silverlight running on a Mac, and the “compact” jitter that runs when you have a C# program in XNA on XBOX 360 all have potentially different performance characteristics. That’s…

Mistake #7: Assuming that runtime characteristics in one environment tell you what behavior will be in a different environment.

Run your benchmarks in the actual environment that the code will be running in; use machines that have the same hardware and software that will typically be used by the customers who ultimately will run the code.

Next time in this series we’ll take a look at how the garbage collector can affect performance benchmarks.

The psychology of C# analysis

developersThe organizers of the recent Static Analysis Symposium — conveniently held four blocks from my office — were kind enough to invite me to give the opening talk. Now, this is a conference where the presentations have titles like “Efficient Generation of Correctness Certificates for the Abstract Domain of Polyhedra“; I know what all those words mean individually, it’s just them next to each other in that order that I don’t understand. Fortunately for me, the SAS organizers invite people in industry to give talks about the less academic, more pragmatic aspects of program analysis, which I was happy to do.

They also let me pad my presentation with funny pictures of cats, which helped a lot.

Unfortunately I don’t have a recording of the talk, but my slides are posted here if you want to check them out.

Special thanks to Scott Meyer of BasicInstructions.net who was kind enough to allow me to use his comic about informative presentations in my informative presentation.

The answer to the string concatenation puzzle

Earlier on FAIC I asked for code that parses as an expression that produces different results for

s = s + expr;


s += expr;

This is a pretty easy puzzle; the answers posted in the comments could largely be grouped into two buckets. The first, which is a bit silly, are expressions which always produce a different value, so of course they produce different results in those two cases.

s = s + Guid.NewGuid();

produces a different result than

s += Guid.NewGuid();

but then again, it also produces different results every time you call

s += Guid.NewGuid();

so that’s not a particularly interesting answer.

Continue reading