Debunking another myth about value types

Debunking another myth about value types

Rate This
  • Comments 40

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?

Wrong. That is not what the C# spec says and not what we do. (Commenter Wesner Moise points out that yes, that is sometimes what we do. More on that in a minute.)

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 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"(*).

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.

Now, what about Wesner's point? Yes, in fact if it 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.

----------------------------

(*) 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.

 

  • M.E. wrote:

    > If I could write "public sealed readonly class CostOfALumpOfCheese" and then declare a non-nullable variable

    > "CostOfALumpOfCheese! cheeseCost" (where '!' is the opposite of '?')

    Yes, that is it. A programmer should not have to deal with such implementation details as value or reference types. It should be up to the compiler / JITer to optimize sealed readonly "classes" in non-nullable variables which are relativly small in size and optimize them as it sees fit by making value types out of them. But a programmer should not need the distinction. We much more need a distinction between mutable and non-mutable (as you specified with readonly) types than we need a distinction between value types and reference types.

    Stephan Leclercq wrote:

    > Clearly, your example code is severely flawed. If your invariant is that x>y, then you cannot call the callback between the

    > assignment of this.x and this.y.

    why? The called function has no way of getting at the intermediate values (I think). Just as Eric wrote, you get 0,0 three times (since the values will be copied after the constuctor is done and no external code can access the intermediate copy). 0,0 satisfies the invariant (remeber x>y results in an exception, meaning the invariant is x is less than or equal y, which 0,0 satisfies).

    If you use structs, you have to accept the fact that someone can make a default struct wich should satisfy your invariants or you made a wrong design choice.

  • You don't need to construct a new instance of S over the top of an old one to get that invariant to fail for one of those callbacks. Just pass (-2, -1) and the invariant will fail for the second callback.

    One good reason to carefully manage dynamic memory allocation is when you're using the Compact Framework. For example take a look at at: blogs.msdn.com/.../713396.aspx

  • Surely the x and y referred to in the conditional test are the parameters to the constructor and NOT the private member fields of the structure?  One would have to use 'this.x' and 'this.y' to refer to the member fields.  Thus, I don't see a case here where x is > y and any exception should be thrown.  What am I missing?

  • [pedants corner...]

    > because copying any struct larger than an int is not guaranteed to be a threadsafe atomic operation

    For the CLI, an IntPtr is atomic, not an int. For C#, an int (and other 32bit values) are guaranteed atomic.

    So for a 16bit CLR, 32bit values are atomic, whereas for a 64bit CLR, any 64bit value is atomic.

    ....according to the specs at any rate....

  • marc: Hopefully you will read through the posts again and see that value types have significant semantic differences from reference types, such that you can't turn a class into a struct without breaking things. The whole point of a value type is that it doesn't have any memory overhead (so an array of a million ints takes 4MB instead of 12MB), meaning that it doesn't include storage for the monitor (to enable the "lock" statement) or type information (to enable things like co-/contravariance).

    What the runtime *could* do is optimize reference types to allocate them on the stack instead of the heap when it knows that that there's no danger that the reference will escape the current method. However, heap allocation is no more expensive than stack allocation in the CLR (as opposed to C++ where allocating on the heap can be expensive), so the optimization only reduces the load on the garbage collector. Presumably since this is a non-trivial optimization to detect (you'd have to prove that no method of the object stores a this-reference anywhere) and may not make things much faster, it's not done at the moment

  • public static void RunSnippet()

    {

       ValueTypeObject x = new ValueTypeObject(1, 2);

    }

    .method public hidebysig static void RunSnippet() cil managed

    {

       .maxstack 3

       .locals init (

           [0] valuetype MyClass/ValueTypeObject x)

       L_0000: nop

       L_0001: ldloca.s x

       L_0003: ldc.i4.1

       L_0004: ldc.i4.2

       L_0005: call instance void MyClass/ValueTypeObject::.ctor(int32, int32)

       L_000a: nop

       L_000b: ret

    }

    C++ allows the compilers to construct directly on the storage of the local variable being initialized.

    In addition, I see no evidence in the example output from Reflector of any additional temporary variable being created to store the initial constructed value.

  • The temporary is stored on the stack, but this becomes a CLR issue, not a C# language issues, as to whether to enable the optimization to initialize directly an previously unused variable. The example in the blog post is not ideal because the local variable is hosted in a compiler-generated display class.

    You make an excellent point Wesner, one which I should have called out in my original article. As an optimization we *can* often initialize "in place" and do so, but only when the consequences of that choice are unobservable. I'll update the text; thanks for the note!

    - Eric

  • Gabe: I know about the semantic differences and the more I read about them, the less I think we should bother a programmer with it.

    So I am not proposing to change C# to be value type / reference type agnostic, but it was mostly a comment to the language construct as a whole, that such a difference should not be made at all. It is too late to do this in C#. The compiler / the CLR could detect if an instance requires monitor and/or type information and provide the storage space if needed. This would basically mean performing the boxing only once if an instance needs to be reference type, but is easy enough to be of value type.

    I still believe that having the assignment and equality operator meaning different things for value / reference types is a source of many (way many) bugs.

  • marc: I'm not sure what you're proposing. Are you suggesting a system like C++ where types are neither value nor reference, but the value/reference aspect is determined at the point of use? Surely you don't want that because it just shifts the problem from the time a type is created to every time it's used!

    Are you instead suggesting that all types should be what are currently considered to be reference types, and make the compiler and runtime responsible for optimizing them where possible to be merely values? If so, the optimization would be extremely rare. A publicly available array of ints, for example, would have to always be an array of references to ints because you never know if some code in another assembly might want to get a reference to one of those ints. Many OO systems don't have value types, and I'm not sure that many of them even attempt this optimization.

  • "Are you instead suggesting that all types should be what are currently considered to be reference types, and make the compiler and runtime responsible for optimizing them where possible to be merely values?"

    I know you weren't talking to me, but I believe I have an answer that makes sense and possibly (?) has some merit. I'm not sure if this is what marc was proposing or not.

    But seems to me that the distinction that's valuable to the programmer is "immutable or not" rather than "value or not". An immutable sealed reference type like string might as well be a value type; a mutable value type is - well, in my opinion - confusing enough that, personally, I'd have no problem making them simply forbidden outside of unsafe code.

    So if there were a way to declare, say, "readonly sealed class X" and have the "readonly" modifier enforce that the class must have value semantics - that is, only have readonly fields and all fields must be of readonly types themselves (and perhaps no finalizer) - then for *those specific types* (and with some other caveats) it perhaps make sense to elide the distinction between value and reference type and make it a purely runtime implementation detail.

    In practice, there are other complications with an approach like that; for example, the question of nullability (an immutable reference type can be; an immutable value type cannot. If we grant that both are semantically "values", shouldn't the nullability question be separate from the storage mechanism? For that matter, why should default(string) be null rather than ""?

    My thought would be that each "readonly" type ought to be able to be used with the ? suffix for nullability, but also that it ought to be able to declare its own default value if it is NOT used with that suffix. And that, as a result, there should not be the restriction that every value type has to accept "all zeros" as a legitimate value; it can declare its own default.

    The CLR would also need a low-level immutable array type in order to support making "string" one of these language-level readonly types.

    All in all, I think it might be a very worthwhile thing to do if someone were redesigning C# from scratch, but I don't think it can be done in a way that's both sane and backward-compatible, because at minimum you'd have to turn every instance of "string" into "string?"...

  • > The whole point of a value type is that it doesn't have any memory overhead (so an array of a million ints takes 4MB

    > instead of 12MB), meaning that it doesn't include storage for the monitor (to enable the "lock" statement) or type

    > information (to enable things like co-/contravariance).

    Now, how am I supposed to know that by declaring something as a value type, I say nothing at all about how that value is allocated in memory, but I DO say something about what extra information the system stores with the object? Eric claims that the first is none of my business, but if so, why is the second my business?

    > Are you suggesting a system like C++ where types are neither value nor reference, but the value/reference aspect is

    > determined at the point of use?

    This does seem like the right model to me.

    > My thought would be that each "readonly" type ought to be able to be used with the ? suffix for nullability, but also that it

    > ought to be able to declare its own default value if it is NOT used with that suffix. And that, as a result, there should not be > the restriction that every value type has to accept "all zeros" as a legitimate value; it can declare its own default.

    This is an interesting suggestion, because one often does run into situations (as in the article) where you want a struct to follow some invariant, but the default values would violate that invariant.  Having a readonly keyword for classes would be oh so nice . . .

  • >My thought would be that each "readonly" type ought to be able to be used with the ? suffix for nullability, but also that it ought to be able to declare its own default value if it is NOT used with that suffix. And that, as a result, there should not be the restriction that every value type has to accept "all zeros" as a legitimate value; it can declare its own default.

    That's a performance nightmare; granted you might not care about that in some circumstances, but it's still a concern I would expect the CLR team to be worried about.

    Right now newing up an array with 1,000,000 elements is a fairly straightforward task: grab the necessary amount of memory and make sure it's zeroed (and newly allocated memory from the OS will be zeroed already. If not, writing zero to a large contiguous block of memory is super fast). If the struct has non-zero default values (2 for the first field, 12 for the second, 0x35dffe2 for the third) the runtime's new[] code has to loop through writing the default values into each location.

    This is particularly painful since it has to be done even if the various elements of the array are only going to be overwritten with some non-default values shortly afterwards! The same applies to fields in classes, you can't just zero out the memory when constructing an object (something that, as above, might already have been done for you in advance), the runtime has to go through and fill in a bunch of default values - which you'll probably go and overwrite in your constructor anyway.

  • Eek! That's a very good point. Ouch.

    I hate when reality messes with my perfectly good theories! ;-)

  • ficedula: Isn't there a command to blit a certain byte array repeatedly 1,000,000 (or any N) times?

  • configurator: You could optimise the fill, yes. It's still going to be more complex than filling with zeroes; rather than writing zero to every location, you have to fetch the default values based on the type being allocated; and rather than writing data in blocks of 16+ bytes at a time, you may end up having to write it in smaller chunks if your struct is an inconvenient size.

    That aside, since it *is* possible to "pre clear" your unused memory to zeroes, you lose out fairly significantly there. As I mentioned, memory straight from the OS allocator will be zero-filled already so you currently don't have to do anything before using it. Memory that's not come straight from the OS and was already allocated, you could arrange for that to be cleared to zero as part of garbage collection (when you're touching that memory already and it's fresh in the CPU cache, so the update is practically 'free'.) Compared to that, doing *any* unnecessary work filling in default values is a loss.

Page 2 of 3 (40 items) 123