Jakie są zastrzeżenia związane z wdrażaniem podstawowych typów (takich jak int) jako klas?

27

Przy projektowaniu i wykonawczym języka programowania obiektowego, w jakimś jednym punkcie musi dokonać wyboru o realizacji podstawowych typów (jak int, float, doublelub odpowiedników) jako klasy lub czegoś innego. Wyraźnie, języków z rodziny C mają tendencję nie je zdefiniować jako klasy (Java ma specjalnych typów prymitywnych, C # wdraża je jako niezmiennych strukturach, etc).

Mogę wymyślić bardzo ważną zaletę, gdy podstawowe typy są implementowane jako klasy (w systemie typów o ujednoliconej hierarchii): typy te mogą być odpowiednimi podtypami typu Liskov typu root. W ten sposób unikamy komplikowania języka z boksowaniem / rozpakowywaniem (jawnym lub niejawnym), typami opakowań, specjalnymi regułami wariancji, specjalnym zachowaniem itp.

Oczywiście, częściowo rozumiem, dlaczego projektanci języków decydują o tym, jak to robią: instancje klas mają zwykle pewien narzut przestrzenny (ponieważ instancje mogą zawierać vtable lub inne metadane w ich układzie pamięci), że prymitywy / struktury nie muszą mieć (jeśli język nie pozwala na dziedziczenie po nich).

Czy wydajność przestrzenna (i poprawiona lokalizacja przestrzenna, szczególnie w dużych tablicach) jest jedynym powodem, dla którego podstawowe typy często nie są klasami?

Generalnie założyłem, że odpowiedź brzmi „tak”, ale kompilatory mają algorytmy analizy ucieczki, dzięki czemu mogą wydedukować, czy mogą (selektywnie) pominąć narzut przestrzenny, gdy wystąpienie (dowolne wystąpienie, a nie tylko typ podstawowy) jest ściśle określone lokalny.

Czy powyższe jest złe, czy też brakuje mi czegoś jeszcze?

Theodoros Chatzigiannakis
źródło

Odpowiedzi:

19

Tak, w zasadzie sprowadza się to do wydajności. Ale wydaje się, że nie doceniasz wpływu (lub przeceniasz, jak dobrze działają różne optymalizacje).

Po pierwsze, nie jest to tylko „narzut przestrzenny”. Tworzenie prymitywów w pudełkach / przydziałach stert również ma koszty wydajności. GC ma dodatkową presję na przydzielanie i zbieranie tych obiektów. Dzieje się to podwójnie, jeśli „prymitywne obiekty” są niezmienne, tak jak powinny. Następnie pojawia się więcej braków pamięci podręcznej (zarówno z powodu pośredniego, jak i mniejszej ilości danych mieszczących się w danej ilości pamięci podręcznej). Plus sam fakt, że „załaduj adres obiektu, a następnie załaduj rzeczywistą wartość z tego adresu” wymaga więcej instrukcji niż „załaduj wartość bezpośrednio”.

Po drugie, analiza ucieczki nie jest szybszym wróżkiem. Dotyczy to tylko wartości, które, no cóż, nie uciekają. Z pewnością miło jest zoptymalizować lokalne obliczenia (takie jak liczniki pętli i pośrednie wyniki obliczeń) i przyniesie wymierne korzyści. Ale znacznie większa większość wartości żyje w obiektach i tablicach. To prawda, że ​​mogą one same podlegać analizie ucieczki, ale ponieważ są to zwykle zmienne typy referencyjne, każde ich aliasing stanowi poważne wyzwanie dla analizy ucieczki, która musi teraz udowodnić, że te aliasy (1) również nie uciekają oraz (2) nie robią różnicy w celu wyeliminowania przydziałów.

Biorąc pod uwagę, że wywołanie dowolnej metody (w tym pobierającej) lub przekazanie obiektu jako argumentu do dowolnej innej metody może pomóc w ucieczce z obiektu, będziesz potrzebować analizy międzyproceduralnej we wszystkich przypadkach oprócz najbardziej trywialnych. Jest to o wiele droższe i skomplikowane.

Są też przypadki, w których rzeczy naprawdę uciekają i nie można ich racjonalnie zoptymalizować. Sporo z nich, jeśli weźmiesz pod uwagę, jak często programiści C mają problem z przydzielaniem sterty. Gdy obiekt zawierający int ucieka, analiza ucieczki przestaje obowiązywać również dla int. Pożegnaj się z wydajnymi prymitywnymi polami .

To wiąże się z innym punktem: wymagane analizy i optymalizacje są bardzo skomplikowane i stanowią aktywny obszar badań. Można dyskutować, czy jakakolwiek implementacja języka kiedykolwiek osiągnęła sugerowany przez ciebie stopień optymalizacji, a nawet jeśli tak, to był to rzadki i herculeański wysiłek. Z pewnością stanięcie na ramionach tych gigantów jest łatwiejsze niż bycie gigantem, ale wciąż jest dalekie od trywialnych. Nie spodziewaj się konkurencyjnych wyników w pierwszych latach, jeśli w ogóle.

Nie oznacza to, że takie języki nie mogą być wykonalne. Najwyraźniej są. Tylko nie zakładaj, że będzie on działał tak szybko, jak języki z dedykowanymi prymitywami. Innymi słowy, nie łudz się wizjami wystarczająco inteligentnego kompilatora .


źródło
Mówiąc o analizie ucieczki, miałem również na myśli przydzielanie do automatycznego przechowywania (nie rozwiązuje wszystkiego, ale, jak mówisz, rozwiązuje pewne rzeczy). Przyznaję również, że nie doceniłem stopnia, w jakim pola i aliasing mogą powodować częstsze niepowodzenia analizy ucieczki. Brak pamięci podręcznej był tym, co najbardziej mnie martwiło, gdy mówiłem o wydajności przestrzennej, więc dziękuję za zajęcie się tym.
Theodoros Chatzigiannakis
@TheodorosChatzigiannakis W analizie ucieczki uwzględniam zmianę strategii alokacji (bo szczerze mówiąc, wydaje się, że to jedyna rzecz, do jakiej kiedykolwiek była używana).
Zobacz drugi akapit: Obiekty nie zawsze muszą być alokowane na stosie lub być typami referencyjnymi. W rzeczywistości, gdy tak nie jest, sprawia to, że niezbędne optymalizacje są stosunkowo łatwe. Zobacz wczesny przykład obiektów przydzielonych do stosu w C ++, a także system zarządzania własnością Rust'a, aby uzyskać sposób na przeprowadzenie analizy ucieczki bezpośrednio w języku.
amon
@amon Wiem, i może powinienem to wyjaśnić, ale wydaje się, że OP interesuje się tylko językami podobnymi do Java i C #, gdzie przydzielanie sterty jest prawie obowiązkowe (i niejawne) z powodu semantyki referencyjnej i bezstratnych rzutów między podtypami. Warto jednak wiedzieć, że Rust używa kwoty, która pozwala uniknąć analizy!
@delnan To prawda, że ​​najbardziej interesują mnie języki, które wyodrębniają szczegóły przechowywania, ale prosimy o dołączenie wszystkiego, co uważasz za istotne, nawet jeśli nie ma zastosowania w tych językach.
Theodoros Chatzigiannakis
27

Czy wydajność przestrzenna (i poprawiona lokalizacja przestrzenna, szczególnie w dużych tablicach) jest jedynym powodem, dla którego podstawowe typy często nie są klasami?

Nie.

Inną kwestią jest to, że podstawowe typy są zwykle wykorzystywane w podstawowych operacjach. Kompilator musi wiedzieć, że int + intnie będzie kompilowany do wywołania funkcji, ale do podstawowej instrukcji procesora (lub równoważnego kodu bajtowego). W tym momencie, jeśli masz intjako zwykły obiekt, będziesz musiał i tak skutecznie rozpakować rzecz.

Tego rodzaju operacje również nie bardzo dobrze się bawią z subtypingiem. Nie można wysłać instrukcji do procesora. Nie można wysłać z instrukcji procesora. Chodzi mi o to, że cały punkt podtypu jest taki, abyś mógł użyć miejsca, w Dktórym możesz B. Instrukcje procesora nie są polimorficzne. Aby uzyskać prymitywy, aby to zrobić, musisz owinąć ich operacje logiką wysyłki, która kosztuje wiele razy więcej operacji niż zwykły dodatek (lub cokolwiek innego). Korzyści wynikające z intbycia częścią hierarchii typów stają się nieco dyskusyjne, gdy są zapieczętowane / końcowe. I to ignoruje wszystkie problemy z logiką wysyłki dla operatorów binarnych ...

Zasadniczo, prymitywne typy musiałaby mieć wiele specjalnych zasad wokół jak uchwyty kompilatora nich, a co użytkownik może zrobić z ich rodzajów i tak , więc jest często razy prostsze po prostu traktować je jako całkowicie odrębne.

Telastyn
źródło
4
Sprawdź implementację dowolnego z dynamicznie wpisywanych języków, które traktują liczby całkowite i takie jak obiekty. Ostateczna pierwotna instrukcja procesora może być bardzo dobrze ukryta w metodzie (przeciążenie operatora) w jedynej uprzywilejowanej implementacji klasy w bibliotece wykonawczej. Szczegóły wyglądałyby inaczej w przypadku systemu typu statycznego i kompilatora, ale nie jest to podstawowy problem. W najgorszym wypadku wszystko to staje się jeszcze wolniejsze.
3
int + intmoże być zwykłym operatorem na poziomie języka, który wywołuje wewnętrzną instrukcję, która gwarantuje kompilację do (lub zachowanie się) natywnego dodawania liczb całkowitych procesora op. Zaletą intdziedziczenia objectjest nie tylko możliwość dziedziczenia innego rodzaju int, ale także możliwość intzachowania się objectbez boksowania. Rozważmy generyczne C #: możesz mieć kowariancję i kontrawariancję, ale mają one zastosowanie tylko do typów klas - typy struktur są automatycznie wykluczane, ponieważ mogą one stać się tylko objectpoprzez (domyślny, wygenerowany przez kompilator) boks.
Theodoros Chatzigiannakis
3
@delnan - oczywiście, choć z mojego doświadczenia z implementacjami o typie statycznym, ponieważ każde wywołanie niesystemowe sprowadza się do prymitywnych operacji, a obciążenie ogólne ma dramatyczny wpływ na wydajność - co z kolei ma jeszcze bardziej dramatyczny wpływ na adopcję.
Telastyn
@TheodorosChatzigiannakis - świetnie, więc możesz uzyskać wariancję i kontrowariancję na typach, które nie mają użytecznego podtypu / supertypu ... A implementacja tego specjalnego operatora w celu wywołania instrukcji CPU wciąż czyni go wyjątkowym. Nie zgadzam się z tym pomysłem - robiłem bardzo podobne rzeczy w moich zabawkowych językach, ale odkryłem, że istnieją praktyczne problemy podczas wdrażania, które nie sprawiają, że takie rzeczy są tak czyste, jak można się spodziewać.
Telastyn
1
@TheodorosChatzigiannakis Przechodzenie między bibliotekami jest z pewnością możliwe, choć jest to kolejny element listy zakupów „Optymalizacje z najwyższej półki”. Czuję się jednak zobowiązana do wskazania, że ​​bardzo trudno jest całkowicie nie mieć racji bytu, ale nie jest się tak konserwatywnym, że jest bezużyteczny.
4

Jest tylko kilka przypadków, w których potrzebujesz „podstawowych typów”, aby być pełnymi obiektami (tutaj obiekt to dane, które albo zawierają wskaźnik mechanizmu wysyłania, albo są oznaczone typem, który może być użyty przez mechanizm wysyłania):

  • Chcesz, aby typy zdefiniowane przez użytkownika mogły dziedziczyć po typach podstawowych. Zazwyczaj nie jest to pożądane, ponieważ wprowadza bóle głowy związane z wydajnością i bezpieczeństwem. Jest to problem z wydajnością, ponieważ kompilacja nie może zakładać, że intbędzie miała określony stały rozmiar lub że żadne metody nie zostały zastąpione, i jest to problem bezpieczeństwa, ponieważ semantykę ints można podważyć (rozważ liczbę całkowitą równą dowolnej liczbie lub co zmienia jego wartość, a nie jest niezmienne).

  • Twoje typy pierwotne mają nadtypy i chcesz mieć zmienne z typem nadtypu typu pierwotnego. Załóżmy na przykład, że ints są Hashable, i chcesz zadeklarować funkcję, która przyjmuje Hashableparametr, który może odbierać zwykłe obiekty, ale także ints.

    Można to „rozwiązać”, czyniąc takie typy nielegalnymi: pozbądź się podtypów i zdecyduj, że interfejsy nie są typami, ale ograniczeniami typów. Oczywiście zmniejsza to ekspresję twojego systemu typów, a taki system typów nie byłby już nazywany obiektowym. Zobacz Haskell, aby poznać język, który korzysta z tej strategii. C ++ jest w połowie drogi, ponieważ typy pierwotne nie mają nadtypów.

    Alternatywą jest pełne lub częściowe boksowanie podstawowych typów. Typ boksu nie musi być widoczny dla użytkownika. Zasadniczo definiujesz wewnętrzny typ pudełkowy dla każdego typu podstawowego i niejawne konwersje między typem pudełkowym a podstawowym. Może to stać się niezręczne, jeśli typy pudełkowe mają inną semantykę. Java ma dwa problemy: typy pudełkowe mają pojęcie tożsamości, podczas gdy prymitywy mają tylko pojęcie równoważności wartości, a typy pudełkowe są zerowalne, podczas gdy prymitywy są zawsze poprawne. Tych problemów można całkowicie uniknąć, nie oferując koncepcji tożsamości dla typów wartości, oferując przeciążenie operatora i domyślnie nie dopuszczając do zniszczenia wszystkich obiektów.

  • Nie używasz pisania statycznego. Zmienna może zawierać dowolną wartość, w tym typy pierwotne lub obiekty. Dlatego wszystkie pierwotne typy muszą być zawsze zapakowane w ramki, aby zagwarantować mocne pisanie.

Języki, które mają typowanie statyczne, dobrze wykorzystują prymitywne typy tam, gdzie to możliwe, i tylko w ostateczności odwołują się do typów pudełkowych. Chociaż wiele programów nie jest wyjątkowo wrażliwych na wydajność, zdarzają się przypadki, w których rozmiar i skład prymitywnych typów jest niezwykle istotny: Pomyśl o rozbijaniu liczb na dużą skalę, w którym musisz zmieścić miliardy punktów danych w pamięci. Przełączanie z doublenafloatmoże być realną strategią optymalizacji przestrzeni w C, ale nie przyniosłoby żadnego efektu, gdyby wszystkie typy liczbowe były zawsze zapakowane (a zatem marnowałyby co najmniej połowę pamięci na wskaźnik mechanizmu wysyłania). Gdy lokalne typy pierwotne w pudełkach są używane lokalnie, usunięcie boksu jest dość proste przy użyciu wewnętrznych funkcji kompilatora, ale krótkowzrocznie byłoby postawić na ogólną wydajność twojego języka na „wystarczająco zaawansowanym kompilatorze”.

amon
źródło
Nie intjest niezmienny we wszystkich językach.
Scott Whitlock,
6
@ScottWhitlock Rozumiem, dlaczego możesz tak myśleć, ale ogólnie prymitywne typy są niezmiennymi typami wartości. Żaden rozsądny język nie pozwala na zmianę wartości liczby siedem. Jednak wiele języków pozwala ponownie przypisać zmienną zawierającą wartość typu pierwotnego do innej wartości. W językach podobnych do C zmienna jest nazwaną lokalizacją pamięci i działa jak wskaźnik. Zmienna nie jest taka sama jak wartość, na którą wskazuje. intWartość jest niezmienna, ale intzmienna nie jest.
amon
1
@amon: Brak rozsądnego języka; tylko Java: thedailywtf.com/articles/Disgruntled-Bomb-Java-Edition
Mason Wheeler
get rid of subtyping and decide that interfaces aren't types but type constraints.... such a type system wouldn't be called object-oriented any longer ale to brzmi jak programowanie prototypowe, które jest zdecydowanie OOP.
Michael
1
@ScottWhitlock pytanie brzmi, czy jeśli masz int b = a, możesz zrobić coś do b, co zmieni wartość a. Istnieją pewne implementacje języka, w których jest to możliwe, ale ogólnie uważa się je za patologiczne i niepożądane, w przeciwieństwie do robienia tego samego dla tablicy.
Random832
2

Większość implementacji zdaję sobie sprawę z nałożenia trzech ograniczeń na takie klasy, które pozwalają kompilatorowi na efektywne wykorzystanie typów pierwotnych jako reprezentacji leżącej u podstaw przez większość czasu. Te ograniczenia to:

  • Niezmienność
  • Ostateczność (nie można uzyskać)
  • Pisanie statyczne

Sytuacje, w których kompilator musi zapakować operację podstawową do obiektu w reprezentacji bazowej, są stosunkowo rzadkie, na przykład gdy Objectwskazuje na to odwołanie.

Dodaje to trochę specjalnej obsługi przypadków w kompilatorze, ale nie ogranicza się tylko do jakiegoś mitycznego super-zaawansowanego kompilatora. Ta optymalizacja dotyczy rzeczywistych kompilatorów produkcyjnych w głównych językach. Scala pozwala nawet zdefiniować własne klasy wartości.

Karl Bielefeldt
źródło
1

W Smalltalk wszystkie z nich (int, float itp.) Są obiektami pierwszej klasy. Tylko szczególnym przypadkiem jest to, że SmallIntegers są skodyfikowane i traktowane inaczej przez Virtual Machine ze względu na skuteczność, a więc klasa SmallInteger nie przyznają podklasy (co nie jest praktycznym ograniczeniem.) Zauważ, że to nie wymaga żadnej szczególnej uwagi ze strony programisty, ponieważ rozróżnienie jest ograniczone do automatycznych procedur, takich jak generowanie kodu lub odśmiecanie.

Zarówno kompilator Smalltalk (kod źródłowy -> kody bajtowe VM), jak i natywny VM (kod bajtowy -> kod maszynowy) optymalizują generowany kod (JIT), aby zmniejszyć karę za podstawowe operacje na tych podstawowych obiektach.

Leandro Caniglia
źródło
1

Projektowałem langauge OO i środowisko uruchomieniowe (to nie powiodło się z zupełnie innych powodów).

Nie ma nic z natury złego w tworzeniu takich rzeczy jak prawdziwe klasy; w rzeczywistości sprawia to, że GC jest łatwiejsze do zaprojektowania, ponieważ są teraz tylko 2 rodzaje nagłówków sterty (klasa i tablica), a nie 3 (klasa, tablica i prymityw)) [fakt, że możemy scalić klasę i tablicę po tym, co nie jest istotne ].

W naprawdę ważnym przypadku pierwotne typy powinny mieć głównie metody końcowe / zapieczętowane (+ naprawdę ma znaczenie, ToString nie tyle). Pozwala to kompilatorowi na statyczne rozwiązywanie prawie wszystkich wywołań samych funkcji i wstawianie ich. W większości przypadków nie ma to znaczenia przy kopiowaniu (postanowiłem udostępnić osadzanie na poziomie języka [podobnie jak .NET]), ale w niektórych przypadkach, jeśli metody nie są zamknięte, kompilator będzie zmuszony wygenerować wywołanie funkcja używana do implementacji int + int.

Jozuego
źródło