Implementacja czysto abstrakcyjnych klas i interfejsów

27

Chociaż nie jest to obowiązkowe w standardzie C ++, wydaje się, że GCC, na przykład, implementuje klasy nadrzędne, w tym czysto abstrakcyjne, poprzez włączenie wskaźnika do tabeli v dla tej abstrakcyjnej klasy w każdej instancji danej klasy .

Oczywiście powoduje to powiększenie rozmiaru każdej instancji tej klasy o wskaźnik dla każdej klasy nadrzędnej, którą posiada.

Zauważyłem jednak, że wiele klas i struktur C # ma wiele interfejsów nadrzędnych, które są w zasadzie czystymi klasami abstrakcyjnymi. Byłbym zdziwiony, gdyby każdy przykład, powiedzmy Decimal, był rozdęty 6 wskaźnikami do wszystkich jego różnych interfejsów.

Więc jeśli C # robi interfejsy inaczej, to jak to robi, przynajmniej w typowej implementacji (rozumiem, że sam standard może nie definiować takiej implementacji)? I czy jakieś implementacje C ++ pozwalają uniknąć rozdęcia rozmiaru obiektu podczas dodawania klas czysto wirtualnych?

Clinton
źródło
1
Do obiektów C # zwykle dołączonych jest całkiem sporo metadanych, być może tabele vtab nie są aż tak duże
max630
możesz zacząć od zbadania skompilowanego kodu za pomocą deasemblera
idl
C ++ robi znaczną część swoich „interfejsów” statycznie. Porównaj IComparerdoCompare
Caleth,
4
Na przykład GCC używa wskaźnika tabeli vtable (wskaźnika do tabeli vtables lub VTT) na obiekt dla klas z wieloma klasami podstawowymi. Tak więc każdy obiekt ma tylko jeden dodatkowy wskaźnik zamiast kolekcji, którą sobie wyobrażasz. Być może oznacza to, że w praktyce nie stanowi to problemu, nawet gdy kod jest źle zaprojektowany i wiąże się z tym ogromna hierarchia klas.
Stephen M. Webb
1
@ StephenM.Webb O ile rozumiem z tej odpowiedzi SO , VTT są używane tylko do zamawiania budowy / zniszczenia z wirtualnym spadkiem. Nie biorą udziału w wysyłaniu metod i nie kończą oszczędzać miejsca w samym obiekcie. Ponieważ upcasty w C ++ skutecznie wykonują wycinanie obiektów, nie jest możliwe umieszczenie wskaźnika vtable nigdzie indziej niż w obiekcie (który dla MI dodaje wskaźniki vtable na środku obiektu). Zweryfikowałem, patrząc na g++-7 -fdump-class-hierarchywynik.
amon

Odpowiedzi:

35

W implementacjach C # i Java obiekty zwykle mają pojedynczy wskaźnik do swojej klasy. Jest to możliwe, ponieważ są to języki jednego dziedzictwa. Struktura klas zawiera następnie vtable dla hierarchii pojedynczego dziedziczenia. Ale wywoływanie metod interfejsu ma również wszystkie problemy związane z wielokrotnym dziedziczeniem. Zwykle rozwiązuje się to poprzez umieszczenie dodatkowych tabel vtable dla wszystkich zaimplementowanych interfejsów w strukturze klasy. Oszczędza to miejsce w porównaniu z typowymi implementacjami wirtualnego dziedziczenia w C ++, ale komplikuje wysyłanie metod interfejsu - co można częściowo skompensować przez buforowanie.

Np. W OpenJDK JVM każda klasa zawiera tablicę vtables dla wszystkich zaimplementowanych interfejsów (interfejs vtable nazywa się itable ). Gdy wywoływana jest metoda interfejsu, tablica jest przeszukiwana liniowo pod kątem itable tego interfejsu, a następnie metoda może zostać wysłana przez tę itable. Buforowanie jest używane, aby każda strona wywołująca zapamiętała wynik wysłania metody, więc to wyszukiwanie musi być powtórzone tylko wtedy, gdy zmienia się konkretny typ obiektu. Pseudokod dla wysyłki metody:

// Dispatch SomeInterface.method
Method const* resolve_method(
    Object const* instance, Klass const* interface, uint itable_slot) {

  Klass const* klass = instance->klass;

  for (Itable const* itable : klass->itables()) {
    if (itable->klass() == interface)
      return itable[itable_slot];
  }

  throw ...;  // class does not implement required interface
}

(Porównaj prawdziwy kod w interpreterie OpenJDK HotSpot lub kompilatorze x86 ).

C # (a ściślej CLR) stosuje podobne podejście. Jednak tutaj itables nie zawierają wskaźników do metod, ale są mapami gniazd: wskazują na wpisy w głównej tabeli vt klasy. Podobnie jak w przypadku Javy, konieczność znalezienia właściwej opcji jest tylko najgorszym scenariuszem i oczekuje się, że buforowanie w witrynie wywołującej może prawie zawsze uniknąć tego wyszukiwania. CLR używa techniki o nazwie Virtual Stub Dispatch w celu łatania skompilowanego kodu maszynowego JIT za pomocą różnych strategii buforowania. Pseudo kod:

Method const* resolve_method(
    Object const* instance, Klass const* interface, uint interface_slot) {

  Klass const* klass = instance->klass;

  // Walk all base classes to find slot map
  for (Klass const* base = klass; base != nullptr; base = base->base()) {
    // I think the CLR actually uses hash tables instead of a linear search
    for (SlotMap const* slot_map : base->slot_maps()) {
      if (slot_map->klass() == interface) {
        uint vtable_slot = slot_map[interface_slot];
        return klass->vtable[vtable_slot];
      }
    }
  }

  throw ...;  // class does not implement required interface
}

Główną różnicą w stosunku do pseudokodu OpenJDK jest to, że w OpenJDK każda klasa ma tablicę wszystkich bezpośrednio lub pośrednio zaimplementowanych interfejsów, podczas gdy CLR zachowuje tylko tablicę map gniazd dla interfejsów, które zostały bezpośrednio zaimplementowane w tej klasie. Dlatego musimy podążać hierarchią dziedziczenia w górę, dopóki nie zostanie znaleziona mapa miejsca. W przypadku hierarchii głębokiego dziedziczenia powoduje to oszczędność miejsca. Są one szczególnie istotne w CLR ze względu na sposób implementacji generics: w przypadku specjalizacji ogólnej struktura klasy jest kopiowana, a metody w głównej tabeli można zastąpić specjalizacjami. Mapy gniazd nadal wskazują prawidłowe wpisy vtable i dlatego mogą być współużytkowane przez wszystkie ogólne specjalizacje klasy.

Na koniec, istnieje więcej możliwości zaimplementowania wysyłki interfejsu. Zamiast umieszczać wskaźnik vtable / itable w obiekcie lub w strukturze klasy, możemy użyć wskaźników tłuszczu do obiektu, które są w zasadzie (Object*, VTable*)parą. Wadą jest to, że podwaja rozmiar wskaźników i że upcasty (od konkretnego typu do typu interfejsu) nie są darmowe. Ale jest bardziej elastyczny, ma mniej pośredni, a także oznacza, że ​​interfejsy mogą być implementowane zewnętrznie z klasy. Podobne podejścia są stosowane w interfejsach Go, cechach Rust i typach klas Haskell.

Referencje i dalsza lektura:

  • Wikipedia: buforowanie wbudowane . Omówiono metody buforowania, których można użyć, aby uniknąć kosztownego wyszukiwania metod. Zwykle nie jest potrzebny do wysyłki opartej na tabeli, ale jest bardzo pożądany w przypadku droższych mechanizmów wysyłki, takich jak powyższe strategie wysyłki interfejsu.
  • OpenJDK Wiki (2013): Połączenia interfejsu . Omawia itables.
  • Pobar, Neward (2009): SSCLI 2.0 Internals. Rozdział 5 książki szczegółowo omawia mapy automatów. Nigdy nie został opublikowany, ale udostępniony przez autorów na ich blogach . Link PDF od tego czasu przeniósł. Ta książka prawdopodobnie nie odzwierciedla już obecnego stanu CLR.
  • CoreCLR (2006): Virtual Stub Dispatch . W: Book Of Runtime. Omawia mapy miejsc i pamięć podręczną, aby uniknąć kosztownych wyszukiwań.
  • Kennedy, Syme (2001): Projektowanie i implementacja generics dla środowiska uruchomieniowego .NET Common Language . ( Link PDF ). Omawia różne podejścia do implementacji generycznych. Generics wchodzi w interakcję z wysyłaniem metod, ponieważ metody mogą być wyspecjalizowane, więc vtables może wymagać przepisania.
amon
źródło
Dzięki @amon świetna odpowiedź z niecierpliwością oczekująca na dodatkowe szczegóły, zarówno w jaki sposób Java i CLR to osiągają!
Clinton
@Clinton Zaktualizowałem post z kilkoma referencjami. Możesz także odczytać kod źródłowy maszyn wirtualnych, ale trudno mi było go śledzić. Moje referencje są trochę stare, jeśli znajdziesz coś nowszego, byłbym bardzo zainteresowany. Ta odpowiedź jest w zasadzie fragmentem notatek, które leżały mi na blogu, ale nigdy nie udało mi się ich opublikować: /
am
1
callvirtAKA CEE_CALLVIRTw CoreCLR to instrukcja CIL, która obsługuje wywoływanie metod interfejsu, jeśli ktoś chce przeczytać więcej o tym, jak środowisko wykonawcze obsługuje tę konfigurację.
jrh
Zauważ, że callopcode jest używany do staticmetod, co ciekawe, callvirtjest używany, nawet jeśli klasa jest sealed.
jrh
1
Re: „Obiekty [C #] zazwyczaj mają pojedynczy wskaźnik do swojej klasy ... ponieważ [C # jest] językiem pojedynczego dziedziczenia.” Nawet w C ++, z całym jego potencjałem dla złożonych sieci wielokrotnie odziedziczonych typów, nadal możesz określić tylko jeden typ w miejscu, w którym program tworzy nową instancję. Teoretycznie powinno być możliwe zaprojektowanie kompilatora C ++ i biblioteki obsługi w czasie wykonywania, tak aby żadna instancja klasy nigdy nie zawierała więcej niż jednego wskaźnika RTTI o wartości jednego wskaźnika.
Solomon Slow
2

Oczywiście powoduje to powiększenie rozmiaru każdej instancji tej klasy o wskaźnik dla każdej klasy nadrzędnej, którą posiada.

Jeśli przez „klasę nadrzędną” masz na myśli „klasę podstawową”, nie jest tak w przypadku gcc (ani nie oczekuję w żadnym innym kompilatorze).

W przypadku, gdy C pochodzi od B, pochodzi od A, gdzie A jest klasą polimorficzną, instancja C będzie miała dokładnie jedną tabelę.

Kompilator ma wszystkie informacje potrzebne do scalenia danych w tabeli A w B i B w C.

Oto przykład: https://godbolt.org/g/sfdtNh

Zobaczysz, że jest tylko jedna inicjalizacja vtable.

Skopiowałem tutaj dane wyjściowe zestawu dla głównej funkcji z adnotacjami:

main:
        push    rbx

# allocate space for a C on the stack
        sub     rsp, 16

# initialise c's vtable (note: only one)
        mov     QWORD PTR [rsp+8], OFFSET FLAT:vtable for C+16

# use c    
        lea     rdi, [rsp+8]
        call    do_something(C&)

# destruction sequence through virtual destructor
        mov     QWORD PTR [rsp+8], OFFSET FLAT:vtable for B+16
        lea     rdi, [rsp+8]
        call    A::~A() [base object destructor]

        add     rsp, 16
        xor     eax, eax
        pop     rbx
        ret
        mov     rbx, rax
        jmp     .L10

Pełne źródło informacji:

struct A
{
    virtual void foo() = 0;
    virtual ~A();
};

struct B : A {};

struct C : B {

    virtual void extrafoo()
    {
    }

    void foo() override {
        extrafoo();
    }

};

int main()
{
    extern void do_something(C&);
    auto c = C();
    do_something(c);
}
Richard Hodges
źródło
Jeśli weźmiemy przykład, w którym podklasa dziedziczy bezpośrednio z dwóch klas podstawowych, to class Derived : public FirstBase, public SecondBasewtedy mogą istnieć dwie tabele. Możesz uruchomić, g++ -fdump-class-hierarchyaby zobaczyć układ zajęć (pokazany również w moim blogu). Godbolt następnie pokazuje dodatkowy przyrost wskaźnika przed połączeniem, aby wybrać 2. tabelę.
amon