{"id":112,"date":"2013-09-10T22:18:00","date_gmt":"2013-09-10T22:18:00","guid":{"rendered":"http:\/\/evolvedmicrobe.com\/blogs\/?p=112"},"modified":"2014-06-29T02:23:24","modified_gmt":"2014-06-29T02:23:24","slug":"mono-simd-and-the-mandlebrot-set","status":"publish","type":"post","link":"http:\/\/evolvedmicrobe.com\/blogs\/?p=112","title":{"rendered":"Mono.Simd and the Mandlebrot Set."},"content":{"rendered":"

C# and .NET are some of the fastest high level languages, but still cannot truly compete with C\/C++ for low level speed, and C# code can be anywhere from 20%-300% slower. This is despite the fact that the C# compiler often gets as much information about a method as the C compiler.  It has been suggested that SSE\/SIMD<\/a> instructions in C# could overcome some of these issues.  To evaluate this, I took a famous computational task, re-coded it using C# SIMD instructions, and evaluated the performance by looking at the execution time and how the emitted assembly code compared to the optimal assembly code.<\/p>

Background<\/strong><\/p>

In 2009, Miguel de Icaza demonstrated a framework<\/a> that allows C# to use SSE2 intrinsic operations.This is now part of the Mono library and in theory, such methods can greatly save computational time (1.5X-16X), particularly for operations on byte arrays, a common task in bioinformatics. <\/p>

Test Case<\/strong><\/p>

Computing the mandelbrot set<\/a> is one of the tasks of the computer benchmarks game<\/a>, which compares program speed in different languages.  Currently, C# is listed as being slower than Java, though the programs in each language use different techniques and neither uses an optimal algorithm (see here for a better one<\/a>).  However, it makes a useful test case for raw computing speed.  The challenge is to compute the picture shown below by recursively squaring a complex number and adding a constant to it.<\/p>

\"z_{n+1}<\/p> \r\n\r\n

\"image_thumb[1]\"<\/a><\/p> \r\n\r\n

The Algorithm<\/strong><\/p> \r\n\r\n

Complex numbers are a particularly challenging case because their multiplication is not a simple operation, but involves a rather annoyingly squaring of different terms and then adding\/subtracting them. <\/p>

\r\n\r\n\"image_thumb1\"<\/a>
<\/a><\/p>

These are not easy vector operations, and as will be shown later one result of this is that using SSE to speed up the values for one multiplication is useless (I tried, it was worse). So, the performance improvement comes from doing two elements of the loop at a time (this is how the current Java submission is faster than the C# one, though it does not use SIMD).  The current C# version does the inner loop of the program without SIMD instructions as follows:<\/p> \r\n\r\n

\r\nint i = 49;   \r\ndo {\r\n     zi = zr * zi + zr * zi + ci; \r\n     zr = tr - ti + cr;   \r\n     tr = zr * zr; \r\n     ti = zi * zi;  \r\n} while 1)<\/sup>tr + ti <= 4.0) && (--i > 0<\/span>