¿Acelera el código matemático en C# escribiendo un C dll?

Question

Tengo un bucle anidado muy grande en el que se realizan algunas multiplicaciones y adiciones en números de coma flotante.

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; 
    } 
} 

Este ciclo está ocupando la mayor parte de mi tiempo de procesamiento y es un cuello de botella.

¿Sería probable que viera alguna mejora de velocidad si reescribo este bucle en C y lo conecto desde C#?

EDIT: Actualicé el código para mostrar cómo se generan s y c. También el bucle interno en realidad va de 0 a i, aunque probablemente no hay mucha diferencia a la pregunta

Edit2: he implementado el algoritmo en VC++ y vinculado con C# a través de una DLL y vi a un 28% aumento de velocidad sobre C# cuando todas las optimizaciones están habilitadas. El argumento para habilitar SSE2 funciona particularmente bien. La compilación con MinGW y gcc4.4 solo dio un impulso de velocidad del 15%. Acabo de probar el compilador de Intel y vi un aumento de velocidad del 49% para este código.

Answer 1

Si bien la mayoría de las otras respuestas sugieren que considere las soluciones de C#, la mayoría pierde un punto: el código C para este método será más rápido, siempre que use un buen compilador de optimización (sugiero Intel, funciona muy bien para este tipo de código).
El compilador también ahorrará un poco de trabajo del JIT y producirá una salida compilada mucho mejor (incluso el compilador de MSVC puede generar instrucciones SSE2). Los límites de la matriz no se verificarán de manera predeterminada, es probable que haya algún bucle que se desenrolle y, en general, es probable que vea un impulso significativo en el rendimiento.
Como se ha señalado correctamente, llamar al código nativo puede tener un poco de sobrecarga; esto debería, sin embargo, ser insignificante en comparación con la aceleración si length1 es lo suficientemente grande.
Es posible que guarde este código en C#, pero recuerde que comparado con varios compiladores de C, el CLR (como todas las otras máquinas virtuales que conozco) hace poco para optimizar el código generado.

Answer 2

¿Has probado la programación en paralelo?

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

Answer 3

Es muy poco probable que la ejecución de este nativo en C/C++ podría "automáticamente" acelerar las cosas. Si eres bueno con SIMD (y length1 y length2 son lo suficientemente grandes como para que la llamada P/Invoke no sea significativa) entonces quizás podrías hacer algo.

Pero la única manera de saberlo con certeza sería probarlo y perfil.

Answer 4

Muy dudoso. El bucle interno que procesa tipos primitivos y no asigna memoria será muy eficiente en C#. El bytecode nativo se generará una vez desde IL, por lo que no debería haber demasiados gastos generales administrados.

Teniendo en cuenta que es una función bastante pequeña, puede perfilar ambos y ver si hay alguna diferencia.

Answer 5

Utilice un bloque unsafe y punteros para indexar en su matriz omega. Esto eliminará la sobrecarga de la verificación de rango y puede ser una ganancia significativa si realiza suficientes accesos. También puede estar invirtiendo mucho tiempo en las funciones GetS() y GetC(), que no proporcionó la fuente.

Answer 6

El simple hecho de usar C o C++ no le dará mucho aumento de velocidad, si corresponde. También tiene la sobrecarga de llamar a la rutina C, lo cual no es un gran impacto, a menos que lo haga muchas veces en un bucle.

Pruebe algunas otras cosas en C# primero. Si las variables son flotantes en lugar de dobles, esto ralentiza los cálculos. También como Raj dijo que el uso de programación paralela le dará un impulso de gran velocidad.

Answer 7

Para la aritmética de 64 bits en Java, vi una aceleración de alrededor del 33% (23 ns a 16 ns) al portarlo a C y jugar con indicadores de optimización (-fprofile-generate, -fprofile-use). Puede valer la pena.

La otra cosa es que omega [i] [j] hace que parezca que omega es una matriz de matrices: puede obtener un mejor rendimiento con una matriz bidimensional (creo que la sintaxis es algo así como omega [i, j ], pero se me olvida cómo asignar uno).

Answer 8

Actualizado:

¿Qué pasa si usted escribe bucle interno para tener en cuenta la localidad de referencia:

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 9

Usted podría tratar de usar la Mono.Simd para utilizar la CPU más optimimally.

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

Dicho esto, se puede ganar mucho en C# extrayendo manualmente declaraciones duplicadas fuera de bucles.

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 10

Considere también el costo de recopilar datos entre llamadas administradas y nativas. C# tiene una velocidad de ejecución bastante rápida. También puede NGENAR el ensamblaje para generar imágenes nativas del ensamblaje para una ejecución más rápida.

Answer 11

.net la interoperabilidad con código no administrado es muy lenta. Puede usar todos los beneficios de la memoria no administrada solo con la API del sistema para asignar memoria no administrada.

Puede llamar a VirtualAlloc para asignar páginas de memoria y luego llamar a VirtualProtect para fijarlas directamente a la RAM sin cambiarlas.

Este enfoque permite realizar cálculos sobre una gran cantidad de datos al menos 3 veces más rápido de lo que podría hacerlo en la memoria administrada.

Answer 12

No tengo idea de lo práctico que es esto, pero ¿pensó en intentar ejecutar esto en una GPU? Tal vez usando algo como OpenCL o DirectCompute?

Las dependencias y la raíz cuadrada pueden matarlo, pero las GPU tienen un orden de magnitud más de rendimiento en coma flotante que las CPU actualmente.