Implementacja czysto abstrakcyjnych klas i interfejsów

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?

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.

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);
}