When are structs the answer?

Question

I'm doing a raytracer hobby project, and originally I was using structs for my Vector and Ray objects, and I thought a raytracer was the perfect situation to use them: you create millions of them, they don't live longer than a single method, they're lightweight. However, by simply changing 'struct' to 'class' on Vector and Ray, I got a very significant performance gain.

What gives? They're both small (3 floats for Vector, 2 Vectors for a Ray), don't get copied around excessively. I do pass them to methods when needed of course, but that's inevitable. So what are the common pitfalls that kill performance when using structs? I've read this MSDN article that says the following:

When you run this example, you'll see that the struct loop is orders of magnitude faster. However, it is important to beware of using ValueTypes when you treat them like objects. This adds extra boxing and unboxing overhead to your program, and can end up costing you more than it would if you had stuck with objects! To see this in action, modify the code above to use an array of foos and bars. You'll find that the performance is more or less equal.

It's however quite old (2001) and the whole "putting them in an array causes boxing/unboxing" struck me as odd. Is that true? However, I did pre-calculate the primary rays and put them in an array, so I took up on this article and calculated the primary ray when I needed it and never added them to an array, but it didn't change anything: with classes, it was still 1.5x faster.

I am running .NET 3.5 SP1 which I believe fixed an issue where struct methods weren't ever in-lined, so that can't be it either.

So basically: any tips, things to consider and what to avoid?

EDIT: As suggested in some answers, I've set up a test project where I've tried passing structs as ref. The methods for adding two Vectors:

public static VectorStruct Add(VectorStruct v1, VectorStruct v2) {   return new VectorStruct(v1.X + v2.X, v1.Y + v2.Y, v1.Z + v2.Z); }  public static VectorStruct Add(ref VectorStruct v1, ref VectorStruct v2) {   return new VectorStruct(v1.X + v2.X, v1.Y + v2.Y, v1.Z + v2.Z); }  public static void Add(ref VectorStruct v1, ref VectorStruct v2, out VectorStruct v3) {   v3 = new VectorStruct(v1.X + v2.X, v1.Y + v2.Y, v1.Z + v2.Z); } 

For each I got a variation of the following benchmark method:

VectorStruct StructTest() {   Stopwatch sw = new Stopwatch();   sw.Start();   var v2 = new VectorStruct(0, 0, 0);   for (int i = 0; i < 100000000; i++)   {     var v0 = new VectorStruct(i, i, i);     var v1 = new VectorStruct(i, i, i);     v2 = VectorStruct.Add(ref v0, ref v1);   }   sw.Stop();   Console.WriteLine(sw.Elapsed.ToString());   return v2; // To make sure v2 doesn't get optimized away because it's unused.  } 

All seem to perform pretty much identical. Is it possible that they get optimized by the JIT to whatever is the optimal way to pass this struct?

EDIT2: I must note by the way that using structs in my test project is about 50% faster than using a class. Why this is different for my raytracer I don't know.

Answer 1

An array of structs would be a single contiguous structure in memory, while items in an array of objects (instances of reference types) need to be individually addressed by a pointer (i.e. a reference to an object on the garbage-collected heap). Therefore if you address large collections of items at once, structs will give you a performance gain since they need fewer indirections. In addition, structs cannot be inherited, which might allow the compiler to make additional optimizations (but that is just a possibility and depends on the compiler).

However, structs have quite different assignment semantics and also cannot be inherited. Therefore I would usually avoid structs except for the given performance reasons when needed.

---

struct

An array of values v encoded by a struct (value type) looks like this in memory:

vvvv

class

An array of values v encoded by a class (reference type) look like this:

pppp

..v..v...v.v..

where p are the this pointers, or references, which point to the actual values v on the heap. The dots indicate other objects that may be interspersed on the heap. In the case of reference types you need to reference v via the corresponding p, in the case of value types you can get the value directly via its offset in the array.

Answer 2

In the recommendations for when to use a struct it says that it should not be larger than 16 bytes. Your Vector is 12 bytes, which is close to the limit. The Ray has two Vectors, putting it at 24 bytes, which is clearly over the recommended limit.

When a struct gets larger than 16 bytes it can no longer be copied efficiently with a single set of instructions, instead a loop is used. So, by passing this "magic" limit, you are actually doing a lot more work when you pass a struct than when you pass a reference to an object. This is why the code is faster with classes eventhough there is more overhead when allocating the objects.

The Vector could still be a struct, but the Ray is simply too large to work well as a struct.