Dlaczego int w OCaml ma tylko 31 bitów?

Nigdzie indziej nie widziałem tej „funkcji”. Wiem, że 32-ty bit jest używany do czyszczenia pamięci. Ale dlaczego tak jest tylko w przypadku int, a nie w przypadku innych podstawowych typów?

Nazywa się to oznaczoną reprezentacją wskaźnika i jest dość powszechną sztuczką optymalizacyjną używaną w wielu różnych interpreterach, maszynach wirtualnych i systemach wykonawczych od dziesięcioleci. Używa ich prawie każda implementacja Lispa, wiele maszyn wirtualnych Smalltalk, wiele interpreterów języka Ruby i tak dalej.

Zwykle w tych językach zawsze podaje się wskaźniki do obiektów. Sam obiekt składa się z nagłówka obiektu, który zawiera metadane obiektu (takie jak typ obiektu, jego klasy, może ograniczenia kontroli dostępu lub adnotacje bezpieczeństwa itd.), A następnie same dane obiektu. Zatem prosta liczba całkowita byłaby reprezentowana jako wskaźnik plus obiekt składający się z metadanych i rzeczywistej liczby całkowitej. Nawet przy bardzo zwartej reprezentacji, jest to około 6 bajtów dla prostej liczby całkowitej.

Nie można również przekazać takiego obiektu typu integer do procesora w celu wykonania szybkiej arytmetyki całkowitoliczbowej. Jeśli chcesz dodać dwie liczby całkowite, tak naprawdę masz tylko dwa wskaźniki, które wskazują początek nagłówków obiektów dwóch obiektów całkowitych, które chcesz dodać. Więc najpierw musisz wykonać arytmetykę liczb całkowitych na pierwszym wskaźniku, aby dodać przesunięcie do obiektu, do którego są przechowywane dane całkowite. Następnie musisz usunąć ten adres. Zrób to samo ponownie z drugą liczbą całkowitą. Teraz masz dwie liczby całkowite, o dodanie których możesz poprosić procesor. Oczywiście musisz teraz skonstruować nowy obiekt typu integer, który będzie przechowywał wynik.

Tak więc, aby wykonać jedno dodawanie liczb całkowitych, w rzeczywistości musisz wykonać trzy dodawanie liczb całkowitych plus dwa dererefencje wskaźnika i jedną konstrukcję obiektu. Zajmujesz prawie 20 bajtów.

Jednak sztuczka polega na tym, że przy tak zwanych niezmiennych typach wartości, takich jak liczby całkowite, zwykle nie potrzebujesz wszystkich metadanych w nagłówku obiektu: możesz po prostu zostawić te wszystkie rzeczy i po prostu je zsyntetyzować (czyli VM-nerd- mówić „udawać”), gdy ktoś chce spojrzeć. Liczba całkowita zawsze będzie miała klasę Integer, nie ma potrzeby oddzielnego przechowywania tych informacji. Jeśli ktoś używa odbicia, aby obliczyć klasę liczby całkowitej, po prostu odpowiadasz Integeri nikt nigdy się nie dowie, że w rzeczywistości nie zapisałeś tych informacji w nagłówku obiektu i że w rzeczywistości nie ma nawet nagłówka obiektu (lub obiekt).

Więc, sztuką jest przechowywanie wartości z obiektu w ciągu wskaźnika do obiektu, skutecznie zawaleniem się dwa w jednym.

Istnieją procesory, które w rzeczywistości mają dodatkową przestrzeń we wskaźniku (tak zwane bity znaczników ), które pozwalają na przechowywanie dodatkowych informacji o wskaźniku wewnątrz samego wskaźnika. Dodatkowe informacje, takie jak „to właściwie nie jest wskaźnik, to jest liczba całkowita”. Przykłady obejmują Burroughs B5000, różne maszyny Lisp lub AS / 400. Niestety, większość obecnych głównych procesorów nie ma tej funkcji.

Jest jednak wyjście: większość obecnych głównych procesorów działa znacznie wolniej, gdy adresy nie są wyrównane na granicach słów. Niektóre nawet w ogóle nie obsługują niewyrównanego dostępu.

Oznacza to, że w praktyce wszystkie wskaźniki będą podzielne przez 4, co oznacza, że zawsze kończą się dwoma 0bitami. To pozwala nam odróżnić rzeczywiste wskaźniki (które kończą się na 00) od wskaźników, które są w rzeczywistości zamaskowanymi liczbami całkowitymi (te, które kończą się na 1). I nadal pozostawia nam wszystkie wskazówki, które kończą się 10swobodą robienia innych rzeczy. Ponadto większość nowoczesnych systemów operacyjnych rezerwuje bardzo niskie adresy dla siebie, co daje nam kolejny obszar do poruszania się (wskaźniki zaczynające się, powiedzmy, 24 0si kończą na 00).

Możesz więc zakodować 31-bitową liczbę całkowitą we wskaźnik, po prostu przesuwając ją o 1 bit w lewo i dodając 1do niej. Możesz na nich wykonywać bardzo szybkie arytmetyki całkowite, po prostu odpowiednio je przesuwając (czasami nawet to nie jest konieczne).

Co robimy z innymi przestrzeniami adresowymi? Cóż, Typowe przykłady kodowania floatS w innych dużych przestrzeni adresowej oraz szereg obiektów specjalnych takich jak true, false, nil, W 127 znaków ASCII, niektóre powszechnie stosowane krótkie ciągi znaków, pusta lista, pusty obiekt, pusta tablica i tak zbyt blisko 0adres.

Na przykład, w tłumaczy MRI YARV i Rubinius Ruby całkowite są kodowane tak, jak opisano powyżej, falsejest zakodowana jako adres 0(którego tak się dzieje również być przedstawieniem falsew C), truejak adres 2(który tak dzieje się reprezentacja C trueprzesunięta o jeden bit) i niljako 4.

Dobry opis można znaleźć w sekcji „Reprezentacja liczb całkowitych, bitów znaczników, wartości przydzielonych do sterty” na stronie https://ocaml.org/learn/tutorials/performance_and_profiling.html .

Krótka odpowiedź jest taka, że ​​chodzi o wydajność. Podczas przekazywania argumentu do funkcji jest on przekazywany jako liczba całkowita lub wskaźnik. Na poziomie języka na poziomie komputera nie ma sposobu, aby stwierdzić, czy rejestr zawiera liczbę całkowitą lub wskaźnik, jest to tylko wartość 32- lub 64-bitowa. Zatem środowisko wykonawcze OCaml sprawdza bit tagu, aby określić, czy otrzymany element był liczbą całkowitą, czy wskaźnikiem. Jeśli bit tagu jest ustawiony, wartość jest liczbą całkowitą i jest przekazywana do odpowiedniego przeciążenia. W przeciwnym razie jest to wskaźnik i wyszukiwany jest typ.

Dlaczego tylko liczby całkowite mają ten tag? Ponieważ wszystko inne jest przekazywane jako wskaźnik. Przekazywana jest liczba całkowita lub wskaźnik do innego typu danych. Z tylko jednym bitem tagu mogą istnieć tylko dwa przypadki.

Nie jest dokładnie „używany do czyszczenia pamięci”. Służy do wewnętrznego rozróżniania między wskaźnikiem a liczbą całkowitą bez ramki.

Muszę dodać ten link, aby pomóc OP zrozumieć więcej . 63-bitowy typ zmiennoprzecinkowy dla 64-bitowego OCaml

Chociaż wydaje się float, że tytuł artykułu dotyczy , tak naprawdę dotyczy on formatuextra 1 bit

Środowisko wykonawcze OCaml umożliwia polimorfizm dzięki jednolitej reprezentacji typów. Każda wartość OCaml jest reprezentowana jako pojedyncze słowo, dzięki czemu można mieć jedną implementację, powiedzmy, „listy rzeczy”, z funkcjami dostępowymi (np. List.length) i budowaniem (np. List.map) tych list działają tak samo, niezależnie od tego, czy są listami liczb całkowitych, liczbami zmiennoprzecinkowymi czy listami zbiorów liczb całkowitych.

Wszystko, co nie pasuje do słowa, jest umieszczane w bloku w stercie. Słowo reprezentujące te dane jest wówczas wskaźnikiem do bloku. Ponieważ sterta zawiera tylko bloki słów, wszystkie te wskaźniki są wyrównane: ich kilka najmniej znaczących bitów jest zawsze nieustawionych.

Bezargumentowe konstruktory (takie jak ten: typ owoc = Jabłko | Pomarańcza | Banan) i liczby całkowite nie reprezentują tak wielu informacji, które trzeba zaalokować na stercie. Ich reprezentacja jest rozpakowana. Dane znajdują się bezpośrednio w słowie, które w innym przypadku byłoby wskaźnikiem. Tak więc, podczas gdy lista list jest w rzeczywistości listą wskaźników, lista int zawiera int z jednym mniej pośrednim. Funkcje uzyskujące dostęp do list i budujące je nie zauważają, ponieważ wartości int i wskaźniki mają ten sam rozmiar.

Mimo to Garbage Collector musi być w stanie rozpoznawać wskaźniki z liczb całkowitych. Wskaźnik wskazuje na dobrze uformowany blok w stercie, który z definicji jest żywy (ponieważ jest odwiedzany przez GC) i powinien być tak oznaczony. Liczba całkowita może mieć dowolną wartość i mogłaby przypadkowo wyglądać jak wskaźnik, gdyby nie podjęto środków ostrożności. Może to spowodować, że martwe bloki będą wyglądać na żywe, ale o wiele gorzej, spowoduje to również, że GC zmieni bity w tym, co myśli, że jest nagłówkiem aktywnego bloku, kiedy faktycznie podąża za liczbą całkowitą, która wygląda jak wskaźnik i zepsuje użytkownika dane.

Z tego powodu liczby całkowite bez pudełka zapewniają programatorowi OCaml 31 bitów (dla 32-bitowego OCaml) lub 63 bity (dla 64-bitowego OCaml). W reprezentacji, za kulisami, zawsze ustawiany jest najmniej znaczący bit słowa zawierającego liczbę całkowitą, aby odróżnić go od wskaźnika. 31- lub 63-bitowe liczby całkowite są raczej nietypowe, więc każdy, kto w ogóle używa OCaml, wie o tym. Użytkownicy OCaml zwykle nie wiedzą, dlaczego nie ma 63-bitowego typu unboxed float dla 64-bitowego OCaml.

Dlaczego int w OCaml ma tylko 31 bitów?

Zasadniczo, aby uzyskać najlepszą możliwą wydajność testu twierdzenia Coqa, w którym dominującą operacją jest dopasowywanie wzorców, a dominującymi typami danych są typy wariantowe. Okazało się, że najlepszą reprezentacją danych jest jednolita reprezentacja przy użyciu tagów do odróżniania wskaźników od danych bez ramki.

Ale dlaczego tak jest tylko w przypadku int, a nie w przypadku innych podstawowych typów?

Nie tylko int. Inne typy, takie jak chari wyliczenia, używają tej samej oznaczonej reprezentacji.