🚀 go-pugleaf

Dnia 10-03-2007, sob o godzinie 19:17 +0000, Sektor van Skijlen
napisał(a):

> Zrób sobie małą statystykę użycia takiego typu i ilość porównań, dla których
> trafiasz na równość i dla których trafiasz na nierówność.

Zrób statystykę, ile można stracić i ile można zaoszczędzić.

Sprawa nie jest oczywista. Jest wiele czynników wpływających na
opłacalność: statyczne bądź dynamiczne typowanie, statyczna wiedza
kompilatora niekoniecznie wynikająca z systemu typów, reprezentacja
obiektów czy zgoła wymagania semantyki operacji porównania w danym
języku.

Przykład. W OCamlu jest funkcja =, która porównuje zawartość dwóch
obiektów tego samego, dowolnego typu. Porównuje głęboko, nie zważając na
to, które fragmenty są zmienialne. Kompilator generuje specjalny kod dla
pewnych typów (np. liczby różnego rodzaju albo typy wyliczeniowe). Jest
też zmaterializowana w jednym miejscu uniwersalna funkcja porównująca,
zaimplementowana w C, używana dla różnych złożonych typów oraz tam,
gdzie typ nie jest statycznie znany (bo kod jest parametryzowany typem).

Ta funkcja do niedawna zaczynała od porównania fizycznej reprezentacji
argumentów, czyli albo wartości bezpośrednich, albo wskaźników. Jeśli
były równe, to zwracała true bez wchodzenia do środka, a jeśli nie były
równe, to dopiero sprawdzała, czy oba są wartościami bezpośrednimi albo
oba wskaźnikami i czy mają ten sam numer konstruktora. Z punktu widzenia
efektywności uznano, że warto.

Zostało to zmienione z powodu typu float, który jest porównywany przez =
zgodnie z arytmetyką IEEE: nan jest różne od samego siebie. Z tego
wynika, że dowolna struktura zawierająca nan, np. lista [1.0; nan; 2.0],
jest różna od samej siebie. Tymczasem w starej implementacji była równa
albo różna w zależności od tego, czy była zaalokowana osobno, czy nie,
co w przypadku listy nie powinno było mieć znaczenia. Co śmieszniejsze,
ta sama samodzielna wartość nan była równa sobie albo nierówna
w zależności od tego, czy miejsce aplikacji funkcji = było kompilowane
ze świadomością, że argumenty są typu float (wtedy było generowane tylko
zmiennoprzecinkowe porównanie zawartości), czy nie (wtedy używana była
wspomniana uniwersalna implementacja, która najpierw porównywała adres).

Tak więc zarzucono to z powodów semantycznych.

Inny przykład. W Kogucie jest funkcja Is, która porównuje dwie wartości
i z założenia jest najmniejszą relacją równoważności, która nie bierze
pod uwagę fizycznej tożsamości tam gdzie nie musi (czyli przy większości
obiektów niezmienialnych).

Problemu z NaN nie ma, bo równość arytmetyczna, w której NaN jest różne
od siebie, to osobna funkcja.

Reprezentacja wartości jest taka, że małe liczby całkowite są oznaczone
najmłodszym bitem równym 1, a wszystkie pozostałe wartości są
wskaźnikami na obiekt, którego pierwsze słowo jest wskaźnikiem na
tzw. deskryptor, którego jednym z pól jest wskaźnik na typ.

Kompilator generuje specjalny kod dla aplikacji Is, jeśli jeden
z argumentów jest znaną mu stałą. Poza tym jest jedna uniwersalna
implementacja Is, która robi co następuje:

1. Jeśli wartości są fizycznie równe (taka sama mała liczba całkowita
   albo taki sam wskaźnik), to wynikiem jest True.

2. Jeśli któryś z argumentów jest małą liczbą całkowitą, to wynikiem
   jest False.

3. Jeśli wartości są różnych typów, to wynikiem jest False.

4. Wybierana i wykonywana jest implementacja Is zależna od typu
   (wspólnego dla obu argumentów), wyszukiwana w słowniku (standardowy
   mechanizm funkcji generycznych).

Zauważmy, że 3 nie wprowadza dodatkowego kosztu, skoro tak czy siak
czeka nas 4 (dzięki 3 w 4 wystarczy wziąć jeden typ), a 2 nie wprowadza
dodatkowego kosztu, skoro czeka nas 3 (trzeba sprawdzić, czy dana
wartość nie jest małą liczbą całkowitą, zanim sprawdzi się jej typ).

W tej sytuacji punkt 1 narzuca się w sposób naturalny. Porównanie
równych liczb całkowitych jest szybsze (wystarczy pierwszy punkt)..
Porównanie różnych liczb całkowitych jest tak samo szybkie (dwa proste
punkty potrzebne tak czy siak). Porównanie innych wartości jest albo
nieznacznie wolniejsze (jedno dodatkowe porównanie, kiedy są już co
najmniej dwa inne), albo znacznie szybsze (oszczędzenie punktów od 2
do 4 przy porównaniu np. Null z Null albo równych znaków mieszczących
się w ISO-8859-1, a czasem i równych innych stringów, jeśli to ten sam
obiekt).

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/