Warum wird der arithmetische Überlauf ignoriert?

76

Haben Sie jemals versucht, alle Zahlen von 1 bis 2.000.000 in Ihrer bevorzugten Programmiersprache zusammenzufassen? Das Ergebnis kann leicht manuell berechnet werden: 2.000.001.000.000, was etwa 900-mal größer ist als der Maximalwert einer 32-Bit-Ganzzahl ohne Vorzeichen.

C # druckt aus -1453759936- ein negativer Wert! Und ich denke, Java macht das Gleiche.

Das bedeutet, dass es einige gängige Programmiersprachen gibt, die den arithmetischen Überlauf standardmäßig ignorieren (in C # gibt es versteckte Optionen, um dies zu ändern). Das ist ein Verhalten, das für mich sehr riskant aussieht, und wurde der Absturz von Ariane 5 nicht durch einen solchen Überlauf verursacht?

Also: Was sind die Entwurfsentscheidungen hinter solch einem gefährlichen Verhalten?

Bearbeiten:

Die ersten Antworten auf diese Frage drücken die übermäßigen Überprüfungskosten aus. Führen wir ein kurzes C # -Programm aus, um diese Annahme zu testen:

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

Auf meinem Computer dauert die aktivierte Version 11015 ms, während die nicht aktivierte Version 4125 ms dauert. Das heißt, die Überprüfungsschritte dauern fast doppelt so lange wie das Hinzufügen der Zahlen (insgesamt das Dreifache der ursprünglichen Zeit). Bei den 10.000.000.000 Wiederholungen beträgt der Zeitaufwand für eine Überprüfung jedoch immer noch weniger als 1 Nanosekunde. Es kann Situationen geben, in denen dies wichtig ist, aber für die meisten Anwendungen spielt dies keine Rolle.

Bearbeiten 2:

Ich habe unsere Serveranwendung (ein Windows-Dienst, der Daten analysiert, die von mehreren Sensoren empfangen wurden, einige davon sind auffällig) mit dem /p:CheckForOverflowUnderflow="false"Parameter neu kompiliert (normalerweise schalte ich die Überlaufprüfung ein) und auf einem Gerät implementiert. Die Nagios-Überwachung zeigt, dass die durchschnittliche CPU-Auslastung bei 17% blieb.

Dies bedeutet, dass der im obigen Beispiel festgestellte Leistungstreffer für unsere Anwendung völlig irrelevant ist.

Bernhard Hiller
quelle
19
Nur als Hinweis: Für C # können Sie checked { }Abschnitt verwenden, um die Teile des Codes zu markieren, die arithmetische Überlaufprüfungen durchführen sollen. Dies ist auf die Leistung zurückzuführen
Paweł Łukasik
14
"Haben Sie jemals versucht, alle Zahlen von 1 bis 2.000.000 in Ihrer bevorzugten Programmiersprache zusammenzufassen?" - Ja: (1..2_000_000).sum #=> 2000001000000. Eine andere meiner Lieblings Sprachen: sum [1 .. 2000000] --=> 2000001000000. Nicht mein Favorit: Array.from({length: 2000001}, (v, k) => k).reduce((acc, el) => acc + el) //=> 2000001000000. (Um fair zu sein, der letzte betrügt.)
Jörg W Mittag
27
@BernhardHiller Integerin Haskell ist willkürlich genau. Es kann eine beliebige Zahl gespeichert werden, solange Ihnen nicht der zuweisbare Arbeitsspeicher ausgeht.
Polygnome
50
Der Absturz der Ariane 5 wurde dadurch verursacht, dass nach einem Überlauf gesucht wurde, der keine Rolle spielte. Die Rakete befand sich in einem Teil des Fluges, in dem das Ergebnis einer Berechnung nicht einmal mehr benötigt wurde. Stattdessen wurde der Überlauf erkannt und der Flug abgebrochen.
Simon B
9
But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond.Das ist ein Hinweis darauf, dass die Schleife optimiert wird. Auch dieser Satz widerspricht früheren Zahlen, die mir sehr zutreffend erscheinen.
USR

Antworten:

86

Dafür gibt es 3 Gründe:

  1. Die Kosten für die Überprüfung auf Überläufe (für jede einzelne arithmetische Operation) zur Laufzeit sind zu hoch.

  2. Die Komplexität des Nachweises, dass eine Überlaufprüfung zur Kompilierungszeit entfallen kann, ist zu hoch.

  3. In einigen Fällen (z. B. bei CRC-Berechnungen, großen Bibliotheken usw.) ist "Wrap-on-Overflow" für Programmierer praktischer.

Brendan
quelle
10
@DmitryGrigoryev unsigned intsollte nicht in den Sinn kommen, da eine Sprache mit Überlaufprüfung standardmäßig alle Integer-Typen prüfen sollte . Du solltest schreiben müssen wrapping unsigned int.
user253751
32
Ich kaufe das Kostenargument nicht. Die CPU überprüft den Überlauf bei JEDER EINZELNEN Ganzzahlberechnung und setzt das Übertragsflag in der ALU. Es ist die Unterstützung der Programmiersprache, die fehlt. Eine einfache didOverflow()Inline-Funktion oder sogar eine globale Variable __carry, die den Zugriff auf das Übertragsflag ermöglicht, würde keine CPU-Zeit kosten, wenn Sie sie nicht verwenden.
Slebetman
37
@slebetman: Das ist x86. ARM nicht. ZB ADDsetzt nicht den Carry (du brauchst ADDS). Itanium nicht einmal hat einen Carry - Flag. Und selbst auf x86 hat AVX keine Carry-Flags.
MSalters
30
@slebetman Setzt das Carry-Flag, ja (auf x86 wohlgemerkt). Aber dann muss man die Carry-Flagge lesen und über das Ergebnis entscheiden - das ist der teure Teil. Da arithmetische Operationen häufig in Schleifen verwendet werden (und dies gilt auch für enge Schleifen), kann dies auf einfache Weise viele sichere Compileroptimierungen verhindern, die sich sehr stark auf die Leistung auswirken können, selbst wenn Sie nur einen zusätzlichen Befehl benötigen (und viel mehr als diesen benötigen) ). Bedeutet dies, dass dies die Standardeinstellung sein sollte? Vielleicht, besonders in einer Sprache wie C #, wo das Sprechen uncheckedeinfach genug ist; aber Sie überschätzen möglicherweise, wie oft Überlauf wichtig ist.
Luaan
12
ARM addsist derselbe Preis wie add(es ist nur ein Anweisungs-1-Bit-Flag, das auswählt, ob das Übertrags-Flag aktualisiert wird). MIPSs addAnweisung fängt bei Überlauf ab - Sie müssen stattdessen fragen , ob Sie bei Überlauf nicht abfangen möchten, indem Sie verwenden addu!
user253751
65

Wer sagt, dass es ein schlechter Kompromiss ist ?!

Ich führe alle meine Produktions-Apps mit aktivierter Überlaufprüfung aus. Dies ist eine C # -Compileroption. Ich habe dies tatsächlich verglichen und konnte den Unterschied nicht feststellen. Die Kosten für den Zugriff auf die Datenbank zur Generierung von HTML (ohne Spielzeug) überschatten die Kosten für die Überlaufprüfung.

Ich schätze die Tatsache, dass ich weiß, dass in der Produktion keine Vorgänge überlaufen. Fast jeder Code würde sich bei Überläufen unregelmäßig verhalten. Die Käfer wären nicht gutartig. Datenkorruption ist wahrscheinlich, Sicherheitsprobleme sind möglich.

Wenn ich die Leistung benötige, was manchmal der Fall ist, deaktiviere ich die Überlaufprüfung unchecked {}auf granularer Basis. Wenn ich darauf hinweisen möchte, dass ich mich auf eine Operation verlasse, die nicht überläuft, kann ich checked {}den Code redundant ergänzen , um diese Tatsache zu dokumentieren. Ich achte auf Überläufe, muss mich aber nicht unbedingt an die Überprüfung halten.

Ich glaube, das C # -Team hat die falsche Wahl getroffen, als es beschlossen hat, den Überlauf nicht standardmäßig zu überprüfen, aber diese Wahl ist jetzt aufgrund starker Kompatibilitätsprobleme ausgeschlossen. Beachten Sie, dass diese Wahl um das Jahr 2000 getroffen wurde. Die Hardware war weniger leistungsfähig und .NET hatte noch nicht viel Traktion. Vielleicht wollte .NET auf diese Weise Java- und C / C ++ - Programmierer ansprechen. .NET soll auch in der Lage sein, nah am Metall zu sein. Aus diesem Grund verfügt es über unsicheren Code, Strukturen und hervorragende native Aufruffähigkeiten, die Java nicht bietet.

Je schneller unsere Hardware wird und je intelligenter die Compiler sind, desto attraktiver ist standardmäßig die Überlaufprüfung.

Ich glaube auch, dass Überlaufprüfungen oft besser sind als Zahlen mit unbegrenzter Größe. Zahlen mit unbegrenzter Größe haben einen noch höheren Leistungsaufwand, der (meiner Meinung nach) schwerer zu optimieren ist, und sie eröffnen die Möglichkeit eines unbegrenzten Ressourcenverbrauchs.

Die Art und Weise, wie JavaScript mit Überlauf umgeht, ist noch schlimmer. JavaScript-Zahlen sind Gleitkommadoppelwerte. Ein "Überlauf" äußert sich darin, dass der vollständig genaue Satz von ganzen Zahlen übrig bleibt. Es treten leicht falsche Ergebnisse auf (z. B. um eins versetzt - dies kann endliche Schleifen in unendliche verwandeln).

Für einige Sprachen wie C / C ++ ist eine Überlaufprüfung standardmäßig eindeutig ungeeignet, da die Art von Anwendungen, die in diesen Sprachen geschrieben werden, eine Bare-Metal-Performance erfordert. Dennoch gibt es Bemühungen, C / C ++ zu einer sichereren Sprache zu machen, indem es ermöglicht wird, sich für einen sichereren Modus zu entscheiden . Dies ist lobenswert, da 90-99% des Codes kalt sind. Ein Beispiel ist die fwrapvCompiler-Option, die den Komplementumbruch von 2 erzwingt. Dies ist eine "Qualität der Implementierung" -Funktion des Compilers, nicht der Sprache.

Haskell hat keine logische Aufrufliste und keine festgelegte Auswertungsreihenfolge. Dies führt dazu, dass an unvorhersehbaren Punkten Ausnahmen auftreten. In a + bihm ist nicht spezifiziert , ob aoder bzuerst ausgewertet wird und ob diese Ausdrücke überhaupt nicht oder nicht beenden. Daher ist es für Haskell sinnvoll, die meiste Zeit unbegrenzte ganze Zahlen zu verwenden. Diese Auswahl eignet sich für eine rein funktionale Sprache, da Ausnahmen in den meisten Haskell-Codes wirklich unangemessen sind. Und die Division durch Null ist in der Tat ein problematischer Punkt in Haskells Sprachentwurf. Anstelle von unbegrenzten Ganzzahlen hätten sie auch Ganzzahlen mit fester Breite verwenden können, aber das passt nicht zum Thema "Fokus auf Korrektheit", das die Sprache bietet.

Eine Alternative zu Überlaufausnahmen sind Giftwerte, die durch undefinierte Operationen erstellt werden und sich durch Operationen ausbreiten (wie der Gleitkommawert NaN). Das scheint viel teurer als Überlaufprüfung und macht alle Vorgänge langsamer, nicht nur diejenigen , die (abgesehen von Hardware - Beschleunigung , die gewöhnlich schwimmt haben und Ints haben häufig nicht - obwohl ausfallen können Itanium NaT hat, das „kein Ding“ ). Ich sehe auch nicht ganz den Sinn, das Programm mit schlechten Daten weiter hinken zu lassen. Es ist wie ON ERROR RESUME NEXT. Es verbirgt Fehler, hilft aber nicht dabei, korrekte Ergebnisse zu erzielen. supercat weist darauf hin, dass es manchmal eine Leistungsoptimierung ist, dies zu tun.

usr
quelle
2
Hervorragende Antwort. Was ist Ihre Theorie darüber, warum sie sich dazu entschlossen haben? Nur alle anderen kopieren, die C und letztendlich Assembly und Binary kopiert haben?
jpmc26
19
Wenn 99% Ihrer Benutzer ein Verhalten erwarten, tendieren Sie dazu, es ihnen zu geben. Und was "Kopieren von C" angeht, ist es eigentlich keine Kopie von C, sondern eine Erweiterung davon. C garantiert ein ausnahmefreies Verhalten nur für unsignedganze Zahlen. Das Verhalten des Überlaufs von Ganzzahlen mit Vorzeichen ist in C und C ++ tatsächlich undefiniert. Ja, undefiniertes Verhalten . Es kommt einfach so vor, dass fast jeder es als 2-Komplement-Überlauf implementiert. C # macht es offiziell, anstatt es wie C / C ++
Cort Ammon
10
@CortAmmon: Die von Dennis Ritchie entworfene Sprache hatte ein definiertes Wraparound-Verhalten für signierte Ganzzahlen, war jedoch nicht für die Verwendung auf Plattformen mit Nicht-Zweierkomplementen geeignet. Während das Zulassen bestimmter Abweichungen vom genauen Zweierkomplement-Wraparound einige Optimierungen erheblich unterstützen kann (z. B. könnte das Ersetzen von x * y / y durch x durch einen Compiler eine Multiplikation und Division ersparen), haben Compiler-Writer Undefined Behaviour nicht als Gelegenheit interpretiert, dies zu tun was für eine bestimmte Zielplattform und ein bestimmtes Anwendungsfeld Sinn macht, sondern eher als Gelegenheit, Sinn aus dem Fenster zu werfen.
Supercat
3
@CortAmmon - Überprüfen Sie den erzeugten Code gcc -O2für x + 1 > x(wo xeine ist int). Siehe auch gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/… . Das 2s-Komplement-Verhalten bei signiertem Überlauf in C ist optional , auch in realen Compilern, und gccignoriert es standardmäßig in normalen Optimierungsstufen.
Jonathan Cast
2
@supercat Ja, die meisten C-Compiler-Autoren sind mehr daran interessiert, sicherzustellen, dass einige unrealistische Benchmark-Läufe 0,5% schneller ablaufen als der Versuch, Programmierern eine angemessene Semantik bereitzustellen unerwartete Ergebnisse in Kombination, yada, yada, aber es ist einfach kein Fokus und Sie bemerken es, wenn Sie den Gesprächen folgen). Zum Glück gibt es einige Leute, die versuchen, es besser zu machen .
Voo
30

Weil es ein schlechter Kompromiss macht alle Berechnungen sehr viel teurer , um automatisch den seltenen Fall zu fangen , die ein Überlauf tut auftreten. Es ist viel besser, den Programmierer mit dem Erkennen der seltenen Fälle zu belasten, in denen dies ein Problem ist, und spezielle Vorsichtsmaßnahmen hinzuzufügen, als alle Programmierer den Preis für die Funktionalität zahlen zu lassen , die sie nicht verwenden.

Kilian Foth
quelle
28
Das ist wie zu sagen, dass Überprüfungen auf Pufferüberlauf weggelassen werden sollten, da sie selten auftreten ...
Bernhard Hiller
73
@BernhardHiller: und genau das machen C und C ++.
Michael Borgwardt
12
@DavidBrown: Ebenso wie arithmetische Überläufe. Ersteres gefährdet die VM jedoch nicht.
Deduplikator
35
@ Deduplicator macht einen ausgezeichneten Punkt. Die CLR wurde sorgfältig entwickelt, damit überprüfbare Programme die Invarianten der Laufzeit auch dann nicht verletzen können , wenn Fehler auftreten. Sichere Programme können natürlich ihre eigenen Invarianten verletzen, wenn schlechtes Zeug passiert.
Eric Lippert
7
@svick Arithmetische Operationen sind wahrscheinlich weitaus häufiger als Array-Indizierungsoperationen. Und die meisten Integer-Größen sind groß genug, um nur sehr selten überlaufende Arithmetik auszuführen. Die Kosten-Nutzen-Verhältnisse sind also sehr unterschiedlich.
Barmar
20

Was sind die Entwurfsentscheidungen hinter solch einem gefährlichen Verhalten?

"Erzwingen Sie nicht, dass Benutzer eine Leistungsstrafe für eine Funktion zahlen, die sie möglicherweise nicht benötigen."

Es ist eine der grundlegendsten Prinzipien im Design von C und C ++ und stammt aus einer anderen Zeit, in der Sie durch lächerliche Verzerrungen mussten, um für Aufgaben, die heutzutage als trivial gelten, eine kaum ausreichende Leistung zu erzielen.

Neuere Sprachen brechen mit dieser Einstellung für viele andere Funktionen, wie z. B. die Überprüfung der Array-Grenzen. Ich bin mir nicht sicher, warum sie es nicht für die Überlaufprüfung getan haben. Es könnte einfach ein Versehen sein.

Michael Borgwardt
quelle
18
Es ist definitiv kein Versehen im Design von C #. Die Designer von C # haben absichtlich zwei Modi erstellt: checkedund uncheckedSyntax zum lokalen Wechseln zwischen ihnen und Befehlszeilenoptionen (und Projekteinstellungen in VS) hinzugefügt, um sie global zu ändern. Sie stimmen möglicherweise nicht mit uncheckedder Standardeinstellung überein (das tue ich), aber all dies ist eindeutig sehr beabsichtigt.
Svick
8
@slebetman - nur zur Veranschaulichung: Die Kosten hier sind nicht die Kosten für die Überprüfung des Überlaufs (was trivial ist), sondern die Kosten für die Ausführung von unterschiedlichem Code, je nachdem, ob der Überlauf stattgefunden hat (was sehr teuer ist). CPUs mögen keine bedingten Verzweigungsanweisungen.
Jonathan Cast
5
@jcast Würde die Verzweigungsvorhersage auf modernen Prozessoren diese bedingte Verzweigungsanweisungsstrafe nicht beinahe beseitigen? Immerhin sollte der Normalfall kein Überlauf sein, daher ist es ein sehr vorhersehbares Verzweigungsverhalten.
CodeMonkey
4
Stimmen Sie mit @CodeMonkey überein. Ein Compiler würde im Falle eines Überlaufs einen bedingten Sprung zu einer Seite ausführen, die normalerweise nicht geladen / kalt ist. Die Standardvorhersage dafür ist "nicht genommen" und wird sich wahrscheinlich nicht ändern. Der gesamte Overhead ist eine Anweisung in der Pipeline. Dies ist jedoch ein Anweisungs-Overhead pro arithmetischer Anweisung.
MSalters
2
@MSalters ja, es gibt einen zusätzlichen Anweisungsaufwand. Und die Auswirkungen können erheblich sein, wenn Sie ausschließlich Probleme mit der CPU haben. In den meisten Anwendungen mit einer Mischung aus IO- und CPU-starkem Code würde ich davon ausgehen, dass die Auswirkungen minimal sind. Ich mag die Rust-Methode, den Overhead nur in Debug-Builds hinzuzufügen, ihn aber in Release-Builds zu entfernen.
CodeMonkey
20

Erbe

Ich würde sagen, dass das Problem wahrscheinlich im Erbe verwurzelt ist. In C:

  • signierter Überlauf ist undefiniertes Verhalten (Compiler unterstützen Flags, um ihn umbrechen zu lassen),
  • Ein vorzeichenloser Überlauf ist ein definiertes Verhalten (es bricht um).

Dies wurde getan, um die bestmögliche Leistung zu erzielen, und zwar nach dem Prinzip, dass der Programmierer weiß, was er tut .

Führt zu Statu-Quo

Die Tatsache, dass in C (und in der Erweiterung C ++) abwechselnd kein Überlauf erkannt werden muss, bedeutet, dass die Überlaufprüfung nur schleppend durchgeführt wird.

Hardware ist hauptsächlich für C / C ++ ausgelegt (im Ernst, x86 verfügt über eine strcmpAnweisung (auch bekannt als PCMPISTRI ab SSE 4.2)!), Und da es C egal ist, bieten herkömmliche CPUs keine effizienten Möglichkeiten zum Erkennen von Überläufen. In x86 müssen Sie nach jedem potenziell überlaufenden Vorgang ein Pro-Core-Flag überprüfen. wenn Sie wirklich wollen, ist eine "verdorbene" Flagge auf dem Ergebnis (ähnlich wie sich NaN ausbreitet). Und Vektoroperationen können noch problematischer sein. Einige neue Player können mit effizienter Überlaufbehandlung auf dem Markt erscheinen. aber für jetzt x86 und ARM ist das egal.

Compiler-Optimierer sind nicht gut darin, Überlaufprüfungen zu optimieren oder sogar bei vorhandenen Überläufen zu optimieren. Einige Wissenschaftler wie John Regher beschweren sich über diesen Status , aber die Tatsache ist, dass, wenn die einfache Tatsache, dass Überläufe "Fehler" sind, Optimierungen verhindert, noch bevor die Baugruppe aufschlägt, die CPU lahmgelegt werden kann. Besonders wenn es die automatische Vektorisierung verhindert ...

Mit Kaskadeneffekten

In Ermangelung effizienter Optimierungsstrategien und einer effizienten CPU-Unterstützung ist die Überlaufprüfung daher kostspielig. Viel teurer als das Wickeln.

Fügen Sie einige störende Verhaltensweisen hinzu, z. B. x + y - 1einen Überlauf, wenn x - 1 + ydies nicht der Fall ist, was Benutzer berechtigterweise stören kann, und die Überlaufprüfung wird im Allgemeinen zugunsten des Umschließens (das dieses Beispiel und viele andere ordnungsgemäß behandelt) verworfen.

Dennoch ist nicht alle Hoffnung verloren

Die Compiler von clang und gcc haben sich bemüht, "Desinfektionsprogramme" zu implementieren: Möglichkeiten, Binärdateien zu instrumentieren, um Fälle von undefiniertem Verhalten zu erkennen. Bei Verwendung -fsanitize=undefinedwird ein signierter Überlauf erkannt und das Programm abgebrochen. sehr nützlich beim Testen.

In der Rust- Programmiersprache ist die Überlaufprüfung standardmäßig im Debug-Modus aktiviert (aus Leistungsgründen wird im Release-Modus die Umbrucharithmetik verwendet).

Daher wächst die Sorge, dass Überlaufprüfungen und die Gefahren von falschen Ergebnissen nicht erkannt werden, und dies wird hoffentlich das Interesse der Forschungsgemeinschaft, der Compilergemeinschaft und der Hardware-Gemeinschaft wecken.

Matthieu M.
quelle
6
@DmitryGrigoryev ist das Gegenteil einer effektiven Methode zur Überprüfung auf Überläufe. Bei Haswell wird beispielsweise der Durchsatz von 4 normalen Additionen pro Zyklus auf nur 1 geprüfte Addition reduziert, bevor die Auswirkungen von Verzweigungsfehlervorhersagen von jo's' und 's' berücksichtigt werden Weitere globale Auswirkungen der Verschmutzung tragen zum Status der Verzweigungsvorhersage und zur Erhöhung der Codegröße bei. Wenn diese Flagge klebrig wäre, würde sie ein echtes Potenzial bieten. Und dann können Sie es im vektorisierten Code immer noch nicht richtig machen.
3
Da Sie auf einen Blog-Beitrag verlinken, den John Regehr verfasst hat, erschien es mir angebracht, auch auf einen anderen Artikel zu verlinken, der einige Monate vor dem von Ihnen verlinkten Artikel verfasst wurde. Diese Artikel sprechen über verschiedene Philosophien: In dem früheren Artikel sind Ganzzahlen von fester Größe; Integer-Arithmetik wird geprüft (dh der Code kann seine Ausführung nicht fortsetzen); Es gibt entweder eine Ausnahme oder eine Falle. In dem neueren Artikel geht es darum, ganze Zahlen mit fester Größe zu eliminieren, wodurch Überläufe vermieden werden.
Rwong
2
@rwong Unendlich große Ganzzahlen haben ebenfalls ihre Probleme. Wenn Ihr Überlauf das Ergebnis eines Fehlers ist (was häufig der Fall ist), kann dies einen schnellen Absturz in eine anhaltende Qual verwandeln, die alle Serverressourcen in Anspruch nimmt, bis alles schrecklich ausfällt. Ich bin größtenteils ein Fan des "Fail Early" -Ansatzes - weniger Gefahr, die gesamte Umwelt zu vergiften. Ich bevorzuge 1..100stattdessen die Pascal-ish- Typen - seien Sie explizit in Bezug auf die erwarteten Bereiche, anstatt in 2 ^ 31 "gezwungen" zu werden Kompilierzeit, gerade).
Luaan
1
@Luaan: Interessant ist, dass oft Zwischenberechnungen vorübergehend überlaufen können, das Ergebnis jedoch nicht. Beispielsweise kann es in Ihrem Bereich von 1..100 zu einem x * 2 - 2Überlauf kommen, wenn der Wert x51 beträgt, obwohl das Ergebnis passt. Dies zwingt Sie dazu, Ihre Berechnung neu zu ordnen (manchmal auf unnatürliche Weise). Nach meiner Erfahrung habe ich festgestellt, dass ich die Berechnung im Allgemeinen lieber in einem größeren Typ durchführe und dann überprüfe, ob das Ergebnis passt oder nicht.
Matthieu M.
1
@MatthieuM. Ja, hier betreten Sie das Territorium der "ausreichend intelligenten Compiler". Idealerweise sollte ein Wert von 103 für einen Typ von 1..100 gültig sein, solange er in einem Kontext, in dem ein echter Wert von 1..100 erwartet wird, niemals verwendet wird (z. B. x = x * 2 - 2sollte er für alle funktionieren, bei xdenen die Zuweisung eine gültige 1 ergibt). .100 Nummer). Das heißt, Operationen für den numerischen Typ haben möglicherweise eine höhere Genauigkeit als der Typ selbst, solange die Zuweisung passt. Dies wäre sehr nützlich in Fällen wie (a + b) / 2die zu ignorieren (unsigned) überläuft kann die richtige Wahl sein.
Luaan
10

Sprachen, die versuchen, Überläufe zu erkennen, haben die zugehörige Semantik historisch so definiert, dass sie die sonst nützlichen Optimierungen stark einschränkte. Unter anderem ist es oft nützlich, Berechnungen in einer anderen Reihenfolge als der im Code angegebenen durchzuführen. Die meisten Sprachen, die Überläufe abfangen, garantieren jedoch, dass der angegebene Code wie folgt lautet:

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

Wenn der Startwert von x beim 47. Durchlauf durch die Schleife zu einem Überlauf führen würde, wird Operation1 47-mal ausgeführt, und Operation2 wird 46 ausgeführt. In Ermangelung einer solchen Garantie verwendet nichts anderes in der Schleife x und nichts Verwendet den Wert von x nach einer von Operation1 oder Operation2 ausgelösten Ausnahme. Der Code könnte ersetzt werden durch:

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

Leider ist es schwierig, solche Optimierungen durchzuführen und gleichzeitig die korrekte Semantik in Fällen zu gewährleisten, in denen ein Überlauf innerhalb der Schleife aufgetreten wäre. Dies erfordert im Wesentlichen Folgendes:

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

Wenn man bedenkt, dass ein Großteil des Codes in der realen Welt aufwändigere Schleifen verwendet, ist es offensichtlich, dass die Optimierung des Codes unter Beibehaltung der Überlaufsemantik schwierig ist. Aufgrund von Caching-Problemen ist es außerdem durchaus möglich, dass das Gesamtprogramm durch die Erhöhung der Codegröße langsamer ausgeführt wird, obwohl auf dem gemeinsam ausgeführten Pfad weniger Vorgänge ausgeführt werden.

Um die Überlauferkennung kostengünstig zu machen, wäre ein definierter Satz von Semantiken für die Erkennung von Überläufen erforderlich, mit denen Code auf einfache Weise meldet, ob eine Berechnung ohne Überläufe durchgeführt wurde, die sich auf die Ergebnisse auswirken könnten (*), jedoch ohne Belastung der Compiler mit Details darüber hinaus. Wenn sich eine Sprachspezifikation darauf konzentrieren würde, die Kosten für die Überlauferkennung auf das zur Erreichung des oben genannten Ziels erforderliche Minimum zu reduzieren, könnten die Kosten erheblich gesenkt werden, als dies in vorhandenen Sprachen der Fall ist. Es sind mir jedoch keine Bemühungen bekannt, eine effiziente Überlauferkennung zu ermöglichen.

(*) Wenn eine Sprache verspricht, dass alle Überläufe gemeldet werden, kann ein Ausdruck wie x*y/ynicht vereinfacht werden, es xsei denn , es x*ykann garantiert werden, dass kein Überlauf auftritt. Auch wenn das Ergebnis einer Berechnung ignoriert würde, muss eine Sprache, die verspricht, alle Überläufe zu melden, diese trotzdem ausführen, damit die Überlaufprüfung durchgeführt werden kann. Da ein Überlauf in solchen Fällen nicht zu einem arithmetisch falschen Verhalten führen kann, müsste ein Programm solche Prüfungen nicht durchführen, um sicherzustellen, dass keine Überläufe möglicherweise ungenaue Ergebnisse verursacht haben.

Überläufe in C sind übrigens besonders schlimm. Obwohl fast jede Hardwareplattform, die C99 unterstützt, eine Silent-Wraparound-Semantik verwendet, ist es für moderne Compiler in Mode, Code zu generieren, der im Falle eines Überlaufs willkürliche Nebenwirkungen verursachen kann. Zum Beispiel mit etwas wie:

#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 generiert Code für test2, der einmal bedingungslos inkrementiert (* p) und unabhängig von dem an q übergebenen Wert 32768 zurückgibt. Nach seiner Überlegung würde die Berechnung von (32769 * 65535) & 65535u einen Überlauf verursachen, sodass der Compiler keine Fälle berücksichtigen muss, in denen (q | 32768) einen Wert größer als 32768 ergibt Damit bei der Berechnung von (32769 * 65535) & 65535u die oberen Bits des Ergebnisses berücksichtigt werden, verwendet gcc einen vorzeichenbehafteten Überlauf als Begründung für das Ignorieren der Schleife.

Superkatze
quelle
2
"Es ist in Mode für moderne Compiler ..." - Ähnlich war es für die Entwickler bestimmter bekannter Kernel kurzzeitig in Mode, die Dokumentation zu den von ihnen verwendeten Optimierungsflags nicht zu lesen und dann im gesamten Internet wütend zu werden weil sie gezwungen waren, noch mehr Compiler-Flags hinzuzufügen, um das gewünschte Verhalten zu erreichen ;-). In diesem Fall -fwrapvergibt sich ein definiertes Verhalten, wenn auch nicht das vom Fragesteller gewünschte. Zugegeben, die gcc-Optimierung macht aus jeder Art von C-Entwicklung eine gründliche Prüfung des Standards und des Compilerverhaltens.
Steve Jessop
1
@SteveJessop: C wäre eine viel gesündere Sprache, wenn Compiler-Autoren einen einfachen Dialekt erkennen würden, in dem "undefiniertes Verhalten" bedeutet, dass "alles getan wird, was auf der zugrunde liegenden Plattform Sinn macht". anstatt anzunehmen, dass der Ausdruck "nicht tragbar oder fehlerhaft" in der Norm einfach "fehlerhaft" bedeutet. In vielen Fällen ist der optimale Code, der in einer Sprache mit schwachen Verhaltensgarantien erhalten werden kann, viel besser als mit stärkeren Garantien oder ohne Garantien. Zum Beispiel ...
Supercat
1
... wenn ein Programmierer auf x+y > zeine Weise auswerten muss , die niemals etwas anderes als 0 oder 1 ergibt, aber eines der beiden Ergebnisse im Falle eines Überlaufs gleichermaßen akzeptabel wäre, könnte ein Compiler, der diese Garantie bietet, häufig besseren Code für das generieren Ausdruck x+y > zals jeder Compiler wäre in der Lage, für eine defensiv geschriebene Version des Ausdrucks zu generieren. Aus realistischer Sicht würde welcher Bruchteil nützlicher überlaufbezogener Optimierungen durch eine Garantie ausgeschlossen, dass andere Ganzzahlberechnungen als Division / Rest ohne Nebenwirkungen ausgeführt werden?
Supercat
Ich gebe zu, dass ich nicht ganz im Detail bin, aber die Tatsache, dass Ihr Groll mit "Compiler-Autoren" im Allgemeinen und nicht speziell "jemandem auf gcc, der meinen -fwhatever-makes-sensePatch nicht akzeptiert ", legt mir nahe, dass es noch mehr gibt dazu als launisch von ihrer Seite. Die üblichen Argumente, die ich gehört habe, sind, dass Code-Inlining (und sogar Makro-Erweiterung) davon profitiert, so viel wie möglich über die spezifische Verwendung eines Codekonstrukts abzuleiten, da beide Methoden üblicherweise eingefügten Code ergeben, der sich mit Fällen befasst, die nicht benötigt werden dazu, dass sich der umgebende Code als unmöglich "erweist".
Steve Jessop
Wenn ich also ein vereinfachtes Beispiel schreibe foo(i + INT_MAX + 1), sind Compiler-Autoren daran interessiert, Optimierungen für den Inline- foo()Code vorzunehmen , bei denen die Richtigkeit davon abhängt , dass das Argument nicht negativ ist (vielleicht teuflische Divmod-Tricks). Unter Ihren zusätzlichen Einschränkungen können sie nur Optimierungen anwenden, deren Verhalten für negative Eingaben für die Plattform sinnvoll ist. Natürlich würde ich mich freuen, wenn dies eine -fOption wäre, die sich -fwrapvusw. einschaltet , und wahrscheinlich einige Optimierungen deaktivieren müsste, für die es kein Flag gibt. Aber es ist nicht so, dass ich mir die Mühe machen könnte, all diese Arbeiten selbst zu erledigen.
Steve Jessop
9

Nicht alle Programmiersprachen ignorieren Ganzzahlüberläufe. Einige Sprachen bieten sichere Ganzzahloperationen für alle Zahlen (die meisten Lisp-Dialekte, Ruby, Smalltalk usw.) und andere über Bibliotheken - zum Beispiel gibt es verschiedene BigInt-Klassen für C ++.

Ob eine Sprache Integer standardmäßig vor Überlauf schützt oder nicht, hängt von ihrem Zweck ab: Systemsprachen wie C und C ++ müssen kostengünstige Abstraktionen bereitstellen, und "Big Integer" ist keine Eins. Produktivitätssprachen wie Ruby können und bieten große ganze Zahlen von der Stange. Sprachen wie Java und C #, die irgendwo dazwischen liegen, sollten IMHO mit den sicheren Ganzzahlen aus dem Kasten gehen, indem sie es nicht tun.

Nemanja Trifunovic
quelle
Beachten Sie, dass es einen Unterschied zwischen dem Erkennen eines Überlaufs (und dann eines Signals, einer Panik, einer Ausnahme usw.) und dem Umschalten auf eine große Zahl gibt. Ersteres sollte viel billiger machbar sein als Letzteres.
Matthieu M.
@MatthieuM. Absolut - und mir ist klar, dass mir das in meiner Antwort nicht klar ist.
Nemanja Trifunovic
7

Wie Sie gezeigt haben, wäre C # dreimal langsamer gewesen, wenn standardmäßig Überlaufprüfungen aktiviert gewesen wären (vorausgesetzt, Ihr Beispiel ist eine typische Anwendung für diese Sprache). Ich stimme zu, dass die Leistung nicht immer das wichtigste Merkmal ist, aber Sprachen / Compiler werden in der Regel in Bezug auf ihre Leistung bei typischen Aufgaben verglichen. Dies liegt zum Teil daran, dass die Qualität der Sprachmerkmale etwas subjektiv ist, während ein Leistungstest objektiv ist.

Wenn Sie eine neue Sprache einführen würden, die in den meisten Aspekten C # ähnelt, aber dreimal langsamer ist, wäre es nicht einfach, einen Marktanteil zu erreichen, selbst wenn die meisten Endbenutzer letztendlich mehr von Überlaufprüfungen profitieren würden als sie von höherer Leistung.

Dmitry Grigoryev
quelle
10
Dies war insbesondere bei C # der Fall, das in seinen Anfängen im Vergleich zu Java und C ++ nicht mit schwer messbaren Kennzahlen zur Entwicklerproduktivität oder mit Kennzahlen zur Einsparung von Bargeld aus dem Nicht-Umgang-mit-Sicherheitsverletzungen verglichen wurde. die schwer zu messen sind, aber an trivialen Leistungsmaßstäben.
Eric Lippert
1
Und wahrscheinlich wird die Leistung der CPU durch einfaches Zählen von Zahlen überprüft. Optimierungen für die Überlauferkennung können daher bei diesen Tests zu "schlechten" Ergebnissen führen. Fang22.
Bernhard Hiller
5

Abgesehen von den vielen Antworten, die eine mangelnde Überprüfung des Überlaufs auf der Grundlage der Leistung rechtfertigen, sind zwei verschiedene Arten von Berechnungen zu berücksichtigen:

  1. Indizierungsberechnungen (Array-Indizierung und / oder Zeigerarithmetik)

  2. andere Arithmetik

Wenn die Sprache eine Ganzzahlgröße verwendet, die mit der Zeigergröße identisch ist, läuft ein gut aufgebautes Programm bei Indexierungsberechnungen nicht über, da notwendigerweise nicht genügend Arbeitsspeicher vorhanden sein muss, bevor die Indexierungsberechnungen einen Überlauf verursachen.

Daher ist das Überprüfen der Speicherzuordnungen ausreichend, wenn mit Zeigerarithmetik und Indexausdrücken gearbeitet wird, die zugewiesene Datenstrukturen enthalten. Wenn Sie beispielsweise über einen 32-Bit-Adressraum verfügen, 32-Bit-Ganzzahlen verwenden und maximal 2 GB Heap (etwa die Hälfte des Adressraums) zuweisen, werden Index- / Zeigerberechnungen (im Grunde genommen) nicht überlaufen.

Darüber hinaus werden Sie möglicherweise überrascht sein, wie viel Addition / Subtraktion / Multiplikation eine Array-Indizierung oder eine Zeigerberechnung umfasst und somit in die erste Kategorie fällt. Objektzeiger-, Feldzugriffs- und Array-Manipulationen sind Indizierungsoperationen, und viele Programme führen nicht mehr arithmetische Berechnungen durch als diese! Dies ist im Wesentlichen der Hauptgrund dafür, dass Programme genauso gut funktionieren wie ohne Ganzzahlüberlaufprüfung.

Alle Nicht-Indexierungs- und Nicht-Zeiger-Berechnungen sollten entweder als solche klassifiziert werden, die einen Überlauf wünschen / erwarten (z. B. Hashing-Berechnungen), oder als solche, die dies nicht tun (z. B. Ihr Summierungsbeispiel).

Im letzteren Fall verwenden Programmierer häufig alternative Datentypen, wie z. B. doubleoder einige BigInt. Viele Berechnungen erfordern decimaleher einen Datentyp als doublez. B. finanzielle Berechnungen. Wenn sie dies nicht tun und bei Integer-Typen bleiben, müssen sie darauf achten, dass der Integer-Überlauf nicht erkannt wird. Andernfalls kann das Programm einen unerkannten Fehlerzustand erreichen, wie Sie darauf hinweisen.

Als Programmierer müssen wir sensibel auf unsere Auswahl numerischer Datentypen und deren Konsequenzen in Bezug auf die Möglichkeiten eines Überlaufs reagieren, ganz zu schweigen von der Präzision. Im Allgemeinen (und insbesondere bei der Arbeit mit der C-Sprachfamilie mit dem Wunsch, schnelle Ganzzahltypen zu verwenden) müssen wir die Unterschiede zwischen Indexberechnungen und anderen berücksichtigen und berücksichtigen.

Erik Eidt
quelle
3

Die Sprache Rust bietet einen interessanten Kompromiss zwischen der Überprüfung auf Überläufe und nicht, indem die Überprüfungen für den Debugbuild hinzugefügt und in der optimierten Release-Version entfernt werden. Auf diese Weise können Sie die Fehler während des Testens finden und erhalten dennoch die volle Leistung in der endgültigen Version.

Da die Überlaufumgehung manchmal erwünscht ist, gibt es auch Versionen der Operatoren , die niemals auf Überlauf prüfen.

Weitere Informationen zu den Gründen für die Auswahl finden Sie im RFC für die Änderung. Es gibt auch viele interessante Informationen in diesem Blog-Beitrag , einschließlich einer Liste von Fehlern , die mit dieser Funktion beim Auffinden von Fehlern geholfen haben.

Hjulle
quelle
2
Rust stellt auch Verfahren wie checked_mul, das überprüft , ob Überlauf aufgetreten ist, und kehrt hat , Nonewenn ja, Someanders. Dies kann sowohl im Produktions- als auch im Debug-Modus verwendet werden: doc.rust-lang.org/std/primitive.i32.html#examples-15
Akavall
3

In Swift werden Integer-Überläufe standardmäßig erkannt und stoppen das Programm sofort. In Fällen, in denen Sie ein Umlaufverhalten benötigen, gibt es verschiedene Operatoren & +, & - und & *, die dies erreichen. Und es gibt Funktionen, die eine Operation ausführen und feststellen, ob ein Überlauf aufgetreten ist oder nicht.

Es macht Spaß zu sehen, wie Anfänger versuchen, die Collatz-Sequenz zu bewerten und ihren Code zum Absturz bringen :-)

Jetzt sind die Designer von Swift auch die Designer von LLVM und Clang, sodass sie sich ein oder zwei Mal mit Optimierung auskennen und in der Lage sind, unnötige Überlaufprüfungen zu vermeiden. Wenn alle Optimierungen aktiviert sind, trägt die Überlaufprüfung nicht wesentlich zur Codegröße und Ausführungszeit bei. Und da die meisten Überläufe zu absolut falschen Ergebnissen führen, sind Codegröße und Ausführungszeit sinnvoll.

PS. In C, C ++ ist der mit Objective-C vorzeichenbehaftete ganzzahlige arithmetische Überlauf undefiniertes Verhalten. Das heißt, was auch immer der Compiler im Fall eines vorzeichenbehafteten Ganzzahlüberlaufs tut, ist per Definition korrekt. Typische Möglichkeiten, mit einem vorzeichenbehafteten Integer-Überlauf umzugehen, bestehen darin, ihn zu ignorieren. Dabei wird das Ergebnis der CPU berücksichtigt, sodass der Compiler davon ausgeht, dass ein solcher Überlauf niemals auftreten wird Es wird davon ausgegangen, dass dies niemals passiert. Eine selten genutzte Möglichkeit besteht darin, zu überprüfen und abzustürzen, ob ein Überlauf auftritt, wie dies bei Swift der Fall ist.

gnasher729
quelle
1
Ich habe mich manchmal gefragt, ob die Leute, die UB-getriebenen Wahnsinn in C vorantreiben, heimlich versucht haben, ihn zugunsten einer anderen Sprache zu untergraben. Das würde Sinn machen.
Supercat
Wenn x+1>xein Compiler als bedingungslos wahr behandelt wird, muss er keine "Annahmen" über x treffen, wenn er ganzzahlige Ausdrücke mit willkürlich größeren Typen so bequem wie möglich auswerten darf (oder sich so verhält, als ob dies der Fall wäre). Ein schlimmeres Beispiel für überlaufbasierte "Annahmen" wäre die Entscheidung, dass uint32_t mul(uint16_t x, uint16_t y) { return x*y & 65535u; }ein Compiler sum += mul(65535, x)entscheiden xkann , ob er nicht größer als 32768 sein darf [Verhalten, das die Leute, die die C89-Begründung verfasst haben, wahrscheinlich schockieren würde, was darauf hindeutet, dass einer der entscheidenden Faktoren. ..
Supercat
... bei der Heraufstufung unsigned shortzu signed intwar die Tatsache, dass Silent-Wraparound-Implementierungen mit zwei Ergänzungen (dh die Mehrheit der damals verwendeten C-Implementierungen) Code wie oben beschrieben gleich behandeln würden, unabhängig davon, ob unsigned shortzu intoder heraufgestuft wurde unsigned. Der Standard erforderte keine Implementierungen auf Hardware, die sich aus zwei Komponenten zusammensetzt, um Code wie oben beschrieben zu behandeln, aber die Autoren des Standards hatten anscheinend damit gerechnet, dass sie dies dennoch tun würden.
Superkatze
2

Tatsächlich ist die eigentliche Ursache dafür rein technisch / historisch: Die CPU ignoriert zum größten Teil das Vorzeichen. Im Allgemeinen gibt es nur einen einzigen Befehl zum Hinzufügen von zwei Ganzzahlen in Registern, und der CPU ist es gleichgültig, ob Sie diese beiden Ganzzahlen als vorzeichenbehaftet oder nicht vorzeichenbehaftet interpretieren. Das gleiche gilt für die Subtraktion und sogar für die Multiplikation. Die einzige Rechenoperation, die vorzeichenbewusst sein muss, ist die Division.

Der Grund, warum dies funktioniert, ist die 2er-Komplementdarstellung von vorzeichenbehafteten ganzen Zahlen, die von praktisch allen CPUs verwendet wird. In 4-Bit-2-Komplementen sieht die Addition von 5 und -3 beispielsweise folgendermaßen aus:

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

Beobachten Sie, wie das Umlaufverhalten beim Wegwerfen des Übertragsbits das richtige vorzeichenbehaftete Ergebnis liefert. Ebenso implementieren CPUs die Subtraktion normalerweise x - ywie folgt x + ~y + 1:

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

Dies implementiert die Subtraktion als eine Addition in der Hardware, wobei nur die Eingaben in die arithmetisch-logische Einheit (ALU) auf triviale Weise optimiert werden. Was könnte einfacher sein?

Da Multiplikation nichts anderes als eine Folge von Additionen ist, verhält es sich ähnlich gut. Das Ergebnis der Verwendung der Zweierkomplementdarstellung und des Ignorierens der Ausführung von arithmetischen Operationen ist eine vereinfachte Schaltungsanordnung und vereinfachte Befehlssätze.

Da C so konzipiert wurde, dass es in der Nähe des Metalls arbeitet, hat es offensichtlich genau dasselbe Verhalten wie das standardisierte Verhalten von vorzeichenloser Arithmetik angenommen, sodass nur vorzeichenbehaftete Arithmetik undefiniertes Verhalten liefert. Und diese Wahl wurde auf andere Sprachen wie Java und natürlich C # übertragen.

cmaster
quelle
Ich bin hergekommen, um auch diese Antwort zu geben.
Herr Lister,
Leider scheinen einige Leute die Vorstellung, dass Leute, die C-Code auf niedriger Ebene auf einer Plattform schreiben, die Kühnheit haben sollten, zu erwarten, dass sich ein C-Compiler, der für diesen Zweck geeignet ist, im Falle eines Überlaufs auf eingeschränkte Weise verhält, als grob unzumutbar zu betrachten. Persönlich halte ich es für angemessen, wenn sich ein Compiler so verhält, als ob Berechnungen mit willkürlich erweiterter Genauigkeit durchgeführt würden (also auf einem 32-Bit-System, wenn x==INT_MAX, dann x+1könnte er sich beim Compiler willkürlich entweder als +2147483648 oder -2147483648 verhalten Bequemlichkeit), aber ...
Supercat
Einige Leute scheinen zu denken, dass, wenn xund ysind uint16_tund Code auf einem 32-Bit-System berechnet, x*y & 65535uwenn y65535 ist, ein Compiler davon ausgehen sollte, dass Code nie erreicht wird, wenn xgrößer als 32768.
Supercat
1

In einigen Antworten wurden die Überprüfungskosten erörtert, und Sie haben Ihre Antwort bearbeitet, um zu bestreiten, dass dies eine vernünftige Rechtfertigung ist. Ich werde versuchen, diese Punkte anzusprechen.

In C und C ++ (als Beispiel) besteht eines der Prinzipien beim Entwerfen von Sprachen nicht darin, Funktionen bereitzustellen, nach denen nicht gefragt wurde. Dies wird üblicherweise mit dem Satz "Zahlen Sie nicht für das, was Sie nicht verwenden" zusammengefasst. Wenn der Programmierer eine Überlaufprüfung wünscht, kann er danach fragen (und die Strafe bezahlen). Dies macht die Verwendung der Sprache gefährlicher, Sie entscheiden sich jedoch dafür, mit der Sprache zu arbeiten, die dies kennt, und Sie akzeptieren das Risiko. Wenn Sie dieses Risiko nicht möchten oder wenn Sie Code schreiben, bei dem die Sicherheit von größter Bedeutung ist, können Sie eine geeignetere Sprache auswählen, bei der das Verhältnis zwischen Leistung und Risiko unterschiedlich ist.

Bei den 10.000.000.000 Wiederholungen beträgt der Zeitaufwand für eine Überprüfung jedoch immer noch weniger als 1 Nanosekunde.

An dieser Argumentation sind einige Dinge falsch:

  1. Dies ist umgebungsspezifisch. Es ist im Allgemeinen wenig sinnvoll, bestimmte Zahlen wie diese zu zitieren, da Code für alle Arten von Umgebungen geschrieben wird, die hinsichtlich ihrer Leistung um Größenordnungen variieren. Ihre 1 Nanosekunde auf einem (ich nehme an) Desktop-Computer scheint für jemanden, der für eine eingebettete Umgebung codiert, erstaunlich schnell und für jemanden, der für einen Super-Computer-Cluster codiert, unerträglich langsam zu sein.

  2. 1 Nanosekunde scheint für ein Codesegment, das selten ausgeführt wird, nichts zu sein. Auf der anderen Seite kann jeder einzelne Bruchteil der Zeit, den Sie abschneiden können, einen großen Unterschied bewirken, wenn sich der Code in einer inneren Schleife einer Berechnung befindet, die die Hauptfunktion des Codes darstellt. Wenn Sie eine Simulation in einem Cluster ausführen, können diese gespeicherten Bruchteile einer Nanosekunde in Ihrer inneren Schleife direkt in Geld umgewandelt werden, das für Hardware und Strom ausgegeben wird.

  3. Für einige Algorithmen und Kontexte können 10.000.000.000 Iterationen unbedeutend sein. Auch hier ist es im Allgemeinen nicht sinnvoll, über bestimmte Szenarien zu sprechen, die nur in bestimmten Kontexten gelten.

Es kann Situationen geben, in denen dies wichtig ist, aber für die meisten Anwendungen spielt dies keine Rolle.

Vielleicht hast du recht. Aber auch dies ist eine Frage der Ziele einer bestimmten Sprache. In der Tat sind viele Sprachen so konzipiert, dass sie den Bedürfnissen der "meisten" gerecht werden oder die Sicherheit anderen Bedenken vorziehen. Andere wie C und C ++ legen Wert auf Effizienz. In diesem Zusammenhang verstößt es gegen das, was die Sprache zu erreichen versucht, wenn jeder eine Leistungsstrafe zahlen muss, nur weil die meisten Menschen sich nicht darum kümmern.

Jon Bentley
quelle
-1

Es gibt gute Antworten, aber ich denke, hier gibt es einen vermissten Punkt: Die Auswirkungen eines Ganzzahlüberlaufs sind nicht unbedingt schlecht, und im Nachhinein ist es schwierig zu erkennen, ob der iÜbergang vom Sein MAX_INTzum Sein MIN_INTauf ein Überlaufproblem zurückzuführen ist oder wenn dies absichtlich durch Multiplikation mit -1 geschehen ist.

Wenn ich zum Beispiel alle darstellbaren ganzen Zahlen größer als 0 addieren möchte, würde ich einfach eine for(i=0;i>=0;++i){...}Additionsschleife verwenden - und wenn sie überläuft, stoppt sie die Addition, was das Zielverhalten ist (das Auslösen eines Fehlers würde bedeuten, dass ich umgehen muss ein willkürlicher Schutz, weil er die Standardarithmetik stört). Es ist eine schlechte Praxis, primitive Arithmetik einzuschränken, weil:

  • Sie werden in allem verwendet - eine Verlangsamung in der primitiven Mathematik ist eine Verlangsamung in jedem funktionierenden Programm
  • Wenn ein Programmierer sie benötigt, kann er sie jederzeit hinzufügen
  • Wenn Sie sie haben und der Programmierer sie nicht benötigt (aber schnellere Laufzeiten benötigt), können sie sie nicht einfach zur Optimierung entfernen
  • Wenn Sie sie haben und der Programmierer sie nicht dort haben muss (wie im obigen Beispiel), nimmt der Programmierer beide den Laufzeit-Treffer (der möglicherweise relevant ist oder nicht) und der Programmierer muss immer noch Zeit investieren, um sie zu entfernen oder arbeiten um den "Schutz".
Delioth
quelle
3
Es ist für einen Programmierer nicht wirklich möglich, eine effiziente Überlaufprüfung hinzuzufügen, wenn eine Sprache dies nicht vorsieht. Wenn eine Funktion einen Wert berechnet, der ignoriert wird, kann ein Compiler die Berechnung optimieren. Wenn eine Funktion einen Wert berechnet, der überlaufgeprüft, aber ansonsten ignoriert wird, muss ein Compiler die Berechnung durchführen und einen Trap ausführen, wenn er überläuft, auch wenn ein Überlauf die Programmausgabe ansonsten nicht beeinträchtigen würde und sicher ignoriert werden könnte.
Supercat
1
Sie können nicht von INT_MAXzu INT_MINwechseln, indem Sie mit -1 multiplizieren.
David Conrad
Die Lösung besteht offensichtlich darin, dem Programmierer die Möglichkeit zu bieten, die Prüfungen in einem bestimmten Codeblock oder einer bestimmten Kompilierungseinheit auszuschalten.
David Conrad
for(i=0;i>=0;++i){...}ist der Codestil, von dem ich in meinem Team abzuraten versuche: Er beruht auf Spezialeffekten / Nebenwirkungen und drückt nicht klar aus, was er soll. Trotzdem weiß ich Ihre Antwort zu schätzen, da sie ein anderes Programmierparadigma zeigt.
Bernhard Hiller
1
@Delioth: Wenn ies sich um einen 64-Bit-Typ handelt, selbst bei einer Implementierung mit einem konsistenten Verhalten, bei dem eine Milliarde Iterationen pro Sekunde ausgeführt werden, und bei der ein Zweierkomplement-Umlauf ausgeführt wird, kann sichergestellt werden, dass eine solche Schleife nur dann den größten intWert findet, wenn sie ausgeführt werden darf Hunderte von Jahren. Auf Systemen, die kein konsistentes Verhalten bei unbeaufsichtigtem Zugriff versprechen, kann ein solches Verhalten nicht garantiert werden, unabhängig davon, wie lange Code angegeben wird.
Supercat