{"id":52,"date":"2009-10-03T19:01:00","date_gmt":"2009-10-03T17:01:00","guid":{"rendered":"http:\/\/dev.bratched.fr\/en\/?p=52"},"modified":"2009-10-03T19:01:00","modified_gmt":"2009-10-03T17:01:00","slug":"fun-with-matrix-multiplication-and-unsafe-code","status":"publish","type":"post","link":"https:\/\/bratched.com\/en\/2009\/10\/03\/fun-with-matrix-multiplication-and-unsafe-code\/","title":{"rendered":"Fun with matrix multiplication and unsafe code"},"content":{"rendered":"

In this post I will compare two methods that perform matrix multiplication. We start by defining the Matrix class:<\/p>\n

\n
class Matrix\n    {\n        private readonly double[,] _matrix;\n        public Matrix(int dim1, int dim2)\n        {\n            _matrix = new double[dim1, dim2];\n        }\n\n        public int Height { get { return _matrix.GetLength(0); } }\n        public int Width { get { return _matrix.GetLength(1); } }\n\n        public double this[int x, int y]\n        {\n            get { return _matrix[x, y]; }\n            set { _matrix[x, y] = value; }\n        }\n    }<\/pre>\n<\/div>\n
Next we add the first algorithm to the Matrix class which performs a naive multiplication:<\/p>\n
\n
 public static Matrix NaiveMultiplication(Matrix m1, Matrix m2)\n    {\n        Matrix resultMatrix = new Matrix(m1.Height, m2.Width);\n        for (int i = 0; i < resultMatrix.Height; i++)\n        {\n            for (int j = 0; j < resultMatrix.Width; j++)\n            {\n                resultMatrix[i, j] = 0;\n                for (int k = 0; k < m1.Width; k++)\n                {\n                    resultMatrix[i, j] += m1[i, k] * m2[k, j];\n                }\n            }\n        }\n        return resultMatrix;\n    }<\/pre>\n<\/div>\n
The second method uses unsafe code:<\/p>\n
\n
public unsafe static Matrix UnsafeMultiplication(Matrix m1, Matrix m2)\n   {\n       int h = m1.Height;\n       int w = m2.Width;\n       int l = m1.Width;\n       Matrix resultMatrix = new Matrix(h, w);\n       unsafe\n       {\n           fixed (double* pm = resultMatrix._matrix, pm1 = m1._matrix, pm2 = m2._matrix)\n           {\n               int i1, i2;\n               for (int i = 0; i < h; i++)\n               {\n                   i1 = i * l;\n                   for (int j = 0; j < w; j++)\n                   {\n                       i2 = j;\n                       double res = 0;\n                       for (int k = 0; k < l; k++, i2 += w)\n                       {\n                           res += pm1[i1 + k] * pm2[i2];\n                       }\n                       pm[i * w + j] = res;\n                   }\n               }\n           }\n       }\n       return resultMatrix;\n   }<\/pre>\n<\/div>\n
Now it\u2019s time to measure the performance:<\/p>\n
\n
class Program\n    {\n        [DllImport(\"kernel32.dll\")]\n        static extern void QueryPerformanceCounter(ref long ticks);\n\n        static long Measure(Action action, int count)\n        {\n            long startTicks = 0;\n            QueryPerformanceCounter(ref startTicks);\n            for (int i = 0; i < count; i++)\n            {\n                action();\n            }\n            long endTicks = 0;\n            QueryPerformanceCounter(ref endTicks);\n            return endTicks - startTicks;\n        }\n\n        static void Main(string[] args)\n        {\n            Random random = new Random();\n\n            Matrix m1 = new Matrix(20, 30);\n            for (int i = 0; i < m1.Height; i++)\n            {\n                for (int j = 0; j < m1.Width; j++)\n                {\n                    m1[i, j] = random.Next(-100, 100);\n                }\n            }\n\n            Matrix m2 = new Matrix(30, 40);\n            for (int i = 0; i < m2.Height; i++)\n            {\n                for (int j = 0; j < m2.Width; j++)\n                {\n                    m2[i, j] = random.Next(-100, 100);\n                }\n            }\n\n            Console.WriteLine(Measure(() => Matrix.NaiveMultiplication(m1, m2), 10000));\n            Console.WriteLine(Measure(() => Matrix.UnsafeMultiplication(m1, m2), 10000));\n        }\n    }<\/pre>\n<\/div>\n
In this test we perform 10000 multiplications of two randomly generated matrices with sizes 20×30 and 30×40 using both methods:<\/p>\n\n\n\n\n\n
Method<\/strong><\/td>\nCPU cycles<\/strong><\/td>\n<\/tr>\n
unsafe multiplication<\/td>\n4485698<\/td>\n<\/tr>\n
naive multiplication<\/td>\n58762273<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The results show that the naive multiplication is slower by a factor of 13 compared to the multiplication using unsafe code and working directly with memory.<\/p>\n","protected":false},"excerpt":{"rendered":"
In this post I will compare two methods that perform matrix multiplication. We start by defining the Matrix class: class Matrix { private readonly double[,] _matrix; public Matrix(int dim1, int dim2) { _matrix = new double[dim1, dim2]; } public int Height { get { return _matrix.GetLength(0); } } public int Width { get { return […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[263,266],"tags":[284,321],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t