¿Es una comparación 1 10 menos costosa que 1 1000000?

64

Acabo de usar ~ 1 billón como el recuento de z-index en CSS, y estaba pensando en las comparaciones que deben seguir. ¿Existe una diferencia en el rendimiento en el nivel de ALU en las comparaciones entre números muy grandes y muy pequeños?

Por ejemplo, ¿uno de estos dos fragmentos sería más caro que el otro?

snippet 1

for (int i = 0; i < 10000000; i++){
    if (i < 10000000000000) {
        //do nothing
    }
}

snippet 2

for (int i = 0; i < 10000000; i++){
    if (i < 1000) {
        //do nothing
    }
}
    
pregunta Viziionary 02.02.2015 - 15:52

7 respuestas

81

Todos los procesadores en los que he trabajado realizan comparaciones restando uno de los operandos del otro, descartando el resultado y dejando las marcas del procesador (cero, negativo, etc.) solo. Debido a que la resta se realiza como una sola operación, el contenido de los operandos no importa.

La mejor manera de responder a la pregunta es compilar su código en ensamblaje y consultar la documentación del procesador de destino para obtener las instrucciones generadas. Para las CPU Intel actuales, eso sería Manual del desarrollador de software para arquitecturas Intel 64 e IA-32 .

La descripción de la instrucción CMP ("compare") se encuentra en el volumen 2A, página 3-126, o página 618 del PDF, y describe su funcionamiento como:

temp ← SRC1 − SignExtend(SRC2);
ModifyStatusFlags; (* Modify status flags in the same manner as the SUB instruction*)

Esto significa que el segundo operando se extiende con signo si es necesario, se resta del primer operando y el resultado se coloca en un área temporal en el procesador. Luego, los indicadores de estado se configuran de la misma manera que lo serían para la instrucción SUB ("resta") (página 1492 del PDF).

No hay ninguna mención en la documentación CMP o SUB de que los valores de los operandos tienen alguna incidencia en la latencia, por lo que cualquier valor que use es seguro.

    
respondido por el Blrfl 02.02.2015 - 17:20
24
  

¿Existe una diferencia en el rendimiento en el nivel de ALU en las comparaciones entre números muy grandes y muy pequeños?

Es muy poco probable, a menos que pasar de un número pequeño a un número grande cambie su tipo numérico, por ejemplo, de int a long . Incluso entonces, la diferencia podría no ser significativa. Es más probable que veas una diferencia si tu lenguaje de programación cambia silenciosamente a aritmética de precisión arbitraria debajo de las portadas.

No obstante, su compilador en particular podría estar realizando algunas optimizaciones inteligentes de las que no está al tanto. La forma de averiguarlo es medir. Ejecute un generador de perfiles en su código; ver qué comparaciones llevan más tiempo. O simplemente iniciar y detener un temporizador.

    
respondido por el Robert Harvey 02.02.2015 - 16:47
18

Muchos procesadores tienen instrucciones "pequeñas" que pueden realizar operaciones aritméticas, incluidas comparaciones, en ciertos operandos especificados de inmediato. Los operandos que no sean esos valores especiales deben usar un formato de instrucción más grande o, en algunos casos, deben usar una instrucción de "cargar valor desde la memoria". En el conjunto de instrucciones ARM Cortex-M3, por ejemplo, hay al menos cinco formas en que se puede comparar un valor con una constante:

    cmp r0,#1      ; One-word instruction, limited to values 0-255

    cmp r0,#1000   ; Two-word instruction, limited to values 0-255 times a power of 2

    cmn r0,#1000   ; Equivalent to comparing value with -1000
                   ; Two-word instruction, limited to values 0-255 times a power of 2

    mov r1,#30000  ; Two words; can handle any value 0-65535
    cmp r0,r1      ; Could use cmn to compare to values -1 to -65535

    ldr r1,[constant1000000] ; One or two words, based upon how nearby the constant is
    cmp r0,r1
    ...

constant1000000:
    dd  1000000

La primera forma es la más pequeña; la segunda y tercera forma pueden o no ejecutarse tan rápidamente, dependiendo de la velocidad de la memoria desde la cual se obtiene el código. La cuarta forma casi seguramente será más lenta que las tres primeras, y la quinta forma aún más lenta, pero la última puede usarse con cualquier valor de 32 bits.

En los procesadores x86 más antiguos, las instrucciones de comparación de formato corto se ejecutan más rápido que las de formato largo, pero muchos procesadores más nuevos convertirán las formas larga y corta a la misma representación cuando se recuperan por primera vez, y almacenarán esa representación uniforme en el caché Por lo tanto, mientras que los controladores integrados (como los que se encuentran en muchas plataformas móviles) tendrán una diferencia de velocidad, muchas computadoras basadas en x86 no lo harán.

Tenga en cuenta también que, en muchos casos, cuando una constante se usa en gran medida dentro de un bucle, un compilador solo necesitará cargar la constante en un registro una vez, antes de que comience el bucle, lo que hace que las distinciones de tiempo sean discutibles. Por otro lado, hay algunas situaciones, incluso en pequeños bucles, en los que eso no siempre sucede; Si un bucle es pequeño pero está muy ejecutado, ocasionalmente puede haber un rendimiento importante entre comparaciones que involucran valores inmediatos cortos y valores que involucran valores más largos.

    
respondido por el supercat 02.02.2015 - 19:22
5

La respuesta corta a esta pregunta es, no , no hay diferencia de tiempo para comparar dos números según la magnitud de esos números, suponiendo que estén almacenados en el mismo tipo de datos (por ejemplo, ambos 32- bit ints o ambos largos de 64 bits.)

Además, hasta el tamaño de palabra de ALU , es increíblemente improbable que la comparación de dos enteros entre sí alguna vez tome más de 1 ciclo de reloj, ya que esta es una operación trivial equivalente a una resta. Creo que todas las arquitecturas con las que he tratado han tenido una comparación de enteros de un solo ciclo.

Los únicos casos en los que puedo pensar que encontré una comparación de dos números no fue una operación de un solo ciclo son los siguientes:

  • Instrucciones donde realmente hay una latencia de memoria al buscar operandos, pero eso no tiene nada que ver con cómo funciona la comparación (y generalmente no es posible en arquitecturas RISC, aunque generalmente es posible en diseños CISC, como x86 / x64 .)
  • Las comparaciones de punto flotante pueden ser de varios ciclos, dependiendo de la arquitectura.
  • Los números en cuestión no encajan en el tamaño de palabra de la ALU y, por lo tanto, la comparación debe dividirse en varias instrucciones.
respondido por el reirab 02.02.2015 - 19:01
4

La respuesta de @ RobertHarvey es buena; Considera esta respuesta un suplemento a la suya.

También debe considerar Predicción de Rama :

  

En la arquitectura de la computadora, un predictor de rama es un circuito digital que intenta adivinar qué camino tomará una rama (por ejemplo, una estructura if-then-else) antes de que esto se sepa con seguridad. El propósito del predictor de rama es mejorar el flujo en la línea de instrucciones. Los predictores de rama desempeñan un papel fundamental en el logro de un alto rendimiento efectivo en muchas arquitecturas de microprocesadores modernos, como x86.

Básicamente, en su ejemplo, si la instrucción if dentro del bucle siempre devuelve la misma respuesta, entonces el sistema puede optimizarla adivinando correctamente de qué manera se ramificará. En su ejemplo, dado que la declaración if en el primer caso siempre devuelve el mismo resultado, se ejecutará un poco más rápido que el segundo caso.

Excelente pregunta sobre el desbordamiento de pila sobre el tema

    
respondido por el durron597 02.02.2015 - 17:00
3

Depende de la implementación, pero sería muy poco probable .

Admito que no he leído los detalles de implementación de los distintos motores del navegador, y CSS no especifica ningún tipo particular de almacenamiento para números. Pero creo que es seguro asumir que todos los navegadores principales utilizan números de punto flotante de precisión doble de 64 bits ("dobles", para tomar un término de C / C ++) para manejar la mayoría de sus necesidades numéricas en CSS , porque esto es lo que JavaScript usa para los números, y por lo tanto usar el mismo tipo facilita la integración.

Desde el punto de vista de la computadora, todos los dobles llevan la misma cantidad de datos: 64 bits, ya sea que el valor sea 1 o -3.14 o 1000000 o 1e100 . La cantidad de tiempo que lleva hacer una operación con estos números no depende del valor real de esos números, porque siempre está trabajando en la misma cantidad de datos. Hay un compromiso en hacer las cosas de esta manera, ya que los dobles no pueden representar con precisión todos los números (o incluso todos los números dentro de su rango), pero pueden acercarse lo suficiente para la mayoría de los asuntos, y los tipos de cosas que CSS no son numéricamente - exigiendo lo suficiente para necesitar más precisión que eso. Combine esto con los beneficios de la compatibilidad directa con JavaScript, y tendrá un caso bastante sólido para los dobles.

No es imposible que alguien pueda implementar CSS usando una codificación de longitud variable para números. Si alguien usara una codificación de longitud variable, entonces comparar con números pequeños sería menos costoso que comparar con números grandes, porque los números grandes tienen más datos para analizar . Este tipo de codificaciones pueden ser más precisas que las binarias, pero también son mucho más lentas, y para CSS en particular, las ganancias de precisión probablemente no sean suficientes para que valga la pena el rendimiento. Me sorprendería mucho saber que cualquier navegador hizo las cosas de esta manera.

Ahora, en teoría, hay una posible excepción a todo lo que he dicho anteriormente: comparar contra cero a menudo es más rápido que comparar con otros números . Esto no es porque el cero es corto (si ese fuera el motivo, entonces debería ser igual de rápido, pero no lo es). Es porque el cero te deja engañar. Es el único número donde todos los bits están desactivados, por lo que si sabe que uno de los valores es cero, ni siquiera tiene que mirar el otro valor como un número: si alguno de los bits está activado, entonces no es igual a cero, y luego solo hay que mirar un bit para ver si es mayor o menor que cero.

    
respondido por el The Spooniest 04.02.2015 - 03:37
0

Si este código se interpretara cada vez que se ejecutaba, habría una diferencia, ya que demorar más en tokenizar e interpretar 10000000000000 en comparación con 1000 . Sin embargo, esta es la primera optimización obvia de los intérpretes en este caso: tokenise once e interpretar los tokens.

    
respondido por el Mark Hurd 04.02.2015 - 01:50

Lea otras preguntas en las etiquetas