Historia: Przed Go 1.18, język nie miał polimorfizmu parametrycznego, zmuszając programistów do wyboru między interface{} (co powodowało alokacje na stercie i narzut związany z opakowaniem) lub generowaniem kodu (co powodowało nadmiar rozmiaru binarnego). Przy projektowaniu generyków, zespół Go wyraźnie odrzucił model szablonów C++ pełnej monomorfizacji — w którym każda odrębna instancja typu produkuje zduplikowany kod maszynowy — z powodu obaw o eksplozję rozmiaru binarnego w dużych aplikacjach chmurowych łączących tysiące pakietów.
Problem: Czysta monomorfizacja wygenerowałaby oddzielne bloki asemblera dla Process[int] i Process[uint], mimo że oba są 64-bitowymi liczbami całkowitymi, marnując pamięć cache instrukcji i przestrzeń dyskową. Z drugiej strony, wprowadzenie generyków poprzez opakowanie (jak w Java) zmusiłoby typy wartościowe na stertę, niszcząc cechy wydajności zerowej alokacji, które są niezbędne dla niszy programowania systemowego Go. Wyzwanie polegało na zachowaniu bezpieczeństwa typów w czasie kompilacji i zerowych kosztów semantyki wartości, unikając problemu N-krotnego duplikowania kodu.
Rozwiązanie: Go wykorzystuje stencilling kształtu GC w połączeniu z słownikami w czasie wykonania. Kompilator grupuje typy według kształtu GC — zdefiniowanego przez rozmiar, wyrównanie i bitmapę wskaźników — a nie według dokładnej tożsamości typu. Typy o identycznych układach pamięci (np. []int i []string, które są strukturami nagłówkowymi z wskaźnikiem, len i cap) dzielą tę samą zainstancjonowaną maskę kodu maszyny. Dla operacji specyficznych dla typu, takich jak dyspozycje metod czy asercje typów, kompilator przekazuje ukryty słownik czasu wykonania, zawierający offsety metadanych. To gwarantuje, że Point{X:1, Y:2} i Vector{X:1, Y:2} dzielą kod, zachowując jednocześnie typy wartościowe nieopakowane na stosie.
Tworzyliśmy silnik przechowywania kolumnowego o wysokiej wydajności, wymagający generycznej implementacji SkipList do indeksowania zarówno znaczników czasu int64, jak i niestandardowych struktur Decimal128 (16 bajtów, dwa pola uint64). Początkowe testy wydajności z użyciem interface{} wykazały, że 35% czasu CPU było konsumowane przez alokacje sterty w czasie wykonania i pośrednictwo interfejsów, co było nieakceptowalne dla naszych wymagań dotyczących latencji sub-mikrosekundowej.
Rozważaliśmy trzy podejścia architektoniczne. Po pierwsze, pełna monomorfizacja za pomocą go generate i text/template, aby wyprodukować dedykowane implementacje SkipListInt64 i SkipListDecimal. To wyeliminowało alokacje, ale zwiększyło rozmiar naszego binaru o 22 MB przy obsłudze dwunastu różnych typów numerycznych, naruszając nasze ograniczenia wdrożenia bezserwerowego. Po drugie, zjednoczona implementacja z użyciem unsafe.Pointer i refleksji do ręcznego zarządzania pamięcią. To utrzymało rozmiar binarny na minimalnym poziomie, ale wprowadziło katastrofalną złożoność, wymagając ręcznej arytmetyki wskaźników, która łamała inwarianty garbage collectora Go podczas testowania.
Wybraliśmy trzecie podejście: natywne generyki Go z uwagą na grupowanie kształtów GC. Dostosowaliśmy naszą strukturę Decimal128 do układu pamięci [2]uint64, zapewniając, że dzieliła ona kod stencila z innymi typami wartościowymi o rozmiarze 16 bajtów. Analizując wyjście kompilatora z go tool objdump, zweryfikowaliśmy, że SkipList[int64] i SkipList[uint64] dzieliły identyczne bloki asemblera, podczas gdy SkipList[string] poprawnie używał oddzielnego stencila z powodu swojej bitmapy zawierającej wskaźnik. Podejście hybrydowe zmniejszyło rozmiar binarnej o 58% w porównaniu do generowania kodu, przy zachowaniu zerowej alokacji. Efektem była poprawa latencji czterokrotnie w porównaniu do wersji interface{} i rozmiar binarny poniżej 30 MB.
Dlaczego dwa różne typy strukturalne z identycznymi typami pól czasami generują oddzielne instancje generyczne, podczas gdy struktura i alias typu prymitywnego mogą dzielić kod?
Dzieje się tak, ponieważ grupowanie kształtów GC zależy od pełnego opisu typu czasu wykonania, w tym bitmap wskaźników i wyrównania, a nie tylko od powierzchownych typów pól. Jeśli type A struct { x, y int } i type B struct { x, y int } są zdefiniowane w różnych pakietach, dzielą ten sam kształt GC i stencil. Jednak *type C struct { x int; y int } ma inną bitmapę wskaźników niż type D struct { x, y int }, zmuszając do oddzielnej generacji kodu maszynowego. Z drugiej strony, type MyInt int i int dzielą kształty, ale struct { _ int; x int } i struct { x int } mogą się różnić z powodu wyrównania paddingu. Zrozumienie, że garbage collector wymaga dokładnych map stosu dla każdej żywej zmiennej, wyjaśnia, dlaczego tożsamość układu przewyższa tożsamość nominalną typu.
Jak dyspozycja metod na parametrach typu generycznego różni się od bezpośrednich wywołań konkretnych i dlaczego ten narzut jest nieunikniony bez pełnej monomorfizacji?
Podczas wywoływania metody na parametrze typu generycznego T, kompilator generuje pośrednie wywołanie przez słownik czasu wykonania zamiast bezpośredniego adresu funkcji. W przeciwieństwie do wywołań interfejsowych — które rozwiązują metody za pomocą itab w czasie wykonania — wpisy w słowniku generycznym są rozwiązywane w czasie kompilacji, ale przekazywane jako ukryte parametry. To wprowadza jeden poziom pośrednictwa (zwykle 2-5 nanosekund) w porównaniu do zerokosztowego kodu monomorfizowanego. Kandydaci często zakładają, że generyki są całkowicie bezkosztowe w porównaniu do kodu dostosowanego ręcznie; w rzeczywistości, wyszukiwanie w słowniku uniemożliwia pewne optymalizacje inlinowania, które pozwoliłaby monomorfizacja, chociaż pozostaje to rzędy wielkości szybsze niż reflect.Value.Call.
Dlaczego instancjonowanie typu generycznego z polem pustym identyfikatora (np. struct { _ int64; x int64 }) potencjalnie zmusza kompilator do wygenerowania unikalnego stencila, zwiększając rozmiar binarny?
Pola puste zajmują miejsce i przyczyniają się do bitmapy wskaźników struktury, nawet gdy są nieoznaczone, potencjalnie zmieniając kształt GC. struct { _ int64; x int64 } ma inny rozmiar i wyrównanie niż struct { x int64 } w niektórych architekturach, co powoduje, że kompilator przydziela ją do innej grupy stencila. Ponadto, jeśli pole puste jest typu wskaźnikowego (**_ int*), zmienia to wymagania garbage collectora dotyczące śledzenia dla tego typu, wymuszając oddzielne mapy stosu. Programiści optymalizujący pod kątem rozmiaru binarnego muszą zrozumieć, że kształty GC są określane przez cały układ pamięci — w tym padding i pola puste — a nie tylko przez semantycznie istotne człony danych.