¿Una comparación 1 <10 es menos costosa que 1 <1000000?

65

Acabo de usar ~ 1 mil millones como el recuento de un z-indexCSS, y estaba pensando en las comparaciones que deben continuar. ¿Hay alguna diferencia en el rendimiento en el nivel de ALU en las comparaciones entre números muy grandes y muy pequeños?

Por ejemplo, ¿sería uno de estos dos fragmentos 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
    }
}
Visir
fuente
12
OP no pregunta cuánto tiempo llevará la ramificación. Claramente, el ejemplo tiene la intención de garantizar que tome exactamente el mismo tiempo en ambos fragmentos. La pregunta es si la CMPinstrucción individual de la máquina será más lenta si ies mayor.
Kilian Foth
18
Dado que esto se hace en CSS, la conversión de una cadena a un entero probablemente dominará la operación de comparación en sí misma en términos de tiempo dedicado a la ejecución.
58
Si necesita usar 1000000000 como un índice z en un archivo CSS, ha hecho algo mal.
Bergi
66
Para CSS, la sobrecarga de convertir texto en un número entero dependerá de la cantidad de dígitos que se conviertan (donde un número de 6 dígitos como 1000000 puede ser aproximadamente 6 veces más costoso que un número de 1 dígito como 1); y esta sobrecarga puede ser de un orden de magnitud mayor que la sobrecarga de las comparaciones de enteros.
Brendan

Respuestas:

82

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

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

La descripción de la CMPinstrucción ("comparar") 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 SUBinstrucción ("restar") (página 1492 del PDF).

No hay mención en el CMPo SUBdocumentación que los valores de los operandos tienen alguna relación con la latencia, por lo que cualquier valor que se utiliza es seguro.

Blrfl
fuente
55
¿Qué pasa si el número se vuelve demasiado grande para la aritmética de 32 bits? ¿No se dividiría entonces en un cálculo más lento?
Falco
3
No @Falco en una CPU con un 64-bit ALU (que es más o menos todos ellos, excepto en el espacio integrado en estos días.)
reirab
8
@Falco: Sí, pero dado que la pregunta se refiere al rendimiento de ALU, la implicación es que los valores se ajustan al tamaño de palabra de la CPU o las capacidades de cualquier instrucción SIMD que pueda tener. Operar en números más grandes que eso tendría que implementarse con múltiples instrucciones fuera de la CPU. Eso era muy común hace 30 años cuando solo tenías registros de 8 o 16 bits para trabajar.
Blrfl
66
@Falco ¿Cómo requeriría eso depuración? No es un error. es un poco más lento hacer operaciones de 64 bits en una CPU que no admite operaciones de 64 bits de forma nativa. Sugerir que nunca se debe usar un número superior a 2 ^ 31-1 parece un poco ridículo.
reirab
2
@Falco Habiendo dicho eso, ¿los motores de renderizado en los navegadores incluso usan números enteros para representar los índices z? La mayoría de los motores de renderizado con los que estoy familiarizado utilizan flotadores de precisión simple para todo (hasta la etapa final de rasterización), pero realmente no he estudiado los motores de renderizado del navegador.
reirab
25

¿Hay alguna 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, digamos de inta a long. Incluso entonces, la diferencia podría no ser significativa. Es más probable que vea una diferencia si su lenguaje de programación cambia silenciosamente a una aritmética de precisión arbitraria debajo de las cubiertas.

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

Robert Harvey
fuente
Cabe mencionar, que los Números propuestos en la Pregunta son de diferente tipo numérico en un tipo entero típico de 32 bits ...
Falco
19

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 el valor de la memoria". En el conjunto de instrucciones ARM Cortex-M3, por ejemplo, hay al menos cinco formas de 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ápido, 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 será aún más lenta, pero esta última se puede usar con cualquier valor de 32 bits.

En los procesadores x86 más antiguos, las instrucciones de comparación de forma corta se ejecutarían más rápido que las de forma larga, pero muchos procesadores más nuevos convertirán tanto las formas largas como las cortas en la misma representación cuando se recuperan por primera vez, y almacenarán esa representación uniforme en el caché. Por lo tanto, si bien 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.

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

Super gato
fuente
En MIPS solo puede tener elementos inmediatos de 16 bits, por lo que definitivamente la comparación con 1 será más corta y (probablemente) más rápida que 1000000. Quizás lo mismo para Sparc y PowerPC. Y creo que he leído de algunas fuentes que Intel también optimiza las operaciones en pequeños casos inmediatos en varios casos, pero no estoy seguro de comparación o no
phuclv
@ LưuVĩnhPhúc: se puede cargar un registro antes del bucle. En ese punto, la comparación real será la misma cantidad de instrucciones en cualquier caso.
cHao
Como el Loop era solo un ejemplo de la operación y la pregunta era, por ejemplo, un índice z, si tiene 1000 objetos, cada uno con su propio índice z y los configuró en 100000000 ... 1000000999 o en 10000 ... 10999 y los recorre para ordenarlos antes de renderizar, hay muchas comparaciones y muchas instrucciones de carga. ¡Allí podría hacer la diferencia!
Falco
@Falco: en ese caso, los inmediatos ni siquiera tendrían en cuenta; cargar y comparar contra un registro parece bastante inevitable.
cHao
@ cHao: Si uno compara los índices Z entre sí, estarían en registros. Si uno maneja ciertos rangos de índices de manera diferente, eso podría implicar comparaciones inmediatas. Normalmente, las constantes se cargarían antes de que comience un ciclo, pero si, por ejemplo, uno tuviera un ciclo que necesitara leer pares de valores de la memoria y comparar el primer valor de cada par con cinco constantes diferentes (no uniformemente espaciadas) en el rango de 100000 a 100499, y el otro valor con otras cinco constantes, puede ser mucho más rápido restar 100250 (guardado en un registro) y luego comparar con los valores -250 a 250 ...
supercat
5

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

Además, hasta el tamaño de la palabra de la ALU , es increíblemente improbable que comparar dos enteros entre sí lleve 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 tenían una comparación de enteros de ciclo único.

Los únicos casos en los que puedo pensar que he encontrado donde una comparación de dos números no era una operación de ciclo único son los siguientes:

  • Instrucciones donde en realidad hay una latencia de memoria al buscar operandos, pero eso no tiene nada que ver con cómo funciona la comparación en sí (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 se ajustan al tamaño de palabra de la ALU y, por lo tanto, la comparación debe dividirse en varias instrucciones.
reirab
fuente
4

La respuesta de @ RobertHarvey es buena; Considere esta respuesta como un complemento de la suya.


También debe considerar la predicción de rama :

En la arquitectura de la computadora, un predictor de rama es un circuito digital que intenta adivinar en qué dirección irá una rama (por ejemplo, una estructura si-entonces-otra) antes de que esto sea seguro. El propósito del predictor de rama es mejorar el flujo en la tubería de instrucciones. Los predictores de rama desempeñan un papel fundamental para lograr un alto rendimiento efectivo en muchas arquitecturas modernas de microprocesadores canalizados como x86.

Básicamente, en su ejemplo, si la ifdeclaración dentro del ciclo siempre devuelve la misma respuesta, entonces el sistema puede optimizarla adivinando correctamente en qué dirección se bifurcará. En su ejemplo, debido a que la ifdeclaración en el primer caso siempre devuelve el mismo resultado, se ejecutará un poco más rápido que el segundo caso.

Excelente pregunta de desbordamiento de pila sobre el tema

durron597
fuente
La predicción de ramificación afecta el tiempo de ramificación, pero no el tiempo de comparación en sí.
reirab
3

Depende de la implementación, pero sería muy, 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 los números. Pero creo que es seguro asumir que todos los principales navegadores están utilizando números de coma flotante de doble precisión de 64 bits ("dobles", para tomar prestado 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, por lo que 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 una compensación 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 el tipo de cosas que CSS no hace numéricamente Lo suficientemente exigente como para necesitar más precisión que eso. Combine esto con los beneficios de la compatibilidad directa con JavaScript, y tendrá un argumento 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 utiliza una codificación de longitud variable, a continuación, comparando contra un pequeño número sería menos costoso que la comparación contra un gran número, ya que grandes números tienen más datos para crujir . Estos tipos de codificaciones pueden ser más precisos que los binarios, pero también son mucho más lentos, 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 con cero es a menudo más rápido que comparar con otros números . Esto no se debe a que cero es corto (si ese fuera el motivo, entonces 1 debería ser igual de rápido, pero no lo es). Es porque cero te permite hacer trampa. Es el único número donde todos los bits están apagados, 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á encendido, entonces no es igual a cero, y luego solo tiene que mirar un bit para ver si es mayor o menor que cero.

El más cuchara
fuente
0

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

Mark Hurd
fuente