Pourquoi le dépassement arithmétique est-il ignoré?

76

Avez-vous déjà essayé de résumer tous les nombres de 1 à 2 000 000 dans votre langage de programmation préféré? Le résultat est facile à calculer manuellement: 2 000 001 000 000, soit 900 fois la valeur maximale d’un nombre entier non signé de 32 bits.

C # imprime -1453759936- une valeur négative! Et je suppose que Java fait la même chose.

Cela signifie que certains langages de programmation courants ignorent le débordement arithmétique par défaut (en C #, il existe des options cachées pour le changer). C'est un comportement qui me semble très risqué, et le crash d'Ariane 5 n'a-t-il pas été causé par un tel débordement?

Alors: quelles sont les décisions de conception derrière un comportement aussi dangereux?

Modifier:

Les premières réponses à cette question expriment les coûts excessifs de la vérification. Exécutons un court programme C # pour tester cette hypothèse:

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);

Sur ma machine, la version vérifiée prend 11015 ms, tandis que la version non vérifiée prend 4125 ms. C'est-à-dire que les étapes de vérification prennent presque deux fois plus longtemps que l'ajout des nombres (au total, trois fois le temps initial). Mais avec les 10 000 000 000 de répétitions, le temps nécessaire à un contrôle est toujours inférieur à 1 nanoseconde. Il peut y avoir une situation où cela est important, mais pour la plupart des applications, cela n’a aucune importance.

Edit 2:

J'ai recompilé notre application serveur (un service Windows analysant les données reçues de plusieurs capteurs, avec un certain nombre de calculs complexes) avec le /p:CheckForOverflowUnderflow="false"paramètre (normalement, j'active le contrôle de débordement) et je l'ai déployé sur un périphérique. La surveillance de Nagios montre que la charge moyenne du processeur est restée stable à 17%.

Cela signifie que l'impact sur les performances constaté dans l'exemple ci-dessus n'est absolument pas pertinent pour notre application.

Bernhard Hiller
la source
19
À titre de remarque, pour C #, vous pouvez utiliser checked { }section pour marquer les parties du code devant effectuer des contrôles de débordement arithmétique. Cela est dû à la performance
Paweł Łukasik
14
"Avez-vous déjà essayé de résumer tous les chiffres de 1 à 2 000 000 dans votre langue de programmation préférée?" - Oui: (1..2_000_000).sum #=> 2000001000000. Un autre de mes langues préférées: sum [1 .. 2000000] --=> 2000001000000. Pas mon préféré: Array.from({length: 2000001}, (v, k) => k).reduce((acc, el) => acc + el) //=> 2000001000000. (Pour être juste, le dernier triche.)
Jörg W Mittag
27
@ BernhardHiller Integerà Haskell est de précision arbitraire, il contiendra n'importe quel nombre tant que vous ne manquerez pas de RAM allouable.
Polygnome
50
L’accident d’Ariane 5 a été provoqué par la recherche d’un débordement sans importance - la fusée se trouvait dans une partie du vol où le résultat d’un calcul n’était même plus nécessaire. À la place, le débordement a été détecté, ce qui a provoqué l’annulation du vol.
Simon B
9
But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond.c'est une indication de la boucle en cours d'optimisation. Cette phrase contredit également les chiffres précédents qui me paraissent très valables.
USR

Réponses:

86

Il y a 3 raisons à cela:

  1. Le coût de la vérification des débordements (pour chaque opération arithmétique) au moment de l'exécution est excessif.

  2. Il est excessif de prouver qu’un contrôle de dépassement de capacité peut être omis au moment de la compilation.

  3. Dans certains cas (par exemple, calculs CRC, bibliothèques de grands nombres, etc.), le "débordement intégral" est plus pratique pour les programmeurs.

Brendan
la source
10
@DmitryGrigoryev unsigned intne devrait pas venir à l'esprit car une langue avec contrôle de débordement devrait vérifier tous les types d'entiers par défaut. Vous devriez avoir à écrire wrapping unsigned int.
user253751
32
Je n'achète pas l'argument des coûts. La CPU vérifie le débordement lors de chaque calcul d'entier CHAQUE SEUL et règle le drapeau de retenue dans l'ALU. C'est le support du langage de programmation qui manque. Une simple didOverflow()fonction en ligne ou même une variable globale __carrypermettant d'accéder à l'indicateur de portage ne coûterait pas de temps CPU si vous ne l'utilisez pas.
slebetman
37
@slebetman: C'est x86. ARM non. Par exemple, ADDne met pas le carry (vous avez besoin ADDS). Itanium n'a même pas avoir un drapeau de transport. Et même sur x86, AVX n’a pas de drapeau de transport.
MSalters
30
@slebetman Il active le drapeau de report, oui (sur x86, remarquez). Mais ensuite, vous devez lire le drapeau et décider du résultat - c'est la partie la plus chère. Etant donné que les opérations arithmétiques sont souvent utilisées dans les boucles (et les boucles serrées), ceci peut facilement empêcher de nombreuses optimisations sûres du compilateur pouvant avoir un impact très important sur les performances, même si vous n'avez besoin que d'une instruction supplémentaire (et de beaucoup plus que cela). ). Cela signifie-t-il que cela devrait être la valeur par défaut? Peut-être, surtout dans un langage comme C # où dire uncheckedest assez facile; mais vous pourriez peut-être surestimer la fréquence des dépassements.
Luaan
12
ARM a addsle même prix que add(c'est juste un indicateur d'instruction sur 1 bit qui détermine si l'indicateur de report est mis à jour). Les addpièges d'instructions de MIPS sur le débordement - vous devez demander à ne pas piéger sur le débordement en utilisant à la adduplace!
user253751
65

Qui a dit que c'était un mauvais compromis?!

Je lance toutes mes applications de production avec la vérification de débordement activée. C'est une option du compilateur C #. En fait, j’ai comparé cela et j’ai été incapable de déterminer la différence. Le coût d'accès à la base de données pour générer du HTML (non-jouet) éclipse les coûts de la vérification du débordement.

J'apprécie le fait que je sais qu'aucune opération ne déborde en production. Presque tout le code se comporterait de manière erratique en présence de débordements. Les insectes ne seraient pas bénins. La corruption des données est probable, des problèmes de sécurité sont possibles.

Au cas où j'aurais besoin de la performance, ce qui est parfois le cas, je désactive la vérification de débordement en utilisant des unchecked {}paramètres granulaires. Lorsque je veux dire que je compte sur une opération qui ne déborde pas, je peux ajouter de manière redondante checked {}au code pour documenter ce fait. Je suis conscient des débordements mais je n’ai pas nécessairement besoin d’être grâce à la vérification.

Je pense que l'équipe C # a fait le mauvais choix en choisissant de ne pas vérifier le débordement par défaut, mais ce choix est maintenant scellé pour des raisons de compatibilité. Notez que ce choix a été fait vers l'an 2000. Le matériel était moins performant et .NET n'avait pas encore beaucoup de traction. Peut-être que .NET voulait faire appel aux programmeurs Java et C / C ++ de cette manière. .NET est également destiné à pouvoir être proche du métal. C'est pourquoi il a un code non sécurisé, des structures et de grandes capacités d'appel natif que Java n'a pas.

Plus notre matériel est rapide et plus les compilateurs intelligents obtiennent la vérification de débordement plus intéressante par défaut.

Je pense aussi que la vérification du débordement est souvent meilleure que celle des nombres infinis. Les nombres infinis ont un coût de performance encore plus élevé, plus difficile à optimiser (je crois) et ils ouvrent la possibilité d'une consommation de ressources illimitée.

La façon dont JavaScript gère les débordements est encore pire. Les nombres JavaScript sont des doubles en virgule flottante. Un "débordement" se manifeste en laissant l'ensemble parfaitement précis d'entiers. Des résultats légèrement erronés se produiront (par exemple, être mis hors tension par un - cela peut transformer des boucles finies en boucles infinies).

Pour certains langages tels que le dépassement de capacité en C / C ++, la vérification par défaut est clairement inappropriée car les types d'applications écrites dans ces langages requièrent des performances sans système d'exploitation. Néanmoins, des efforts sont déployés pour rendre le langage C / C ++ plus sûr en permettant de s’inscrire en mode plus sûr. C'est louable car 90 à 99% du code a tendance à être froid. Un exemple est l' fwrapvoption du compilateur qui force le wrapping du complément à 2. Ceci est une fonctionnalité de "qualité d'implémentation" par le compilateur, pas par le langage.

Haskell n'a pas de pile d'appels logiques ni d'ordre d'évaluation spécifié. Cela crée des exceptions à des moments imprévisibles. Il a + bn'est pas spécifié si aou best évalué en premier et si ces expressions se terminent ou non. Par conséquent, il est logique que Haskell utilise la plupart du temps des entiers non liés. Ce choix convient à un langage purement fonctionnel car les exceptions sont vraiment inappropriées dans la plupart des codes Haskell. Et la division par zéro est en effet un point problématique dans la conception du langage Haskells. Au lieu d’entiers non liés, ils auraient pu utiliser des entiers enveloppants à largeur fixe, mais cela ne correspond pas au thème "focus on correct" mis en avant par le langage.

Une alternative aux exceptions de dépassement de capacité est constituée par des valeurs toxiques créées par des opérations non définies et propagées par des opérations (comme la NaNvaleur float ). Cela semble beaucoup plus coûteux que la vérification du débordement et rend toutes les opérations plus lentes, pas seulement celles qui peuvent échouer (à part l’accélération matérielle qui flotte et que l’intensité n’a généralement pas, bien qu’Itanium ait NaT qui n’est "pas une chose" ). Je ne vois pas non plus l'intérêt de faire en sorte que le programme continue de boiter avec de mauvaises données. C'est comme ON ERROR RESUME NEXT. Il cache les erreurs mais n’aide pas à obtenir des résultats corrects. Supercat souligne que cela représente parfois une optimisation des performances.

usr
la source
2
Excellente réponse. Alors, quelle est votre théorie sur la raison pour laquelle ils ont décidé de le faire de cette façon? Copier simplement tous ceux qui ont copié C et finalement assembler et binaire?
jpmc26
19
Lorsque 99% de vos utilisateurs s'attendent à un comportement, vous avez tendance à le leur donner. Et pour ce qui est de "copier C", ce n’est pas une copie de C, mais une extension de celle-ci. C garantit un comportement sans exception pour les unsignedentiers uniquement. Le comportement du dépassement d'entier signé est en réalité un comportement indéfini en C et C ++. Oui, comportement indéfini . Il se trouve que presque tout le monde l’implémente en tant que complément à 2. C # le rend réellement officiel, plutôt que de le laisser UB comme C / C ++
Cort Ammon
10
@CortAmmon: le langage conçu par Dennis Ritchie avait un comportement enveloppant défini pour les entiers signés, mais n'était pas vraiment adapté à une utilisation sur des plates-formes sans complément à deux. Bien que le fait d'autoriser certaines déviations par rapport à un complément à deux complément précis peut grandement aider certaines optimisations (par exemple, permettre à un compilateur de remplacer x * y / y avec x pourrait enregistrer une multiplication et une division), les auteurs du compilateur ont interprété le comportement non défini comme une opportunité. Ce qui est logique pour une plate-forme cible et un champ d'application donnés, mais plutôt comme une opportunité de jeter un sens par la fenêtre.
Supercat
3
@CortAmmon - Vérifiez le code généré par gcc -O2pour x + 1 > x(où xest un int). Voir aussi gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/… . Le comportement en complément à 2s sur le dépassement signé en C est facultatif , même dans les vrais compilateurs, et l' gccignore par défaut dans les niveaux d'optimisation normaux.
Jonathan Cast
2
@supercat Oui, la plupart des rédacteurs du compilateur C sont plus intéressés à s'assurer que certains tests non réalistes s'exécutent 0,5% plus vite que d'essayer de fournir une sémantique raisonnable aux programmeurs (oui, je comprends pourquoi ce n'est pas un problème facile à résoudre et certaines optimisations raisonnables peuvent en résulter résultats inattendus une fois combinés, yada, yada mais ce n’est tout simplement pas une cible et vous le remarquez si vous suivez les conversations). Heureusement, il y a des gens qui essaient de faire mieux .
Voo
30

Parce qu'il est un mauvais compromis pour faire tous les calculs beaucoup plus cher afin de rattraper automatiquement les rares cas où un débordement ne se produire. Il est bien mieux de charger le programmeur de reconnaître les rares cas où cela pose un problème et d'ajouter des mesures préventives spéciales plutôt que de faire payer à tous les programmeurs le prix des fonctionnalités qu'ils n'utilisent pas.

Kilian Foth
la source
28
C'est en quelque sorte comme si on disait que les vérifications de dépassement de tampon doivent être omises car elles ne se produisent presque jamais ...
Bernhard Hiller
73
@ BernardHiller: et c'est exactement ce que font C et C ++.
Michael Borgwardt
12
@DavidBrown: De même que les débordements arithmétiques. Les premiers ne compromettent cependant pas la VM.
Déduplicateur
35
@Duplicator fait un excellent point. Le CLR a été soigneusement conçu pour que des programmes vérifiables ne puissent pas violer les invariants du runtime, même en cas de problème. Les programmes sûrs peuvent bien sûr violer leurs propres invariants lorsque de mauvaises choses se produisent.
Eric Lippert
7
@svick Les opérations arithmétiques sont probablement beaucoup plus courantes que les opérations d'indexation de tableaux. Et la plupart des tailles entières sont suffisamment grandes pour qu'il soit très rare d'effectuer une arithmétique qui déborde. Les ratios coûts-avantages sont donc très différents.
Barmar
20

Quelles sont les décisions de conception derrière un comportement aussi dangereux?

"Ne forcez pas les utilisateurs à payer une pénalité de performance pour une fonctionnalité dont ils n'ont peut-être pas besoin."

C’est l’un des principes les plus fondamentaux de la conception de C et C ++, et découle d’une époque différente où il fallait passer par des contorsions ridicules pour obtenir des performances à peine suffisantes pour des tâches qui sont aujourd’hui considérées comme triviales.

Les nouvelles langues rompent avec cette attitude pour de nombreuses autres fonctionnalités, telles que la vérification des limites du tableau. Je ne sais pas pourquoi ils ne l'ont pas fait pour vérifier les débordements; ce pourrait être simplement un oubli.

Michael Borgwardt
la source
18
Ce n'est certainement pas un oubli dans la conception de C #. Les concepteurs de C # ont délibérément créé deux modes: checkedet unchecked, ils ont ajouté une syntaxe pour basculer localement entre eux et des commutateurs de ligne de commande (ainsi que des paramètres de projet dans VS) pour les modifier globalement. Vous pouvez être en désaccord avec uncheckedle choix par défaut (je le fais), mais tout cela est clairement très délibéré.
svick
8
@slebetman - juste pour l'enregistrement: le coût ici n'est pas le coût de la vérification du débordement (ce qui est trivial), mais le coût de l'exécution d'un code différent selon que le dépassement s'est produit (ce qui est très coûteux). Les processeurs n'aiment pas les instructions de branche conditionnelles.
Jonathan Cast
5
@jcast La prédiction de branche sur les processeurs modernes n'éliminerait-elle pas presque cette pénalité d'instruction de branche conditionnelle? Après tout, le cas normal ne devrait pas entraîner de dépassement de capacité, ce qui en fait un comportement de branchement très prévisible.
CodeMonkey
4
D'accord avec @CodeMonkey. Un compilateur mettrait un saut conditionnel en cas de débordement, vers une page qui n'est normalement pas chargée / froide. La prédiction par défaut pour cela est "non prise" et ne changera probablement pas. Les frais généraux totaux sont une instruction dans le pipeline. Mais cela représente une surcharge d’instruction par instruction arithmétique.
MSalters
2
@MSalters Oui, il y a une surcharge d'instruction supplémentaire. Et l'impact pourrait être important si vous rencontrez exclusivement des problèmes liés au processeur. Dans la plupart des applications avec un mélange de code lourd d'E / S et d'UC, l'impact serait minime. J'aime la méthode Rust, qui consiste à ajouter la surcharge uniquement dans les versions Debug, mais à la supprimer dans les versions Release.
CodeMonkey
20

Héritage

Je dirais que le problème est probablement enraciné dans l'héritage. En C:

  • le dépassement signé est un comportement indéfini (les compilateurs prennent en charge des indicateurs pour le rendre bouclé),
  • Le débordement non signé est un comportement défini (il enveloppe).

Cela a été fait pour obtenir la meilleure performance possible, en suivant le principe que le programmeur sait ce qu'il fait .

Conduit à Statu-Quo

Le fait que C (et par extension C ++) ne nécessite pas la détection de débordement à tour de rôle signifie que la vérification du débordement est lente.

Le matériel s'adresse principalement au C / C ++ (sérieusement, x86 a une strcmpinstruction (alias PCMPISTRI à partir de SSE 4.2)!), Et comme C ne s’en soucie pas, les processeurs classiques n’offrent pas de moyen efficace de détecter les débordements. En x86, vous devez cocher un indicateur par cœur après chaque opération susceptible de déborder. quand ce que vous voulez vraiment est un drapeau "corrompu" sur le résultat (un peu comme le fait NaN). Et les opérations vectorielles peuvent être encore plus problématiques. Certains nouveaux acteurs peuvent apparaître sur le marché avec une gestion efficace des débordements; mais pour l'instant x86 et ARM s'en moquent.

Les optimiseurs de compilateur ne parviennent pas à optimiser les contrôles de débordement, ni même à optimiser en présence de débordements. Certains universitaires, tels que John Regher, se plaignent de ce statu quo , mais le simple fait de créer des "défaillances" de débordement empêche les optimisations de se faire avant même que l’assemblage ne frappe le processeur peut être paralysant. Surtout quand il empêche l'auto-vectorisation ...

Avec des effets en cascade

Ainsi, en l’absence de stratégies d’optimisation efficaces et de prise en charge efficace du processeur, la vérification des débordements est coûteuse. Beaucoup plus coûteux que l'emballage.

Ajoutez à cela un comportement gênant, comme par exemple, x + y - 1déborder quand x - 1 + ycela ne gêne pas, ce qui peut légitimement gêner les utilisateurs, et la vérification de débordement est généralement abandonnée au profit de l’emballage (qui traite cet exemple et de nombreux autres de manière élégante).

Pourtant, tout espoir n'est pas perdu

Les compilateurs clang et gcc ont déployé des efforts pour implémenter des "désinfectants": moyens d'instrumenter des fichiers binaires pour détecter les cas de comportement non défini. Lors de l'utilisation -fsanitize=undefined, un débordement signé est détecté et interrompt le programme. très utile lors des tests.

La vérification de débordement est activée par défaut en langage Debug dans le langage de programmation Rust (elle utilise l'arithmétique de wrapping en mode Release pour des raisons de performances).

On s'inquiète donc de plus en plus de la vérification des débordements et du danger que des résultats erronés ne soient pas détectés. Nous espérons que cela suscitera de l'intérêt pour la communauté des chercheurs, des compilateurs et du matériel.

Matthieu M.
la source
6
@DmitryGrigoryev qui est à l'opposé d'un moyen efficace pour vérifier les dépassements, par exemple sur Haswell il réduit le débit à partir de 4 additions normales par cycle d'addition seulement 1 vérifié, et qui est , avant d' envisager l'impact de la branche mauvaises prédictions de la jo« s, et la effets plus globaux de la pollution qu’ils ajoutent à l’état du prédicteur de branche et à l’augmentation de la taille du code. Si ce drapeau était collant, il offrirait un potentiel réel… et vous ne pourrez toujours pas le faire correctement dans du code vectorisé.
3
Puisque vous créez un lien vers un article de blog écrit par John Regehr, j’ai pensé qu’il serait également approprié de créer un lien vers un autre article de son article , écrit quelques mois avant celui que vous avez lié. Ces articles parlent de différentes philosophies: Dans l'article précédent, les entiers ont une taille fixe; les arithmétiques entières sont vérifiées (le code ne peut pas continuer son exécution); il y a soit une exception, soit un piège. Le nouvel article parle de la suppression des entiers de taille fixe, ce qui élimine les débordements.
Rwong
2
@rwong Les entiers de taille infinie ont aussi leurs problèmes. Si votre débordement est le résultat d'un bogue (ce qui est souvent le cas), il peut en résulter un crash rapide en une agonie prolongée qui consomme toutes les ressources du serveur jusqu'à ce que tout échoue terriblement. Je suis surtout un partisan de l'approche "échec précoce", qui réduit les risques d'empoisonnement de tout l'environnement. Je préférerais les 1..100types Pascal-ish à la place - soyez explicite sur les plages attendues, plutôt que d’être "forcé" dans 2 ^ 31, etc. compile-time, même).
Luaan
1
@ Luan: Ce qui est intéressant, c'est que souvent, des calculs intermédiaires peuvent déborder temporairement, mais pas le résultat. Par exemple, sur votre gamme 1..100, il est x * 2 - 2possible que le débordement xsoit égal à 51 même si le résultat est correct, ce qui vous oblige à réorganiser vos calculs (parfois de manière non naturelle). D'après mon expérience, j'ai généralement constaté que je préfère exécuter le calcul dans un type plus grand, puis vérifier si le résultat est correct ou non.
Matthieu M.
1
@MatthieuM. Oui, c'est là que vous entrez dans le domaine du "compilateur suffisamment intelligent". Idéalement, une valeur de 103 devrait être valide pour un type 1..100 tant qu'elle n'est jamais utilisée dans un contexte dans lequel un vrai 1..100 est attendu (par exemple, cela x = x * 2 - 2devrait fonctionner pour tous les xcas où l'affectation aboutit à un 1 valide. .100 nombre). C'est-à-dire que les opérations sur le type numérique peuvent avoir une précision supérieure à celle du type lui-même tant que l'affectation convient. Cela serait très utile dans les cas (a + b) / 2où ignorer les débordements (non signés) pourrait être la bonne option.
Luaan
10

Les langues qui tentent de détecter les débordements ont historiquement défini la sémantique associée de manière à restreindre considérablement ce qui aurait autrement été des optimisations utiles. Entre autres choses, bien qu’il soit souvent utile d’effectuer des calculs dans une séquence différente de celle spécifiée dans le code, la plupart des langages qui encerclent les dépassements de capacité garantissent un code tel que:

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

si la valeur de départ de x provoque un dépassement de capacité lors du 47ème passage dans la boucle, Operation1 sera exécuté 47 fois et Operation2 en exécutera 46. En l'absence d'une telle garantie, si rien d'autre dans la boucle n'utilise x, et rien utilisera la valeur de x après une exception levée par Operation1 ou Operation2, le code pourrait être remplacé par:

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

Malheureusement, il est difficile d'effectuer de telles optimisations tout en garantissant une sémantique correcte dans les cas où un dépassement de capacité se serait produit dans la boucle. Cette opération nécessite essentiellement quelque chose comme:

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 l'on considère qu'un grand nombre de codes du monde réel utilisent des boucles plus complexes, il est évident qu'il est difficile d'optimiser le code tout en préservant la sémantique de dépassement de capacité. En outre, en raison de problèmes de mise en cache, il est tout à fait possible que l’augmentation de la taille du code ralentisse l’exécution du programme dans son ensemble, même s’il ya moins d’opérations sur le chemin généralement exécuté.

Ce qui serait nécessaire pour rendre la détection de débordement peu coûteuse serait un ensemble défini de sémantiques de détection de débordement plus souples, ce qui permettrait au code de signaler facilement si un calcul a été effectué sans aucun débordement susceptible d’affecter les résultats (*), mais sans alourdir le compilateur avec des détails au-delà. Si une spécification de langue visait à réduire le coût de la détection de débordement au strict minimum nécessaire pour atteindre les objectifs susmentionnés, elle pourrait être rendue beaucoup moins coûteuse que dans les langues existantes. Je ne suis au courant d'aucun effort visant à faciliter une détection efficace des débordements, cependant.

(*) Si une langue promet que tous les débordements seront signalés, une expression comme x*y/yne peut pas être simplifiée, à xmoins qu'il x*yne soit garanti de ne pas déborder. De même, même si le résultat d'un calcul serait ignoré, un langage qui promet de signaler tous les débordements devra le réaliser de toute façon pour pouvoir effectuer le contrôle de débordement. Étant donné que les débordements dans de tels cas ne peuvent pas donner lieu à un comportement arithmétiquement incorrect, un programme n’aurait pas besoin de procéder à de telles vérifications pour garantir qu’aucun débordement n’a provoqué des résultats potentiellement inexacts.

Incidemment, les débordements en C sont particulièrement graves. Bien que presque toutes les plates-formes matérielles prenant en charge C99 utilisent une sémantique silencieuse et enveloppante à deux complément, il est courant que les compilateurs modernes génèrent du code pouvant entraîner des effets secondaires arbitraires en cas de débordement. Par exemple, étant donné quelque chose comme:

#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 générera un code pour test2 qui incrémente de manière inconditionnelle (* p) une fois et renvoie 32768 quelle que soit la valeur transmise à q. Selon son raisonnement, le calcul de (32769 * 65535) & 65535u provoquerait un dépassement de capacité et le compilateur n’a donc pas besoin d’envisager les cas où (q | 32768) donnerait une valeur supérieure à 32768. Même s’il n’existe pas Pour que le calcul de (32769 * 65535) & 65535u doive tenir compte des bits supérieurs du résultat, gcc utilisera le débordement signé pour justifier l’ignorance de la boucle.

supercat
la source
2
"C’est à la mode pour les compilateurs modernes ..." - De même, il a été brièvement recommandé aux développeurs de certains noyaux bien connus de ne pas lire la documentation concernant les indicateurs d’optimisation qu’ils utilisaient, puis de se fâcher sur Internet. parce qu'ils ont été obligés d'ajouter encore plus d'indicateurs de compilation pour obtenir le comportement souhaité ;-). Dans ce cas, le -fwrapvcomportement défini est défini, bien que ce ne soit pas le comportement souhaité par le questionneur. Certes, l’optimisation gcc transforme tout type de développement C en un examen approfondi du comportement du standard et du compilateur.
Steve Jessop
1
@SteveJessop: C serait un langage beaucoup plus sain si les rédacteurs du compilateur reconnaissaient un dialecte de bas niveau dans lequel "comportement indéfini" signifiait "faire tout ce qui aurait du sens sur la plate-forme sous-jacente", et offrirait ainsi aux programmeurs des moyens supplémentaires de renoncer aux garanties inutiles implicites, Plutôt que de supposer que l'expression "non-portable ou erroné" figurant dans la norme signifie simplement "erronée". Dans de nombreux cas, le code optimal pouvant être obtenu dans une langue avec de faibles garanties comportementales sera bien meilleur que ce qui peut être obtenu avec des garanties plus fortes ou aucune garantie. Par exemple ...
Supercat
1
... si un programmeur doit évaluer x+y > zd'une manière qui ne fera jamais que donner 0 ou 1, mais que le résultat soit tout aussi acceptable en cas de dépassement, un compilateur offrant cette garantie pourrait souvent générer un meilleur code pour le expression x+y > zque n'importe quel compilateur serait capable de générer pour une version écrite défensive de l'expression. De manière réaliste, quelle fraction d' optimisations utiles liées au dépassement de capacité serait exclue si l'on garantissait que les calculs d'entiers autres que la division / le reste s'exécuteraient sans effets secondaires?
Supercat
J'avoue que je ne suis pas tout à fait dans les détails, mais le fait que votre rancune est avec les "auteurs de compilateur" en général, et pas spécifiquement "quelqu'un sur gcc qui n'acceptera pas mon -fwhatever-makes-sensepatch", me suggère fortement qu'il y a plus à cela que la fantaisie de leur part. Les arguments habituels que j'ai entendus sont que l'inclusion de code (et même le développement de macros) profite de la déduction autant que possible de l'utilisation spécifique d'une construction de code, puisque l'une ou l'autre chose résulte généralement en un code inséré qui traite des cas dont il n'a pas besoin. à, que le code environnant "s'avère" impossible.
Steve Jessop
Ainsi, pour un exemple simplifié, si j'écris foo(i + INT_MAX + 1), les auteurs de compilateur souhaitent appliquer des optimisations au foo()code en ligne, qui reposent sur l'exactitude de l'argument non négatif (des astuces divmod diaboliques, peut-être). Sous vos restrictions supplémentaires, ils ne pouvaient appliquer que des optimisations dont le comportement pour les entrées négatives est logique pour la plate-forme. Bien sûr, personnellement, je serais heureux que cela soit une -foption qui active -fwrapvetc., et doit probablement désactiver certaines optimisations pour lesquelles il n’ya pas de drapeau. Mais ce n'est pas comme si je pouvais être dérangé de faire tout ce travail moi-même.
Steve Jessop
9

Tous les langages de programmation n'ignorent pas les débordements d'entiers. Certaines langues fournissent des opérations entières sûres pour tous les nombres (la plupart des dialectes Lisp, Ruby, Smalltalk, ...) et d'autres via des bibliothèques - par exemple, il existe différentes classes BigInt pour C ++.

Le fait qu'un langage protège les entiers du dépassement de capacité par défaut ou non dépend de son objectif: les langages système tels que C et C ++ doivent fournir des abstractions à coût zéro et le "grand entier" n'en est pas une. Les langages de productivité, tels que Ruby, peuvent fournir et fournissent de grands entiers prêts à l'emploi. Les langages tels que Java et C # qui se situent quelque part entre les deux, devraient à mon avis aller avec les entiers sûrs prêts à l'emploi, sinon ils ne le font pas.

Nemanja Trifunovic
la source
Notez qu'il y a une différence entre détecter un débordement (et ensuite avoir un signal, une panique, une exception, ...) et basculer vers de grands chiffres. Le premier devrait être faisable beaucoup moins cher que le dernier.
Matthieu M.
@MatthieuM. Absolument - et je me rends compte que cela n’est pas clair dans ma réponse.
Nemanja Trifunovic
7

Comme vous l'avez montré, C # aurait été 3 fois plus lent si les vérifications de débordement étaient activées par défaut (en supposant que votre exemple soit une application typique de cette langue). Je conviens que la performance n'est pas toujours la fonctionnalité la plus importante, mais les langages / compilateurs sont généralement comparés sur leurs performances dans des tâches typiques. Cela est dû en partie au fait que la qualité des fonctionnalités du langage est quelque peu subjective, alors qu'un test de performance est objectif.

Si vous deviez introduire un nouveau langage similaire au C # dans la plupart des cas, mais 3 fois plus lent, obtenir une part du marché ne serait pas facile, même si au final, la plupart de vos utilisateurs finaux bénéficieraient davantage des contrôles de débordement que de la leur. de plus hautes performances.

Dmitry Grigoryev
la source
10
C'était particulièrement le cas pour C #, qui en était à ses débuts comparé à Java et à C ++, et non sur les métriques de productivité des développeurs, difficiles à mesurer, ni sur les métriques économisées de manière à éviter les violations de sécurité, qui sont difficiles à mesurer, mais sur des critères de performance triviaux.
Eric Lippert
1
Et probablement, les performances du processeur sont vérifiées avec quelques calculs simples. Ainsi, les optimisations pour la détection de débordement peuvent donner de "mauvais" résultats sur ces tests. Catch22.
Bernhard Hiller
5

Outre les nombreuses réponses qui justifient l'absence de vérification du dépassement de capacité en fonction des performances, il existe deux types d'arithmétique à prendre en compte:

  1. calculs d'indexation (indexation de tableaux et / ou arithmétique de pointeur)

  2. autre arithmétique

Si le langage utilise une taille entière identique à celle du pointeur, un programme bien construit ne débordera pas dans les calculs d’indexation car il devra nécessairement manquer de mémoire avant que les calculs d’indexation ne provoquent un débordement.

Ainsi, la vérification des allocations de mémoire est suffisante lorsque vous utilisez des expressions arithmétiques et d'indexation de pointeur impliquant des structures de données allouées. Par exemple, si vous avez un espace d'adressage de 32 bits et utilisez des entiers de 32 bits et que vous allouez un maximum de 2 Go de tas à allouer (environ la moitié de l'espace d'adressage), les calculs d'indexation / pointeur (en principe) ne débordent pas.

En outre, vous pourriez être surpris de savoir combien d’additions / soustractions / multiplications impliquent une indexation de tableau ou un calcul de pointeur, entrant ainsi dans la première catégorie. Le pointeur d'objet, l'accès aux champs et les manipulations de tableaux sont des opérations d'indexation, et de nombreux programmes ne font pas plus de calculs arithmétiques que ceux-ci! En gros, c’est la raison principale pour laquelle les programmes fonctionnent aussi bien qu’ils ne le font pas sans vérification du débordement d’entier.

Tous les calculs non indexés et non pointés doivent être classés en deux catégories: ceux qui veulent / attendent un débordement (par exemple, les calculs de hachage) et ceux qui ne le sont pas (par exemple, votre exemple de somme).

Dans ce dernier cas, les programmeurs utiliseront souvent d'autres types de données, tels que doubleou certains BigInt. De nombreux calculs nécessitent un decimaltype de données plutôt que doubledes calculs financiers. S'ils ne le font pas et qu'ils s'en tiennent à des types entiers, ils doivent alors veiller à vérifier le dépassement d'entier - sinon, oui, le programme peut atteindre une condition d'erreur non détectée, comme vous le signalez.

En tant que programmeurs, nous devons être sensibles à nos choix en matière de types de données numériques et à leurs conséquences en termes de possibilités de débordement, sans parler de la précision. En général (et particulièrement lorsque vous travaillez avec la famille de langues C avec le désir d’utiliser les types d’entiers rapides), nous devons être attentifs aux différences entre les calculs d’indexation et les prendre en compte.

Erik Eidt
la source
3

Le langage Rust constitue un compromis intéressant entre la vérification des débordements et non, en ajoutant les vérifications de la version de débogage et en les supprimant dans la version optimisée. Cela vous permet de rechercher les bogues lors des tests, tout en obtenant des performances optimales dans la version finale.

Parce que le bouclage de débordement est parfois le comportement souhaité, il existe également des versions des opérateurs qui ne vérifient jamais le débordement.

Vous pouvez en savoir plus sur le raisonnement derrière le choix de la RFC pour le changement. Ce billet de blog contient également de nombreuses informations intéressantes , notamment une liste de bogues que cette fonctionnalité a contribué à résoudre.

Hjulle
la source
2
Rust fournit également des méthodes telles checked_mulque, qui vérifie si un dépassement de capacité a eu lieu et renvoie le Nonecas échéant, Somesinon. Cela peut être utilisé aussi bien en production qu'en mode débogage: doc.rust-lang.org/std/primitive.i32.html#examples-15
Akavall
3

Dans Swift, tout dépassement d'entier est détecté par défaut et arrête instantanément le programme. Dans les cas où vous avez besoin d'un comportement enveloppant, il existe différents opérateurs & +, & - et & * qui y parviennent. Et il y a des fonctions qui effectuent une opération et disent s'il y a eu un débordement ou non.

C'est amusant de regarder les débutants essayer d'évaluer la séquence de Collatz et de faire planter leur code :-)

Maintenant, les concepteurs de Swift sont également les concepteurs de LLVM et de Clang. Ils connaissent donc un peu l'optimisation et sont tout à fait capables d'éviter les contrôles de débordement inutiles. Avec toutes les optimisations activées, la vérification du débordement n’ajoute pas grand chose à la taille du code et au temps d’exécution. Et comme la plupart des débordements donnent des résultats absolument incorrects, la taille du code et le temps d'exécution sont bien dépensés.

PS En C, C ++, le dépassement arithmétique d’entiers entiers signés d’Objective-C est un comportement indéfini. Cela signifie que tout ce que le compilateur fait dans le cas d'un dépassement d'entier signé est correct, par définition. Les moyens habituels de gérer le dépassement d'entier signé sont de l'ignorer, en prenant le résultat que vous donne le processeur, en supposant dans le compilateur qu'un tel débordement ne se produira jamais (et concluez par exemple que n + 1> n est toujours vrai, car overflow supposée ne jamais arriver), et une possibilité rarement utilisée est de vérifier et de planter si un débordement se produit, comme le fait Swift.

gnasher729
la source
1
Je me suis parfois demandé si les personnes qui poussent la folie en C provoquée par UB essayaient secrètement de la miner en faveur d'une autre langue. Cela aurait du sens.
Supercat
Traiter x+1>xcomme inconditionnellement vrai ne demanderait pas à un compilateur de formuler des "hypothèses" sur x si un compilateur est autorisé à évaluer des expressions entières à l'aide de types arbitraires plus grands (ou se comporte comme si c'était le cas). Un exemple plus révélateur d '"hypothèses" basées sur le dépassement de uint32_t mul(uint16_t x, uint16_t y) { return x*y & 65535u; }capacité serait de décider qu'un compilateur peut sum += mul(65535, x)décider de xne pas dépasser 32768 [comportement qui pourrait choquer ceux qui ont écrit la justification C89, ce qui suggère l'un des facteurs décisifs. ..
Supercat
... en faisant la unsigned shortpromotion, signed intle fait que les implémentations enveloppantes silencieuses à complément à deux (c'est-à-dire que la majorité des implémentations C alors utilisées) traitent le code comme ci-dessus de la même manière, qu'il soit unsigned shortpromu intou unsigned. La norme ne nécessitait pas d' implémentations sur du matériel à complément complémentaire silencieux pour traiter le code de la même manière que précédemment, mais les auteurs de la norme semblaient s'attendre à ce qu'ils le fassent de toute façon.
Supercat
2

En réalité, la véritable cause de ceci est purement technique / historique: les CPU ignorent le signe pour la plupart. Il n'y a généralement qu'une seule instruction pour ajouter deux nombres entiers dans des registres, et la CPU ne se soucie pas du tout de savoir si vous interprétez ces deux nombres entiers comme signés ou non. La même chose vaut pour la soustraction, et même pour la multiplication. La division est la seule opération arithmétique à prendre en compte.

La raison pour laquelle cela fonctionne est la représentation en complément à 2 des entiers signés utilisée par pratiquement tous les processeurs. Par exemple, en complément de 2 bits, l'addition de 5 et -3 ressemble à ceci:

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

Observez comment le comportement enveloppant consistant à jeter le bit de report produit le résultat signé correct. De même, les processeurs implémentent généralement la soustraction de la x - ymanière suivante x + ~y + 1:

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

Ceci implémente la soustraction en tant qu'addition dans le matériel, ne modifiant que de manière triviale les entrées de l'unité arithmetico-logique (ALU). Quoi de plus simple?

Puisque la multiplication n’est rien d’autre qu’une séquence d’additions, elle se comporte de la même manière. L'utilisation de la représentation du complément à 2 et le non-respect des opérations arithmétiques ont pour résultat de simplifier les circuits et les jeux d'instructions.

Évidemment, puisque C a été conçu pour fonctionner à proximité du métal, il a adopté exactement le même comportement que le comportement normalisé de l'arithmétique non signée, permettant uniquement à l'arithmétique signée de produire un comportement non défini. Et ce choix s'est répercuté sur d'autres langages tels que Java et, évidemment, C #.

cmaster
la source
Je suis venu ici pour donner cette réponse aussi.
M. Lister
Malheureusement, certaines personnes semblent considérer comme totalement déraisonnable l'idée selon laquelle les personnes qui écrivent du code C de bas niveau sur une plate-forme devraient avoir l'audace de s'attendre à ce qu'un compilateur C adapté à cet usage se comporte de manière contrainte en cas de débordement. Personnellement, je pense qu'il est raisonnable pour un compilateur de se comporter comme si les calculs étaient effectués en utilisant une précision étendue de façon arbitraire à la convenance du compilateur (ainsi sur un système 32 bits, si x==INT_MAX, alors, x+1pourrait se comporter arbitrairement comme +2147483648 ou -2147483648 commodité), mais ...
Supercat
Certaines personnes semblent penser que si xet ysont uint16_tet que le code sur un système 32 bits calcule x*y & 65535uquand yest 65535, un compilateur devrait supposer que le code ne sera jamais atteint s'il xest supérieur à 32768.
supercat
1

Certaines réponses ont discuté du coût de la vérification, et vous avez modifié votre réponse pour contester qu'il s'agit d'une justification raisonnable. Je vais essayer de répondre à ces points.

En C et C ++ (à titre d'exemple), l'un des principes de conception de langages n'est pas de fournir une fonctionnalité qui n'a pas été demandée. Ceci est généralement résumé par la phrase "ne payez pas pour ce que vous n'utilisez pas". Si le programmeur veut vérifier le débordement, il peut le demander (et payer la pénalité). Cela rend le langage plus dangereux à utiliser, mais vous choisissez de travailler avec le langage en sachant cela, vous acceptez donc le risque. Si vous ne voulez pas ce risque, ou si vous écrivez du code où la sécurité est une performance primordiale, vous pouvez alors choisir une langue plus appropriée où le compromis performance / risque est différent.

Mais avec les 10 000 000 000 de répétitions, le temps nécessaire à un contrôle est toujours inférieur à 1 nanoseconde.

Il y a quelques erreurs dans ce raisonnement:

  1. Ceci est spécifique à l'environnement. Il est généralement peu logique de citer des chiffres précis comme celui-ci, car le code est écrit pour toutes sortes d’environnements dont les performances varient en ordre de grandeur. Votre 1 nanoseconde sur une machine de bureau (je suppose) peut sembler incroyablement rapide à une personne qui code pour un environnement intégré et trop lente pour une personne qui code pour un cluster de super-ordinateurs.

  2. Une nanoseconde peut sembler bien inutile pour un segment de code qui s'exécute rarement. D'autre part, si c'est dans une boucle interne d'un calcul qui est la fonction principale du code, chaque fraction de temps que vous pouvez gagner peut faire une grande différence. Si vous exécutez une simulation sur un cluster, ces fractions de nanosecondes enregistrées dans votre boucle interne peuvent se traduire directement par des dépenses en matériel et en électricité.

  3. Pour certains algorithmes et contextes, 10 000 000 000 d'itérations peuvent être insignifiantes. Encore une fois, il n’a généralement pas de sens de parler de scénarios spécifiques qui ne s’appliquent que dans certains contextes.

Il peut y avoir une situation où cela est important, mais pour la plupart des applications, cela n’a aucune importance.

Vous avez peut-être raison. Mais là encore, il s’agit de savoir quels sont les objectifs d’une langue donnée. De nombreuses langues sont en fait conçues pour répondre aux besoins de "la plupart" ou pour favoriser la sécurité par rapport à d'autres préoccupations. D'autres, comme C et C ++, accordent la priorité à l'efficacité. Dans ce contexte, imposer à tout le monde une pénalité de performance simplement parce que la plupart des gens ne se laisseront pas déranger va à l'encontre de l'objectif recherché par le langage.

Jon Bentley
la source
-1

Il y a de bonnes réponses, mais je pense qu'il ya un point manqué ici: les effets d'un débordement d'entier ne sont pas nécessairement une mauvaise chose, et après le fait , il est difficile de savoir si est ipassé d' MAX_INTà être MIN_INTétait due à un problème de trop - plein ou si cela a été fait intentionnellement en multipliant par -1.

Par exemple, si je veux additionner tous les entiers représentables supérieurs à 0, je voudrais simplement utiliser une for(i=0;i>=0;++i){...}boucle d’addition. Quand elle déborde, elle arrête l’ajout, ce qui est le comportement de l’objectif (lancer une erreur signifierait que je dois contourner une protection arbitraire car elle interfère avec l'arithmétique standard). C'est une mauvaise pratique de limiter les arithmétiques primitives, parce que:

  • Ils sont utilisés dans tout. Un ralentissement dans les mathématiques primitives est un ralentissement dans tous les programmes qui fonctionnent.
  • Si un programmeur en a besoin, il peut toujours les ajouter
  • Si vous en avez et que le programmeur n'en a pas besoin (mais a besoin d'une exécution plus rapide), il ne peut pas les supprimer facilement pour une optimisation.
  • Si vous en avez et que le programmeur a besoin qu'ils ne soient pas là (comme dans l'exemple ci-dessus), le programmeur subit tous les deux le coup du run-time (qui peut ou non être pertinent), et le programmeur doit toujours investir du temps à supprimer ou travailler autour de la «protection».
Delioth
la source
3
Il n’est pas vraiment possible pour un programmeur d’ajouter une vérification efficace du débordement si une langue ne le prévoit pas. Si une fonction calcule une valeur ignorée, un compilateur peut optimiser le calcul. Si une fonction calcule une valeur qui est trop plein vérifié mais sinon ignoré, un compilateur doit effectuer le calcul et le piège si elle déborde, même si un débordement serait par ailleurs aucune incidence sur la sortie du programme et pourrait être ignoré en toute sécurité.
Supercat
1
Vous ne pouvez pas aller de INT_MAXà INT_MINen multipliant par -1.
David Conrad
La solution consiste évidemment à fournir au programmeur un moyen de désactiver les vérifications dans un bloc de code ou une unité de compilation donné.
David Conrad
for(i=0;i>=0;++i){...}C’est le style de code que j’essaie de décourager dans mon équipe: il repose sur des effets spéciaux / des effets secondaires et n’exprime pas clairement ce qu’il est censé faire. Mais j’apprécie toujours votre réponse car elle montre un paradigme de programmation différent.
Bernhard Hiller
1
@Delioth: Si iest un type 64 bits, même sur une implémentation avec un comportement de complément à deux silences cohérent, exécutant un milliard d'itérations par seconde, une telle boucle ne pourrait être garantie de trouver la plus grande intvaleur si elle est autorisée à s'exécuter pendant des centaines d'années. Sur les systèmes qui ne promettent pas un comportement enveloppant silencieux cohérent, de tels comportements ne seraient pas garantis quelle que soit la longueur du code donné.
Supercat