migueltk's picture

Matrix implementation, class or structure?

Matrix, class or structure?

I wonder if there is any reason to implement an array as a structure type.

In principle I think it's more a problem than an advantage. For example:

Given the following code ...

 
    public partial class Form1 : Form
    {
        Entity[] entities = new Entity[10];
        public Form1()
        {
            InitializeComponent();
 
            for (int cont = 0; cont < 10; cont++)
                entities[cont] = new Entity();
 
            foreach (Entity e in entities)
            {
                Matrix m = e.Transform; // first copy (16 values)
                Modification(ref m);
                e.Transform = m; // second copy (16 values)
            }
        }
 
        void Modification(ref Matrix m)
        {
            m.m1 = 1;
        }
    }
 
    struct Matrix
    {
        public int m1; public int m9;
        public int m2; public int m10;
        public int m3; public int m11;
        public int m4; public int m12;
        public int m5; public int m13;
        public int m6; public int m14;
        public int m7; public int m15;
        public int m8; public int m16;
    }
 
    class Entity
    {
        public Matrix Transform
        {
            get;
            set;
        }
    }

For each cycle of the foreach loop are necessary 32 assignments.

asign_number = num_entities * 32

For a total of 100 entities.

asign_number = 100 * 32 = 3200

Although the required surveillance operations using the stack, are 3200 assignments are made for each frame.

In contrast, if Matrix is implemented as a class, do not perform copy and is accessed by reference.

What is the advantage of implementing a matrix structure? Anyone know?


Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
flopoloco's picture

This is a very interested topic, I was very into it a few months back but I could not find an explanation.

It is said that structs are better only by design (for limited functionality), for type definition purposes rather than optimization criteria.
On the other hand there are not enough types of optimizations you can do in .NET regarding system types.

I have made a silly benchmark just to have a look (CPU - Intel i5)

using System;
 
namespace StructBenchmark
{
	internal struct MatrixStruct
	{
		public float M1, M2, M3, M4, M5, M6, M7, M8, M9, M10, M11, M12, M13, M14, M15, M16;
	}
 
	internal struct MatrixClass
	{
		public float M1, M2, M3, M4, M5, M6, M7, M8, M9, M10, M11, M12, M13, M14, M15, M16;
	}
 
	class Program
	{
		#region Variables for test
		// Timing
		static DateTime timeStart;
 
		static string[] msgPattern = {
			"Results for {0} Matrix",			// 0
			"Array with {0} objects",			// 1
			"Time took to allocate: {0} ms",	// 2
			"Time took to assign: {0} ms",		// 3
			"Time took for math assignment: {0} ms"// 4
		};
 
		static System.Text.StringBuilder sbstr = new System.Text.StringBuilder();
		static System.Text.StringBuilder sbcls = new System.Text.StringBuilder();
 
		static MatrixStruct[] matstruct;
		static MatrixClass[] matclass;
 
		static int[] testsNumObjects = {
			100, 1000, 10000, 100000,
			1000000,
			10000000,
		};
		#endregion
 
		#region Time keeping methods
 
		static void Timekeep()
		{
			timeStart = DateTime.Now;
		}
 
		static void Timecheckout(ref System.Text.StringBuilder sb, int stringPatternIndex)
		{
			// http://msdn.microsoft.com/en-us/library/system.datetime.ticks.aspx
			// Ticks => Ticks * 100 = Nanoseconds => Nanoseconds * 100 = Milliseconds
			// There are 10,000 ticks in a millisecond. (Ticks * (100 * 100))
//			long ticks = (DateTime.Now.Ticks - timeStart.Ticks) * 100 * 100;
 
			int ms = DateTime.Now.Millisecond - timeStart.Millisecond;
 
			sb.AppendLine(String.Format(msgPattern[stringPatternIndex], ms.ToString()));
		}
 
		#endregion
 
		public static void Main(string[] args)
		{
			Console.WriteLine("Welcome to Struct VS Class Matrix benchmark");
 
			// Initialize messages
			sbstr.AppendLine(String.Format(msgPattern[0], "struct"));
			sbstr.AppendLine();
 
			sbcls.AppendLine(String.Format(msgPattern[0], "class"));
			sbcls.AppendLine();
			// ------------------
 
			int matrixStructSize = System.Runtime.InteropServices.Marshal.SizeOf(typeof(MatrixStruct));
			int matrixClassSize = System.Runtime.InteropServices.Marshal.SizeOf(typeof(MatrixClass));
 
			foreach (int i in testsNumObjects)
			{
				sbstr.AppendLine(String.Format(msgPattern[1], i.ToString()));
				sbcls.AppendLine(String.Format(msgPattern[1], i.ToString()));
 
				#region Allocation
 
				Timekeep();
				matstruct = new MatrixStruct[i];
				Timecheckout(ref sbstr, 2);
 
				sbstr.AppendLine(
					"Size of struct = " + 
					(((matrixStructSize * i) / 1024) / 1024).ToString() + " MB"
				);
 
				Timekeep();
				matclass = new MatrixClass[i];
				Timecheckout(ref sbcls, 2);
 
				sbcls.AppendLine(
					"Size of class = " + 
					(((matrixClassSize * i) / 1024) / 1024).ToString() + " MB"
				);
 
				#endregion
 
				#region Assignment
 
				Timekeep();
				for (int j = 0; j < i; j++)
				{
					matstruct[j].M1 = 1; matstruct[j].M2 = 1;
					matstruct[j].M3 = 1; matstruct[j].M4 = 1;
					matstruct[j].M5 = 1; matstruct[j].M6 = 1;
					matstruct[j].M7 = 1; matstruct[j].M8 = 1;
					matstruct[j].M9 = 1; matstruct[j].M10 = 1;
					matstruct[j].M11 = 1; matstruct[j].M12 = 1;
					matstruct[j].M13 = 1; matstruct[j].M14 = 1;
					matstruct[j].M15 = 1; matstruct[j].M16 = 1;
				}
				Timecheckout(ref sbstr, 3);
 
				Timekeep();
				for (int j = 0; j < i; j++)
				{
					matclass[j].M1 = 1; matclass[j].M2 = 1;
					matclass[j].M3 = 1; matclass[j].M4 = 1;
					matclass[j].M5 = 1; matclass[j].M6 = 1;
					matclass[j].M7 = 1; matclass[j].M8 = 1;
					matclass[j].M9 = 1; matclass[j].M10 = 1;
					matclass[j].M11 = 1; matclass[j].M12 = 1;
					matclass[j].M13 = 1; matclass[j].M14 = 1;
					matclass[j].M15 = 1; matclass[j].M16 = 1;
				}
				Timecheckout(ref sbcls, 3);
 
 
				#endregion
 
				#region Math assignment
 
				Timekeep();
				for (int j = 0; j < i; j++)
				{
					matstruct[j].M1 += 1; matstruct[j].M2 += 1;
					matstruct[j].M3 += 1; matstruct[j].M4 += 1;
					matstruct[j].M5 += 1; matstruct[j].M6 += 1;
					matstruct[j].M7 += 1; matstruct[j].M8 += 1;
					matstruct[j].M9 += 1; matstruct[j].M10 += 1;
					matstruct[j].M11 += 1; matstruct[j].M12 += 1;
					matstruct[j].M13 += 1; matstruct[j].M14 += 1;
					matstruct[j].M15 += 1; matstruct[j].M16 += 1;
				}
				Timecheckout(ref sbstr, 4);
 
				Timekeep();
				for (int j = 0; j < i; j++)
				{
					matclass[j].M1 += 1; matclass[j].M2 += 1;
					matclass[j].M3 += 1; matclass[j].M4 += 1;
					matclass[j].M5 += 1; matclass[j].M6 += 1;
					matclass[j].M7 += 1; matclass[j].M8 += 1;
					matclass[j].M9 += 1; matclass[j].M10 += 1;
					matclass[j].M11 += 1; matclass[j].M12 += 1;
					matclass[j].M13 += 1; matclass[j].M14 += 1;
					matclass[j].M15 += 1; matclass[j].M16 += 1;
				}
				Timecheckout(ref sbcls, 4);
 
				#endregion
 
				matstruct = null;
				matclass = null;
 
				GC.Collect();
 
				sbstr.AppendLine();
				sbcls.AppendLine();
			}
 
			// Print results
 
			Console.WriteLine(sbstr.ToString());
			Console.WriteLine(sbcls.ToString());
 
 
			System.IO.File.WriteAllText(
				"C:\\MatrixBenchResults.txt",
				sbstr.ToString() + "\n" + sbcls.ToString());
 
 
			Console.ReadKey();
		}
	}
}
Results for struct Matrix
 
Array with 100 objects
Time took to allocate: 1 ms
Size of struct = 0 MB
Time took to assign: 0 ms
Time took for math assignment: 0 ms
 
Array with 1000 objects
Time took to allocate: 0 ms
Size of struct = 0 MB
Time took to assign: 0 ms
Time took for math assignment: 0 ms
 
Array with 10000 objects
Time took to allocate: 0 ms
Size of struct = 0 MB
Time took to assign: 0 ms
Time took for math assignment: 0 ms
 
Array with 100000 objects
Time took to allocate: 0 ms
Size of struct = 6 MB
Time took to assign: 2 ms
Time took for math assignment: 3 ms
 
Array with 1000000 objects
Time took to allocate: 0 ms
Size of struct = 61 MB
Time took to assign: 27 ms
Time took for math assignment: 32 ms
 
Array with 10000000 objects
Time took to allocate: 1 ms
Size of struct = 610 MB
Time took to assign: 256 ms
Time took for math assignment: 309 ms
 
 
Results for class Matrix
 
Array with 100 objects
Time took to allocate: 0 ms
Size of class = 0 MB
Time took to assign: 0 ms
Time took for math assignment: 0 ms
 
Array with 1000 objects
Time took to allocate: 0 ms
Size of class = 0 MB
Time took to assign: 0 ms
Time took for math assignment: 0 ms
 
Array with 10000 objects
Time took to allocate: 0 ms
Size of class = 0 MB
Time took to assign: 1 ms
Time took for math assignment: 0 ms
 
Array with 100000 objects
Time took to allocate: 1 ms
Size of class = 6 MB
Time took to assign: 3 ms
Time took for math assignment: 3 ms
 
Array with 1000000 objects
Time took to allocate: 0 ms
Size of class = 61 MB
Time took to assign: 25 ms
Time took for math assignment: 33 ms
 
Array with 10000000 objects
Time took to allocate: 1 ms
Size of class = 610 MB
Time took to assign: -752 ms
Time took for math assignment: 327 ms

This benchmark needs to be tested in GameWindow to be close to game development.

Inertia's picture

IIRC profiling proved that Structs are both faster to instantiate and to collect, and you can pin struct[] for unmanaged functions.

Instead of

foreach (Entity e in entities)
            {
                Matrix m = e.Transform; // first copy (16 values)
                Modification(ref m);
                e.Transform = m; // second copy (16 values)
            }

do

foreach (Entity e in entities)
            {
                Modification(ref e.Transform); // no copy at all and save 2 unnecessary mov
            }
migueltk's picture

@ flopoloco

In principle, it is demonstrated that the access time to members of an array is not characteristic of the end use of the structures.

@ inertia

In the sample code I've been careful to state that "e.Transform" is a property and therefore can not be passed by reference as a method parameter "Modification(ref)". Visual Studio Error "Property, an indexer or a dynamic member access can not be Passed as an out or ref parameter (CS0206)."

Actually, the code is this:

    class Entity : ITransformable
    {
        public Matrix Transform
        {
            get;
            set;
        }
    }
 
    public interface ITransformable
    {
    	Matrix Transform
    	{
    		get; set;
    	}
    }

"e.Transform" must be a property.

Do not attempt to reopen the controversial "structure vs class" I just want to be convinced that Matrix struct is better than Matrix as a class,

I have not found sufficient grounds for taking this step!

Inertia's picture

Apologies, but your Entity class does nothing but wrap the matrix struct? Properties imply a performance penalty, I recommend using public/internal fields only. (Penalty is even worse on .Net compact framework.)

Here is Fiddler's reply when we discussed the class vs. struct question when the math library was built: http://www.opentk.com/node/52#comment-171