Já tentou resumir todos os números de 1 a 2.000.000 na sua linguagem de programação favorita? O resultado é fácil de calcular manualmente: 2.000.001.000.000, que cerca de 900 vezes maior que o valor máximo de um inteiro de 32 bits não assinado.
C # imprime -1453759936 - um valor negativo! E eu acho que o Java faz o mesmo.
Isso significa que existem algumas linguagens de programação comuns que ignoram o Arithmetic Overflow por padrão (em C #, há opções ocultas para mudar isso). Esse é um comportamento que parece muito arriscado para mim, e não foi o acidente do Ariane 5 causado por tal transbordamento?
Então: quais são as decisões de design por trás de um comportamento tão perigoso?
Editar:
As primeiras respostas a esta pergunta expressam os custos excessivos da verificação. Vamos executar um programa C # curto para testar essa suposição: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);
Na minha máquina, a versão verificada leva 11015ms, enquanto a versão desmarcada leva 4125ms. Ou seja as etapas de verificação demoram quase o dobro do tempo para adicionar os números (no total 3 vezes a hora original). Mas com as 10.000.000.000 de repetições, o tempo gasto por uma verificação ainda é inferior a 1 nanossegundo. Pode haver situações em que isso é importante, mas, para a maioria das aplicações, isso não importa.
Editar 2:
Eu recompilei nosso aplicativo de servidor (um serviço do Windows analisando dados recebidos de vários sensores, bastante processamento de dados envolvidos) com o parâmetro /p:CheckForOverflowUnderflow="false" (normalmente, eu alternava a verificação de estouro) e implantei em um dispositivo. O monitoramento do Nagios mostra que a carga média da CPU ficou em 17%.
Isso significa que o hit de desempenho encontrado no exemplo inventado acima é totalmente irrelevante para nossa aplicação.
Existem 3 motivos para isso:
O custo de verificação de sobrecargas (para cada operação aritmética única) em tempo de execução é excessivo.
A complexidade de provar que uma verificação de estouro pode ser omitida em tempo de compilação é excessiva.
Em alguns casos (por exemplo, cálculos de CRC, grandes bibliotecas numéricas, etc.) "wrap on overflow" é mais conveniente para programadores.
Quem disse que é uma troca ruim?!
Eu executo todos os meus aplicativos de produção com a verificação de estouro ativada. Esta é uma opção de compilador C #. Na verdade, aferi isso e não consegui determinar a diferença. O custo de acessar o banco de dados para gerar HTML (sem brinquedo) ofusca os custos de verificação de estouro.
Eu aprecio o fato de que eu conheço que nenhuma operação transborda na produção. Quase todo o código se comportaria de maneira irregular na presença de transbordamentos. Os bugs não seriam benignos. Corrupção de dados é provável, questões de segurança são uma possibilidade.
Caso eu precise de desempenho, o que às vezes é o caso, desabilite a verificação de estouro usando unchecked {} em uma base granular. Quando eu quero dizer que eu confio em uma operação que não está sobrecarregada, eu posso adicionar redundantemente checked {} ao código para documentar esse fato. Estou consciente de transbordamentos, mas não preciso necessariamente ser graças à verificação.
Acredito que a equipe de C # fez a escolha errada quando optou por não verificar o estouro por padrão, mas essa opção agora está selada devido a strongs preocupações de compatibilidade. Note que esta escolha foi feita por volta do ano 2000. O hardware era menos capaz e o .NET ainda não tinha muita tração. Talvez a .NET quisesse atrair programadores Java e C / C ++ dessa maneira. O .NET também deve estar próximo ao metal. É por isso que ele tem código inseguro, estruturas e grandes capacidades de chamadas nativas, tudo o que o Java não possui.
Quanto mais rápido o nosso hardware fica e os compiladores mais inteligentes recebem a verificação de estouro mais atraente por padrão.
Eu também acredito que a verificação de estouro é muitas vezes melhor do que números infinitamente dimensionados. Números infinitamente dimensionados têm um custo de desempenho ainda maior, mais difícil de otimizar (acredito) e abrem a possibilidade de um consumo ilimitado de recursos.
A maneira de lidar com o estouro do JavaScript é ainda pior. Números JavaScript são duplas de ponto flutuante. Um "estouro" se manifesta como deixar o conjunto totalmente preciso de inteiros. Ligeiramente resultados incorretos ocorrerão (como estar desligado por um - isso pode transformar loops finitos em infinitos).
Para alguns idiomas, como a verificação de estouro de C / C ++ por padrão, é claramente inadequado, porque os tipos de aplicativos que estão sendo gravados nesses idiomas precisam de desempenho bare-metal. Ainda assim, existem esforços para tornar o C / C ++ em uma linguagem mais segura, permitindo optar por em um modo mais seguro. Isso é louvável, já que 90-99% do código tende a ser frio. Um exemplo é a opção de compilador fwrapv que força o agrupamento de complemento de 2. Este é um recurso de "qualidade de implementação" pelo compilador, não pela linguagem.
O Haskell não possui pilha de chamadas lógicas e nenhuma ordem de avaliação especificada. Isso faz com que exceções ocorram em pontos imprevisíveis. Em a + b não é especificado se a ou b é avaliado primeiro e se essas expressões terminam ou não. Portanto, faz sentido para Haskell usar números inteiros ilimitados na maioria das vezes. Essa opção é adequada para uma linguagem puramente funcional, pois as exceções são realmente inadequadas na maioria dos códigos Haskell. E a divisão por zero é de fato um ponto problemático no design de linguagem do Haskell. Em vez de inteiros ilimitados, eles poderiam ter usado números inteiros de largura fixa, mas isso não se ajusta ao tema "foco na correção" que a linguagem apresenta.
Uma alternativa às exceções de estouro é valores suspeitos que são criados por operações indefinidas e se propagam por meio de operações (como o valor float NaN ). Isso parece muito mais caro do que a verificação de estouro e torna todas as operações mais lentas, não apenas as que podem falhar (exceto a aceleração de hardware que os flutuadores comumente têm e normalmente não têm - embora Itanium tem NaT, que é "Não é uma coisa" . Eu também não vejo o ponto de fazer o programa continuar a ficar fraco com dados ruins. É como ON ERROR RESUME NEXT . Ele oculta erros, mas não ajuda a obter resultados corretos. O supercat aponta que às vezes é uma otimização de desempenho para fazer isso.
Porque é um compromisso ruim tornar todos os cálculos muito mais caros para capturar automaticamente o caso raro em que ocorre um estouro . É muito melhor sobrecarregar o programador com o reconhecimento dos casos raros em que isso é um problema e adicionar prevenções especiais do que fazer com que todos programadores paguem o preço pelas funcionalidades que não usam.
what are the design decisions behind such a dangerous behavior?
"Não force os usuários a pagar uma penalidade de desempenho por um recurso que eles podem não precisar."
É um dos princípios mais básicos no design de C e C ++, e deriva de uma época diferente em que você teve que passar por contorções ridículas para obter um desempenho insuficiente para tarefas que hoje são consideradas triviais.
Os idiomas mais recentes quebram essa atitude para muitos outros recursos, como a verificação de limites de matriz. Eu não tenho certeza porque eles não fizeram isso para verificação de estouro; pode ser simplesmente um descuido.
Legado
Eu diria que o problema provavelmente está enraizado no legado. Em C:
Isso foi feito para obter o melhor desempenho possível, seguindo o princípio de que o programador sabe o que está fazendo .
Leva ao Statu-Quo
O fato de C (e por extensão C ++) não exigir a detecção de estouro em turnos significa que a verificação de estouro é lenta.
O hardware atende principalmente a C / C ++ (sério, o x86 tem uma instrução strcmp (também conhecida como PCMPISTRI ) SSE 4.2)!) e, como C não se importa, CPUs comuns não oferecem maneiras eficientes de detectar overflows. No x86, você precisa verificar um sinalizador por núcleo após cada operação potencialmente transbordante; quando o que você realmente quer é uma bandeira "contaminada" no resultado (muito parecido com o NaN se propaga). E as operações vetoriais podem ser ainda mais problemáticas. Alguns novos players podem aparecer no mercado com eficiente manuseio de overflow; mas por enquanto x86 e ARM não se importam.
Os otimizadores de compiladores não são bons para otimizar as verificações de estouro, ou até mesmo otimizar na presença de transbordamentos. Alguns acadêmicos, como John Regher, queixam-se desta estátua , mas o fato é que, quando o simples fato de transbordar " falhas "impede que as otimizações, mesmo antes que o conjunto atinja a CPU, possam ser incapacitantes. Especialmente quando previne a autovetorização ...
Com efeitos em cascata
Portanto, na falta de estratégias de otimização eficientes e de suporte eficiente à CPU, a verificação de estouro é cara. Muito mais caro do que embrulho.
Adicione um comportamento irritante, como x + y - 1 pode estourar quando x - 1 + y não, o que pode irritar usuários legitimamente, e a verificação de estouro geralmente é descartada em favor da quebra automática (que lida com este exemplo e muitos outros graciosamente ).
Ainda assim, nem toda esperança está perdida
Houve um esforço nos compiladores clang e gcc para implementar "saneantes": maneiras de instrumentar binários para detectar casos de Comportamento Indefinido. Ao usar -fsanitize=undefined , o estouro assinado é detectado e anula o programa; muito útil durante o teste.
A linguagem de programação Rust tem a verificação de estouro ativada por padrão no modo de depuração (ela usa a divisão de aritmética no modo Release por motivos de desempenho).
Portanto, há uma crescente preocupação com a verificação de estouro e os perigos de resultados falsos passarem despercebidos, e esperamos que isso desperte interesse na comunidade de pesquisa, comunidade de compiladores e comunidade de hardware.
As linguagens que tentam detectar overflows definiram historicamente a semântica associada de maneiras que restringiam severamente o que de outra forma seriam otimizações úteis. Entre outras coisas, embora muitas vezes seja útil realizar cálculos em uma sequência diferente daquela especificada no código, a maioria das linguagens que interceptam transbordamentos garantem que determinado código como:
for (int i=0; i<100; i++)
{
Operation1();
x+=i;
Operation2();
}
se o valor inicial de x causar um estouro na 47ª passar pelo loop, Operation1 executará 47 vezes e Operation2 executará 46. Na ausência de tal garantia, se nada mais dentro do loop usa x, e nada usará o valor de x seguindo uma exceção lançada por Operation1 ou Operation2, o código poderia ser substituído com:
x+=4950;
for (int i=0; i<100; i++)
{
Operation1();
Operation2();
}
Infelizmente, executar essas otimizações garantindo a semântica correta nos casos em que um estouro teria ocorrido dentro do loop é difícil - essencialmente exigir 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();
}
}
Se considerarmos que muitos códigos do mundo real usam loops mais envolvidos, será óbvio que otimizar o código enquanto preserva semântica de estouro é difícil. Além disso, devido a problemas de armazenamento em cache, é totalmente possível que o aumento no tamanho do código faça com que o programa geral seja executado mais lentamente, mesmo que haja menos operações no caminho normalmente executado.
O que seria necessário para tornar a detecção de estouro barato seria um conjunto definido de semânticas de detecção de estouro mais lentas que tornariam fácil para o código relatar se uma computação foi executada sem estouros que possam ter afetado os resultados (*), mas sem sobrecarregar o compilador com detalhes além disso. Se uma especificação de idioma estivesse focada na redução do custo da detecção de excesso para o mínimo necessário para alcançar o que foi mencionado acima, ela poderia ser muito menos dispendiosa do que nos idiomas existentes. Eu não tenho conhecimento de quaisquer esforços para facilitar a detecção eficiente de estouro, no entanto.
(*) Se um idioma prometer que todos os estouros serão informados, uma expressão como x*y/y não poderá ser simplificada para x , a menos que seja garantido que x*y não estourar. Da mesma forma, mesmo que o resultado de uma computação seja ignorado, uma linguagem que prometa informar todos os estouros precisará executá-la de qualquer maneira, para que possa realizar a verificação de estouro. Como o estouro em tais casos não pode resultar em um comportamento aritmeticamente incorreto, um programa não precisaria executar essas verificações para garantir que nenhum estouro de informações tenha causado resultados potencialmente imprecisos.
A propósito, os overflows em C são especialmente ruins. Embora quase todas as plataformas de hardware que suportam C99 usem a semântica silenciosa envolvente de complemento de dois, está na moda para os compiladores modernos gerar código que pode causar efeitos colaterais arbitrários em caso de estouro. Por exemplo, 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;
}
O GCC gerará código para o test2, que incrementa incondicionalmente (* p) uma vez e retorna 32768, independentemente do valor passado para q. Pelo seu raciocínio, o cálculo de (32769 * 65535) & 65535u causaria um estouro e, portanto, não há necessidade de o compilador considerar qualquer caso em que (q | 32768) produziria um valor maior do que 32768. Mesmo que não haja razão para que o cálculo de (32769 * 65535) & 65535u deve se preocupar com os bits superiores do resultado, o gcc usará o estouro assinado como justificativa para ignorar o loop.
Nem todas as linguagens de programação ignoram estouros de inteiro. Algumas linguagens fornecem operações inteiras seguras para todos os números (a maioria dos dialetos Lisp, Ruby, Smalltalk, ...) e outros através de bibliotecas - por exemplo, existem várias classes BigInt para C ++.
Se uma linguagem torna o inteiro seguro contra estouro por padrão ou não, depende de sua finalidade: linguagens de sistema como C e C ++ precisam fornecer abstrações de custo zero e "inteiro grande" não é um. Linguagens de produtividade, como Ruby, podem fornecer grandes números inteiros prontos para uso. Idiomas como Java e C # que estão em algum lugar no meio devem IMHO ir com os inteiros seguros fora da caixa, por eles não o fazem.
Como você mostrou, o C # teria sido 3 vezes mais lento se as verificações de overflow estivessem ativadas por padrão (supondo que seu exemplo seja um aplicativo típico para esse idioma). Concordo que o desempenho nem sempre é o recurso mais importante, mas os idiomas / compiladores são normalmente comparados em seu desempenho em tarefas típicas. Isso se deve em parte ao fato de que a qualidade dos recursos de linguagem é um tanto subjetiva, enquanto um teste de desempenho é objetivo.
Se você introduzisse um novo idioma semelhante ao C # na maioria dos aspectos, mas 3 vezes mais lento, obter uma participação de mercado não seria fácil, mesmo que no final a maioria dos usuários finais se beneficiasse de verificações de estouro do que eles teriam de melhor desempenho.
Além das muitas respostas que justificam a falta de verificação de excesso com base no desempenho, existem dois tipos diferentes de aritmética a serem considerados:
indexação de cálculos (indexação de matrizes e / ou aritmética de ponteiros)
outra aritmética
Se o idioma usar um tamanho inteiro igual ao tamanho do ponteiro, um programa bem construído não sobrecarregará os cálculos de indexação, porque ele necessariamente teria que ficar sem memória antes que os cálculos de indexação causassem estouro.
Portanto, verificar as alocações de memória é suficiente ao trabalhar com expressões aritméticas e de indexação de ponteiro envolvendo estruturas de dados alocadas. Por exemplo, se você tiver um espaço de endereço de 32 bits e usar números inteiros de 32 bits e permitir um máximo de 2 GB de heap alocado (cerca de metade do espaço de endereço), os cálculos de indexação / ponteiro (basicamente) não estourarão.Além disso, você pode se surpreender com o quanto de adição / subtração / multiplicação envolve a indexação de matrizes ou o cálculo de ponteiros, caindo assim na primeira categoria. Ponteiros de objetos, acesso a campos e manipulações de array são operações de indexação, e muitos programas não fazem mais cálculo aritmético do que estes! Essencialmente, este é o principal motivo pelo qual os programas funcionam tão bem quanto o fazem sem verificação de estouro de inteiro.
Todos os cálculos sem indexação e sem ponteiro devem ser classificados como aqueles que desejam / esperam estouro (por exemplo, cálculos de hashing) e aqueles que não desejam (por exemplo, seu exemplo de soma).
No último caso, os programadores frequentemente usam tipos de dados alternativos, como double ou algum BigInt . Muitos cálculos exigem um tipo de dados decimal em vez de double , por ex. cálculos financeiros. Se não o fizerem e ficar com os tipos inteiros, então eles precisam tomar cuidado para verificar o estouro de inteiro - ou então, sim, o programa pode alcançar uma condição de erro não detectada conforme você está apontando.
Como programadores, precisamos ser sensíveis às nossas escolhas em tipos de dados numéricos e as conseqüências deles em termos de possibilidades de estouro, para não mencionar a precisão. Em geral (e especialmente quando se trabalha com a família de linguagens C com o desejo de usar os tipos inteiros rápidos), precisamos ser sensíveis e conscientes das diferenças entre cálculos de indexação e outros.
O idioma Ferrugem fornece um compromisso interessante entre a verificação de estouros e não, adicionando as verificações depuração compilar e removê-los na versão de lançamento otimizada. Isso permite que você encontre os bugs durante o teste, enquanto ainda obtém desempenho total na versão final.
Como o comportamento de estouro é às vezes desejado, também há versões dos operadores que nunca verifica o estouro.
Você pode ler mais sobre o raciocínio por trás da escolha na RFC para a mudança. Há também muitas informações interessantes em este post , incluindo um lista de bugs que esta funcionalidade ajudou na captura.
No Swift, qualquer transbordamento de inteiros é detectado por padrão e interrompe instantaneamente o programa. Nos casos em que você precisa de um comportamento envolvente, existem diferentes operadores & +, & - e & * que conseguem isso. E há funções que executam uma operação e informam se houve um estouro ou não.
É divertido assistir aos iniciantes tentando avaliar a sequência do Collatz e ter seu código travado: -)
Agora, os projetistas do Swift também são os designers do LLVM e do Clang, então eles sabem um pouco ou dois sobre otimização e são bem capazes de evitar verificações desnecessárias de estouro. Com todas as otimizações habilitadas, a verificação de estouro não adiciona muito ao tamanho do código e ao tempo de execução. E como a maioria dos transbordamentos leva a resultados absolutamente incorretos, o tamanho do código e o tempo de execução são bem aproveitados.
PS. Em C, C ++, o excedente aritmético inteiro assinado Objective-C é um comportamento indefinido. Isso significa que o que o compilador fizer no caso de estouro de inteiro assinado está correto, por definição. Maneiras típicas de lidar com o estouro de inteiro assinado é ignorá-lo, tomando qualquer resultado que a CPU forneça, construindo suposições no compilador de que tal estouro nunca acontecerá (e concluir, por exemplo, que n + 1 > n é sempre verdadeiro, já que estouro Presume-se que isso nunca aconteça), e uma possibilidade que raramente é usada é verificar e travar se ocorrer um transbordamento, como acontece com o Swift.
Na verdade, a causa real para isso é puramente técnica / histórica: na maioria das vezes, o sinal ignorar da CPU. Geralmente, há apenas uma única instrução para adicionar dois inteiros em registradores, e a CPU não se importa um pouco se você interpreta esses dois inteiros como assinados ou não assinados. O mesmo vale para subtração e até para multiplicação. A única operação aritmética que precisa ser consciente de sinais é a divisão.
A razão pela qual isso funciona é a representação do complemento de 2 de inteiros assinados que é usado por praticamente todos os processadores. Por exemplo, no complemento de 4 bits 2 a adição de 5 e -3 se parece com isso:
0101 (5)
1101 (-3)
(11010) (carry)
----
0010 (2)
Observe como o comportamento wrap-around de jogar fora o bit carry-out produz o resultado assinado correto. Da mesma forma, as CPUs geralmente implementam a subtração x - y as x + ~y + 1 :
0101 (5)
1100 (~3, binary negation!)
(11011) (carry, we carry in a 1 bit!)
----
0010 (2)
Isto implementa a subtração como uma adição em hardware, ajustando apenas as entradas para a unidade lógica-aritmética (ULA) de formas triviais. O que poderia ser mais simples?
Como a multiplicação nada mais é do que uma sequência de acréscimos, ela se comporta de maneira igualmente agradável. O resultado de usar a representação de complemento de 2 e ignorar a execução de operações aritméticas é um circuito simplificado e conjuntos de instruções simplificados.
Obviamente, como o C foi projetado para trabalhar próximo ao metal, adotou exatamente o mesmo comportamento do comportamento padronizado da aritmética sem sinal, permitindo que apenas a aritmética assinada produzisse um comportamento indefinido. E essa escolha foi transferida para outras linguagens como Java e, obviamente, C #.Algumas respostas discutiram o custo da verificação e você editou sua resposta para contestar que essa é uma justificativa razoável. Vou tentar abordar esses pontos.
Em C e C ++ (como exemplos), um dos princípios de design de idiomas não é fornecer funcionalidade que não foi solicitada. Isso é comumente resumido pela frase "não pague pelo que você não usa". Se o programador quiser checar o estouro, ele pode pedir (e pagar a penalidade). Isso torna a linguagem mais perigosa de usar, mas você escolhe trabalhar com o idioma sabendo disso, então aceita o risco. Se você não quer esse risco, ou se você está escrevendo códigos onde a segurança é de desempenho supremo, então você pode selecionar um idioma mais apropriado onde a relação desempenho / risco é diferente.
But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond.
Existem algumas coisas erradas com este raciocínio:
Isso é específico do ambiente. Geralmente faz muito pouco sentido citar figuras específicas como essa, porque o código é escrito para todos os tipos de ambientes que variam em ordem de grandeza em termos de desempenho. Seu 1 nanossegundo em uma (eu presumo) máquina desktop pode parecer incrivelmente rápido para alguém codificando para um ambiente embarcado, e insuportavelmente lento para alguém codificando um super cluster de computador.
1 nanossegundo pode parecer nada para um segmento de código que é executado com pouca frequência. Por outro lado, se estiver em um loop interno de algum cálculo que é a principal função do código, então cada fração de tempo que você pode eliminar pode fazer uma grande diferença. Se você estiver executando uma simulação em um cluster, as frações salvas de um nanossegundo em seu loop interno podem se traduzir diretamente em dinheiro gasto em hardware e eletricidade.
Para alguns algoritmos e contextos, 10.000.000.000 de iterações podem ser insignificantes. Novamente, geralmente não faz sentido falar sobre cenários específicos que só se aplicam em certos contextos.
There may be situation where that is important, but for most applications, that won't matter.
Talvez você esteja certo. Mas, novamente, isso é uma questão de quais são os objetivos de um idioma específico. Muitas línguas são, de fato, projetadas para acomodar as necessidades de "mais" ou para favorecer a segurança em detrimento de outras preocupações. Outros, como C e C ++, priorizam a eficiência. Nesse contexto, fazer com que todos paguem uma penalidade de desempenho simplesmente porque a maioria das pessoas não será incomodada, vai contra o que a linguagem está tentando alcançar.
Existem boas respostas, mas acho que há um ponto perdido aqui: os efeitos de um estouro de inteiro não são necessariamente uma coisa ruim, e depois do fato é difícil saber se i foi de MAX_INT para ser MIN_INT foi devido a um problema de estouro ou se foi intencionalmente feito multiplicando por -1.
Por exemplo, se eu quiser adicionar todos os inteiros representáveis maiores que 0 juntos, eu usaria apenas um loop de adição for(i=0;i>=0;++i){...} - e quando ele estourar, ele interromperá a adição, que é o comportamento do objetivo (lançar um erro significaria que tenho de contornar uma proteção arbitrária porque está interferindo na aritmética padrão). É uma prática ruim restringir a aritmética primitiva, porque: