Czy `Vector <float> .Equals` powinien być zwrotny, czy powinien być zgodny z semantyką IEEE 754?

9

Porównując wartości zmiennoprzecinkowe dla równości, istnieją dwa różne podejścia:

Wbudowane typy zmiennoprzecinkowe IEEE w języku C # ( floati double) są zgodne z semantyką IEEE dla ==i !=(oraz operatorów relacyjnych, takich jak <), ale zapewniają zwrotność dla object.Equals, IEquatable<T>.Equals(i CompareTo).

Rozważmy teraz bibliotekę, która zawiera struktury wektorowe na float/ double. Taki typ wektora spowodowałby przeciążenie ==/ !=i zastąpienie object.Equals/ IEquatable<T>.Equals.

Co każdy zgadza się na to, że ==/ !=powinny być zgodne IEEE semantykę. Pytanie brzmi, czy taka biblioteka powinna implementować Equalsmetodę (która jest niezależna od operatorów równości) w sposób zwrotny lub zgodny z semantyką IEEE.

Argumenty za zastosowaniem semantyki IEEE dla Equals:

  • Jest zgodny z IEEE 754
  • Jest (prawdopodobnie znacznie) szybszy, ponieważ może korzystać z instrukcji SIMD

    Zadałem osobne pytanie na temat przepełnienia stosu dotyczące sposobu wyrażenia równości zwrotnej za pomocą instrukcji SIMD i ich wpływu na wydajność: instrukcje SIMD do porównania zmiennoprzecinkowego

    Aktualizacja: Wydaje się, że możliwe jest skuteczne wdrożenie równości zwrotnej przy użyciu trzech instrukcji SIMD.

  • Dokumentacja dotycząca Equalsnie wymaga zwrotności w przypadku zmiennoprzecinkowego:

    Poniższe instrukcje muszą być prawdziwe dla wszystkich implementacji metody Equals (Object). Na liście x, yi zreprezentują odwołań do obiektów, które nie są puste.

    x.Equals(x)zwraca true, z wyjątkiem przypadków, które dotyczą typów zmiennoprzecinkowych. Patrz ISO / IEC / IEEE 60559: 2011, Informatyka - Systemy mikroprocesorowe - Arytmetyka zmiennoprzecinkowa.

  • Jeśli używasz liczb zmiennoprzecinkowych jako kluczy słownikowych, żyjesz w stanie grzechu i nie powinieneś oczekiwać rozsądnego zachowania.

Argumenty za byciem zwrotnym:

  • Jest to zgodne z istniejących typów, w tym Single, Double, Tuplei System.Numerics.Complex.

    Nie znam żadnego precedensu w BCL, w którym Equalsnastępuje IEEE zamiast bycia refleksyjnym. Licznik przykłady obejmują Single, Double, Tuplei System.Numerics.Complex.

  • Equalsjest najczęściej używany przez kontenery i algorytmy wyszukiwania, które opierają się na zwrotności. W przypadku tych algorytmów wzrost wydajności nie ma znaczenia, jeśli uniemożliwia im działanie. Nie poświęcajcie poprawności dla wydajności.
  • Łamie ona wszystkie zestawy oparte hash i słowniki, Contains, Find, IndexOfna różnych zbiorach / LINQ, zestaw operacji na bazie (LINQ Union, Exceptitp), jeśli dane zawierają NaNwartości.
  • Kod wykonujący rzeczywiste obliczenia, w których semantyczny IEEE jest akceptowalny, zwykle działa na konkretnych typach i wykorzystuje ==/ !=(lub bardziej prawdopodobne porównania epsilon).

    Obecnie nie można pisać obliczeń o wysokiej wydajności przy użyciu ogólnych, ponieważ potrzebne są do tego operacje arytmetyczne, ale nie są one dostępne za pośrednictwem interfejsów / metod wirtualnych.

    Dlatego wolniejsza Equalsmetoda nie wpłynie na większość kodu o wysokiej wydajności.

  • Możliwe jest podanie IeeeEqualsmetody lub IeeeEqualityComparer<T>dla przypadków, w których albo potrzebujesz semantyki IEEE, albo potrzebujesz przewagi wydajności.

Moim zdaniem argumenty te zdecydowanie sprzyjają refleksyjnej realizacji.

Zespół Microsoft CoreFX planuje wprowadzić taki typ wektora w .NET. W przeciwieństwie do mnie preferują rozwiązanie IEEE , głównie ze względu na zalety wydajnościowe. Ponieważ taka decyzja z pewnością nie ulegnie zmianie po ostatecznym wydaniu, chcę uzyskać informacje zwrotne od społeczności na temat tego, co uważam za duży błąd.

CodesInChaos
źródło
1
Doskonałe i prowokujące do myślenia pytanie. Dla mnie (przynajmniej) nie ma to sensu ==i Equalszwróciłoby inne wyniki. Wielu programistów zakłada, że ​​są i robią to samo . Ponadto - ogólnie, implementacje operatorów równości przywołują tę Equalsmetodę. Argumentowałeś, że można dołączyć a IeeeEquals, ale można to zrobić na odwrót i dołączyć metodę ReflexiveEquals. Ten Vector<float>typ może być używany w wielu aplikacjach krytycznych pod względem wydajności i powinien zostać odpowiednio zoptymalizowany.
die maus
@diemaus Niektóre powody, dla których nie uważam tego za przekonujące: 1) dla float/ doublei kilku innych typów ==i Equalsjuż są różne. Myślę, że niespójność z istniejącymi typami byłaby nawet bardziej myląca niż niespójność między ==i Equalsnadal będziesz musiał radzić sobie z innymi typami. 2) Prawie wszystkie ogólne algorytmy / kolekcje używają Equalsi polegają na swojej zwrotności do działania (LINQ i słowniki), podczas gdy konkretne algorytmy zmiennoprzecinkowe zwykle używają ==tam, gdzie uzyskują semantykę IEEE.
CodesInChaos
Rozważałbym Vector<float>inną „bestię” niż zwykłą floatlub double. Dzięki takiemu rozwiązaniu nie widzę powodu Equalsani ==operatora do przestrzegania ich standardów. Sam powiedziałeś: „Jeśli używasz liczb zmiennoprzecinkowych jako kluczy słownikowych, żyjesz w stanie grzechu i nie powinieneś oczekiwać rozsądnego zachowania”. Jeśli ktoś miałby przechowywać NaNw słowniku, to ich cholerna wina za stosowanie okropnej praktyki. Nie sądzę, żeby zespół CoreFX nie przemyślał tego. Wybrałbym coś ReflexiveEqualspodobnego, tylko ze względu na wydajność.
die maus

Odpowiedzi:

5

Twierdziłbym, że zachowanie IEEE jest prawidłowe. NaNs nie są sobie równe w żaden sposób; odpowiadają one źle zdefiniowanym warunkom, w których odpowiedź numeryczna jest niewłaściwa.

Poza korzyściami wynikającymi z zastosowania arytmetyki IEEE, którą większość procesorów obsługuje natywnie, myślę, że jest problem semantyczny z powiedzeniem, że jeśli isnan(x) && isnan(y), to wtedy x == y. Na przykład:

// C++
double inf = std::numeric_limits<double>::infinity();
double x = 0.0 / 0.0;
double y = inf - inf;

Twierdziłbym, że nie ma żadnego uzasadnionego powodu, dla którego można by uznać za xrówny y. Trudno stwierdzić, że są to liczby równoważne; wcale nie są liczbami, więc wydaje się, że jest to całkowicie błędna koncepcja.

Co więcej, z perspektywy projektowania interfejsu API, jeśli pracujesz nad biblioteką ogólnego przeznaczenia, która ma być używana przez wielu programistów, sensowne jest użycie najbardziej typowej w branży semantyki zmiennoprzecinkowej. Celem dobrej biblioteki jest oszczędność czasu dla tych, którzy z niej korzystają, więc budowanie niestandardowych zachowań jest gotowe do zamieszania.

Jason R.
źródło
3
To NaN == NaNpowinno zwrócić wartość false jest niekwestionowanym. Pytanie brzmi, co .Equalspowinna zrobić metoda. Na przykład, jeśli NaNużyję jako klucza słownika, powiązana wartość stanie się niemożliwa do odzyskania, jeśli NaN.Equals(NaN)zwróci false.
CodesInChaos
1
Myślę, że musisz zoptymalizować dla typowego przypadku. Częstym przypadkiem wektora liczb jest obliczenia numeryczne o wysokiej przepustowości (często zoptymalizowane za pomocą instrukcji SIMD). Twierdziłbym, że użycie wektora jako klucza słownika jest niezwykle rzadkim przypadkiem użycia i nie warto projektować semantyki. Przeciwko dotychczasowej który wydaje się najbardziej rozsądne jest dla mnie konsystencja, ponieważ istniejący Single, Doubleitp klas mają już refleksyjne zachowanie. IMHO, od samego początku była to zła decyzja. Ale nie pozwoliłbym, aby elegancja przeszkadzała w użyteczności / szybkości.
Jason R
Ale zwykle będą używane obliczenia numeryczne, ==które zawsze były zgodne z IEEE, więc otrzymają szybki kod, bez względu na Equalsto, jak zostanie zaimplementowany. IMO cały sens posiadania oddzielnej Equalsmetody wykorzystuje w algorytmach, które nie dbają o konkretny typ, takich jak Distinct()funkcja LINQ .
CodesInChaos
1
Rozumiem. Ale argumentowałbym przeciwko API, które ma ==operator i Equals()funkcję, która ma inną semantykę. Myślę, że ponosisz koszty potencjalnego zamieszania z perspektywy programisty, bez realnych korzyści (nie przypisuję żadnej wartości temu, że mogę użyć wektora liczb jako klucza słownika). To tylko moja opinia; Nie sądzę, aby na obiektywne pytanie była obiektywna odpowiedź.
Jason R
0

Istnieje problem: IEEE754 definiuje operacje relacyjne i równość w sposób, który jest odpowiedni dla aplikacji numerycznych. Nie nadaje się do sortowania i mieszania. Więc jeśli chcesz posortować tablicę na podstawie wartości liczbowych lub jeśli chcesz dodać wartości liczbowe do zestawu lub użyć ich jako kluczy w słowniku, albo deklarujesz, że wartości NaN są niedozwolone, albo nie używasz IEEE754 wbudowane operacje. Twoja tablica skrótów musiałaby się upewnić, że wszystkie NaN są dopasowane do tej samej wartości i porównywać się ze sobą.

Jeśli zdefiniujesz Vector, musisz podjąć decyzję projektową, czy chcesz go używać tylko do celów numerycznych, czy też powinien on być zgodny z sortowaniem i mieszaniem. Osobiście uważam, że cel liczbowy powinien być znacznie ważniejszy. Jeśli potrzebne jest sortowanie / haszowanie, możesz napisać klasę z Vector jako element członkowski i zdefiniować haszowanie i równość w tej klasie w dowolny sposób.

gnasher729
źródło
1
Zgadzam się, że cele numeryczne są ważniejsze. Ale już mamy==!= dla nich operatorów i . Z mojego doświadczenia Equalswynika, że metoda ta jest używana głównie przez algorytmy nieliczbowe.
CodesInChaos