Speed up math code in C# by writing a C dll?

Question

I have a very large nested for loop in which some multiplications and additions are performed on floating point numbers.

for (int i = 0; i < length1; i++)
{
    double aa = 0;
    for(int h = 0; h < 10; h++)
    {
       aa += omega[i][outsideGeneratedAddress[h]];
    }

    double alphaOld = alpha;
    alpha = Math.Sqrt(alpha * alpha + aa * aa);

    s = -aa / alpha;
    c = alphaOld / alpha;

    for(int j = 0; j <= i; j++)
    {
        double oldU = u[j];
        u[j] = c * oldU + s * omega[i][j];
        omega[i][j] = c * omega[i][j] - s * oldU;
    }
}

This loop is taking up the majority of my processing time and is a bottleneck.

Would I be likely to see any speed improvements if I rewrite this loop in C and interface to it from C#?

EDIT: I updated the code to show how s and c are generated. Also the inner loop actually goes from 0 to i, though it probably doesn't make much difference to the question

EDIT2: I implemented the algorithm in VC++ and linked it with C# through a dll and saw a 28% speed boost over C# when all optimisations are enabled. The argument to enable SSE2 works particularly well. Compiling with MinGW and gcc4.4 only gave a 15% speed boost. Just tried the Intel compiler and saw a 49% speed boost for this code.

Answer 1

Did you try parallel programming?

http://msdn.microsoft.com/en-us/library/system.threading.tasks.parallel.aspx

Answer 2

It's highly unlikely that running this in native C/C++ would "automatically" speed things up. If you're good with SIMD (and length1 and length2 are large enough that the P/Invoke call is not significant) then maybe you could do something.

But the only way to know for sure would be to try it and profile.

Answer 3

Highly doubt it. Inner loop that processes primitive types and doesn't allocate memory will be very damn efficient in C#. The native bytecode will get generated once from IL, so there shouldn't be much managed overhead.

Considering it's a pretty small function, you can profile both and see if there is any difference.

Answer 4

Use an unsafe block and pointers to index into your omega array. This will remove the overhead of range checking and may be a significant win if you do enough accesses. A lot of time may also be being spent in your GetS() and GetC() functions, which you didn't provide source for.

Answer 5

Simply using C or C++ will not give you much of a speed increase, if any. You also have the overhead of calling into the C routine, not a huge impact, unless you are doing it many times in a loop.

Try some other things in C# first. If the variables are floats rather than doubles this slows down calculations. Also as Raj said using parallel programming will give you a big speed boost.

Answer 6

For plain 64-bit arithmetic in Java, I saw around 33% speedup (23 ns to 16 ns) when porting it to C and fiddling with optimization flags (-fprofile-generate, -fprofile-use). It might be worth it.

The other thing is that omega[i][j] makes it look like omega is an array of arrays — you may get better performance with a two dimensional array (I think the syntax is something like omega[i,j], but I forget how you allocate one).

Answer 7

Updated:

What happens if you write inner loop to take account of locality of reference:

for (int i = 0; i < length1; i++) 
{ 
    s = GetS(i); 
    c = GetC(i); 
    double[] omegaTemp = omega[i]; 

    for(int j = 0; j < length2; j++) 
    { 
        double oldU = u[j]; 
        u[j] = c * oldU + s * omegaTemp[j]; 
        omegaTemp[j] = c * omegaTemp[j] - s * oldU; 
    } 
} 

Answer 8

You could try to use the Mono.Simd to utilize the CPU more optimimally.

http://tirania.org/blog/archive/2008/Nov-03.html

That being said, much can be gained in C# by manually extracting duplicate statements out of loops.

var outsideAddr0 = outsideGeneratedAddress[0];
var outsideAddr1 = outsideGeneratedAddress[1];
var outsideAddr2 = outsideGeneratedAddress[2];
var outsideAddr3 = outsideGeneratedAddress[3];
var outsideAddr4 = outsideGeneratedAddress[4];
var outsideAddr5 = outsideGeneratedAddress[5];
var outsideAddr6 = outsideGeneratedAddress[6];
var outsideAddr7 = outsideGeneratedAddress[7];
var outsideAddr8 = outsideGeneratedAddress[8];
var outsideAddr9 = outsideGeneratedAddress[9];
for (int i = 0; i < length1; i++)
{
  var omegaAtI = omega[i];
  double aa = 
   omegaAtI[outsideAddr0]
   + omegaAtI[outsideAddr1]
   + omegaAtI[outsideAddr2]
   + omegaAtI[outsideAddr3]
   + omegaAtI[outsideAddr4]
   + omegaAtI[outsideAddr5]
   + omegaAtI[outsideAddr6]
   + omegaAtI[outsideAddr7]
   + omegaAtI[outsideAddr8]
   + omegaAtI[outsideAddr9];

  double alphaOld = alpha;
  alpha = Math.Sqrt(alpha * alpha + aa * aa);

  var s = -aa / alpha;
  var c = alphaOld / alpha;

  for(int j = 0; j <= i; j++)
  {
    double oldU = u[j];
    var omegaAtIJ = omegaAtI[j];
    u[j] = c * oldU + s * omegaAtIJ;
    omegaAtI[j] = c * omegaAtIJ  - s * oldU;
  }
}

Answer 9

Also consider the cost of marshalling data between managed and native calls. C# has pretty fast execution speed. You can also NGEN the assembly to generate native images of the assembly for faster execution.

Answer 10

.net interop with unmanaged code is very slow. You can use all benefits of unmanaged memory just by using system api to allocate unmanaged memory.

You can call VirtualAlloc to allocate memory pages and then call VirtualProtect to pin them directly to RAM without swaping.

This approach allows to perform calculations over large amount of data at least 3 times faster then you could do it in managed memory.

Answer 11

While most other answers tend to suggest that you look into C# solutions, most miss a point: C code for this method will be faster, provided that you use a good optimizing compiler (I'd suggest Intel, works great for this kind of code).
The compiler will also save a bit of work from the JIT and will yield a much better compiled output (even MSVC compiler can generate SSE2 instructions). Array bounds won't be checked by default, there will probably be some loop unrolling and - all in all - you're likely to see a significant performance boost.
As it has been properly pointed out, calling into native code may have a bit of overhead; this should, however, be insignificant compared to the speedup if length1 is big enough.
You may sure keep this code in C# but please remember that compared to several C compilers the CLR (like all other VMs I know) does little to optimize the generated code.

Answer 12

I have no idea how practical this is, but did you think of trying to run this on a GPU? Perhaps using something like OpenCL or DirectCompute?

The dependencies and the square root might kill you, but GPUs have an order of magnitude more raw floating point performance than CPUs these days.