¿Por qué se ignora el desbordamiento aritmético?

76

¿Alguna vez trató de resumir todos los números del 1 al 2,000,000 en su lenguaje de programación favorito? El resultado es fácil de calcular manualmente: 2,000,001,000,000, que es aproximadamente 900 veces mayor que el valor máximo de un entero de 32 bits sin signo.

C # imprime -1453759936 : ¡un valor negativo! Y supongo que Java hace lo mismo.

Eso significa que hay algunos lenguajes de programación comunes que ignoran el desbordamiento aritmético de forma predeterminada (en C #, hay opciones ocultas para cambiar eso). Ese es un comportamiento que me parece muy arriesgado, y ¿no fue el accidente de Ariane 5 causado por tal desbordamiento?

Entonces: ¿cuáles son las decisiones de diseño detrás de un comportamiento tan peligroso?

Editar:

Las primeras respuestas a esta pregunta expresan los costos excesivos de la verificación. Ejecutemos un breve programa de C # para probar esta suposición:

Stopwatch watch = Stopwatch.StartNew();
checked
{
    for (int i = 0; i < 200000; i++)
    {
        int sum = 0;
        for (int j = 1; j < 50000; j++)
        {
            sum += j;
        }
    }
}
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);

En mi máquina, la versión comprobada tarda 11015 ms, mientras que la versión no comprobada tarda 4125 ms. Es decir, los pasos de verificación toman casi el doble de tiempo que sumar los números (en total 3 veces el tiempo original). Pero con las 10,000,000,000 de repeticiones, el tiempo que demora un cheque sigue siendo inferior a 1 nanosegundo. Puede haber una situación en la que eso sea importante, pero para la mayoría de las aplicaciones, eso no importará.

Edición 2:

Volví a compilar nuestra aplicación de servidor (un servicio de Windows que analiza los datos recibidos de varios sensores, involucrando bastantes cálculos numéricos) /p:CheckForOverflowUnderflow="false" parámetro (normalmente, enciendo la verificación de desbordamiento) y lo implementé en un dispositivo. El monitoreo de Nagios muestra que la carga promedio de CPU se mantuvo en 17%.

Esto significa que el impacto en el rendimiento que se encuentra en el ejemplo anterior es totalmente irrelevante para nuestra aplicación.

Bernhard Hiller
fuente
19
solo como una nota, para C # puede usar la checked { }sección para marcar las partes del código que deben realizar comprobaciones de desbordamiento aritmético. Esto se debe al rendimiento
Paweł Łukasik
14
"¿Alguna vez trató de resumir todos los números del 1 al 2,000,000 en su lenguaje de programación favorito?" - Sí: (1..2_000_000).sum #=> 2000001000000. Otra de mis favoritas idiomas: sum [1 .. 2000000] --=> 2000001000000. No es mi favorito: Array.from({length: 2000001}, (v, k) => k).reduce((acc, el) => acc + el) //=> 2000001000000. (Para ser justos, el último es hacer trampa.)
Jörg W Mittag
27
@BernhardHiller Integeren Haskell es de precisión arbitraria, contendrá cualquier número siempre que no se quede sin RAM asignable.
Polygnome
50
El accidente del Ariane 5 fue causado por la comprobación de un desbordamiento que no importaba: el cohete estaba en una parte del vuelo donde el resultado de un cálculo ya no era necesario. En cambio, se detectó el desbordamiento, y eso provocó que el vuelo abortara.
Simon B
9
But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond.eso es una indicación del bucle que se está optimizando. También esa oración contradice números anteriores que me parecen muy válidos.
usr

Respuestas:

86

Hay 3 razones para esto:

  1. El costo de verificar los desbordamientos (para cada operación aritmética) en tiempo de ejecución es excesivo.

  2. La complejidad de probar que una verificación de desbordamiento puede omitirse en tiempo de compilación es excesiva.

  3. En algunos casos (p. Ej., Cálculos de CRC, bibliotecas de números grandes, etc.) "envolver en desbordamiento" es más conveniente para los programadores.

Brendan
fuente
10
@DmitryGrigoryev unsigned intno debería venir a la mente porque un lenguaje con comprobación de desbordamiento debería verificar todos los tipos enteros de forma predeterminada. Deberías tener que escribir wrapping unsigned int.
user253751
32
No compro el argumento del costo. La CPU verifica el desbordamiento en CADA cálculo de entero entero y establece el indicador de acarreo en la ALU. Es el soporte del lenguaje de programación lo que falta. Una didOverflow()función en línea simple o incluso una variable global __carryque permita el acceso al indicador de acarreo costaría cero tiempo de CPU si no la usa.
slebetman
37
@Slebetman: Eso es x86. BRAZO no. Por ejemplo ADD, no establece el acarreo (lo que necesita ADDS). Itanium ni siquiera tiene una bandera de acarreo. E incluso en x86, AVX no tiene banderas de transporte.
MSalters
30
@slebetman Establece la bandera de acarreo, sí (en x86, eso sí). Pero luego tienes que leer la bandera de acarreo y decidir el resultado, esa es la parte costosa. Dado que las operaciones aritméticas a menudo se usan en bucles (y bucles estrechos), esto puede evitar fácilmente muchas optimizaciones seguras del compilador que pueden tener un gran impacto en el rendimiento incluso si solo necesita una instrucción adicional (y necesita mucho más que eso) ) ¿Significa que debería ser el predeterminado? Tal vez, especialmente en un lenguaje como C # donde decir uncheckedes bastante fácil; pero puede estar sobreestimando la frecuencia con la que el desbordamiento es importante.
Luaan
12
Los ARM addstienen el mismo precio que add(es solo un indicador de instrucción de 1 bit que selecciona si se actualiza el indicador de acarreo). Las addinstrucciones de MIPS quedan atrapadas en el desbordamiento . ¡En su lugar, debe solicitar no atrapar el desbordamiento addu!
user253751
65

¿Quién dice que es una mala compensación?

Ejecuto todas mis aplicaciones de producción con la comprobación de desbordamiento habilitada. Esta es una opción de compilador de C #. De hecho, comparé esto y no pude determinar la diferencia. El costo de acceder a la base de datos para generar HTML (que no sea de juguete) eclipsa los costos de comprobación de desbordamiento.

Aprecio el hecho de que que ninguna operación se desborda en la producción. Casi todo el código se comportaría de manera errática en presencia de desbordamientos. Los errores no serían benignos. La corrupción de los datos es probable, los problemas de seguridad son una posibilidad.

En caso de que necesite el rendimiento, que a veces es el caso, desactivo la comprobación de desbordamiento utilizando unchecked {}de forma granular. Cuando quiero decir que confío en una operación que no se desborda, podría agregar redundantemente checked {}al código para documentar ese hecho. Soy consciente de los desbordamientos, pero no necesariamente tengo que estarlo gracias a la comprobación.

Creo que el equipo de C # tomó la decisión equivocada cuando eligieron no verificar el desbordamiento de forma predeterminada, pero esa opción ahora está sellada debido a fuertes preocupaciones de compatibilidad. Tenga en cuenta que esta elección se realizó alrededor del año 2000. El hardware era menos capaz y .NET todavía no tenía mucha tracción. Tal vez .NET quería atraer a los programadores Java y C / C ++ de esta manera. .NET también está diseñado para poder estar cerca del metal. Es por eso que tiene código inseguro, estructuras y excelentes capacidades de llamadas nativas que Java no tiene.

Cuanto más rápido se vuelve nuestro hardware y los compiladores más inteligentes obtienen la comprobación de desbordamiento más atractiva por defecto.

También creo que la comprobación de desbordamiento suele ser mejor que los números de tamaño infinito. Los números de tamaño infinito tienen un costo de rendimiento que es aún mayor, más difícil de optimizar (creo) y abren la posibilidad de un consumo ilimitado de recursos.

La forma en que JavaScript trata el desbordamiento es aún peor. Los números de JavaScript son dobles de coma flotante. Un "desbordamiento" se manifiesta como un conjunto de enteros totalmente preciso. Ocurrirán resultados ligeramente incorrectos (como estar apagado por uno, esto puede convertir bucles finitos en infinitos).

Para algunos lenguajes como C / C ++, la comprobación de desbordamiento por defecto es claramente inapropiada porque los tipos de aplicaciones que se escriben en estos lenguajes necesitan un rendimiento básico. Aún así, hay esfuerzos para convertir C / C ++ en un lenguaje más seguro al permitir optar por un modo más seguro. Esto es recomendable ya que el 90-99% del código tiende a estar frío. Un ejemplo es la fwrapvopción del compilador que fuerza el ajuste del complemento de 2. Esta es una característica de "calidad de implementación" del compilador, no del lenguaje.

Haskell no tiene una pila de llamadas lógicas ni un orden de evaluación especificado. Esto hace que ocurran excepciones en puntos impredecibles. En a + bqueda sin especificar si ao bse evalúan primero y si esas expresiones terminan en absoluto o no. Por lo tanto, tiene sentido que Haskell use enteros ilimitados la mayor parte del tiempo. Esta opción es adecuada para un lenguaje puramente funcional porque las excepciones son realmente inapropiadas en la mayoría del código Haskell. Y la división por cero es de hecho un punto problemático en el diseño del lenguaje Haskells. En lugar de enteros ilimitados, también podrían haber usado enteros de ajuste de ancho fijo, pero eso no encaja con el tema "centrarse en la corrección" que presenta el lenguaje.

Una alternativa a las excepciones de desbordamiento son los valores tóxicos creados por operaciones indefinidas y propagados a través de operaciones (como el NaNvalor flotante ). Eso parece mucho más costoso que la verificación de desbordamiento y hace que todas las operaciones sean más lentas, no solo las que pueden fallar (salvo la aceleración de hardware que los flotadores comúnmente tienen y los ints comúnmente no tienen, aunque Itanium tiene NaT que no es "una cosa" ). Tampoco veo el punto de hacer que el programa continúe cojeando junto con datos erróneos. Es como ON ERROR RESUME NEXT. Oculta errores pero no ayuda a obtener resultados correctos. Supercat señala que a veces es una optimización del rendimiento hacer esto.

usr
fuente
2
Excelente respuesta Entonces, ¿cuál es su teoría sobre por qué decidieron hacerlo de esa manera? ¿Simplemente copiando a todos los que copiaron C y finalmente ensamblaje y binario?
jpmc26
19
Cuando el 99% de su base de usuarios espera un comportamiento, tiende a dárselos. Y en cuanto a "copiar C", en realidad no es una copia de C, sino una extensión de la misma. C garantiza un comportamiento libre de excepciones unsignedsolo para enteros. El comportamiento del desbordamiento de enteros con signo es en realidad un comportamiento indefinido en C y C ++. Sí, comportamiento indefinido . Sucede que casi todos lo implementan como desbordamiento del complemento de 2. C # en realidad lo hace oficial, en lugar de dejarlo UB como C / C ++
Cort Ammon
10
@CortAmmon: el lenguaje diseñado por Dennis Ritchie había definido el comportamiento envolvente para los enteros con signo, pero no era realmente adecuado para su uso en plataformas que no son dos complementos. Si bien permitir ciertas desviaciones de la envoltura precisa del complemento a dos puede ayudar en gran medida a algunas optimizaciones (por ejemplo, permitir que un compilador reemplace x * y / y con x podría salvar una multiplicación y una división), los escritores del compilador han interpretado el comportamiento indefinido no como una oportunidad para hacerlo lo que tiene sentido para una plataforma objetivo determinada y un campo de aplicación, sino más bien como una oportunidad para arrojar sentido por la ventana.
supercat
3
@CortAmmon: comprueba el código generado por gcc -O2for x + 1 > x(donde xes un int). Ver también gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/… . El comportamiento del complemento 2s en el desbordamiento firmado en C es opcional , incluso en compiladores reales, y por gccdefecto lo ignora en los niveles normales de optimización.
Jonathan Cast
2
@supercat Sí, la mayoría de los escritores de compiladores de C están más interesados ​​en asegurarse de que un punto de referencia poco realista se ejecute 0.5% más rápido que tratar de proporcionar una semántica razonable a los programadores (sí, entiendo por qué no es un problema fácil de resolver y hay algunas optimizaciones razonables que pueden causar resultados inesperados cuando se combinan, yada, yada pero aún así no es foco y lo notas si sigues las conversaciones). Afortunadamente, hay algunas personas que intentan hacerlo mejor .
Voo
30

Porque es una mala compensación para hacer todos los cálculos mucho más caro con el fin de captar automáticamente el raro caso de que un desbordamiento hace aparecer. Es mucho mejor cargar al programador con el reconocimiento de los casos raros en los que esto es un problema y agregar prevenciones especiales que hacer que todos los programadores paguen el precio por la funcionalidad que no usan.

Kilian Foth
fuente
28
Eso es como decir que de alguna manera los controles de desbordamiento del búfer deben omitirse, ya que casi nunca ocurren ...
Bernhard Hiller
73
@BernhardHiller: y eso es exactamente lo que hacen C y C ++.
Michael Borgwardt
12
@DavidBrown: al igual que los desbordamientos aritméticos. Sin embargo, los primeros no comprometen la VM.
Deduplicador
35
@Deduplicator hace un excelente punto. El CLR fue diseñado cuidadosamente para que los programas verificables no puedan violar los invariantes del tiempo de ejecución, incluso cuando suceden cosas malas. Por supuesto, los programas seguros pueden violar a sus propios invariantes cuando suceden cosas malas.
Eric Lippert
77
@svick Las operaciones aritméticas son probablemente mucho más comunes que las operaciones de indexación de matrices. Y la mayoría de los tamaños enteros son lo suficientemente grandes como para que sea muy raro realizar operaciones aritméticas que se desborden. Entonces las relaciones costo-beneficio son muy diferentes.
Barmar
20

¿Cuáles son las decisiones de diseño detrás de un comportamiento tan peligroso?

"No obligue a los usuarios a pagar una penalización de rendimiento por una función que no necesiten".

Es uno de los principios más básicos en el diseño de C y C ++, y se origina en un momento diferente cuando tenía que pasar por contorsiones ridículas para obtener un rendimiento apenas adecuado para las tareas que hoy se consideran triviales.

Los idiomas más nuevos rompen con esta actitud para muchas otras características, como la comprobación de límites de matriz. No estoy seguro de por qué no lo hicieron para la verificación de desbordamiento; Podría ser simplemente un descuido.

Michael Borgwardt
fuente
18
Definitivamente no es un descuido en el diseño de C #. Los diseñadores de C # crearon deliberadamente dos modos: checkedy uncheckedagregaron sintaxis para cambiar entre ellos localmente y también modificadores de línea de comando (y configuraciones de proyecto en VS) para cambiarlo globalmente. Es posible que no uncheckedesté de acuerdo con la configuración predeterminada (lo hago), pero todo esto es claramente muy deliberado.
svick
8
@slebetman: solo para el registro: el costo aquí no es el costo de verificar el desbordamiento (que es trivial), sino el costo de ejecutar un código diferente dependiendo de si ocurrió el desbordamiento (lo cual es muy costoso). A las CPU no les gustan las declaraciones de rama condicionales.
Jonathan Cast
55
@jcast ¿La predicción de bifurcación en los procesadores modernos casi no eliminaría esa penalización de declaración de bifurcación condicional? Después de todo, el caso normal no debería ser un desbordamiento, por lo que es un comportamiento de ramificación muy predecible.
CodeMonkey
44
De acuerdo con @CodeMonkey. Un compilador pondría un salto condicional en caso de desbordamiento, a una página que normalmente no está cargada / fría. La predicción predeterminada para eso es "no tomada", y probablemente no cambiará. La sobrecarga total es una instrucción en la tubería. Pero esa es una sobrecarga de instrucciones por instrucción aritmética.
MSalters
2
@MSalters sí, hay una sobrecarga de instrucciones adicionales. Y el impacto podría ser grande si tiene problemas exclusivamente vinculados a la CPU. En la mayoría de las aplicaciones con una combinación de código pesado de IO y CPU, supongo que el impacto es mínimo. Me gusta la forma Rust, de agregar la sobrecarga solo en las compilaciones de depuración, pero eliminarla en las compilaciones de lanzamiento.
CodeMonkey
20

Legado

Yo diría que el problema probablemente esté enraizado en el legado. Cía:

  • el desbordamiento firmado es un comportamiento indefinido (los compiladores admiten marcas para que se ajuste),
  • el desbordamiento sin signo es un comportamiento definido (se ajusta).

Esto se hizo para obtener el mejor rendimiento posible, siguiendo el principio de que el programador sabe lo que está haciendo .

Conduce a Statu-Quo

El hecho de que C (y por extensión C ++) no requiera la detección de desbordamiento por turnos significa que la comprobación de desbordamiento es lenta.

El hardware abastece principalmente a C / C ++ (en serio, x86 tiene una strcmpinstrucción (también conocida como PCMPISTRI a partir de SSE 4.2)), y dado que a C no le importa, las CPU comunes no ofrecen formas eficientes de detectar desbordamientos. En x86, debe verificar un indicador por núcleo después de cada operación potencialmente desbordante; cuando lo que realmente desea es una bandera "contaminada" en el resultado (al igual que los propagadores de NaN). Y las operaciones vectoriales pueden ser aún más problemáticas. Algunos nuevos jugadores pueden aparecer en el mercado con un manejo eficiente de desbordamiento; pero por ahora a x86 y ARM no les importa.

Los optimizadores del compilador no son buenos para optimizar las comprobaciones de desbordamiento, o incluso para optimizar en presencia de desbordamientos. Algunos académicos como John Regher se quejan de este statu quo , pero el hecho es que cuando el simple hecho de hacer "desbordamientos" de desbordamientos impide optimizaciones incluso antes de que el ensamblaje llegue a la CPU puede ser paralizante. Especialmente cuando evita la auto-vectorización ...

Con efectos en cascada

Por lo tanto, en ausencia de estrategias de optimización eficientes y soporte de CPU eficiente, la verificación de desbordamiento es costosa. Mucho más costoso que envolver.

Agregue un comportamiento molesto, como x + y - 1puede desbordarse cuando x - 1 + yno lo hace, lo que puede molestar legítimamente a los usuarios, y la verificación de desbordamiento generalmente se descarta a favor del ajuste (que maneja este ejemplo y muchos otros con gracia).

Aún así, no toda la esperanza está perdida

Se ha realizado un esfuerzo en los compiladores de clang y gcc para implementar "desinfectantes": formas de instrumentar los binarios para detectar casos de comportamiento indefinido. Cuando se usa -fsanitize=undefined, se detecta un desbordamiento firmado y aborta el programa; Muy útil durante las pruebas.

El lenguaje de programación Rust tiene habilitada la verificación de desbordamiento de forma predeterminada en el modo de depuración (utiliza la aritmética de ajuste en el modo Release por razones de rendimiento).

Por lo tanto, existe una creciente preocupación por la verificación de desbordamiento y los peligros de que los resultados falsos no se detecten, y con suerte esto despertará el interés en la comunidad de investigación, la comunidad de compiladores y la comunidad de hardware.

Matthieu M.
fuente
66
@DmitryGrigoryev es lo opuesto a una forma efectiva de verificar si hay desbordamientos, por ejemplo, en Haswell reduce el rendimiento de 4 adiciones normales por ciclo a solo 1 adición verificada, y eso es antes de considerar el impacto de las predicciones erróneas de las ramas joy Más efectos globales de la contaminación que agregan al estado predictivo de la rama y el aumento del tamaño del código. Si esa bandera fuera pegajosa, ofrecería un potencial real ... y aún así no puede hacerlo correctamente en código vectorizado.
3
Dado que está enlazando a una publicación de blog escrita por John Regehr, pensé que sería apropiado también enlazar a otro de su artículo , escrito unos meses antes del que usted enlazó. Estos artículos hablan de diferentes filosofías: en el artículo anterior, los enteros son de tamaño fijo; la aritmética de enteros se verifica (es decir, el código no puede continuar su ejecución); hay una excepción o una trampa. El artículo más reciente habla sobre deshacerse de enteros de tamaño fijo por completo, lo que elimina los desbordamientos.
rwong
2
@rwong Los enteros de tamaño infinito también tienen sus problemas. Si su desbordamiento es el resultado de un error (que a menudo lo es), puede convertir un bloqueo rápido en una agonía prolongada que consume todos los recursos del servidor hasta que todo falla horriblemente. Soy un gran admirador del enfoque de "fallar temprano": menos posibilidades de envenenar todo el entorno. Preferiría los 1..100tipos de Pascal-ish en su lugar: sea explícito sobre los rangos esperados, en lugar de ser "forzado" a 2 ^ 31, etc. Algunos idiomas ofrecen esto, por supuesto, y tienden a hacer una verificación de desbordamiento por defecto (a veces en tiempo de compilación, incluso).
Luaan
1
@Luaan: Lo interesante es que a menudo los cálculos intermedios pueden desbordarse temporalmente, pero el resultado no. Por ejemplo, en su rango de 1..100, x * 2 - 2puede desbordarse cuando xsea ​​51 a pesar de que el resultado se ajuste, lo que le obligará a reorganizar su cálculo (a veces de manera no natural). En mi experiencia, descubrí que generalmente prefiero ejecutar el cálculo en un tipo más grande y luego verificar si el resultado se ajusta o no.
Matthieu M.
1
@MatthieuM. Sí, ahí es donde entras en el territorio del "compilador suficientemente inteligente". Idealmente, un valor de 103 debería ser válido para un tipo 1..100 siempre y cuando nunca se use en un contexto donde se espera un verdadero 1..100 (por ejemplo, x = x * 2 - 2debería funcionar para todos xdonde la asignación da como resultado un 1 válido. .100 número). Es decir, las operaciones en el tipo numérico pueden tener una precisión más alta que el tipo en sí, siempre y cuando la asignación se ajuste. Esto sería bastante útil en casos como (a + b) / 2ignorar desbordamientos (sin signo) puede ser la opción correcta.
Luaan
10

Los lenguajes que intentan detectar desbordamientos han definido históricamente la semántica asociada de formas que restringieron severamente lo que de otro modo habrían sido optimizaciones útiles. Entre otras cosas, si bien a menudo será útil realizar cálculos en una secuencia diferente de la especificada en el código, la mayoría de los lenguajes que atrapan desbordamientos garantizan ese código dado como:

for (int i=0; i<100; i++)
{
  Operation1();
  x+=i;
  Operation2();
}

si el valor inicial de x causaría un desbordamiento en la 47ª pasada a través del ciclo, la Operación1 se ejecutará 47 veces y la Operación2 ejecutará 46. En ausencia de tal garantía, si nada más dentro del ciclo usa x, y nada usará el valor de x después de una excepción lanzada por Operation1 u Operation2, el código podría reemplazarse con:

x+=4950;
for (int i=0; i<100; i++)
{
  Operation1();
  Operation2();
}

Desafortunadamente, realizar tales optimizaciones al tiempo que garantiza una semántica correcta en los casos en que se hubiera producido un desbordamiento dentro del ciclo es difícil, esencialmente requiere algo como:

if (x < INT_MAX-4950)
{
  x+=4950;
  for (int i=0; i<100; i++)
  {
    Operation1();
    Operation2();
  }
}
else
{
  for (int i=0; i<100; i++)
  {
    Operation1();
    x+=i;
    Operation2();
  }
}

Si se considera que una gran cantidad de código del mundo real usa bucles que están más involucrados, será obvio que optimizar el código mientras se preserva la semántica de desbordamiento es difícil. Además, debido a problemas de almacenamiento en caché, es completamente posible que el aumento en el tamaño del código haga que el programa general se ejecute más lentamente, a pesar de que hay menos operaciones en la ruta de ejecución común.

Lo que se necesitaría para que la detección de desbordamiento sea económica sería un conjunto definido de semánticas de detección de desbordamiento más flexibles, lo que facilitaría que el código informara si se realizó un cálculo sin desbordamientos que pudieran haber afectado los resultados (*), pero sin sobrecargarlo el compilador con detalles más allá de eso. Si una especificación de idioma se enfocara en reducir el costo de la detección de desbordamiento al mínimo necesario para lograr lo anterior, podría hacerse mucho menos costoso de lo que es en los idiomas existentes. Sin embargo, no conozco ningún esfuerzo para facilitar la detección eficiente de desbordamiento.

(*) Si un idioma promete que se informarán todos los desbordamientos, x*y/yno se puede simplificar una expresión como a xmenos que x*yse pueda garantizar que no se desborde. Del mismo modo, incluso si se ignorara el resultado de un cálculo, un lenguaje que prometa informar todos los desbordamientos deberá realizarlo de todos modos para que pueda realizar la verificación de desbordamiento. Dado que el desbordamiento en tales casos no puede dar lugar a un comportamiento aritméticamente incorrecto, un programa no necesitaría realizar tales comprobaciones para garantizar que ningún desbordamiento haya causado resultados potencialmente inexactos.

Por cierto, los desbordamientos en C son especialmente malos. Aunque casi todas las plataformas de hardware que admiten C99 utilizan una semántica envolvente silenciosa de dos complementos, está de moda que los compiladores modernos generen código que puede causar efectos secundarios arbitrarios en caso de desbordamiento. Por ejemplo, dado algo como:

#include <stdint.h>
uint32_t test(uint16_t x, uint16_t y) { return x*y & 65535u; }
uint32_t test2(uint16_t q, int *p)
{
  uint32_t total=0;
  q|=32768;
  for (int i = 32768; i<=q; i++)
  {
    total+=test(i,65535);
    *p+=1;
  }
  return total;
}

GCC generará código para test2 que incrementa incondicionalmente (* p) una vez y devuelve 32768 independientemente del valor pasado a q. Por su razonamiento, el cálculo de (32769 * 65535) y 65535u causaría un desbordamiento y, por lo tanto, no es necesario que el compilador considere ningún caso en el que (q | 32768) arroje un valor mayor que 32768. Aunque no hay Debido a que el cálculo de (32769 * 65535) y 65535u debe preocuparse por los bits superiores del resultado, gcc utilizará un desbordamiento firmado como justificación para ignorar el bucle.

Super gato
fuente
2
"está de moda para los compiladores modernos ..." - de manera similar, estuvo brevemente de moda para los desarrolladores de ciertos núcleos conocidos elegir no leer la documentación con respecto a las banderas de optimización que usaron, y luego actuar enojados en Internet porque se vieron obligados a agregar aún más indicadores del compilador para obtener el comportamiento que querían ;-). En este caso, -fwrapvda como resultado un comportamiento definido, aunque no el comportamiento que el interlocutor desea. Por supuesto, la optimización de gcc convierte cualquier tipo de desarrollo de C en un examen exhaustivo del comportamiento estándar y del compilador.
Steve Jessop
1
@SteveJessop: C sería un lenguaje mucho más saludable si los escritores de compiladores reconocieran un dialecto de bajo nivel donde "comportamiento indefinido" significara "hacer lo que tenga sentido en la plataforma subyacente", y luego agregar formas para que los programadores renuncien a las garantías innecesarias implícitas de ese modo, en lugar de suponer que la frase "no portátil o errónea" en la Norma simplemente significa "errónea". En muchos casos, el código óptimo que se puede obtener en un lenguaje con garantías de comportamiento débiles será mucho mejor que el que se puede obtener con garantías más fuertes o sin garantías. Por ejemplo ...
supercat
1
... si un programador necesita evaluar x+y > zde una manera que nunca hará otra cosa que no sea el rendimiento 0 o el rendimiento 1, pero cualquiera de los resultados sería igualmente aceptable en caso de desbordamiento, un compilador que ofrece esa garantía a menudo podría generar un mejor código para expresión x+y > zque cualquier compilador podría generar para una versión de la expresión escrita a la defensiva. Hablando de manera realista, ¿qué fracción de optimizaciones útiles relacionadas con el desbordamiento se vería impedida por una garantía de que los cálculos enteros distintos de la división / resto se ejecutarán sin efectos secundarios?
supercat
Confieso que no estoy completamente en los detalles, pero el hecho de que tu rencor es con los "escritores de compiladores" en general, y no específicamente "alguien en gcc que no aceptará mi -fwhatever-makes-senseparche", me sugiere fuertemente que hay más a eso de fantasía por su parte. Los argumentos habituales que he escuchado son que la alineación de código (e incluso la expansión de macros) se benefician de deducir tanto como sea posible sobre el uso específico de una construcción de código, ya que cualquiera de las dos cosas comúnmente da como resultado un código insertado que trata casos que no necesita a, que el código circundante "prueba" imposible.
Steve Jessop
Entonces, para un ejemplo simplificado, si escribo foo(i + INT_MAX + 1), los escritores de compiladores están interesados ​​en aplicar optimizaciones al foo()código en línea que se basan en la corrección de su argumento como no negativo (trucos diabólicos divmod, quizás). Bajo sus restricciones adicionales, solo podrían aplicar optimizaciones cuyo comportamiento para entradas negativas tenga sentido para la plataforma. Por supuesto, personalmente me alegraría que esa sea una -fopción que se enciende -fwrapv, etc., y probablemente deba desactivar algunas optimizaciones para las que no hay bandera. Pero no es que me moleste en hacer todo ese trabajo yo mismo.
Steve Jessop
9

No todos los lenguajes de programación ignoran los desbordamientos de enteros. Algunos idiomas proporcionan operaciones enteras seguras para todos los números (la mayoría de los dialectos de Lisp, Ruby, Smalltalk, ...) y otros a través de bibliotecas; por ejemplo, hay varias clases BigInt para C ++.

Si un lenguaje hace que el entero esté a salvo del desbordamiento de forma predeterminada o no, depende de su propósito: los lenguajes del sistema como C y C ++ necesitan proporcionar abstracciones de costo cero y el "entero grande" no es uno. Los lenguajes de productividad, como Ruby, pueden proporcionar grandes números enteros listos para usar. Los lenguajes como Java y C # que están en algún punto intermedio deberían, en mi humilde opinión, ir con los enteros seguros listos para usar, por no decirlo.

Nemanja Trifunovic
fuente
Tenga en cuenta que hay una diferencia entre detectar el desbordamiento (y luego tener una señal, pánico, excepción, ...) y cambiar a números grandes. El primero debería ser factible mucho más barato que el segundo.
Matthieu M.
@MatthieuM. Absolutamente, y me doy cuenta de que no tengo claro eso en mi respuesta.
Nemanja Trifunovic
7

Como ha demostrado, C # habría sido 3 veces más lento si tuviera habilitadas las comprobaciones de desbordamiento de forma predeterminada (suponiendo que su ejemplo sea una aplicación típica para ese idioma). Estoy de acuerdo en que el rendimiento no siempre es la característica más importante, pero los lenguajes / compiladores generalmente se comparan con su rendimiento en tareas típicas. Esto se debe en parte al hecho de que la calidad de las características del lenguaje es algo subjetiva, mientras que una prueba de rendimiento es objetiva.

Si tuviera que introducir un nuevo lenguaje que sea similar a C # en la mayoría de los aspectos pero 3 veces más lento, obtener una cuota de mercado no sería fácil, incluso si al final la mayoría de los usuarios finales se beneficiarían de las comprobaciones de desbordamiento más de lo que lo harían de mayor rendimiento.

Dmitry Grigoryev
fuente
10
Este fue particularmente el caso de C #, que estaba en sus primeros días en comparación con Java y C ++, no en las métricas de productividad del desarrollador, que son difíciles de medir, o en las métricas de efectivo ahorrado por no lidiar con violaciones de seguridad, que son difíciles de medir, pero en puntos de referencia de rendimiento triviales.
Eric Lippert
1
Y probablemente, el rendimiento de la CPU se verifica con un simple cálculo de números. Por lo tanto, las optimizaciones para la detección de desbordamiento pueden arrojar resultados "malos" en esas pruebas. 22 capturas.
Bernhard Hiller
5

Más allá de las muchas respuestas que justifican la falta de comprobación de desbordamiento en función del rendimiento, hay dos tipos diferentes de aritmética a tener en cuenta:

  1. cálculos de indexación (indexación de matriz y / o aritmética de puntero)

  2. otra aritmética

Si el lenguaje usa un tamaño entero que es el mismo que el tamaño del puntero, entonces un programa bien construido no se desbordará haciendo cálculos de indexación porque necesariamente tendría que quedarse sin memoria antes de que los cálculos de indexación causen desbordamiento.

Por lo tanto, verificar las asignaciones de memoria es suficiente cuando se trabaja con aritmética de puntero y expresiones de indexación que involucran estructuras de datos asignadas. Por ejemplo, si tiene un espacio de direcciones de 32 bits y usa números enteros de 32 bits y permite asignar un máximo de 2 GB de almacenamiento dinámico (aproximadamente la mitad del espacio de direcciones), los cálculos de indexación / puntero (básicamente) no se desbordarán.

Además, es posible que se sorprenda de cuánto de la suma / resta / multiplicación implica la indexación de matriz o el cálculo del puntero, por lo tanto, cae en la primera categoría. El puntero de objeto, el acceso a campo y las manipulaciones de matriz son operaciones de indexación, ¡y muchos programas no hacen más cálculos aritméticos que estos! Esencialmente, esta es la razón principal por la que los programas funcionan tan bien como lo hacen sin verificación de desbordamiento de enteros.

Todos los cálculos sin indexación y sin puntero deben clasificarse como aquellos que desean / esperan un desbordamiento (por ejemplo, cálculos de hashing) y aquellos que no lo hacen (por ejemplo, su ejemplo de suma).

En el último caso, los programadores a menudo usarán tipos de datos alternativos, como doubleo algunos BigInt. Muchos cálculos requieren un decimaltipo de datos en lugar de double, por ejemplo, cálculos financieros. Si no lo hacen y se adhieren a los tipos enteros, deben tener cuidado de verificar el desbordamiento de enteros, o de lo contrario, sí, el programa puede alcanzar una condición de error no detectada como usted señala.

Como programadores, debemos ser sensibles a nuestras elecciones en los tipos de datos numéricos y sus consecuencias en términos de posibilidades de desbordamiento, sin mencionar la precisión. En general (y especialmente cuando trabajamos con la familia de lenguajes C con el deseo de usar los tipos enteros rápidos) debemos ser sensibles y conscientes de las diferencias entre los cálculos de indexación frente a otros.

Erik Eidt
fuente
3

El lenguaje Rust proporciona un compromiso interesante entre la comprobación de desbordamientos y no, al agregar las comprobaciones para la compilación de depuración y eliminarlas en la versión de lanzamiento optimizada. Esto le permite encontrar los errores durante las pruebas, mientras obtiene el rendimiento completo en la versión final.

Debido a que el entorno de desbordamiento a veces es un comportamiento deseado, también hay versiones de los operadores que nunca comprueban el desbordamiento.

Puede leer más sobre el razonamiento detrás de la elección en el RFC para el cambio. También hay mucha información interesante en esta publicación de blog , incluida una lista de errores que esta función ha ayudado a detectar.

Hjulle
fuente
2
Rust también proporciona métodos como checked_mul, que comprueba si se ha producido un desbordamiento y devuelve Nonesi es así, de lo Somecontrario. Esto se puede usar tanto en producción como en modo de depuración: doc.rust-lang.org/std/primitive.i32.html#examples-15
Akavall
3

En Swift, cualquier desbordamiento de entero se detecta por defecto y detiene instantáneamente el programa. En los casos en que necesite un comportamiento envolvente, existen diferentes operadores & +, & - y & * que lo logran. Y hay funciones que realizan una operación y dicen si hubo un desbordamiento o no.

Es divertido ver a los principiantes intentar evaluar la secuencia de Collatz y tener su código bloqueado :-)

Ahora, los diseñadores de Swift también son los diseñadores de LLVM y Clang, por lo que saben un par o dos sobre la optimización y son bastante capaces de evitar verificaciones innecesarias de desbordamiento. Con todas las optimizaciones habilitadas, la comprobación de desbordamiento no agrega mucho al tamaño del código y al tiempo de ejecución. Y dado que la mayoría de los desbordamientos conducen a resultados absolutamente incorrectos, el tamaño del código y el tiempo de ejecución bien empleado.

PD. En C, C ++, el desbordamiento aritmético de enteros con signo de Objective-C es un comportamiento indefinido. Eso significa que todo lo que hace el compilador en el caso de desbordamiento de entero con signo es correcto, por definición. Las formas típicas de hacer frente al desbordamiento de enteros con signo es ignorarlo, tomando cualquier resultado que la CPU le dé, construyendo suposiciones en el compilador de que tal desbordamiento nunca sucederá (y concluya, por ejemplo, que n + 1> n siempre es cierto, ya que el desbordamiento es se supone que nunca sucederá), y una posibilidad que rara vez se usa es verificar y bloquearse si ocurre un desbordamiento, como lo hace Swift.

gnasher729
fuente
1
A veces me he preguntado si las personas que están presionando a la locura impulsada por UB en C intentan socavarla en secreto a favor de algún otro lenguaje. Eso tendría sentido.
supercat
Tratar x+1>xcomo incondicionalmente verdadero no requeriría que un compilador haga "suposiciones" sobre x si un compilador puede evaluar expresiones enteras usando tipos arbitrarios más grandes como sea conveniente (o comportarse como si lo estuviera haciendo). Un ejemplo más desagradable de "supuestos" basados ​​en el desbordamiento sería decidir que uint32_t mul(uint16_t x, uint16_t y) { return x*y & 65535u; }un compilador dado puede usar sum += mul(65535, x)para decidir que xno puede ser mayor que 32768 [comportamiento que probablemente sorprendería a las personas que escribieron el Fundamento C89, lo que sugiere que uno de los factores decisivos. ..
supercat
... en la fabricación de unsigned shortpromover en signed intel hecho de que en complemento a dos implementaciones silencio-envolventes (es decir, la mayoría de las implementaciones de C entonces en uso) trataría de código como el de arriba de la misma manera ya sea unsigned shortpromovido a into unsigned. El estándar no requería implementaciones en hardware de complemento silencioso para dos para tratar el código de la manera más acertada, pero los autores del estándar parecen haber esperado que lo hicieran de todos modos.
supercat
2

En realidad, la verdadera causa de esto es puramente técnica / histórica: el signo de ignorar de la CPU en su mayor parte. Por lo general, solo hay una sola instrucción para agregar dos enteros en los registros, y a la CPU no le importa un poco si interpreta estos dos enteros como con signo o sin signo. Lo mismo vale para la resta, e incluso para la multiplicación. La única operación aritmética que necesita ser consciente de signos es la división.

La razón por la cual esto funciona es la representación complementaria de 2 de enteros con signo que es utilizada por prácticamente todas las CPU. Por ejemplo, en el complemento 2 de 4 bits, la adición de 5 y -3 se ve así:

  0101   (5)
  1101   (-3)
(11010)  (carry)
  ----
  0010   (2)

Observe cómo el comportamiento envolvente de tirar la broca produce el resultado firmado correcto. Del mismo modo, las CPU generalmente implementan la resta x - ycomo x + ~y + 1:

  0101   (5)
  1100   (~3, binary negation!)
(11011)  (carry, we carry in a 1 bit!)
  ----
  0010   (2)

Esto implementa la resta como una adición en el hardware, ajustando solo las entradas a la unidad lógica-aritmética (ALU) de manera trivial. ¿Qué podría ser más simple?

Como la multiplicación no es más que una secuencia de adiciones, se comporta de una manera similarmente agradable. El resultado de usar la representación del complemento de 2 e ignorar la realización de operaciones aritméticas es un circuito simplificado y conjuntos de instrucciones simplificados.

Obviamente, dado que C fue diseñado para trabajar cerca del metal, adoptó exactamente el mismo comportamiento que el comportamiento estandarizado de la aritmética sin signo, permitiendo que solo la aritmética con signo produzca un comportamiento indefinido. Y esa elección se trasladó a otros lenguajes como Java y, obviamente, C #.

cmaster
fuente
Vine aquí para dar esta respuesta también.
Sr. Lister
Desafortunadamente, algunas personas parecen considerar como irracional la noción de que las personas que escriben código C de bajo nivel en una plataforma deberían tener la audacia de esperar que un compilador de C adecuado para tal propósito se comportaría de manera restringida en caso de desbordamiento. Personalmente, creo que es razonable que un compilador se comporte como si los cálculos se realizaran con precisión arbitrariamente extendida a conveniencia del compilador (entonces, en un sistema de 32 bits, si x==INT_MAX, entonces x+1podría comportarse arbitrariamente como +2147483648 o -2147483648 en el compilador conveniencia), pero ...
supercat
algunas personas parecen pensar que si xy yson uint16_ty el código en un sistema de 32 bits calcula x*y & 65535ucuando yes 65535, no se llegará a un compilador debe asumir que el código cuando xes mayor que 32768.
supercat
1

Algunas respuestas han discutido el costo de la verificación, y usted ha editado su respuesta para disputar que esta es una justificación razonable. Trataré de abordar esos puntos.

En C y C ++ (como ejemplos), uno de los principios de diseño de los lenguajes es no proporcionar una funcionalidad que no se solicitó. Esto se resume comúnmente en la frase "no pague por lo que no usa". Si el programador desea verificar el desbordamiento, puede solicitarlo (y pagar la multa). Esto hace que el lenguaje sea más peligroso de usar, pero usted elige trabajar con el idioma sabiendo eso, por lo que acepta el riesgo. Si no desea ese riesgo, o si está escribiendo un código donde la seguridad es de rendimiento primordial, puede seleccionar un lenguaje más apropiado donde el equilibrio entre el rendimiento y el riesgo sea diferente.

Pero con las 10,000,000,000 de repeticiones, el tiempo que demora un cheque sigue siendo inferior a 1 nanosegundo.

Hay algunas cosas mal con este razonamiento:

  1. Esto es específico del entorno. Por lo general, tiene muy poco sentido citar cifras específicas como esta, porque el código está escrito para todo tipo de entornos que varían en orden de magnitud en términos de su rendimiento. Su 1 nanosegundo en una máquina de escritorio (supongo) puede parecer increíblemente rápido para alguien que codifica para un entorno incrustado, e insoportablemente lento para alguien que codifica para un súper grupo de computadoras.

  2. 1 nanosegundo puede parecer nada para un segmento de código que se ejecuta con poca frecuencia. Por otro lado, si está en un bucle interno de algún cálculo que es la función principal del código, entonces cada fracción de tiempo que puede eliminar puede hacer una gran diferencia. Si está ejecutando una simulación en un clúster, esas fracciones guardadas de un nanosegundo en su bucle interno pueden traducirse directamente en dinero gastado en hardware y electricidad.

  3. Para algunos algoritmos y contextos, 10,000,000,000 de iteraciones podrían ser insignificantes. Nuevamente, generalmente no tiene sentido hablar sobre escenarios específicos que solo se aplican en ciertos contextos.

Puede haber una situación en la que eso sea importante, pero para la mayoría de las aplicaciones, eso no importará.

Quizás tengas razón. Pero, de nuevo, se trata de cuáles son los objetivos de un idioma en particular. De hecho, muchos idiomas están diseñados para satisfacer las necesidades de "la mayoría" o para favorecer la seguridad sobre otras preocupaciones. Otros, como C y C ++, priorizan la eficiencia. En ese contexto, hacer que todos paguen una penalización de rendimiento simplemente porque la mayoría de las personas no se molestarán, va en contra de lo que el idioma está tratando de lograr.

Jon Bentley
fuente
-1

Hay buenas respuestas, pero creo que hay un punto perdido aquí: los efectos de un desbordamiento de enteros no son necesariamente algo malo, y después de los hechos es difícil saber si ipasó de ser MAX_INTa ser MIN_INTdebido a un problema de desbordamiento o si se hizo intencionalmente multiplicando por -1.

Por ejemplo, si quiero agregar todos los enteros representables mayores que 0 juntos, simplemente usaría un for(i=0;i>=0;++i){...}ciclo de suma y, cuando se desborda, detiene la suma, que es el comportamiento objetivo (arrojar un error significaría que tengo que eludir una protección arbitraria porque está interfiriendo con la aritmética estándar). Es una mala práctica restringir la aritmética primitiva porque:

  • Se usan en todo: una desaceleración en las matemáticas primitivas es una desaceleración en cada programa funcional
  • Si un programador los necesita, siempre pueden agregarlos
  • Si los tiene y el programador no los necesita (pero necesita tiempos de ejecución más rápidos), no pueden eliminarlos fácilmente para la optimización
  • Si los tiene y el programador necesita que no estén allí (como en el ejemplo anterior), el programador está tomando el tiempo de ejecución (que puede o no ser relevante), y el programador aún necesita invertir tiempo para eliminar o trabajando alrededor de la 'protección'.
Delioth
fuente
3
Realmente no es posible para un programador agregar una comprobación de desbordamiento eficiente si un idioma no lo proporciona. Si una función calcula un valor que se ignora, un compilador puede optimizar el cálculo. Si una función calcula un valor que se verifica por desbordamiento pero se ignora, un compilador debe realizar el cálculo y atraparlo si se desborda, incluso si un desbordamiento no afectaría la salida del programa y podría ignorarse de manera segura.
supercat
1
No puedes pasar de INT_MAXa INT_MINmultiplicando por -1.
David Conrad
Obviamente, la solución es proporcionar una forma para que el programador desactive las comprobaciones en un bloque de código o unidad de compilación determinado.
David Conrad
for(i=0;i>=0;++i){...}es el estilo de código que trato de desalentar en mi equipo: se basa en efectos especiales / efectos secundarios y no expresa claramente lo que debe hacer. Pero aún así aprecio su respuesta, ya que muestra un paradigma de programación diferente.
Bernhard Hiller
1
@Delioth: si se itrata de un tipo de 64 bits, incluso en una implementación con un comportamiento de complemento de dos silencioso consistente y envolvente, ejecutando mil millones de iteraciones por segundo, tal ciclo solo podría garantizarse para encontrar el intvalor más grande si se le permite ejecutar cientos de años. En los sistemas que no prometen un comportamiento coherente silencioso, estos comportamientos no estarán garantizados sin importar cuánto tiempo se proporcione el código.
supercat