Nullable micro-optimizations, part one

Which is faster, Nullable<T>.Value or Nullable<T>.GetValueOrDefault()?

Before I answer that question, my standard response to "which horse is faster?" questions applies. Read that first.

.
.
.

Welcome back. But again, before I answer the question I need to point out that the potential performance difference between these two mechanisms for obtaining the non-nullable value of a nullable value type is a consequence of the fact that these two mechanisms are not semantically equivalent. The former may legally only be called if you are sure that the nullable value is non-null;1 the latter may be called on any nullable value. A glance at a simplified version of the source code illustrates the difference.

struct Nullable<T> where T : struct
{
  private bool hasValue;
  private T value;
  public Nullable(T value)
  {
    this.hasValue = true;
    this.value = value;
  }
  public bool HasValue { get { return this.hasValue; } }
  public T Value
  {
    get
    {
      if (!this.HasValue) throw something;
      return this.value;
    }
  }
  public T GetValueOrDefault() 
  {
    return this.value; 
  }
  ... and then all the other conversion gear and so on ...
}

The first thing to notice is that a nullable value type's ability to represent a "null" integer or decimal or whatever is not magical.2 A nullable value type is nothing more than an instance of the value type plus a bool saying whether it's null or not.

If a variable of nullable value type is initialized with the default constructor then the hasValue field will be its default value, false, and the value field will be default(T). If it is initialized with the declared constructor then of course the hasValue field is true and the value field is any legal value, including possibly T's default value. Thus, the implementation of GetValueOrDefault() need not check the flag; if the flag is true then the value field is set correctly, and if it is false, then it is set to the default value of T.

Looking at the code it should be clear that Value is almost certainly not faster than GetValueOrDefault() because obviously the former does exactly the same work as the latter in the success case, plus the additional work of the flag check. Moreover, because GetValueOrDefault() is so brain-dead simple, the jitter is highly likely to perform an inlining optimization.3 How the jitter chooses to inline or not is an implementation detail, but it is reasonable to assume that it is less likely to perform an inlining optimization on code that contains more than one "basic block"4 and explicitly throws.

It should also be clear that though the relative performance difference might be large, the absolute difference is small. A call, field fetch, conditional jump and return in the typical case makes up the difference, and those things are each only nanoseconds.

Now, this is of course not to say that you should willy-nilly change all your calls to Value to GetValueOrDefault() for performance reasons. Read my rant again if you have the urge to do that! Don't go changing working, debugged, tested code in order to obtain a performance benefit that is (1) highly unlikely to be a real bottleneck, and (2) highly unlikely to be your worst performance problem.

And besides, using Value has the nice property that if you have made a mistake and fetched the value of a null, you'll get an exception that informs you of where your bug is! Code that draws attention to its faults is a good thing.5


Next time on FAIC: How does the C# compiler use its knowledge of the facts discussed today to your advantage? Have a great Christmas everyone; we'll pick up this subject again in a week.

  1. Put another way, calling Value without knowing that HasValue is true is a boneheaded exception.
  2. Nullable value types are magical in other ways; for example, there's no way to write your own struct that has the strange boxing behaviour of a nullable value type; an int? boxes to either an int or null, never to a boxed int?.
  3. An inlining optimization is where the jitter eliminates an unnecessary "call" and "return" instruction by simply generating the code of the method body "inline" in the caller. This is a great optimization because doing so can make code both smaller and faster in some cases, though it does make it harder to debug because the debugger has no good way to generate breakpoints inside the inlined method.
  4. A "basic block" is a region of code where you know that the code will execute from the top of the block to the bottom without any "normal" branches in or out of the middle of the block. (A basic block may of course have exceptions thrown out of it.) Many optimizing compilers use "basic blocks" as an abstraction because it abstracts away the unnecessary details of what the block actually does, and treats it solely as a node in a flow control graph.
  5. Note that here we have one of those rare cases where the frameworks design guidelines have been deliberately bent. We have a "Get" method is actually faster than a property getter, and the property getter throws! Normally you expect the opposite: the "Get" method is usually the one that is slow and can throw, and the property is the one that is fast and never throws. Though this is somewhat unfortunate, remember, the design guidelines are our servants, not our masters, and they are guidelines, not rules.

Null is not false, part one

The way you typically represent a "missing" or "invalid" value in C# is to use the "null" value of the type. Every reference type has a "null" value; that is, the reference that does not actually refer to anything. And every "normal" value type has a corresponding "nullable" value type which has a null value.

The way these concepts are implemented is completely different. A reference is typically implemented behind the scenes as a 32 or 64 bit number. As we've discussed previously, that number should logically be treated as an "opaque" handle that only the garbage collector knows about, but in practice that number is the offset into the virtual memory space of the process that the referred-to object lives at, inside the managed heap. The number zero is reserved as the representation of null because the operating system reserves the first few pages of virtual memory as invalid, always. There is no chance that by some accident, the zero address is going to be a valid address in the heap.

Continue reading

Inheritance and representation

(Note: Not to be confused with Representation and Identity.)

Here's a question I got this morning:

class Alpha<X>
where X : class
{}
class Bravo<T, U>
where T : class
where U : T
{
  Alpha<U> alpha;
}

This gives a compilation error stating that U cannot be used as a type argument for Alpha's type parameter X because U is not known to be a reference type. But surely U is known to be a reference type because U is constrained to be T, and T is constrained to be a reference type. Is the compiler wrong?

Of course not. Bravo<object, int> is perfectly legal and gives a type argument for U which is not a reference type. All the constraint on U says is that U must inherit from T.1 int inherits from object, so it meets the constraint. All struct types inherit from at least two reference types, and some of them inherit from many more.2

The right thing for the developer to do here is of course to add the reference type constraint to U as well.

That easily-solved problem got me thinking a bit more deeply about the issue. I think a lot of people don't have a really solid understanding of what "inheritance" means in C#. It is really quite simple: a derived type which inherits from a base type implicitly has all inheritable members of the base type. That's it! If a base type has a member M then a type that inherits from it has a member M as well.3

People sometimes ask me if private members are inherited; surely not! What would that even mean? But yes, private members are inherited, though most of the time it makes no difference because the private member cannot be accessed outside of its accessibility domain. However, if the derived class is inside the accessibility domain then it becomes clear that yes, private members are inherited:

class B
{
  private int x;
  private class D : B
  {

D inherits x from B, and since D is inside the accessibility domain of x, it can use x no problem.

I am occasionally asked "but how can a value type, like int, which is 32 bits of memory, no more, no less, possibly inherit from object?  An object laid out in memory is way bigger than 32 bits; it's got a sync block and a virtual function table and all kinds of stuff in there."  Apparently lots of people think that inheritance has something to do with how a value is laid out in memory. But how a value is laid out in memory is an implementation detail, not a contractual obligation of the inheritance relationship! When we say that int inherits from object, what we mean is that if object has a member -- say, ToString -- then int has that member as well. When you call ToString on something of compile-time type object, the compiler generates code which goes and looks up that method in the object's virtual function table at runtime. When you call ToString on something of compile-time type int, the compiler knows that int is a sealed value type that overrides ToString, and generates code which calls that function directly. And when you box an int, then at runtime we do lay out an int the same way that any reference-typed object is laid out in memory.

But there is no requirement that int and object be always laid out the same in memory just because one inherits from the other; all that is required is that there be some way for the compiler to generate code that honours the inheritance relationship.

  1. More specifically, it must inherit from T or be identical to T, or inherit from a type related to T by some variant conversion. Consult the specification for details.
  2. Enum types inherit from System.Enum, many struct types implement interface types, and so on.
  3. Of course that's not quite it; there are some odd corner cases. For example, a class which "inherits" from an interface must have an implementation of every member of that interface, but it could do an explicit interface implementation rather than exposing the interface's members as its own members. This is yet another reason why I'm not thrilled that we chose the word "inherits" over "implements" to describe interface implementations. Also, certain members like destructors and constructors are not inheritable.

To box or not to box

Suppose you have an immutable value type that is also disposable. Perhaps it represents some sort of handle.

struct MyHandle : IDisposable
{
  public MyHandle(int handle) : this() { this.Handle = handle; }
  public int Handle { get; private set; }
  public void Dispose() 
  {
    Somehow.Close(this.Handle);
  }
}

You might think hey, you know, I'll decrease my probability of closing the same handle twice by making the struct mutate itself on disposal!

public void Dispose()
{
  if (this.Handle != 0)
    Somehow.Close(this.Handle);
  this.Handle = 0;
}

This should already be raising red flags in your mind. We're mutating a value type, which we know is dangerous because value types are copied by value; you're mutating a variable, and different variables can hold copies of the same value. Mutating one variable does not mutate the others, any more than changing one variable that contains 12 changes every variable in the program that also contains 12. But let's go with it for now.

What does this do?
Continue reading

Debunking another myth about value types

Here's another myth about value types that I sometimes hear:

"Obviously, using the new operator on a reference type allocates memory on the heap. But a value type is called a value type because it stores its own value, not a reference to its value. Therefore, using the new operator on a value type allocates no additional memory. Rather, the memory already allocated for the value is used."

That seems plausible, right? Suppose you have an assignment to, say, a field s of type S:

s = new S(123, 456);

If S is a reference type then this allocates new memory out of the long-term garbage collected pool, a.k.a. "the heap", and makes s refer to that storage. But if S is a value type then there is no need to allocate new storage because we already have the storage. The variable s already exists and we're going to call the constructor on it, right?

The C# specification says no, that's not what we do. But as we'll see in a minute, things are a bit more complicated.

It is instructive to ask "what if the myth were true?" Suppose it were the case that the statement above meant "determine the memory location to which the constructed type is being assigned, and pass a reference to that memory location as the 'this' reference in the constructor". Consider the following class defined in a single-threaded program (for the remainder of this article I am considering only single-threaded scenarios; the guarantees in multi-threaded scenarios are much weaker.)

using System;
struct S
{
  private int x;
  private int y;
  public int X { get { return x; } }
  public int Y { get { return y; } }
  public S(int x, int y, Action callback)
  {
    if (x > y)
      throw new Exception();
    callback();
    this.x = x;
    callback();
    this.y = y;
    callback();
  }
}

We have an immutable struct which throws an exception if x > y. Therefore it should be impossible to ever get an instance of S where x > y, right? That's the point of this invariant. But watch:

static class P
{
  static void Main()
  {
    S s = default(S);
    Action callback = ()=>{Console.WriteLine("{0}, {1}", s.X, s.Y);};
    s = new S(1, 2, callback);
    s = new S(3, 4, callback);
  }
}

Again, remember that we are supposing the myth I stated above to be the truth. What happens?

  • First we make a storage location for local variable s. (Because s is an outer variable used in a lambda, this storage is on the heap. But the location of the storage for s is irrelevant to today's myth, so let's not consider it further.)
  • We assign a default S to s; this does not call any constructor. Rather it simply assigns zero to both x and y.
  • We make the action.
  • We (mythically) obtain a reference to s and use it for the 'this' to the constructor call. The constructor calls the callback three times.
  • The first time, s is still (0, 0).
  • The second time, x has been mutated, so s is (1, 0), violating our precondition that X is not observed to be greater than Y.
  • The third time s is (1, 2).
  • Now we do it again, and again, the callback observes (1, 2), (3, 2) and (3, 4), violating the condition that X must not be observed to be greater than Y.

This is horrid. We have a perfectly sensible precondition that looks like it should never be violated because we have an immutable value type that checks its state in the constructor. And yet, in our mythical world, it is violated.

Here's another way to demonstrate that this is mythical. Add another constructor to S:

public S(int x, int y, bool panic)
{
  if (x > y)
    throw new Exception();
  this.x = x;
  if (panic)
    throw new Exception();
  this.y = y;
}

We have

static class P
{
  static void Main()
  {
    S s = default(S);
    try
    {
      s = new S(1, 2, false);
      s = new S(3, 4, true);
    }
    catch(Exception ex)
    {
      Console.WriteLine("{0}, {1}", s.X, s.Y);};
    }
  }
}

Again, remember that we are supposing the myth I stated above to be the truth. What happens? If the storage of s is mutated by the first constructor and then partially mutated by the second constructor, then again, the catch block observes the object in an inconsistent state. Assuming the myth to be true. Which it is not. The mythical part is right here:

Therefore, using the new operator on a value type allocates no additional memory. Rather, the memory already allocated for the value is used.

That's not true, and as we've just seen, if it were true then it would be possible to write some really bad code. The fact is that both statements are false. The C# specification is clear on this point:

If T is a struct type, an instance of T is created by allocating a temporary local variable

That is, the statement

s = new S(123, 456);

actually means:

  • Determine the location referred to by s.
  • Allocate a temporary variable t of type S, initialized to its default value.
  • Run the constructor, passing a reference to t for "this".
  • Make a by-value copy of t to s.

This is as it should be. The operations happen in a predictable order: first the "new" runs, and then the "assignment" runs. In the mythical explanation, there is no assignment; it vanishes. And now the variable s is never observed to be in an inconsistent state. The only code that can observe x being greater than y is code in the constructor. Construction followed by assignment becomes "atomic".1

In the real world if you run the first version of the code above you see that s does not mutate until the constructor is done. You get (0,0) three times and then (1,2) three times. Similarly, in the second version s is observed to still be (1,2); only the temporary was mutated when the exception happened.

I said that things were more complicated than they seemed. In fact if the target of the assignment is a stack-allocated local variable (and not a field in a closure) that is declared at the same level of "try" nesting as the constructor call then we do not go through this rigamarole of making a new temporary, initializing the temporary, and copying it to the local. In that specific (and common) case we can optimize away the creation of the temporary and the copy because it is impossible for a C# program to observe the difference! But conceptually you should think of the creation as a creation-then-copy rather than a creation-in-place; that it sometimes can be in-place is an implementation detail that you should not rely upon.

  1. Again, I am referring to single-threaded scenarios here. If the variable s can be observed on different threads then it can be observed to be in an inconsistent state because copying any struct larger than an int is not guaranteed to be a threadsafe atomic operation.