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

Hay 3 razones para esto:

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

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

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

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

Ejecuto todas mis aplicaciones de producción con la verificació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 (no de juguete) eclipsa los costos de verificación de desbordamiento.

Aprecio el hecho de que sé que no hay operaciones desbordadas en la producción. Casi todo el código se comportaría de forma errática en presencia de desbordamientos. Los bichos no serían benignos. La corrupción de datos es probable, los problemas de seguridad son una posibilidad.

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

Creo que el equipo de C # tomó la decisión equivocada cuando optó por no verificar el desbordamiento por defecto, pero esa opción ahora está sellada debido a problemas de compatibilidad. Tenga en cuenta que esta elección se realizó alrededor del año 2000. El hardware era menos capaz y .NET aún no tenía mucha tracción. Tal vez .NET quería atraer a los programadores de Java y C / C ++ de esta manera. .NET también está destinado a poder estar cerca del metal. Es por eso que tiene códigos no seguros, 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 verificació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 aún mayor, más difícil de optimizar (creo) y abren la posibilidad de un consumo de recursos ilimitado.

La manera de manejar el desbordamiento de JavaScript es aún peor. Los números de JavaScript son dobles de punto flotante. Un "desbordamiento" se manifiesta como si dejara el conjunto de números enteros totalmente preciso. Ligeramente se producirán resultados incorrectos (como estar desactivado por uno, esto puede convertir los bucles finitos en infinitos).

Para algunos idiomas, como C / C ++, el control de desbordamiento por defecto es claramente inadecuado porque los tipos de aplicaciones que se escriben en estos idiomas necesitan un rendimiento completo. Sin embargo, se están realizando esfuerzos para convertir C / C ++ en un lenguaje más seguro permitiendo habilitar en un modo más seguro. Esto es recomendable ya que el 90-99% del código tiende a ser frío. Un ejemplo es la opción del compilador fwrapv que fuerza el ajuste del complemento 2. Esta es una característica de "calidad de implementación" por el compilador, no por el idioma.

Haskell no tiene una pila de llamadas lógica ni un orden de evaluación específico. Esto hace que se produzcan excepciones en puntos impredecibles. En a + b no se especifica si primero se evalúa a o b y si esas expresiones terminan 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 de los códigos de 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 envoltura de ancho fijo, pero eso no encaja con el tema "enfoque en la corrección" que presenta el idioma.

Una alternativa a las excepciones de desbordamiento son los valores venenosos que son creados por operaciones no definidas y se propagan a través de operaciones (como el valor de float NaN ). Eso parece mucho más costoso que la comprobación de desbordamiento y hace que todas las operaciones sean más lentas, no solo las que pueden fallar (excepto la aceleración de hardware que las flotaciones comúnmente tienen y las ints 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 los errores pero no ayuda a obtener resultados correctos. Supercat señala que a veces es una optimización del rendimiento para hacer esto.

Debido a que es una mala compensación hacer que todos los cálculos de todos sean mucho más caros para detectar automáticamente el raro caso de que se produzca un desbordamiento . Es mucho mejor agobiar al programador para que reconozca los casos excepcionales en que esto sea un problema y agregue prevenciones especiales que para que todos los programadores todos paguen el precio por la funcionalidad que no usan.

  

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

"No obligue a los usuarios a pagar una multa por rendimiento por una característica que tal vez no necesiten".

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

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

Legacy

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

• el desbordamiento firmado es un comportamiento indefinido (los compiladores admiten los indicadores para hacer que se ajuste),
• el desbordamiento sin firmar 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 la extensión C ++) no requiera la detección de desbordamiento por turnos significa que la comprobación de desbordamiento es lenta.

El hardware se dirige principalmente a C / C ++ (en serio, x86 tiene una instrucción strcmp (también conocida como PCMPISTRI como de SSE 4.2)!), y como 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 quieres es una bandera "contaminada" en el resultado (como se propaga NaN). Y las operaciones vectoriales pueden ser aún más problemáticas. Algunos jugadores nuevos pueden aparecer en el mercado con un manejo eficiente del desbordamiento; pero por ahora a x86 y ARM no les importa.

Los optimizadores del compilador no son buenos para optimizar los controles 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 desbordes " fallos "evita las optimizaciones incluso antes de que el ensamblaje llegue a la CPU, lo que puede ser paralizante. Especialmente cuando previene la auto-vectorización ...

Con efectos en cascada

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

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

Sin embargo, no se pierde toda la esperanza

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

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

Por lo tanto, existe una creciente preocupación por la verificación de desbordamiento y los peligros de resultados falsos que no se detectan, y esperamos que esto a su vez despierte el interés en la comunidad de investigación, la comunidad de compiladores y la comunidad de hardware.

Los lenguajes que intentan detectar desbordamientos han definido históricamente la semántica asociada de manera que restringen severamente lo que de otra manera habrían sido optimizaciones útiles. Entre otras cosas, aunque a menudo será útil realizar cálculos en una secuencia diferente de lo que se especifica en el código, la mayoría de los idiomas que atrapan los desbordamientos garantizan que el código dado como:

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

si el valor de inicio de x causaría un desbordamiento en la 47a. Pase por el bucle, Operation1 se ejecutará 47 veces y Operation2 Se ejecutará 46. En ausencia de tal garantía, si nada más. dentro del bucle usa x, y nada usará el valor de x siguiente una excepción lanzada por Operation1 u Operation2, el código podría ser reemplazado con:

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

Desafortunadamente, realizar tales optimizaciones mientras se garantiza la semántica correcta en los casos en que se hubiera producido un desbordamiento dentro del bucle es difícil - esencialmente requiriendo 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 muchos códigos del mundo real utilizan bucles que son más involucrados, será obvio que la optimización del código preservando La semántica de desbordamiento es difícil. Además, debido a problemas de almacenamiento en caché, es totalmente posible que el aumento en el tamaño del código haga que el programa en general se ejecute más lentamente a pesar de que haya menos operaciones en la ruta de ejecución común.

Lo que se necesitaría para hacer que la detección de desbordamiento sea barata sería una conjunto definido de semántica de detección de desbordamiento más flexible que facilitaría que el código informe si un cálculo se realizó sin ningún desbordamiento que pudiera haber afectado los resultados (*), pero sin cargar al 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, se podría hacer mucho menos costoso que 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, entonces una expresión como x*y/y no se puede simplificar a x a menos que se pueda garantizar que no se desborde a x*y . 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. Debido a que el desbordamiento en tales casos no puede dar como resultado un comportamiento aritméticamente incorrecto, un programa no tendría que realizar tales controles para garantizar que ningún desbordamiento haya provocado resultados potencialmente inexactos.

Por cierto, los desbordamientos en C son especialmente malos. Aunque casi todas las plataformas de hardware que admiten C99 utilizan semánticas de envoltura silenciosa de complemento a dos, 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á un código para test2 que se incrementa incondicionalmente (* p) una vez y devuelve 32768 independientemente del valor pasado en q. Por su razonamiento, el cálculo de (32769 * 65535) & 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 razón para que el cálculo de (32769 * 65535) & 65535u debe preocuparse por los bits superiores del resultado, gcc utilizará el desbordamiento firmado como justificación para ignorar el bucle.

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

El hecho de que un idioma haga que los enteros no se desborden de manera predeterminada o no depende de su propósito: los lenguajes del sistema como C y C ++ deben proporcionar abstracciones de costo cero y el "entero grande" no es uno. Los lenguajes de productividad, como Ruby, pueden proporcionar grandes enteros fuera de la caja. Los lenguajes como Java y C # que se encuentran en algún lugar intermedio deberían ir con los números enteros seguros fuera de la caja, por el contrario.

Como ha demostrado, C # habría sido 3 veces más lento si hubiera activado las verificaciones de desbordamiento de manera predeterminada (suponiendo que su ejemplo es 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 en su desempeño 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 introdujera un nuevo idioma que sea similar a C # en la mayoría de los aspectos pero 3 veces más lento, obtener una participación de mercado no sería fácil, incluso si al final la mayoría de los usuarios finales se beneficiarían de los controles de desbordamiento más de lo que lo harían con un mayor rendimiento.

Más allá de las muchas respuestas que justifican la falta de control de desbordamiento basado en el rendimiento, hay dos tipos diferentes de aritmética que deben considerarse:

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

2. otra aritmética

Si el idioma usa un tamaño entero que es igual al tamaño del puntero, entonces un programa bien construido no se desbordará haciendo cálculos de indexación porque necesariamente se quedaría 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 punteros y expresiones de indexación que involucran estructuras de datos asignadas. Por ejemplo, si tiene un espacio de direcciones de 32 bits y utiliza números enteros de 32 bits y permite un máximo de 2 GB de almacenamiento dinámico asignado (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 en cuanto a cuánto de la suma / resta / multiplicación implica la indexación de matrices o el cálculo de punteros, por lo que cae en la primera categoría. El puntero del objeto, el acceso a los campos y las manipulaciones de la 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 el control de desbordamiento de enteros.

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

En este último caso, los programadores a menudo usarán tipos de datos alternativos, como double o algo de BigInt . Muchos cálculos requieren un tipo de datos decimal en lugar de double , por ejemplo. cálculos financieros. Si no lo hacen y se apegan a los tipos de enteros, entonces deben tener cuidado de verificar el desbordamiento de enteros, o bien, sí, el programa puede alcanzar una condición de error no detectada como se indica.

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

El lenguaje Rust proporciona un compromiso interesante entre la verificación de desbordamientos y no, al agregar los controles para depurando la compilación y eliminándolos en la versión de lanzamiento optimizada. Esto le permite encontrar los errores durante las pruebas, mientras obtiene un rendimiento completo en la versión final.

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

Puede leer más sobre el razonamiento detrás de la elección en RFC para el cambio. También hay mucha información interesante en esta publicación de blog , incluido un lista de errores que esta característica ha ayudado con la captura.

En Swift, cualquier desbordamiento de enteros se detecta de forma predeterminada y detiene el programa al instante. En los casos en que necesite un comportamiento de envoltura, hay 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 tratar de evaluar la secuencia de Collatz y hacer que su código se bloquee :-)

Ahora los diseñadores de Swift también son diseñadores de LLVM y Clang, por lo que saben un poco o dos acerca de la optimización y son bastante capaces de evitar verificaciones de desbordamiento innecesarias. Con todas las optimizaciones habilitadas, la verificació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 están bien empleados.

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

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

La razón por la que 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 de 4 bits 2, 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 de arrastre produce el resultado firmado correcto. Del mismo modo, las CPU suelen implementar la resta x - y como 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 hardware, ajustando solo las entradas a la unidad lógica-aritmética (ALU) de manera trivial. ¿Qué podría ser más simple?

Dado que la multiplicación no es más que una secuencia de adiciones, se comporta de una manera similar. El resultado de usar la representación del complemento de 2 e ignorar la realización de operaciones aritméticas es una circuitería simplificada y conjuntos de instrucciones simplificados.

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

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

En C y C ++ (como ejemplos), uno de los principios de diseño de lenguajes no es proporcionar funcionalidad que no se solicitó. Esto suele resumirse en la frase "no pague por lo que no usa". Si el programador quiere una verificación de desbordamiento, entonces él / ella puede solicitarla (y pagar la multa). Esto hace que el lenguaje sea más peligroso de usar, pero 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 en el que la seguridad es un desempeño primordial, puede seleccionar un idioma más apropiado en el que la compensación entre rendimiento y riesgo sea diferente.

  

Pero con las 10,000,000,000 repeticiones, el tiempo tomado por un cheque es aún menor a 1 nanosegundo.

Hay algunas cosas mal con este razonamiento:

1. Esto es específico del entorno. Por lo general, no tiene mucho sentido citar cifras específicas como esta, porque el código está escrito para todo tipo de entornos que varían según los órdenes 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 integrado, e insoportablemente lento para alguien que codifica para un súper equipo de computación.

2. 1 nanosegundo puede parecer nada para un segmento de código que se ejecuta con poca frecuencia. Por otro lado, si se encuentra 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 afeitarse puede hacer una gran diferencia. Si está ejecutando una simulación en un grupo, entonces las fracciones guardadas de un nanosegundo en su bucle interno se pueden traducir directamente al dinero gastado en hardware y electricidad.

3. Para algunos algoritmos y contextos, 10,000,000,000 iteraciones podrían ser insignificantes. Nuevamente, generalmente no tiene sentido hablar de 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   Aplicaciones, eso no importará.

Quizás tienes 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 multa por rendimiento simplemente porque la mayoría de la gente no se molestará, va en contra de lo que el lenguaje está tratando de lograr.

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 del hecho es difícil saber si i pasó de ser MAX_INT a ser MIN_INT se debió 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, solo usaría un bucle de adición for(i=0;i>=0;++i){...} y, cuando se desborda, detiene la adición, que es el comportamiento objetivo (lanzar 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 utilizan en todo: una desaceleración en las matemáticas primitivas es una desaceleración en todos los programas que funcionan
• Si un programador los necesita, siempre pueden agregarlos
• Si los tiene y el programador no los necesita (pero sí necesita tiempos de ejecución más rápidos), no pueden eliminarlos fácilmente para su optimización
• Si los tiene y el programador los necesita para no estar allí (como en el ejemplo anterior), el programador está recibiendo el impacto en tiempo de ejecución (lo que puede o no ser relevante) , y el programador aún debe invertir tiempo eliminando o trabajando en torno a la "protección".