Odpowiedź na pytanie

Historia pytania

Przed C++20, obliczanie średniej arytmetycznej dwóch liczb całkowitych lub wskaźników wymagało ręcznej implementacji, zazwyczaj poprzez naiwne wyrażenie (a + b) / 2. Takie podejście wywołuje jednak niezdefiniowane zachowanie, gdy suma przekracza maksymalną wartość, którą można reprezentować w danym typie. std::midpoint została ustandaryzowana w C++20 w nagłówku <numeric>, aby zapewnić przenośne, constexpr i noexcept rozwiązanie, które gwarantuje poprawne wyniki w całym zakresie typów całkowitych i wskaźników bez wywoływania przepełnienia liczb całkowitych ze znakiem.

Problem

Przepełnienie liczb całkowitych ze znakiem jest niezdefiniowanym zachowaniem w C++, nawet w świetle mandatu o uzupełnieniu do dwóch z wersji C++20. Gdy uśrednia się dwie duże dodatnie liczby całkowite (np. blisko INT_MAX), ich suma wywołuje przepełnienie. Podobnie, w przypadku dwóch dużych liczb całkowitych ujemnych, suma może być poniżej zera. Chociaż arytmetyka wskaźników również ma niezdefiniowane zachowanie w przypadku przepełnienia, różnica między dwoma wskaźnikami do tej samej tablicy jest gwarantowana, aby mieściła się w std::ptrdiff_t, eliminując ryzyko przepełnienia związane z dodawaniem całkowitym. Wyzwanie polega na wdrożeniu algorytmu średniej dla liczb całkowitych, który unika przepełnienia inherentnego w dodawaniu, zachowując poprawność dla danych wejściowych z różnymi znakami.

Rozwiązanie

Dla liczb całkowitych ze znakiem, std::midpoint unika przepełnienia, przekształcając operandy na ich odpowiedniki bez znaku przed odejmowaniem. Oblicza średnią jako a - (unsigned_type(a) - b) / 2, gdy a > b, lub odpowiednio symetrycznie w przeciwnym przypadku. Wykorzystuje dobrze zdefiniowaną arytmetykę modulo typów bez znaku do obliczenia połowy odległości między liczbami, bez tworzenia pośredniej wartości, której wielkość przekraczałaby dane wejściowe. Dla wskaźników implementacja po prostu wykorzystuje first + (last - first) / 2, ponieważ różnica (last - first) jest dobrze zdefiniowana i reprezentowalna, a jej połowienie zapewnia, że kolejne dodawanie mieści się w ważnym zakresie tablicy.

#include <numeric>
#include <limits>
#include <iostream>

int main() {
    int a = std::numeric_limits<int>::max() - 10;
    int b = std::numeric_limits<int>::max() - 2;
    
    // int naive = (a + b) / 2; // Niezdefiniowane zachowanie: przepełnienie
    int safe = std::midpoint(a, b); // Dobrze zdefiniowane: zwraca max - 6
    
    int arr[] = {1, 2, 3, 4, 5};
    int* mid = std::midpoint(&arr[0], &arr[4]); // Wskazuje na arr[2]
}

Sytuacja z życia wzięta

Opis problemu

Na platformie handlu o wysokiej częstotliwości system potrzebował obliczyć temporalny punkt średni między dwoma znacznikami czasowymi zamówień reprezentowanymi jako std::int64_t nanosekund od epochy Unix. Podczas testów obciążeniowych w pobliżu otwarcia rynku, gdy znaczniki czasowe były bliskie INT64_MAX, klasyczne obliczenie (t1 + t2) / 2 spowodowało sporadyczne awarie z powodu przepełnienia liczb całkowitych ze znakiem, co uszkodziło logikę kolejki priorytetowej zarządzającej realizacją zamówień.

Rozważane różne rozwiązania

Rozwiązanie 1: Użycie wbudowanych typów o rozszerzonej precyzji Zespół rozważał rzutowanie na __int128_t dla obliczenia pośredniego, a następnie rzutowanie z powrotem. To podejście zapewniało poprawną arytmetykę w obsługiwanych kompilatorach (GCC, Clang, MSVC). Jednak brakowało mu przenośności do zintegrowanych celów z rygorystyczną zgodnością z C++17 i wprowadzało subtelne regresje wydajności na architekturach 32-bitowych, gdzie emulacja 128-bitowa jest kosztowna.

Rozwiązanie 2: Rzutowanie na arytmetykę bez znaku Zapewnienie, aby oba znaczniki czasowe były przekształcone na std::uint64_t, wykonanie średniej, a następnie przekształcenie z powrotem, zostało zaproponowane. Choć unika to przepełnienia dla wartości dodatnich, daje wyniki zdefiniowane przez implementację, gdy zajmują się historycznymi znacznikami czasowymi (wartości ujemne w reprezentacji ze znakiem) ponieważ przekształcenie bez znaku wartości ujemnych daje duże dodatnie wartości (opad o 2), co skutkuje matematycznie niepoprawną średnią dla obliczeń przechodzących przez zero.

Rozwiązanie 3: Ręczne gałęziowanie z kontrolami przepełnienia Zaimplementowanie funkcji niestandardowej sprawdzającej znaki operandów i warunkowo wykorzystującej a + (b - a)/2 lub manipulację bitową zostało rozważone. To zapewniało poprawność, ale dodawało narzut związany z gałęziowaniem i złożonością. Utrzymując tę logikę w wielu dziedzinach numerycznych (współrzędne, ceny, znaczniki czasowe), naruszano zasadę DRY i wprowadzano ryzyko błędów konserwacyjnych.

Rozwiązanie 4: Przyjęcie C++20 std::midpoint Uaktualnienie narzędzi do C++20 i wykorzystanie std::midpoint zapewniło zerowy narzut złożoności, który poprawnie obsługiwał wszystkie przypadki brzegowe, w tym dane wejściowe z różnymi znakami oraz wartości bliskie granic typu całkowitego.

Wybrane rozwiązanie i wynik

Zespół wybrał Rozwiązanie 4, migrując warstwę obliczeniową do C++20. Zmiana wyeliminowała awarie związane z przepełnieniem w produkcji, zmniejszyła kod o 200 linii niestandardowych narzędzi matematycznych, oraz poprawiła lokalność pamięci podręcznej, eliminując logikę gałęziową. Testy regresyjne potwierdziły identyczną wydajność z naiwna podejścia na x86-64, z dodatkową korzyścią oceniania constexpr dla stałych czasu kompilacji.

Co często umyka kandydatom

Pytanie 1: Dlaczego rzutowanie liczb całkowitych ze znakiem na typy bez znaku jest niewystarczające dla ogólnej obliczeń punktów średnich?

Odpowiedź Chociaż arytmetyka bez znaku opiera się na modularności 2^N i unika przepełnienia, przekształcenie ujemnej liczby całkowitej ze znakiem na bez znakową daje dużą dodatnią wartość (np. -1 staje się UINT_MAX). Uśredniając znacznik czasowy ujemny i dodatni za pomocą arytmetyki bez znaku, otrzymuje się wynik bliski środka zakresu bez znaku, a nie poprawnej ujemnej średniej. std::midpoint zachowuje znak i poprawnie zaokrągla w stronę pierwszego argumentu, gdy różnica jest nieparzysta, właściwie obsługując bit znaku bez polegania na owijaniu bez znaku dla ostatecznego wyniku.

Pytanie 2: Pod jakim konkretnym ograniczeniem modelu obiektów wywołuje std::midpoint dla wskaźników niezdefiniowane zachowanie?

Odpowiedź std::midpoint wymaga, aby oba wskaźniki wskazywały na elementy tej samej tablicy (lub jeden za ostatnim elementem). Jeśli wskaźniki odnoszą się do różnych tablic lub niezwiązanej pamięci, zachowanie jest niezdefiniowane, ponieważ wyrażenie last - first (używane wewnętrznie) jest zdefiniowane tylko dla wskaźników w tej samej tablicy. To subtelna różnica w porównaniu do uśredniania liczb całkowitych; kandydaci często zakładają, że działa to jak prosta średnia arytmetyczna i pomijają ścisłe wymagania dotyczące aliasowania i modelu obiektu dla arytmetyki wskaźników.

Pytanie 3: Jak std::midpoint zachowuje się inaczej dla typów zmiennoprzecinkowych w porównaniu do liczb całkowitych, szczególnie w odniesieniu do wartości NaN?

Odpowiedź Dla typów zmiennoprzecinkowych std::midpoint zapobiega przepełnieniu i niedopłynięciu w sumie (co mogłoby niepoprawnie prowadzić do nieskończoności lub zera), stosując strategię zdefiniowaną przez implementację, często równą a/2 + b/2. Kluczowo, jeśli którykolwiek z argumentów to NaN, std::midpoint zwraca NaN. Jeśli jeden argument to dodatnia nieskończoność, a drugi to ujemna nieskończoność, zwraca NaN (nieoznaczone), podczas gdy średnia dla liczb całkowitych po prostu przepełniałaby lub owijała. Kandydaci często zakładają, że działa to jako prosta arytmetyka, nie uwzględniając reguł propagacji specjalnych wartości IEEE 754.