Czy kiedykolwiek próbowałeś zsumować wszystkie liczby od 1 do 2 000 000 w swoim ulubionym języku programowania? Wynik można łatwo obliczyć ręcznie: 2 000 001 000 000, czyli około 900 razy więcej niż maksymalna wartość 32-bitowej liczby całkowitej bez znaku.
Drukuje się C # -1453759936
- wartość ujemna! I chyba Java robi to samo.
Oznacza to, że istnieje kilka popularnych języków programowania, które domyślnie ignorują przepełnienie arytmetyczne (w języku C # istnieją ukryte opcje zmiany tego). To zachowanie wydaje mi się bardzo ryzykowne, a czy awaria Ariane 5 nie była spowodowana takim przepełnieniem?
Więc: jakie decyzje projektowe kryją się za tak niebezpiecznym zachowaniem?
Edytować:
Pierwsze odpowiedzi na to pytanie wyrażają nadmierne koszty sprawdzania. Uruchommy krótki program w języku C #, aby przetestować to założenie:
Stopwatch watch = Stopwatch.StartNew();
checked
{
for (int i = 0; i < 200000; i++)
{
int sum = 0;
for (int j = 1; j < 50000; j++)
{
sum += j;
}
}
}
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);
Na moim komputerze wersja sprawdzona zajmuje 11015 ms, a wersja niezaznaczona 4125 ms. Tzn. Kroki sprawdzania trwają prawie dwa razy dłużej niż dodawanie liczb (w sumie 3 razy pierwotny czas). Ale przy 10 000 000 000 powtórzeń czas sprawdzania jest nadal krótszy niż 1 nanosekunda. Może się zdarzyć, że jest to ważne, ale w przypadku większości aplikacji nie będzie to miało znaczenia.
Edycja 2:
Zrekompilowałem naszą aplikację serwerową (usługa Windows analizująca dane otrzymane z kilku czujników, dość sporo kradzieży danych) z /p:CheckForOverflowUnderflow="false"
parametrem (zwykle włączam kontrolę przepełnienia) i wdrożyłem ją na urządzeniu. Monitorowanie Nagios pokazuje, że średnie obciążenie procesora pozostało na poziomie 17%.
Oznacza to, że uderzenie wydajności znalezione w powyższym przykładzie jest zupełnie nieistotne dla naszej aplikacji.
źródło
checked { }
sekcji do oznaczenia części kodu, które powinny wykonywać sprawdzanie przepełnienia arytmetycznego. Wynika to z występu(1..2_000_000).sum #=> 2000001000000
. Jeszcze jedno z moich ulubionych językach:sum [1 .. 2000000] --=> 2000001000000
. Nie mój ulubiony:Array.from({length: 2000001}, (v, k) => k).reduce((acc, el) => acc + el) //=> 2000001000000
. (Szczerze mówiąc, ostatni oszukuje.)Integer
w Haskell ma dowolną precyzję, będzie przechowywać dowolną liczbę, o ile nie zabraknie przydzielonej pamięci RAM.But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond.
wskazuje to na optymalizację pętli. Również to zdanie jest sprzeczne z poprzednimi liczbami, które wydają mi się bardzo ważne.Odpowiedzi:
Istnieją 3 powody tego:
Koszt sprawdzania przepełnień (dla każdej pojedynczej operacji arytmetycznej) w czasie wykonywania jest nadmierny.
Złożoność udowodnienia, że kontrola przepełnienia może zostać pominięta w czasie kompilacji, jest nadmierna.
W niektórych przypadkach (np. Obliczenia CRC, biblioteki dużych liczb itp.) „Zawijanie przy przepełnieniu” jest wygodniejsze dla programistów.
źródło
unsigned int
nie powinien przychodzić na myśl, ponieważ język z funkcją sprawdzania przepełnienia powinien domyślnie sprawdzać wszystkie typy liczb całkowitych. Powinieneś napisaćwrapping unsigned int
.didOverflow()
funkcja wbudowana, a nawet zmienna globalna,__carry
która pozwala na dostęp do flagi przenoszenia, kosztowałaby zero czasu procesora, gdybyś jej nie używał.ADD
Nie ustawia przenoszenia (potrzebujeszADDS
). Itanium nawet nie mieć flagę carry. Nawet na x86 AVX nie ma flag przenoszenia.unchecked
jest dość łatwe; ale możesz przeceniać, jak często liczy się przepełnienie.adds
ma tę samą cenę coadd
(to tylko 1-bitowa flaga instrukcji, która decyduje, czy flaga przeniesienia jest aktualizowana).add
Instrukcje MIPS pułapki na przepełnienie - musisz poprosić, aby nie pułapki na przepełnienie, używającaddu
zamiast tego!Kto powiedział, że to zły kompromis ?!
Uruchamiam wszystkie moje aplikacje produkcyjne z włączoną kontrolą przepełnienia. Jest to opcja kompilatora C #. Właściwie to przeprowadziłem testy porównawcze i nie byłem w stanie określić różnicy. Koszt dostępu do bazy danych w celu wygenerowania (nie-zabawkowego) kodu HTML przesłania koszty kontroli przepełnienia.
Doceniam fakt, że wiem, że w produkcji nie przepełniają się żadne operacje. Niemal cały kod zachowywałby się nieprawidłowo w przypadku przepełnienia. Błędy nie byłyby łagodne. Prawdopodobne jest uszkodzenie danych, istnieje możliwość bezpieczeństwa.
W przypadku, gdy potrzebuję wydajności, co czasami bywa, wyłączam sprawdzanie przepełnienia za
unchecked {}
pomocą granulacji. Kiedy chcę zawołać, że polegam na operacji, która się nie przepełnia, mogę nadmiarowo dodaćchecked {}
do kodu, aby udokumentować ten fakt. Mam na myśli przepełnienia, ale niekoniecznie muszę być dzięki kontroli.Uważam, że zespół C # dokonał złego wyboru, gdy postanowił nie sprawdzać domyślnie przepełnienia, ale ten wybór jest teraz zamknięty z powodu poważnych obaw dotyczących zgodności. Zauważ, że tego wyboru dokonano około 2000 roku. Sprzęt był mniej zdolny, a .NET nie miał jeszcze dużej przyczepności. Być może .NET chciał w ten sposób spodobać się programistom Java i C / C ++. .NET ma także być blisko metalu. Właśnie dlatego ma niebezpieczny kod, struktury i świetne natywne możliwości połączeń, których nie ma Java.
Im szybszy jest nasz sprzęt i im bardziej inteligentne kompilatory, tym bardziej atrakcyjne jest domyślnie sprawdzanie przepełnienia.
Uważam również, że kontrola przepełnienia jest często lepsza niż liczby nieskończone. Liczby o nieskończonej wielkości mają jeszcze wyższy koszt wydajności, trudniejszy do optymalizacji (uważam) i otwierają możliwość nieograniczonego zużycia zasobów.
Sposób radzenia sobie z przepełnieniem JavaScript jest jeszcze gorszy. Numery JavaScript są podwójnymi zmiennoprzecinkowymi. „Przelew” objawia się jako pozostawienie w pełni precyzyjnego zestawu liczb całkowitych. Pojawią się nieco niepoprawne wyniki (takie jak wyłączenie przez jeden - może to zmienić pętle skończone w nieskończone).
W przypadku niektórych języków, takich jak C / C ++, kontrola przepełnienia domyślnie jest wyraźnie nieodpowiednia, ponieważ rodzaje aplikacji pisanych w tych językach wymagają wydajności od zera. Nadal jednak podejmowane są starania, aby język C / C ++ stał się bezpieczniejszym językiem, umożliwiając włączenie trybu bezpieczniejszego. Jest to godne pochwały, ponieważ 90–99% kodu wydaje się być zimne. Przykładem jest
fwrapv
opcja kompilatora, która wymusza zawijanie dopełniacza 2. Jest to funkcja „jakości implementacji” kompilatora, a nie języka.Haskell nie ma logicznego stosu wywołań ani określonej kolejności oceny. To powoduje, że wyjątki występują w nieprzewidywalnych punktach. W
a + b
to jest określone, czya
lubb
oceniana jest pierwszym i czy te wyrażenia zakończyć w ogóle, czy nie. Dlatego sensowne jest, aby Haskell przez większość czasu używał nieograniczonych liczb całkowitych. Ten wybór jest odpowiedni dla czysto funkcjonalnego języka, ponieważ wyjątki są naprawdę nieodpowiednie w większości kodów Haskell. A podział przez zero jest rzeczywiście problematycznym punktem w projektowaniu języka Haskells. Zamiast nieograniczonych liczb całkowitych mogliby również użyć liczb całkowitych zawijających o stałej szerokości, ale to nie pasuje do motywu „skupienie się na poprawności”, który oferuje ten język.Alternatywą dla wyjątków przepełnienia są wartości trucizny tworzone przez niezdefiniowane operacje i propagowane przez operacje (takie jak
NaN
wartość zmiennoprzecinkowa ). Wydaje się to o wiele droższe niż sprawdzanie przepełnienia i powoduje, że wszystkie operacje są wolniejsze, nie tylko te, które mogą zawieść (z wyjątkiem przyspieszania sprzętowego, które często mają zmiennoprzecinkowe, a intry zwykle nie - chociaż Itanium ma NaT, który jest „Not a Thing” ). Nie widzę też sensu, aby program nadal słabał wraz ze złymi danymi. To jest jakON ERROR RESUME NEXT
. Ukrywa błędy, ale nie pomaga uzyskać poprawnych wyników. supercat wskazuje, że czasami jest to optymalizacja wydajności.źródło
unsigned
tylko dla liczb całkowitych. Zachowanie się przepełnienia liczby całkowitej jest faktycznie niezdefiniowanym zachowaniem w C i C ++. Tak, niezdefiniowane zachowanie . Tak się składa, że prawie wszyscy implementują go jako przepełnienie uzupełnienia 2. C # faktycznie czyni to oficjalnym, zamiast pozostawiać UB jak C / C ++gcc -O2
forx + 1 > x
(gdziex
jest anint
). Zobacz także gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/… . Zachowanie uzupełniania 2s przy podpisanym przepełnieniu w C jest opcjonalne , nawet w prawdziwych kompilatorach, igcc
domyślnie ignoruje je w normalnych poziomach optymalizacji.Bo to zły kompromis, aby wszystkie obliczenia dużo droższe w celu automatycznego złapać rzadki przypadek, że przepełnienie robi wystąpić. O wiele lepiej jest obciążać programistę rozpoznawaniem rzadkich przypadków, w których jest to problem, i dodawać specjalne środki zapobiegawcze, niż zmuszać wszystkich programistów do płacenia ceny za funkcje, których nie używają.
źródło
„Nie zmuszaj użytkowników do płacenia kary za wydajność za funkcję, której mogą nie potrzebować”.
Jest to jedna z najbardziej podstawowych zasad w projektowaniu C i C ++ i wynika z innego czasu, kiedy musiałeś przejść przez absurdalne wysiłki, aby uzyskać ledwo wystarczającą wydajność dla zadań, które dziś są uważane za trywialne.
Nowsze języki zrywają z tym podejściem w przypadku wielu innych funkcji, takich jak sprawdzanie granic tablicy. Nie jestem pewien, dlaczego nie zrobili tego w celu sprawdzenia przepełnienia; może to być po prostu przeoczenie.
źródło
checked
iunchecked
dodali składnię do przełączania między nimi lokalnie, a także przełączniki wiersza poleceń (i ustawienia projektu w VS), aby zmienić go globalnie. Możesz nie zgadzać się zunchecked
ustawieniem domyślnym (ja to robię), ale wszystko to jest bardzo celowe.Dziedzictwo
Powiedziałbym, że problem jest prawdopodobnie zakorzeniony w dziedzictwie. W C:
Zrobiono to, aby uzyskać najlepszą możliwą wydajność, zgodnie z zasadą, że programista wie, co robi .
Prowadzi do Statu-Quo
Fakt, że C (i przez rozszerzenie C ++) nie wymagają wykrywania przepełnienia po kolei, oznacza, że sprawdzanie przepełnienia jest powolne.
Sprzęt głównie obsługuje C / C ++ (poważnie, x86 ma
strcmp
instrukcję (aka PCMPISTRI od SSE 4.2)!), A ponieważ C nie obchodzi, wspólne procesory nie oferują wydajnych sposobów wykrywania przepełnień. W wersji x86 należy sprawdzać flagę poszczególnych rdzeni po każdej potencjalnie przepełnionej operacji; kiedy tak naprawdę chcesz, to flaga „skażona” na wyniku (podobnie jak propaguje NaN). A operacje wektorowe mogą być jeszcze bardziej problematyczne. Niektórzy nowi gracze mogą pojawić się na rynku z wydajną obsługą przepełnienia; ale na razie x86 i ARM nie dbają.Optymalizatory kompilatora nie są dobre w optymalizacji kontroli przepełnienia, a nawet optymalizacji w przypadku przepełnienia. Niektórzy naukowcy, tacy jak John Regher, narzekają na takie status-quo , ale faktem jest, że gdy zwykły fakt spowodowania przelewu „awarie” uniemożliwia optymalizacje nawet zanim zespół uderzy procesor może być paraliżujący. Zwłaszcza gdy zapobiega automatycznej wektoryzacji ...
Z efektami kaskadowymi
Wobec braku skutecznych strategii optymalizacji i wydajnego wsparcia procesora, kontrola przepełnienia jest kosztowna. Znacznie droższe niż pakowanie.
Dodaj trochę irytujących zachowań, takich jak
x + y - 1
przepełnienie, gdyx - 1 + y
tego nie zrobi, co może słusznie zirytować użytkowników, a sprawdzanie przepełnienia jest ogólnie odrzucane na rzecz zawijania (które obsługuje ten przykład i wiele innych z wdziękiem).Nadal jednak nie wszystko stracone
W kompilatorach clang i gcc podjęto starania, aby zaimplementować „środki dezynfekujące”: sposoby instrumentowania plików binarnych w celu wykrycia przypadków niezdefiniowanego zachowania. Podczas używania
-fsanitize=undefined
wykrywane przepełnienie jest wykrywane i przerywa działanie programu; bardzo przydatne podczas testowania.Język programowania Rust ma domyślnie włączoną funkcję sprawdzania przepełnienia w trybie debugowania (używa arytmetyki zawijania w trybie zwalniania ze względu na wydajność).
Wzrasta więc obawa związana z sprawdzaniem przepełnienia i niebezpieczeństwami, że fałszywe wyniki pozostaną niewykryte, i mam nadzieję, że to z kolei wzbudzi zainteresowanie społeczności badawczej, kompilatorów i społeczności sprzętowej.
źródło
jo
i bardziej globalne skutki zanieczyszczenia dodają do stanu predyktora gałęzi i zwiększają rozmiar kodu. Gdyby ta flaga była lepka, oferowałby pewien prawdziwy potencjał ... a następnie nadal nie można tego zrobić poprawnie w kodzie wektorowym.1..100
zamiast tego typy pascalskie - wyraźne określenie oczekiwanych zakresów, zamiast „wymuszania” na 2 ^ 31 itd. Oczywiście niektóre języki to oferują i zazwyczaj sprawdzają przepełnienie (czasami w nawet czas kompilacji).x * 2 - 2
może się przepełnić, gdyx
wynosi 51, nawet jeśli wynik pasuje, co zmusza cię do zmiany kolejności obliczeń (czasami w nienaturalny sposób). Z mojego doświadczenia wynika, że generalnie wolę uruchomić obliczenia w większym typie, a następnie sprawdzić, czy wynik pasuje, czy nie.x = x * 2 - 2
Powinna działać dla wszystkich, wx
których przypisanie daje poprawną wartość 1). .100). Oznacza to, że operacje na typie numerycznym mogą mieć większą dokładność niż sam typ, o ile pasuje to przypisanie. Byłoby to bardzo przydatne w przypadkach, w(a + b) / 2
których ignorowanie (niepodpisane) przepełnienia może być prawidłową opcją.Języki, które próbują wykryć przepełnienie, historycznie zdefiniowały powiązaną semantykę w sposób, który poważnie ograniczyłby to, co w innym przypadku byłoby użytecznymi optymalizacjami. Między innymi, chociaż często przydatne będzie wykonywanie obliczeń w innej sekwencji niż określona w kodzie, większość języków, w których występują przepełnienia pułapek, gwarantuje, że dany kod, taki jak:
jeśli początkowa wartość x spowodowałaby przepełnienie przy 47. przejściu przez pętlę, Operacja1 wykona 47 razy, a Operacja2 wykona 46. W przypadku braku takiej gwarancji, jeśli nic innego w pętli nie używa x i nic użyje wartości x po zgłoszonym wyjątku przez Operację1 lub Operację2, kod można zastąpić:
Niestety, przeprowadzanie takich optymalizacji przy jednoczesnym zagwarantowaniu poprawnej semantyki w przypadkach, w których nastąpiłoby przepełnienie w pętli, jest trudne - zasadniczo wymaga czegoś takiego:
Jeśli weźmie się pod uwagę, że wiele rzeczywistych kodów wykorzystuje bardziej zaangażowane pętle, oczywiste będzie, że optymalizacja kodu przy jednoczesnym zachowaniu semantyki przepełnienia jest trudna. Ponadto, ze względu na problemy z buforowaniem, jest całkiem możliwe, że zwiększenie rozmiaru kodu spowoduje, że cały program będzie działał wolniej, mimo że na często wykonywanej ścieżce jest mniej operacji.
Aby wykrycie przepełnienia było niedrogie, potrzebny byłby zdefiniowany zestaw luźniejszej semantyki wykrywania przepełnienia, który ułatwiłby kodowi raportowanie, czy obliczenia zostały wykonane bez przelewów, które mogłyby wpłynąć na wyniki (*), ale bez obciążenia kompilator ze szczegółami poza tym. Gdyby specyfikacja językowa koncentrowała się na obniżeniu kosztów wykrywania przepełnienia do absolutnego minimum niezbędnego do osiągnięcia powyższego, można by to uczynić znacznie mniej kosztownym niż w istniejących językach. Nie jestem jednak świadomy żadnych wysiłków mających na celu ułatwienie skutecznego wykrywania przepełnienia.
(*) Jeśli język obiecuje, że wszystkie przepełnienia zostaną zgłoszone, wyrażenie takie
x*y/y
nie może być uproszczone,x
chyba żex*y
można zagwarantować, że się nie przepełni. Podobnie, nawet jeśli wynik obliczeń zostanie zignorowany, język, który obiecuje zgłosić wszystkie przepełnienia, i tak będzie musiał go wykonać, aby mógł wykonać kontrolę przepełnienia. Ponieważ przepełnienie w takich przypadkach nie może spowodować nieprawidłowego działania arytmetycznego, program nie musiałby przeprowadzać takich kontroli, aby zagwarantować, że żadne przepełnienie nie spowodowało potencjalnie niedokładnych wyników.Nawiasem mówiąc, przelewy w C są szczególnie złe. Chociaż prawie każda platforma sprzętowa, która obsługuje C99, wykorzystuje semantykę komplementu dwóch cichych elementów, modne jest, aby nowoczesne kompilatory generowały kod, który może powodować dowolne skutki uboczne w przypadku przepełnienia. Na przykład biorąc pod uwagę coś takiego:
GCC wygeneruje kod dla testu2, który bezwarunkowo zwiększa (* p) jeden raz i zwraca 32768 niezależnie od wartości przekazanej do q. Zgodnie z rozumowaniem obliczenia (32769 * 65535) i 65535u spowodowałyby przepełnienie, a zatem kompilator nie musi brać pod uwagę przypadków, w których (q | 32768) dałoby wartość większą niż 32768. Nawet jeśli nie ma powód, dla którego obliczenia (32769 * 65535) i 65535u powinny obchodzić górne bity wyniku, gcc użyje przepełnienia ze znakiem jako uzasadnienia dla ignorowania pętli.
źródło
-fwrapv
powoduje określone zachowanie, choć nie zachowanie, którego chce pytający. To prawda, że optymalizacja gcc przekształca każdy rozwój języka C w dokładną analizę standardu i zachowania kompilatora.x+y > z
w sposób, który nigdy nie zrobi nic innego niż wydajność 0 lub wydajność 1, ale którykolwiek wynik byłby równie akceptowalny w przypadku przepełnienia, kompilator oferujący tę gwarancję często może generować lepszy kod dla wyrażeniex+y > z
niż jakikolwiek kompilator byłby w stanie wygenerować dla defensywnie napisanej wersji wyrażenia. Mówiąc realistycznie, jaki ułamek użytecznych optymalizacji związanych z przepełnieniem byłby wykluczony przez gwarancję, że obliczenia liczb całkowitych inne niż podział / pozostała część będą wykonywane bez skutków ubocznych?-fwhatever-makes-sense
łatki”, zdecydowanie sugeruje mi, że jest więcej do tego niż kapryśny z ich strony. Zwykle argumenty, które słyszałem, to to, że wstawianie kodu (a nawet rozwijanie makr) przynosi korzyść z wnioskowania w jak największym stopniu o konkretnym zastosowaniu konstrukcji kodu, ponieważ każda rzecz zwykle powoduje wstawienie kodu, który zajmuje się przypadkami, których nie potrzebuje aby otaczający kod „okazał się” niemożliwy.foo(i + INT_MAX + 1)
, autorzy kompilatorów chętnie stosują optymalizacje do wstawionegofoo()
kodu, który polega na poprawności, ponieważ jego argument nie jest ujemny (być może diabelskie sztuczki divmod). Pod Twoimi dodatkowymi ograniczeniami mogą stosować tylko optymalizacje, których zachowanie w przypadku negatywnych danych wejściowych ma sens dla platformy. Oczywiście osobiście byłbym szczęśliwy, gdyby była to-f
opcja, która włącza się-fwrapv
itp. I prawdopodobnie musi wyłączyć niektóre optymalizacje, dla których nie ma flagi. Ale to nie tak, że sam nie mogę sobie pozwolić na to, by robić to wszystko.Nie wszystkie języki programowania ignorują przepełnienia liczb całkowitych. Niektóre języki zapewniają bezpieczne operacje na liczbach całkowitych dla wszystkich liczb (większość dialektów Lisp, Ruby, Smalltalk, ...) i inne za pośrednictwem bibliotek - na przykład istnieją różne klasy BigInt dla C ++.
To, czy język domyślnie zabezpieczy liczbę całkowitą przed przepełnieniem, czy nie, zależy od jego celu: języki systemowe, takie jak C i C ++, muszą zapewniać abstrakty o zerowym koszcie, a „duża liczba całkowita” nie jest jednym. Języki produktywności, takie jak Ruby, mogą i dostarczają duże liczby całkowite po wyjęciu z pudełka. Języki, takie jak Java i C #, które są gdzieś pomiędzy, powinny IMHO iść z bezpiecznymi liczbami całkowitymi od razu po wyjęciu z pudełka.
źródło
Jak pokazałeś, C # byłby 3 razy wolniejszy, gdyby miał domyślnie włączone kontrole przepełnienia (zakładając, że twój przykład jest typową aplikacją dla tego języka). Zgadzam się, że wydajność nie zawsze jest najważniejszą funkcją, ale języki / kompilatory są zazwyczaj porównywane pod względem wydajności w typowych zadaniach. Wynika to częściowo z faktu, że jakość cech językowych jest nieco subiektywna, podczas gdy test wydajności jest obiektywny.
Jeśli miałbyś wprowadzić nowy język, który pod wieloma względami jest podobny do C #, ale 3 razy wolniejszy, uzyskanie udziału w rynku nie byłoby łatwe, nawet jeśli ostatecznie większość użytkowników końcowych skorzystałaby z kontroli przepełnienia bardziej niż z wyższej wydajności.
źródło
Oprócz wielu odpowiedzi uzasadniających brak sprawdzania przepełnienia w oparciu o wydajność, istnieją dwa różne rodzaje arytmetyki:
obliczenia indeksujące (indeksowanie tablic i / lub arytmetyka wskaźników)
inna arytmetyka
Jeśli język używa rozmiaru liczby całkowitej, który jest taki sam jak rozmiar wskaźnika, wówczas dobrze skonstruowany program nie przepełni się podczas wykonywania obliczeń indeksowania, ponieważ musi koniecznie zabraknąć pamięci, zanim obliczenia indeksowania spowodują przepełnienie.
Dlatego sprawdzanie przydziałów pamięci jest wystarczające podczas pracy z arytmetyką wskaźników i wyrażeniami indeksującymi obejmującymi przydzielone struktury danych. Na przykład, jeśli masz 32-bitową przestrzeń adresową i używasz 32-bitowych liczb całkowitych i zezwalasz na przydzielenie maksymalnie 2 GB sterty (około połowy przestrzeni adresowej), obliczenia indeksowania / wskaźnika (w zasadzie) nie zostaną przepełnione.
Co więcej, możesz być zaskoczony, jak wiele dodawania / odejmowania / mnożenia wymaga indeksowania tablic lub obliczania wskaźnika, a zatem należy do pierwszej kategorii. Wskaźnik obiektu, dostęp do pola i manipulacje tablicami są operacjami indeksowania, a wiele programów nie wykonuje więcej obliczeń arytmetycznych niż te! Zasadniczo jest to główny powód, dla którego programy działają tak samo, jak działają bez sprawdzania przepełnienia liczb całkowitych.
Wszystkie obliczenia nieindeksowane i niepointerowe należy klasyfikować jako te, które chcą / oczekują przepełnienia (np. Obliczenia mieszające), oraz te, które tego nie robią (np. Przykład sumowania).
W tym drugim przypadku programiści często używają alternatywnych typów danych, takich jak
double
niektóreBigInt
. Wiele obliczeń wymagadecimal
raczej rodzaju danych niżdouble
np. Obliczeń finansowych. Jeśli nie i trzymają się liczb całkowitych, muszą sprawdzić, czy nie występuje przepełnienie liczb całkowitych - w przeciwnym razie program może osiągnąć niewykryty błąd, jak wskazujesz.Jako programiści musimy być wyczuleni na nasze wybory liczbowych typów danych i ich konsekwencje pod względem możliwości przepełnienia, nie mówiąc już o precyzji. Ogólnie (a zwłaszcza podczas pracy z rodziną języków C z chęcią korzystania z szybkich typów całkowitych) musimy być wrażliwi na różnice między obliczeniami indeksowania a innymi.
źródło
Język Rust zapewnia interesujący kompromis między sprawdzaniem przepełnienia, a nie przez dodanie kontroli debugowania kompilacji i usunięcie ich w zoptymalizowanej wersji. Pozwala to znaleźć błędy podczas testowania, a jednocześnie uzyskać pełną wydajność w ostatecznej wersji.
Ponieważ czasem wymagane jest zachowanie obejścia przepełnienia, istnieją również wersje operatorów, które nigdy nie sprawdzają przepełnienia.
Możesz przeczytać więcej o uzasadnieniu wyboru w RFC zmiany. W tym wpisie na blogu znajduje się również wiele interesujących informacji, w tym lista błędów, które ta funkcja pomogła w wyłapywaniu.
źródło
checked_mul
, które sprawdzają, czy nastąpiło przepełnienie i zwraca,None
jeśli tak, wSome
przeciwnym razie. Można to wykorzystać zarówno w trybie produkcyjnym, jak i debugowania: doc.rust-lang.org/std/primitive.i32.html#examples-15W Swift wszelkie przepełnienia liczb całkowitych są wykrywane domyślnie i natychmiast zatrzymują program. W przypadkach, w których potrzebujesz zachowania pełnego, istnieją różni operatorzy i +, oraz - i & *, które to osiągają. Istnieją funkcje, które wykonują operację i informują, czy nastąpiło przepełnienie, czy nie.
Fajnie jest obserwować, jak początkujący próbują ocenić sekwencję Collatza i ich awaria kodu :-)
Teraz projektanci Swift są również projektantami LLVM i Clang, więc wiedzą trochę o optymalizacji i są w stanie uniknąć niepotrzebnych kontroli przepełnienia. Po włączeniu wszystkich optymalizacji kontrola przepełnienia nie wpływa znacząco na rozmiar kodu i czas wykonywania. A ponieważ większość przepełnień prowadzi do absolutnie niepoprawnych wyników, rozmiar kodu i czas wykonania są dobrze wykorzystane.
PS. W C, C ++ przepełnienie arytmetyczne liczb całkowitych ze znakiem Objective-C jest zachowaniem niezdefiniowanym. Oznacza to, że wszystko, co kompilator robi w przypadku przepełnienia liczby całkowitej ze znakiem, jest z definicji prawidłowe. Typowe sposoby radzenia sobie z przepełnieniem liczb całkowitych ze znakiem to zignorowanie go, przyjmowanie dowolnego wyniku, jaki daje procesor, budowanie w kompilatorze założeń, że takie przepełnienie nigdy się nie zdarzy (i stwierdź na przykład, że n + 1> n jest zawsze prawdziwe, ponieważ przepełnienie jest zakłada się, że nigdy się nie zdarzy), a rzadko spotykaną możliwością jest sprawdzanie i zawieszanie się w przypadku przepełnienia, podobnie jak Swift.
źródło
x+1>x
jako bezwarunkowo prawdziwe nie wymagałoby od kompilatora dokonywania jakichkolwiek „założeń” dotyczących x, jeśli kompilator może oceniać wyrażenia liczb całkowitych przy użyciu dowolnych większych typów jako wygodnych (lub zachowywać się tak, jakby to robił). Paskudniejszym przykładem „założeń” opartych na przepełnieniu byłoby stwierdzenie, że biorącuint32_t mul(uint16_t x, uint16_t y) { return x*y & 65535u; }
pod uwagę kompilator, możnasum += mul(65535, x)
zdecydować, żex
nie może być ono większe niż 32768 [zachowanie, które prawdopodobnie zszokuje ludzi, którzy napisali uzasadnienie C89, co sugeruje, że jest to jeden z decydujących czynników. ..unsigned short
promowaniusigned int
był fakt, że dwie komplementarne implementacje cichego owijania (tj. większość implementacji C wówczas używanych) potraktowałyby kod jak wyżej w ten sam sposób, niezależnie od tego, czy jestunsigned short
promowany doint
czyunsigned
. Standard nie wymagał implementacji na sprzęcie z cichym dopełnianiem dwóch, aby traktować kod jak wyżej, ale autorzy Standardu prawdopodobnie spodziewali się, że i tak to zrobią.W rzeczywistości prawdziwa przyczyna jest czysto techniczna / historyczna: znak ignorowania procesora w przeważającej części. Zasadniczo istnieje tylko jedna instrukcja dodawania dwóch liczb całkowitych do rejestrów, a procesor nie dba o to, czy interpretujesz te dwie liczby całkowite jako podpisane czy niepodpisane. To samo dotyczy odejmowania, a nawet mnożenia. Jedyną operacją arytmetyczną, która wymaga rozpoznawania znaków, jest podział.
Powodem, dla którego to działa, jest uzupełnienie 2 liczb całkowitych ze znakiem, które jest używane przez praktycznie wszystkie procesory. Na przykład w 4-bitowych uzupełnieniach 2 dodanie 5 i -3 wygląda następująco:
Zauważ, jak zachowanie zawijania podczas wyrzucania bitu wykonania daje poprawnie podpisany wynik. Podobnie procesory zwykle implementują odejmowanie
x - y
jakox + ~y + 1
:To implementuje odejmowanie jako dodatek w sprzęcie, modyfikując tylko dane wejściowe do jednostki arytmetyczno-logicznej (ALU) w trywialny sposób. Co może być prostsze?
Ponieważ mnożenie jest niczym innym jak sekwencją dodatków, zachowuje się w podobny sposób. Rezultatem użycia reprezentacji uzupełnienia 2 i zignorowania przeprowadzania operacji arytmetycznych jest uproszczony zespół obwodów i uproszczone zestawy instrukcji.
Oczywiście, ponieważ C został zaprojektowany do pracy blisko metalu, przyjął to dokładnie to samo zachowanie, co znormalizowane zachowanie nieoznaczonej arytmetyki, pozwalając tylko arytmetyki podpisanej na zachowanie niezdefiniowane. I ten wybór został przeniesiony na inne języki, takie jak Java i oczywiście C #.
źródło
x==INT_MAX
, tox+1
może dowolnie zachowywać się jak +2147483648 lub -2147483648 w kompilatorze wygoda), ale ...x
iy
są,uint16_t
a kod w systemie 32-bitowym oblicza,x*y & 65535u
gdyy
jest 65535, kompilator powinien założyć, że kod nigdy nie zostanie osiągnięty, gdyx
jest większy niż 32768.Niektóre odpowiedzi omawiały koszty sprawdzania, a ty zredagowałeś swoją odpowiedź, aby zakwestionować, że jest to uzasadnione uzasadnienie. Spróbuję zająć się tymi punktami.
W C i C ++ (jako przykłady) jedną z zasad projektowania języków nie jest zapewnienie funkcjonalności, o którą nie poproszono. Jest to często podsumowane zwrotem „nie płać za to, czego nie używasz”. Jeśli programista chce sprawdzić przepełnienie, może o to poprosić (i zapłacić karę). To sprawia, że używanie języka jest bardziej niebezpieczne, ale decydujesz się na pracę z tym językiem, wiedząc o tym, więc akceptujesz ryzyko. Jeśli nie chcesz tego ryzyka lub piszesz kod, w którym bezpieczeństwo jest najważniejsze, możesz wybrać bardziej odpowiedni język, w którym wydajność / ryzyko jest inna.
W tym rozumowaniu jest kilka rzeczy błędnych:
Jest to specyficzne dla środowiska. Zazwyczaj nie ma sensu cytowanie takich liczb, ponieważ kod jest napisany dla wszystkich rodzajów środowisk, które różnią się pod względem wydajności pod względem rzędów wielkości. Twoja 1 nanosekunda na (przypuszczam) komputerze stacjonarnym może wydawać się zadziwiająco szybka dla kogoś, kto koduje środowisko osadzone, i nieznośnie powolna dla kogoś, kto koduje super klaster komputerowy.
1 nanosekunda może wydawać się niczym dla fragmentu kodu, który działa rzadko. Z drugiej strony, jeśli jest to wewnętrzna funkcja jakiegoś obliczenia, która jest główną funkcją kodu, to każdy ułamek czasu, który można się ogolić, może mieć duże znaczenie. Jeśli prowadzisz symulację w klastrze, te zaoszczędzone ułamki nanosekundy w wewnętrznej pętli mogą przełożyć się bezpośrednio na pieniądze wydane na sprzęt i energię elektryczną.
W przypadku niektórych algorytmów i kontekstów 10 000 000 000 iteracji może być nieznaczne. Ponownie, ogólnie nie ma sensu mówić o konkretnych scenariuszach, które mają zastosowanie tylko w określonych kontekstach.
Być może masz rację. Ale znowu chodzi o to, jakie są cele danego języka. Wiele języków zostało zaprojektowanych tak, aby zaspokoić potrzeby „większości” lub zapewnić bezpieczeństwo w stosunku do innych problemów. Inne, takie jak C i C ++, stawiają na wydajność. W tym kontekście zmuszanie wszystkich do płacenia kary za wydajność po prostu dlatego, że większość ludzi nie będzie się tym przejmować, jest sprzeczne z tym, co ten język stara się osiągnąć.
źródło
Są dobre odpowiedzi, ale myślę, że tutaj brakuje jednego punktu: skutki przepełnienia liczb całkowitych niekoniecznie są złe, a po tym trudno jest ustalić, czy
i
przejście od byciaMAX_INT
do byciaMIN_INT
było spowodowane problemem z przepełnieniem lub jeśli zostało to celowo zrobione przez pomnożenie przez -1.Na przykład, jeśli chcę dodać wszystkie reprezentowalne liczby całkowite większe niż 0, po prostu
for(i=0;i>=0;++i){...}
użyję pętli dodawania - a gdy się przepełni, zatrzymuje dodawanie, co jest zachowaniem celu (rzucanie błędu oznaczałoby, że musiałbym obejść dowolna ochrona, ponieważ zakłóca ona standardową arytmetykę). Ograniczanie prymitywnej arytmetyki jest złą praktyką, ponieważ:źródło
INT_MAX
doINT_MIN
, mnożąc przez -1.for(i=0;i>=0;++i){...}
to styl kodu, który staram się zniechęcić w moim zespole: opiera się on na efektach specjalnych / skutkach ubocznych i nie wyraża jasno, co ma robić. Ale nadal doceniam twoją odpowiedź, ponieważ pokazuje inny paradygmat programowania.i
jest to wersja 64-bitowa, nawet w przypadku implementacji o spójnym działaniu komplementarnym dla dwóch uzupełnień, uruchamiającej miliard iteracji na sekundę, można by zagwarantować, że taka pętla znajdzie największąint
wartość, jeśli będzie mogła działać setki lat. W systemach, które nie obiecują spójnego zachowania cichego, takie zachowania nie byłyby gwarantowane bez względu na długość kodu.