resueltos prefijo prefija postfijo postfija polaca notacion infijo infija ejercicios convertir codigo c# performance optimization il postfix-notation

c# - prefijo - notacion infija a postfija en java



C#generó IL para el operador++: cuándo y por qué la notación de prefijo/postfijo es más rápida (3)

Ya que esta pregunta es sobre el incremento en el operador y las diferencias de velocidad con la notación de prefijo / postfijo, describiré la pregunta con mucho cuidado para que Eric Lippert no lo descubra y me ignore.

(Puede encontrar más información y más detalles sobre por qué estoy preguntando en http://www.codeproject.com/KB/cs/FastLessCSharpIteration.aspx?msg=3899456#xx3899456xx/ )

Tengo cuatro fragmentos de código de la siguiente manera: -

(1) Separado, Prefijo:

for (var j = 0; j != jmax;) { total += intArray[j]; ++j; }

(2) Separado, Postfix:

for (var j = 0; j != jmax;) { total += intArray[j]; j++; }

(3) Indexador, Postfix:

for (var j = 0; j != jmax;) { total += intArray[j++]; }

(4) Indexador, Prefijo:

for (var j = -1; j != last;) { total += intArray[++j]; } // last = jmax - 1

Lo que estaba tratando de hacer era probar / refutar si hay una diferencia de rendimiento entre el prefijo y la notación de postfijo en este contexto (es decir, una variable local, por lo tanto, no es volátil, no se puede cambiar de otro hilo, etc.) y si existiera .

Las pruebas de velocidad demostraron que:

  • (1) y (2) corren a la misma velocidad entre sí.

  • (3) y (4) corren a la misma velocidad entre sí.

  • (3) / (4) son ~ 27% más lentos que (1) / (2).

Por lo tanto, estoy concluyendo que no hay una ventaja de rendimiento al elegir la notación de prefijo sobre la notación de postfix per se. Sin embargo, cuando el Resultado de la Operación se utiliza realmente, esto se traduce en un código más lento que si simplemente se desecha.

Luego eché un vistazo a la IL generada usando Reflector y encontré lo siguiente:

  • El número de bytes IL es idéntico en todos los casos.

  • El .maxstack varió entre 4 y 6, pero creo que se usa solo para fines de verificación y, por lo tanto, no es relevante para el rendimiento.

  • (1) y (2) generaron exactamente el mismo IL, por lo que no es de extrañar que la sincronización fuera idéntica. Así que podemos ignorar (1).

  • (3) y (4) generaron un código muy similar, la única diferencia relevante es el posicionamiento de un código de operación de duplicación para dar cuenta del resultado de la operación . Una vez más, no es de extrañar que el tiempo sea idéntico.

Entonces comparé (2) y (3) para averiguar qué podría explicar la diferencia de velocidad:

  • (2) utiliza una operación ldloc.0 dos veces (una vez como parte del indexador y luego como parte del incremento).

  • (3) usó ldloc.0 seguido inmediatamente por un dup op.

Entonces, el IL relevante para el incremento j para (1) (y (2)) es:

// ldloc.0 already used once for the indexer operation higher up ldloc.0 ldc.i4.1 add stloc.0

(3) se ve así:

ldloc.0 dup // j on the stack for the *Result of the Operation* ldc.i4.1 add stloc.0

(4) se ve así:

ldloc.0 ldc.i4.1 add dup // j + 1 on the stack for the *Result of the Operation* stloc.0

Ahora (¡por fin!) A la pregunta:

¿Es (2) más rápido porque el compilador JIT reconoce que un patrón de ldloc.0/ldc.i4.1/add/stloc.0 simplemente incrementa una variable local en 1 y la optimiza? (y la presencia de un dup en (3) y (4) rompe ese patrón y se pierde la optimización)

Y un complemento: si esto es cierto, entonces, para (3) al menos, ¿no reemplazaría el dup con otro ldloc.0 reintroducir ese patrón?

Me encantan las pruebas de rendimiento y me encantan los programas rápidos, así que admiro tu pregunta.

Intenté reproducir tus hallazgos y fallé. En mi sistema Intel i7 x64 que ejecuta sus ejemplos de código en el marco .NET4 en la configuración de la versión x86, los cuatro casos de prueba produjeron aproximadamente los mismos tiempos.

Para realizar la prueba, creé un nuevo proyecto de aplicación de consola y utilicé la llamada a la API QueryPerformanceCounter para obtener un temporizador basado en CPU de alta resolución. Probé dos configuraciones para jmax :

  • jmax = 1000
  • jmax = 1000000

porque la ubicación de la matriz a menudo puede hacer una gran diferencia en cómo se comporta el rendimiento y aumenta el tamaño del bucle de. Sin embargo, ambos tamaños de matriz se comportaron igual en mis pruebas.

He realizado una gran cantidad de optimización del rendimiento y una de las cosas que aprendí es que puede optimizar una aplicación muy fácilmente para que se ejecute más rápido en una computadora en particular y, de manera inadvertida, se ejecute más lentamente en otra computadora.

No estoy hablando hipotéticamente aquí. He ajustado los bucles internos y he invertido horas y días de trabajo para hacer que un programa se ejecute más rápido, solo para que mis esperanzas se desbaraten porque lo estaba optimizando en mi estación de trabajo y la computadora de destino era un modelo diferente de procesador Intel.

Así que la moraleja de esta historia es:

  • El fragmento de código (2) se ejecuta más rápido que el fragmento de código (3) en su computadora pero no en mi computadora

Esta es la razón por la que algunos compiladores tienen interruptores de optimización especiales para diferentes procesadores o algunas aplicaciones vienen en versiones diferentes, aunque una versión podría ejecutarse fácilmente en todo el hardware compatible.

Por lo tanto, si va a realizar pruebas de este tipo, debe hacerlo de la misma manera que lo hacen los escritores de compiladores JIT: debe realizar sus pruebas en una amplia variedad de hardware y luego elegir una combinación , un medio feliz que da lo mejor Rendimiento en el hardware más ubicuo.

OK después de mucha investigación (¡lo siento, lo siento!), Creo que he respondido a mi propia pregunta:

La respuesta es Tal vez. Al parecer, los compiladores JIT buscan patrones (consulte http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds-check-elimination-in-the-clr.aspx ) para decidir cuándo y cómo se puede optimizar la verificación de los límites de la matriz, pero no sé si es el mismo patrón que estaba adivinando.

En este caso, es un punto discutible porque el aumento de velocidad relativo de (2) se debió a algo más que eso. Resulta que el compilador JIT x64 es lo suficientemente inteligente como para determinar si la longitud de un arreglo es constante (y aparentemente también es un múltiplo del número de desenrollados en un bucle): Por lo tanto, el código era solo una verificación de límites al final de cada iteración y cada desenrollado se convirtió en justo: -

total += intArray[j]; j++; 00000081 8B 44 0B 10 mov eax,dword ptr [rbx+rcx+10h] 00000085 03 F0 add esi,eax

Esto lo probé cambiando la aplicación para permitir que el tamaño de la matriz se especifique en la línea de comandos y ver los diferentes resultados del ensamblador.

Otras cosas descubiertas durante este ejercicio:

  • Para una operación de incremento independiente (es decir, el resultado no se usa), no hay diferencia en la velocidad entre el prefijo / postfix.
  • Cuando se usa una operación de incremento en un indexador, el ensamblador muestra que la notación de prefijo es ligeramente más eficiente (y tan cerca en el caso original que asumí que era solo una discrepancia de tiempo y que los llamé iguales - mi error). La diferencia es más pronunciada cuando se compila como x86.
  • El desenrollado de bucles funciona. En comparación con un bucle estándar con optimización de límites de matriz, 4 resúmenes siempre dieron una mejora de 10% -20% (y el caso de x64 / constante 34%). Aumentar el número de rollups dio lugar a tiempos variados con un poco más lento en el caso de un postfix en el indexador, así que me quedo con 4 si se desenrolla y solo lo cambiaré después de un tiempo extenso para un caso específico.

Resultados interesantes. Lo que yo haría es:

  • Reescriba la aplicación para hacer la prueba completa dos veces.
  • Ponga un cuadro de mensaje entre las dos ejecuciones de prueba.
  • Compilar para el lanzamiento, sin optimizaciones, y así sucesivamente.
  • Inicie el ejecutable fuera del depurador .
  • Cuando aparezca el cuadro de mensaje, adjunte el depurador
  • Ahora inspecciona el código generado para los dos casos diferentes por el jitter.

Y luego sabrás si el jitter está haciendo un mejor trabajo con uno que con el otro. La fluctuación de fase podría, por ejemplo, darse cuenta de que en un caso puede eliminar las comprobaciones de los límites de la matriz, pero no darse cuenta de que en el otro caso. No lo sé; No soy un experto en el jitter.

La razón de todo el rigamarole es que la fluctuación de fase puede generar un código diferente cuando se adjunta el depurador. Si desea saber qué hace en circunstancias normales, debe asegurarse de que el código se adapte a las circunstancias normales y no de depuración.