[ACCEPTED]-When are structs the answer?-raytracing
An array of structs would be a single contiguous 28 structure in memory, while items in an array 27 of objects (instances of reference types) need 26 to be individually addressed by a pointer 25 (i.e. a reference to an object on the garbage-collected 24 heap). Therefore if you address large collections 23 of items at once, structs will give you 22 a performance gain since they need fewer 21 indirections. In addition, structs cannot 20 be inherited, which might allow the compiler 19 to make additional optimizations (but that 18 is just a possibility and depends on the 17 compiler).
However, structs have quite different 16 assignment semantics and also cannot be 15 inherited. Therefore I would usually avoid 14 structs except for the given performance 13 reasons when needed.
An array of values v 12 encoded by a struct (value type) looks like 11 this in memory:
An array of values v 10 encoded by a class (reference type) look 9 like this:
where p are 8 the this pointers, or references, which 7 point to the actual values v on the heap. The 6 dots indicate other objects that may be 5 interspersed on the heap. In the case of 4 reference types you need to reference v 3 via the corresponding p, in the case of 2 value types you can get the value directly 1 via its offset in the array.
In the recommendations for when to use a 15 struct it says that it should not be larger 14 than 16 bytes. Your Vector is 12 bytes, which 13 is close to the limit. The Ray has two Vectors, putting 12 it at 24 bytes, which is clearly over the 11 recommended limit.
When a struct gets larger 10 than 16 bytes it can no longer be copied 9 efficiently with a single set of instructions, instead 8 a loop is used. So, by passing this "magic" limit, you 7 are actually doing a lot more work when 6 you pass a struct than when you pass a reference 5 to an object. This is why the code is faster 4 with classes eventhough there is more overhead 3 when allocating the objects.
The Vector could 2 still be a struct, but the Ray is simply 1 too large to work well as a struct.
Anything written regarding boxing/unboxing 7 prior to .NET generics can be taken with 6 something of a grain of salt. Generic collection 5 types have removed the need for boxing and 4 unboxing of value types, which makes using 3 structs in these situations more valuable.
As 2 for your specific slowdown - we'd probably 1 need to see some code.
Basically, don't make them too big, and 5 pass them around by ref when you can. I 4 discovered this the exact same way... By 3 changing my Vector and Ray classes to structs.
With 2 more memory being passed around, it's bound 1 to cause cache thrashing.
I think the key lies in these two statements 7 from your post:
you create millions of them
I 6 do pass them to methods when needed of course
Now 5 unless your struct is less than or equal 4 to 4 bytes in size (or 8 bytes if you are 3 on a 64-bit system) you are copying much 2 more on each method call then if you simply 1 passed an object reference.
The first thing I would look for is to make 12 sure that you have explicitly implemented 11 Equals and GetHashCode. Failing to do this 10 means that the runtime implementation of 9 each of these does some very expensive operations 8 to compare two struct instances (internally 7 it uses reflection to determine each of 6 the private fields and then checkes them 5 for equality, this causes a significant 4 amount of allocation).
Generally though, the 3 best thing you can do is to run your code 2 under a profiler and see where the slow 1 parts are. It can be an eye-opening experience.
Have you profiled the application? Profiling 6 is the only sure fire way to see where the 5 actual performance problem is. There are 4 operations that are generally better/worse 3 on structs but unless you profile you'd 2 just be guessing as to what the problem 1 is.
While the functionality is similar, structures 5 are usually more efficient than classes. You 4 should define a structure, rather than a 3 class, if the type will perform better as a value type than a reference 2 type.
Specifically, structure types should 1 meet all of these criteria:
- Logically represents a single value
- Has an instance size less than 16 bytes
- Will not be changed after creation
- Will not be cast to a reference type
I use structs basically for parameter objects, returning 3 multiple pieces of information from a function, and... nothing 2 else. Don't know whether it's "right" or 1 "wrong," but that's what I do.
My own ray tracer also uses struct Vectors 12 (though not Rays) and changing Vector to 11 class does not appear to have any impact 10 on the performance. I'm currently using 9 three doubles for the vector so it might 8 be bigger than it ought to be. One thing 7 to note though, and this might be obvious 6 but it wasn't for me, and that is to run 5 the program outside of visual studio. Even 4 if you set it to optimized release build 3 you can get a massive speed boost if you 2 start the exe outside of VS. Any benchmarking 1 you do should take this into consideration.
More Related questions