Overflow – jak to ugryźć
Zastanawiam się nad jakimś sprytnym sposobem osadzania twittów w czasie generowani statycznego HTMLa za pomocą jekylla, ale dziś nie o tym.
Pomyślcie nad takim problematem. Mamy duży plik z jakimiś danymi pomiarowymi. Duży w sensie GB dążące do TB. Format jest mniej istotny, ale możemy
roboczo przyjąć, że wygląda on mniej więcej tak id-czujnika;data w ISO;wartości. Nic nadzwyczajnego. Teraz trzeba zrobić statystykę z tego pliku.
Policzyć średnie, odchylenia, duperele… niby nic trudnego. Wrzucamy plik do pamięci i… czy ja wspomniałem o GB dążących do TB? Na całe szczęście w
Javie mamy klasę Files, która ma kilka fajnych metod m.in. lines(Path), która zwraca strumień linii. Eleganckie i niezbyt pamięciożerne narzędzie,
które leci po kolei linia po linii. Załóżmy, że potrafimy wczytaną linię przekształcić do rekordu reprezentującego dane. Jak? To też nie jest istotne.
Podpowiem tylko, że jak chcesz mieć coś, co szybko działa i nie żre pamięci, to zapomnij o String.split. Jeszcze wrócimy do tego tematu, jak tylko
wrócę z wakacji. Dziś inny temat.
Jak mamy bardzo dużo danych, nawet po wstępnym przefiltrowaniu, to chcąc policzyć średnią, mogę naciąć się na pewien mały problem…
Ten paskudny Overflow
W dużym uproszczeniu każda liczba całkowita (Integer i int) w Javie jest zapisywana na czterech bajtach. Daje to 232(4294967296)
wartości. W tym zakresie musimy upchnąć liczby dodatnie i ujemne oraz zero. Żeby opisać czy liczba jest dodatnia, czy ujemna, musimy zabrać jeden bit.
Mamy zatem do dyspozycji 231-1 dla liczb dodatnich (bo 0 będzie dodatnie) i 231 dla liczb ujemnych (bo nie ma ujemnego 0). Dla
typu long będzie to odpowiednio więcej, ale zasada jest zachowana.
Co to oznacza dla nas?
Jeżeli chcemy dodać dwie liczby całkowite, to może okazać się, że ich suma będzie większa niż maksymalna wartość dla typu. Komputer nie jest jednak zbyt bystry i wykona taką operację.
Listing 1. Dodawanie dwóch liczb 4-bitowych ze znakiem
0011 » 3
+0101 » 5
---------
1000 » -8
Zgadza się, ale tak nie do końca. Niby 8, ale z minusem :D Inaczej mówiąc, jesteśmy w dupie. Podobny problem powstanie, jeżeli będziemy odejmować od liczby w okolicach wartości minimalnej. W takim przypadku mówimy o Underflow (niedomiarze). Jeszcze jeden przykład, tym razem w Javie:
Listing 2. Overflow w Javie
class OverflowGuard {
public static void main(String[] args) {
simple();
}
public static void simple() {
int stored = Integer.MAX_VALUE - 100;
int toAdd = 25;
for (int i = 0; i < 10; i++) {
stored += toAdd;
System.out.println("stored = " + stored);
}
}
}
/*
stored = 2147483572
stored = 2147483597
stored = 2147483622
stored = 2147483647
stored = -2147483624
stored = -2147483599
stored = -2147483574
stored = -2147483549
stored = -2147483524
stored = -2147483499
*/
Jak z tym „walczyć”?
Na początek musisz sobie odpowiedzieć na dwa bardzo ważne pytania.
- Po co chcesz rozwiązać ten problem?
- Jakimi środkami dysponujesz (CPU, RAM, czas wykonania)?
Użyj BigInteger
Jeżeli masz dużo RAM-u dużo CPU i nie boli cię ilość pracy, jaką ma wykonać GC, to jest to niezłe rozwiązanie. Maksymalną wartością jest tutaj 2 2147483647, czyli liczba posiadająca 646 456 994 cyfr. To dużo… Poszukajmy jednak innych rozwiązań.
Użyj Math.addExact
Jeżeli masz dużo czasu i w przypadku problemów z przepełnieniem możesz je obsłużyć „biznesowo” (co kolwiek to znaczy) :D Serio. To rozwiązanie będzie rzucać wyjątkami.
Listing 3. Użycie Math.addExact
class OverflowGuard {
public static void main(String[] args) {
simple();
detectionInApi();
}
//…
public static void detectionInApi() {
int stored = Integer.MAX_VALUE - 100;
int toAdd = 25;
for (int i = 0; i < 10; i++) {
try {
stored = Math.addExact(stored, toAdd);
System.out.println("stored = " + stored);
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
System.out.println("APi detection end");
}
}
/*
stored = 2147483572
stored = 2147483597
stored = 2147483622
stored = 2147483647
integer overflow
integer overflow
integer overflow
integer overflow
integer overflow
integer overflow
*/
Powyższe rozwiązania są „podręcznikowe”. Jeżeli chcecie poczytać, jak jeszcze można ugryźć ten problem, to zerknijcie na As-If Infinitely Ranged Integer Model. Ja jednak pokażę wam pewną „designerską sztuczkę”, która oczywiście jest tylko PoCem i nie powinna trafić na produkcję w takim stanie (a i tak pewno trafi).
Jak obsłużyć przepełnienie?
Istnieje kilka poziomów takiej obsługi. Na najniższym możemy ostrzegać użytkownika, że działa w „niebezpiecznej strefie”. Na kolejnym etapie możemy zablokować działanie, ale zamiast błędu uruchomić „kod zapasowy”. W końcu możemy opakować działanie w swoisty „protektor”, który będzie nie tylko wykrywać problem, ale w razie jego wystąpienia postara się zmienić typ wyniku na taki, który pomieści ten wynik.
Detekcja
Przyjmijmy, że istnieje pewna „bezpieczna” granica, po której osiągnięciu chcemy poinformować użytkownika, że jego działanie może być niebezpieczne.
Listing 4. Detekcja zagrożenia
class OverflowGuard {
public static void main(String[] args) {
simple();
detectionInApi();
detection(() -> System.out.println("Danger zone"));
}
//…
public static void detection(Runnable dangerZoneReaction) {
int stored = Integer.MAX_VALUE - 100;
int toAdd = 25;
int epsilon = 50;
for (int i = 0; i < 10; i++) {
if (Integer.MAX_VALUE - epsilon < stored) {
dangerZoneReaction.run();
}
stored += toAdd;
System.out.println("stored = " + stored);
}
}
}
/*
stored = 2147483572
stored = 2147483597
stored = 2147483622
Danger zone
stored = 2147483647
Danger zone
stored = -2147483624
stored = -2147483599
stored = -2147483574
stored = -2147483549
stored = -2147483524
stored = -2147483499
*/
Trochę to naciągane rozwiązanie, bo jednak dodajemy w pętli i działania użytkownika nie mają na nas wpływu, ale mam nadzieję, że rozumiecie koncepcję. Wysyłamy użytkownikowi sygnał, że operuje on w niebezpiecznej strefie. Jeżeli nie podejmie działań, to przekręcamy licznik jak w passeratti.
Detekcja możliwego przepełnienia i jego obsługa
Zastosujmy trochę inne podejście. Użytkownik będzie miał informację, że operuje w niebezpiecznej strefie, a jak kolejna operacja spowodowałaby przepełnienie, to wykonamy jakiś kod zapasowy.
Listing 5. Detekcja i obsługa po stronie użytkownika
class OverflowGuard {
public static void main(String[] args) throws Exception {
simple();
detectionInApi();
detection(() -> System.out.println("Danger zone"));
protection(() -> System.out.println("Danger zone"), () -> {
System.out.println("pull up!");
return null;
});
}
//…
public static void protection(Runnable dangerZoneReaction, Callable<Void> overflowReaction) throws Exception {
int stored = Integer.MAX_VALUE - 100;
int toAdd = 25;
int epsilon = 50;
for (int i = 0; i < 10; i++) {
if (Integer.MAX_VALUE - epsilon < stored) {
dangerZoneReaction.run();
}
if (Integer.MAX_VALUE - stored < toAdd) {
overflowReaction.call();
} else {
stored += toAdd;
}
System.out.println("stored = " + stored);
}
}
}
/*
stored = 2147483572
stored = 2147483597
stored = 2147483622
Danger zone
stored = 2147483647
Danger zone
pull up!
stored = 2147483647
Danger zone
pull up!
stored = 2147483647
Danger zone
pull up!
stored = 2147483647
Danger zone
pull up!
stored = 2147483647
Danger zone
pull up!
stored = 2147483647
Danger zone
pull up!
stored = 2147483647
*/
Nie wygląda to głupio. Zamiast Callable można spróbować użyć funkcji, która przyjmie obecny stan i zwróci nowy stan. Spróbujmy jednak czegoś
zupełnie innego. Zamknijmy naszą wartość w swoistym „protektorze”, który będzie zmieniał swój stan, a jeżeli operacja będzie zagrażać przepełnieniem,
to utworzy swojego „następcę”, który będzie w stanie obsłużyć większy zakres.
Protektor
Tutaj implementacja ma dwa etapy. Pierwszy to wspólny korzeń i jednocześnie fabryka, dla poszczególnych klas:
Listing 6. Abstrakcyjny OverflowGuardedStorage
sealed abstract class OverflowGuardedStorage {
public static OverflowGuardedStorage getInstance() {
return new IntOverflowGuardedStorage(0);
}
public static OverflowGuardedStorage getLongInstance() {
return new LongOverflowGuardedStorage(0L);
}
public static OverflowGuardedStorage getBigIntInstance() {
return new BigIntegerOverflowGuardedStorage(BigInteger.ZERO);
}
public static OverflowGuardedStorage getInstance(int i) {
return new IntOverflowGuardedStorage(i);
}
public static OverflowGuardedStorage getLongInstance(long l) {
return new LongOverflowGuardedStorage(l);
}
public static OverflowGuardedStorage getBigIntInstance(BigInteger bigInteger) {
return new BigIntegerOverflowGuardedStorage(bigInteger);
}
public abstract OverflowGuardedStorage add(int i);
public abstract Value<?> get();
public record Value<T>(T value, Class<T> type) {
}
}
Problemem może być metoda add, bo obsługuje jedynie int. Ale to jest zagadka dla was jak to zrobić, żeby było zrobione :D Teraz na
przykładzie IntOverflowGuardedStorage zobaczmy, jak działa implementacja.
Listing 7. Implementacja IntOverflowGuardedStorage
final class IntOverflowGuardedStorage extends OverflowGuardedStorage {
private int value;
public IntOverflowGuardedStorage(int i) {
this.value = i;
}
@Override
public OverflowGuardedStorage add(int i) {
if (Integer.MAX_VALUE - value < i) {
return new LongOverflowGuardedStorage(value).add(i);
}
value += i;
return this;
}
@Override
public Value<Integer> get() {
return new Value<Integer>(value, Integer.class);
}
}
Tu jest pewna mała magia. Jeżeli różnica pomiędzy maksymalną wartością int, a obecną wartością jest mniejsza niż to, co chcemy dodać, to
„awansujemy” na większy typ. Użytkownik wykorzystuje typ abstrakcyjny, a nie konkretny, więc dla niego zmiana jest przezroczysta. Jeżeli pobierze
wartość, to otrzyma też informację, jakiego typu musi użyć, żeby wszystko zadziałało.
Listing 8. Użycie naszego rozwiazania
class OverflowGuard {
public static void main(String[] args) throws Exception {
simple();
detectionInApi();
detection(() -> System.out.println("Danger zone"));
protection(() -> System.out.println("Danger zone"), () -> {
System.out.println("pull up!");
return null;
});
storage();
}
//…
public static void storage() {
OverflowGuardedStorage stored = OverflowGuardedStorage.getInstance(Integer.MAX_VALUE - 100);
int toAdd = 25;
for (int i = 0; i < 10; i++) {
stored = stored.add(toAdd);
System.out.println("stored = " + stored.get());
}
}
}
/*
stored = Value[value=2147483572, type=class java.lang.Integer]
stored = Value[value=2147483597, type=class java.lang.Integer]
stored = Value[value=2147483622, type=class java.lang.Integer]
stored = Value[value=2147483647, type=class java.lang.Integer]
stored = Value[value=2147483672, type=class java.lang.Long]
stored = Value[value=2147483697, type=class java.lang.Long]
stored = Value[value=2147483722, type=class java.lang.Long]
stored = Value[value=2147483747, type=class java.lang.Long]
stored = Value[value=2147483772, type=class java.lang.Long]
stored = Value[value=2147483797, type=class java.lang.Long]
*/
Jak widać działa. Oczywiście podobny zestaw sprawdzeń trzeba wykonać dla liczb ujemnych oraz innych operacji, ale to już szczegół.