c# .net performance bounds-check-elimination

c# - Los límites de matriz comprueban la eficacia en.net 4 y superior



performance bounds-check-elimination (4)

Me interesa saber qué tan eficientes pueden ser los algoritmos de bajo nivel en .net. Me gustaría permitirnos elegir escribir más de nuestro código en C # en lugar de C ++ en el futuro, pero un obstáculo es la comprobación de límites en .NET que se produce con el bucle y el acceso aleatorio a las matrices.

Un ejemplo motivador es una función que calcula la suma de productos de elementos correspondientes en dos matrices (este es el producto de puntos de dos vectores).

static void SumProduct(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); for (int i = 0; i < length; i++) // Check X.Length instead? See below sum += X[i] * Y[i]; }

Por lo que puedo decir, y no conozco suficiente IL o x86 para verificar, el compilador no optimizará la comprobación de límites de X e Y ¿Estoy equivocado y / o hay una forma de escribir mi código para permitir que el compilador me ayude?

Más detalles

Hay muchos argumentos de eficiencia a favor y en contra de utilizar idiomas particulares, entre los que destaca que es mejor concentrarse en el costo algorítmico de "O gran" que en la constante de proporcionalidad, y los lenguajes de nivel superior lo ayudan a hacerlo. En el tema de comprobación de límites en .net, el mejor artículo que encontré es Array Bounds Bounds Elimination en el CLR en MSDN (también se hace referencia en una respuesta de desbordamiento de pila sobre la importancia de habilitar la optimización).

Esto data de 2009, así que me pregunto si las cosas han cambiado significativamente desde entonces. Además, el artículo revela algunas sutilezas reales que me habrían sorprendido, por esta razón solo quisiera recibir algunos consejos de expertos.

Por ejemplo, parece que en mi código anterior sería mejor escribir i< X.Length lugar de i < length . Además, también había supuesto ingenuamente que para un algoritmo con un solo arreglo, escribir un ciclo foreach mejor declararía su intención al compilador y le daría la mejor oportunidad de optimizar la verificación de límites.

De acuerdo con el artículo de MSDN, SumForBAD , a continuación, que pensé que estaba seguro de ser optimizado, no lo sería. Mientras que SumFor se optimizaría directamente, y SumForEach también se optimizaría, pero no de forma trivial (y podría no optimizarse en absoluto si la matriz se pasara a una función como IEnumerable<int> ).

static double SumForBAD(double[] X) { double sum = 0; int length = X.Length; // better to use i < X.length in loop for (int i = 0; i < length; i++) sum += X[i]; return sum; } static double SumFor(double[] X) { double sum = 0; for (int i = 0; i < X.Length; i++) sum += X[i]; return sum; } static double SumForEach(double[] X) { double sum = 0; foreach (int element in X) sum += element; return sum; }

Investigué basándome en la respuesta de doug65536. En C ++, comparé los tiempos de un SumProduct que hace una verificación de límites

for(int i=0; i<n; ++i) sum += v1[i]*v2[i];

contra otra versión que hace dos controles de límites

for(int i=0; i<n1 && i <n2; ++i) sum += v1[i]*v2[i];

Descubrí que la segunda versión era más lenta, pero solo en un 3.5% (Visual Studio 2010, compilación optimizada, opciones predeterminadas). Sin embargo, se me ocurrió que en C #, podría haber tres límites de verificación. Una explícita ( i < length en la función static void SumProduct(double[] X, double[] Y) al comienzo de esta pregunta), y dos implícitas ( X[i] e Y[i] ). Así que probé una tercera función de C ++, con tres controles de límites

for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i];

Esto llegó un 35% más lento que el primero, lo cual vale la pena preocuparse. Investigué un poco más en esta pregunta, ¿por qué añadir un control adicional en el bucle hace una gran diferencia en algunas máquinas y una pequeña diferencia en otras? . Curiosamente, parece que el costo de la verificación de límites varía significativamente en diferentes máquinas.

64 bits

El jitter de 64 bits hace un buen trabajo eliminando cheques de límites (al menos en escenarios simples). Agregué la return sum; al final de su método y luego compiló el programa usando Visual Studio 2010 en modo Release. En el siguiente desmontaje (que anoté con una traducción de C #), observe que:

  • No hay límites para X , a pesar de que tu código compara i con la length lugar de X.Length . Esto es una mejora sobre el comportamiento descrito en el artículo.
  • Antes del ciclo principal, hay una única comprobación para asegurarse de que Y.Length >= X.Length .
  • El bucle principal (desplazamientos 00000032 a 00000052) no contiene ninguna comprobación de límites.

Desmontaje

; Register assignments: ; rcx := i ; rdx := X ; r8 := Y ; r9 := X.Length ("length" in your code, "XLength" below) ; r10 := Y.Length ("YLength" below) ; r11 := X.Length - 1 ("XLengthMinus1" below) ; xmm1 := sum ; (Prologue) 00000000 push rbx 00000001 push rdi 00000002 sub rsp,28h ; (Store arguments X and Y in rdx and r8) 00000006 mov r8,rdx ; Y 00000009 mov rdx,rcx ; X ; int XLength = X.Length; 0000000c mov r9,qword ptr [rdx+8] ; int XLengthMinus1 = XLength - 1; 00000010 movsxd rax,r9d 00000013 lea r11,[rax-1] ; int YLength = Y.Length; 00000017 mov r10,qword ptr [r8+8] ; if (XLength != YLength) ; throw new ArgumentException("X and Y must be same size"); 0000001b cmp r9d,r10d 0000001e jne 0000000000000060 ; double sum = 0; 00000020 xorpd xmm1,xmm1 ; if (XLength > 0) ; { 00000024 test r9d,r9d 00000027 jle 0000000000000054 ; int i = 0; 00000029 xor ecx,ecx 0000002b xor eax,eax ; if (XLengthMinus1 >= YLength) ; throw new IndexOutOfRangeException(); 0000002d cmp r11,r10 00000030 jae 0000000000000096 ; do ; { ; sum += X[i] * Y[i]; 00000032 movsd xmm0,mmword ptr [rdx+rax+10h] 00000038 mulsd xmm0,mmword ptr [r8+rax+10h] 0000003f addsd xmm0,xmm1 00000043 movapd xmm1,xmm0 ; i++; 00000047 inc ecx 00000049 add rax,8 ; } ; while (i < XLength); 0000004f cmp ecx,r9d 00000052 jl 0000000000000032 ; } ; return sum; 00000054 movapd xmm0,xmm1 ; (Epilogue) 00000058 add rsp,28h 0000005c pop rdi 0000005d pop rbx 0000005e ret 00000060 ... 00000096 ...

32 bits

La trepidación de 32 bits, desafortunadamente, no es tan inteligente. En el desmontaje a continuación, tenga en cuenta que:

  • No hay límites para X , a pesar de que tu código compara i con la length lugar de X.Length . Nuevamente, esto es una mejora sobre el comportamiento descrito en el artículo.
  • El ciclo principal (desplazamientos 00000018 a 0000002a) contiene una verificación de límites para Y

Desmontaje

; Register assignments: ; eax := i ; ecx := X ; edx := Y ; esi := X.Length ("length" in your code, "XLength" below) ; (Prologue) 00000000 push ebp 00000001 mov ebp,esp 00000003 push esi ; double sum = 0; 00000004 fldz ; int XLength = X.Length; 00000006 mov esi,dword ptr [ecx+4] ; if (XLength != Y.Length) ; throw new ArgumentException("X and Y must be same size"); 00000009 cmp dword ptr [edx+4],esi 0000000c je 00000012 0000000e fstp st(0) 00000010 jmp 0000002F ; int i = 0; 00000012 xor eax,eax ; if (XLength > 0) ; { 00000014 test esi,esi 00000016 jle 0000002C ; do ; { ; double temp = X[i]; 00000018 fld qword ptr [ecx+eax*8+8] ; if (i >= Y.Length) ; throw new IndexOutOfRangeException(); 0000001c cmp eax,dword ptr [edx+4] 0000001f jae 0000005A ; sum += temp * Y[i]; 00000021 fmul qword ptr [edx+eax*8+8] 00000025 faddp st(1),st ; i++; 00000027 inc eax ; while (i < XLength); 00000028 cmp eax,esi 0000002a jl 00000018 ; } ; return sum; 0000002c pop esi 0000002d pop ebp 0000002e ret 0000002f ... 0000005a ...

Resumiendo

El jitter ha mejorado desde 2009, y el jitter de 64 bits puede generar un código más eficiente que el jitter de 32 bits.

Sin embargo, si es necesario, siempre puede omitir completamente las verificaciones de límites de la matriz mediante el uso de códigos y punteros inseguros (como señala Svick). Esta técnica es utilizada por algún código de rendimiento crítico en la Biblioteca de clases base.

En primer lugar, me gustaría agradecer a todos los que hablaron en esta publicación, desde OP original a los tipos que proporcionaron explicaciones extremadamente detalladas y perspicaces. Realmente, realmente disfruté leyendo las respuestas existentes. Dado que ya existe una gran cantidad de teoría de cómo y por qué los bucles funcionan de la manera en que lo hacen, me gustaría ofrecer algunas mediciones empíricas (por alguna definición con autoridad):

Conclusiones

  • El bucle Foreach es más rápido que el bucle For.
  • La variable local es más rápida que la propiedad array .Length .
  • GC-pinning utilizando unsafe fixed no unsafe fixed no es más rápido que lo normal para el ciclo.

Código de Benchmarking:

using System; using System.Diagnostics; using System.Runtime; namespace demo { class MainClass { static bool ByForArrayLength (byte[] data) { for (int i = 0; i < data.Length; i++) if (data [i] != 0) return false; return true; } static bool ByForLocalLength (byte[] data) { int len = data.Length; for (int i = 0; i < len; i++) if (data [i] != 0) return false; return true; } static unsafe bool ByForUnsafe (byte[] data) { fixed (byte* datap = data) { int len = data.Length; for (int i = 0; i < len; i++) if (datap [i] != 0) return false; return true; } } static bool ByForeach (byte[] data) { foreach (byte b in data) if (b != 0) return false; return true; } static void Measure (Action work, string description) { GCSettings.LatencyMode = GCLatencyMode.LowLatency; var watch = Stopwatch.StartNew (); work.Invoke (); Console.WriteLine ("{0,-40}: {1} ms", description, watch.Elapsed.TotalMilliseconds); } public static void Main (string[] args) { byte[] data = new byte[256 * 1024 * 1024]; Measure (() => ByForArrayLength (data), "For with .Length property"); Measure (() => ByForLocalLength (data), "For with local variable"); Measure (() => ByForUnsafe (data), "For with local variable and GC-pinning"); Measure (() => ByForeach (data), "Foreach loop"); } } }

Resultados: (usa Mono runtime)

$ mcs Program.cs -optimize -unsafe For with .Length property : 440,9208 ms For with local variable : 333,2252 ms For with local variable and GC-pinning : 330,2205 ms Foreach loop : 280,5205 ms

La verificación de límites no importará porque:

  • La comprobación de límites consiste en un par de instrucciones cmp / jae , que se fusiona en una sola microoperación en arquitecturas de CPU modernas (el término es "fusión macro-op"). Compare y sucursal está muy optimizado.

  • La verificación de límites es una rama hacia adelante, que se pronosticará estáticamente que no se tomará, reduciendo también el costo. La rama nunca será tomada. (Si alguna vez se toma, una excepción arrojará de todos modos, por lo que el costo del error de escritura se vuelve totalmente irrelevante)

  • Tan pronto como haya algún retraso en la memoria, la ejecución especulativa pondrá en cola muchas iteraciones del ciclo, por lo que el costo de decodificación del par de instrucciones extra casi desaparece.

El acceso a la memoria probablemente sea su cuello de botella, por lo que desaparecerán las micro-optimizaciones de efectos, como la eliminación de las verificaciones de límites.

Una forma de asegurarse de que la comprobación de límites no se realiza es usar punteros, que puede hacer en C # en modo inseguro (esto requiere que establezca un indicador en las propiedades del proyecto):

private static unsafe double SumProductPointer(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); fixed (double* xp = X, yp = Y) { for (int i = 0; i < length; i++) sum += xp[i] * yp[i]; } return sum; }

Traté de medir su método original, su método con el cambio X.Length y mi código usando punteros, compilados como x86 y x64 en .Net 4.5. Específicamente, traté de calcular el método para vectores de longitud 10 000 y ejecuté el método 10 000 veces.

Los resultados están más o menos en línea con la respuesta de Michael Liu: no hay una diferencia medible entre los tres métodos, lo que significa que la comprobación de límites no se realiza o que su efecto en el rendimiento es insignificante. Sin embargo, hubo una diferencia medible entre x86 y x64: x64 fue aproximadamente un 34% más lento.

Código completo que utilicé:

static void Main() { var random = new Random(42); double[] x = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray(); double[] y = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray(); // make sure JIT doesn''t affect the results SumProduct(x, y); SumProductLength(x, y); SumProductPointer(x, y); var stopwatch = new Stopwatch(); stopwatch.Start(); for (int i = 0; i < 10000; i++) { SumProduct(x, y); } Console.WriteLine(stopwatch.ElapsedMilliseconds); stopwatch.Restart(); for (int i = 0; i < 10000; i++) { SumProductLength(x, y); } Console.WriteLine(stopwatch.ElapsedMilliseconds); stopwatch.Restart(); for (int i = 0; i < 10000; i++) { SumProductPointer(x, y); } Console.WriteLine(stopwatch.ElapsedMilliseconds); } private static double SumProduct(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); for (int i = 0; i < length; i++) sum += X[i] * Y[i]; return sum; } private static double SumProductLength(double[] X, double[] Y) { double sum = 0; if (X.Length != Y.Length) throw new ArgumentException("X and Y must be same size"); for (int i = 0; i < X.Length; i++) sum += X[i] * Y[i]; return sum; } private static unsafe double SumProductPointer(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); fixed (double* xp = X, yp = Y) { for (int i = 0; i < length; i++) sum += xp[i] * yp[i]; } return sum; }