Performance Quiz #11: Ten Questions on Value-Based Programming : Solution
In my last quiz I asked a few questions about a few hypothetical classes that might appear in a value-rich context. I styled my example in the form of some graphics library classes but the idea is a general one. Many contexts can and should be rich in values to get nice data density and the resulting good performance that comes with it. I allude to some of these notions in my posting on real-time managed programming, so in a way this posting is sort of a continuation of that discussion.
Now as usual there is more than one way to do this properly so I will not pretend to be giving The Definitive Way To Write These Classes but my example does tend to show some important issues that are worth talking about. So without further ado, here's my thoughts on the matter.
Question #1: Point3d is a struct, not a class. Why?
The main reason goes right back to data density. There is a strong expectation that this class will be embedded in other classes such as Vertex and you can imagine many others. It is likely that there will be temporaries of this type, and importantly arrays of this type. Using a value type will make it so that walking through sets of related points does not require following multiple pointers and therefore data density is likely to be enhanced. And of course, there is storage overhead for classes -- the object header and the method table pointer -- these will be absent in packed arrays of structures.
Contrariwise the usual benefits of being a class are not especially valuable. Will we be subtyping? No. Sychronizing? No. Do we want point "identity" (e.g. the canonical instance of point (1,2,-1)? No.
This leads to a pretty clear decision for me.
What rules am I breaking? I just made a public mutable value type that is larger than 16 bytes. Three strikes and I have barely begun:)
Oh, I'm sorry about that last part, I didn't make it clear but I intended all of these to be public types. Krzysztof of course busted my chops about that. Thanks :)
On to...
Question #2: Point3d.x is a field, not a property. Why?
Common expected usage of the point primitive will involve things like translations, scaling, and other user defined operations which I can't possibly predict. The Point structure itself has the lovely property that there are no illegal values so I truly do not care how it is manipulated. The opportunity that I might have for adding any kind of side-effect to the point calculations is vanishingly small. Contrariwise the statement that I make by making the member a field is a powerful one. It's a field. I expect you to edit it. It will never be other than a field. Could I even, truly, afford even a modest overhead (a few clocks) for an operation so primitive as writing a single coordinate of a point? Even something that small would double the write costs.
The property setting code can certainly be no better than the field code, and in this case it's actually a tad worse (Alois discovered this in his comment). Furthermore, adding additional IL for the inliner to try to fold can only make the situation worse when these field operations are composed with other operations and we would like the larger operation inlined.
But for me, the main reason is to make the openness completely apparent. It's a strong promise and an important one.
I've broken another guideline now, there is no public property for this field.
Question #3: Vertex is a struct, not a class. Why? Same reason as #1?
Substantially yes, the same reasons as #1. Density, no need for identity, and substantial likelihood of composition.
Question #4: Vertex.location is a field, not a property. Why? Same reason as #2?
The reasons given in #2 all apply, but now there is an additional reason. Vertex is not leaf value-type, it has embedded members. We expect the vertex itself to be mutated and we would like to write things like Vertex.normal.dx = 0 or something. All manner of transformations might be possible. However the result of a property is not a true l-value so we cannot do something like Vertex.Normal.dx = 0. The chaining of properties gives very unexpected results.
Question #5: Quad has no methods. Why?
Importantly, Quad has no context and therefore it cannot hope to add any value other than as a bucket of 4 integers, for which we need no methods. Quad cannot have any context because we would not wish every Quad to know things like what Mesh it is a part of, the cost of such a pointer would be astonishing. Indeed a frugal graphics package might limit the Quad to using short integers for the vertex numbers if that were reasonable (though that would limit the mesh size signficantly). Lacking context we can't do things like range check the integers, check for consistency in the normals, or any other sort of thing we might like to do on a single face. We need to put those sorts of functions at the next higher level (the Mesh).
Since we can't do those sorts of things, lets be very open about the fact that this is nothing more than a 4 slot integer container, it's not "smart" and never will be. As a reward we get the benefits indicated in #1.
Question #6: MeshSection is a class with private members. Why?
Well now we've reached a level of implementation where the class actually has some idea what's going on and this class should probably be following all the regular sorts of rules you would expect. I'm showing some of the internals for illustration purposes, such as arrays of Vertex objects and Quad objects but naturally these should not be exposed. A MeshSection might wish to have some growable array form, or chunks, or some other dense representation that might evolve over time. The MeshSection can do validation on the items when they are passed in and provide high level semantic functions such as normal adjustment, tessalation, morphs, and other operations of that ilk.
Importantly, these representation choices, even the more flexible ones, are rich in represented data and extremely low in overhead. The number of pointers present is virtual nil so garbage collection costs even in the presence of massive peices of geometry would be virtually nil. Effectively the Quad objects are integer 'handles' to vertices as I discussed in my article on real-time managed programming. Yet I can still have a nice abstracted and maintainable interface.
Question #7: Why do I suggest that MeshSection methods accept arrays of Vertices, Quads, and the like rather than singletons?
Two significant reasons really. The first is that we might be dealing with MeshSections having millions of vertices and so it seems unwise to talk about operations that affect singleton primitives. While it's possible to imagine adding and connecting single vertices to a MeshSection it's as likely that we might want to merge signficant pieces of geometry. If this kind of operation requried millions of function calls we would have signficant overhead. So perhaps the most important reason of all is that chunky arrays as arguments offer a nice unit of work.
Secondly, the suggested prohibition against large value types (greater than say 16 bytes) is not without merit. But actually we give that advice not so much because large value types are inherently bad but because if used directly there can be an inordinate amount of pushing and popping of big objects on the stack as well as lost inlining opportunities. Using arrays neatly avoids both this problem as we merely pass around array references, and indeed the array could be reused.
This leads to an important observation, which is, wait for it...
It's not the size of the value type that matters. It's how you use it :)
Ahem. Moving swiftly along... :)
Question #8: No mention is made of synchronization here at all, is that just an oversight?
Certainly I would put no synchronization in any of the structs. The operations on those are so small that any sychronization primitive, even the cheapest, would be deadly at that level. But this is actually not the pivotal point. It is much more important to put synchronzation at a semantic level where the code has some understanding of what the unit of work is. That is, how big of an operation is intented to be atomic? What are the high level operations that need to be protected? The soonest you could imagine having this knowledge is at the MeshSection level in this program -- but even there, the code has no thread awareness per se -- it's just doing some vertex math. Lacking knowledge of how things might be scheduled it again becomes difficult to make any interesting synchronization choices. Since the contract for MeshSection is nice and chunky (see #7) you could imagine again leaving the synchronization to the caller, as we do in virtually all of our framework collection classes.
Ultimately, I don't believe these classes have anything of value to add in terms of synchronization assistance and so I decided not to include it. For more on this, see my article "Putting your synchronization at the correct level."
Question #9: How useful is the "foreach" construct likely to be when working with arrays of vertices or quads etc?
Not very. If you were to do foreach (Vertex v in SomeVertices) { whatever } you'd find that in the whatever block you can't modify the vertices because of course it's a value type. You'll likely be having custom iterators or using for loops to manage the array arguments to the MeshSection methods. Unfortunate but in my opinion it's the right thing to do.
Question #10: How many rules did I break? :)
I lost count. I think three big ones but more than once each I suppose.
Thank you very much for all the excellent responses!
P.S. The annotated design guidelines can be found here.
Comments
- Anonymous
September 07, 2006
PingBack from http://blogs.msdn.com/ricom/archive/2006/08/31/733887.aspx - Anonymous
September 07, 2006
The comment has been removed - Anonymous
September 07, 2006
"Question #5: Quad has no methods. Why?"
At least one method could be useful! A method wich changes the order of the corners either to retriangulate the quad or to flip the quad's triangles! Using a method on the quad rather than an method someplace else that recives a quad as a parameter will I think will have better perf because the method on the quad recives a managed pointer as a paramether raher than the structure's copy, so probably there is a reason to have methods on quad. - Anonymous
September 07, 2006
Microsoft's Rico Mariani has two very interesting posts that shed some light on when to prefer structs - Anonymous
September 08, 2006
I still can't understand - why structs coudln't be inherited in C#? was it done for performance reasons or by some other limit in CLR? - Anonymous
September 09, 2006
Structs do not contain any sort of vtable and such, hence you can't do inheritance. If they did they would be classes. - Anonymous
September 11, 2006
Of course that really only prevents virtual functions.
I'd really be worried more about what the subtype behavior would be like. Is it really safe to always pass a Child types where Base is expected? What if Child used some of the gaps previously present in Base?
I think this could be made to work, C++ does it after all, but then C++ has much more rigid rules about sharing types across assemblies and versioning them.
I'd have to think about it. - Anonymous
September 11, 2006
Rico has been posting performance quizzes for a couple of years now. These are always interesting and... - Anonymous
September 14, 2006
I'm sure that it's the same for you: you go away on vacation, have a great time, come back and your email... - Anonymous
September 15, 2006
Only the ignorant think any of those types should be classes. They can go use Java3D if that's what they want. lol.
Just do us all a favor and pass the large structures by "ref" where appropriate.
This is how we should transform Vectors:
public static void Vector3.Transform(ref Vector3 v, ref Matrix m);
PLEASE DO NOT PASS A HUGE MATRIX BY VALUE TO A TRANSFORM FUNCTION! (Like the current XNA Api) - Anonymous
February 01, 2007
My blog reader burped recently, and gave forth a post (and reply ) than Rico wrote last September, but