Implementação de classes e interfaces abstratas puras

Embora isso não seja obrigatório no padrão C ++, parece que o GCC, por exemplo, implementa classes-pai, incluindo as abstratas puras, inclui um ponteiro para a tabela-v dessa classe abstrata em cada instanciação da classe em questão .

Naturalmente, isso incha o tamanho de todas as instâncias dessa classe por um ponteiro para cada classe pai que ela possui.

Mas notei que muitas classes e estruturas C # têm muitas interfaces pai, que são basicamente classes abstratas puras. Eu ficaria surpreso se cada instância Decimal, digamos , estivesse cheia de 6 ponteiros para todas as suas várias interfaces.

Portanto, se o C # faz interfaces de maneira diferente, como as faz, pelo menos em uma implementação típica (eu entendo que o próprio padrão pode não definir essa implementação)? E alguma implementação de C ++ tem como evitar o tamanho do objeto quando adiciona pais virtuais puros às classes?

Nas implementações C # e Java, os objetos geralmente têm um único ponteiro para sua classe. Isso é possível porque são linguagens de herança única. A estrutura de classes então contém a tabela v para a hierarquia de herança única. Mas chamar métodos de interface também tem todos os problemas de herança múltipla. Isso geralmente é resolvido colocando vtables adicionais para todas as interfaces implementadas na estrutura da classe. Isso economiza espaço em comparação às implementações típicas de herança virtual em C ++, mas torna o envio do método de interface mais complicado - o que pode ser parcialmente compensado pelo cache.

Por exemplo, na JVM do OpenJDK, cada classe contém uma matriz de vtables para todas as interfaces implementadas (uma interface de tabela é chamada itable ). Quando um método de interface é chamado, essa matriz é pesquisada linearmente pela itable dessa interface, então o método pode ser despachado através dessa itable. O armazenamento em cache é usado para que cada site de chamada se lembre do resultado do envio do método, portanto, essa pesquisa só precisa ser repetida quando o tipo de objeto concreto é alterado. Pseudocódigo para envio de método:

// 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
}

(Compare o código real no interpretador do OpenJDK HotSpot ou no compilador x86 .)

C # (ou mais precisamente, o CLR) usa uma abordagem relacionada. No entanto, aqui os itables não contêm ponteiros para os métodos, mas são mapas de slots: eles apontam para entradas na tabela principal da classe. Assim como no Java, ter de procurar a itable correta é apenas o pior cenário possível, e espera-se que o cache no site de chamada possa evitar essa pesquisa quase sempre. O CLR usa uma técnica chamada Virtual Stub Dispatch para corrigir o código de máquina compilado por JIT com diferentes estratégias de armazenamento em cache. Pseudo-código:

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
}

A principal diferença para o pseudocódigo do OpenJDK é que, no OpenJDK, cada classe possui uma matriz de todas as interfaces implementadas direta ou indiretamente, enquanto o CLR mantém apenas uma matriz de mapas de slots para interfaces que foram implementadas diretamente nessa classe. Portanto, precisamos percorrer a hierarquia de herança para cima até encontrar um mapa de slots. Para hierarquias profundas de herança, isso resulta em economia de espaço. Isso é particularmente relevante no CLR devido à maneira como os genéricos são implementados: para uma especialização genérica, a estrutura da classe é copiada e os métodos na tabela principal podem ser substituídos por especializações. Os mapas de slots continuam apontando para as entradas vtable corretas e, portanto, podem ser compartilhados entre todas as especializações genéricas de uma classe.

Como observação final, há mais possibilidades de implementar o envio de interface. Em vez de colocar o ponteiro vtable / itable no objeto ou na estrutura de classes, podemos usar ponteiros gordos para o objeto, que são basicamente um (Object*, VTable*)par. A desvantagem é que isso duplica o tamanho dos ponteiros e que upcasts (de um tipo concreto para um tipo de interface) não são livres. Mas é mais flexível, tem menos indireção e também significa que as interfaces podem ser implementadas externamente a partir de uma classe. As abordagens relacionadas são usadas pelas interfaces Go, características de Rust e classes de tipo Haskell.

Referências e leituras adicionais:

• Wikipedia: cache embutido . Discute abordagens de cache que podem ser usadas para evitar a pesquisa cara de métodos. Normalmente não é necessário para o envio baseado em vtable, mas é muito desejável para mecanismos de envio mais caros, como as estratégias de envio de interface acima.
• OpenJDK Wiki (2013): chamadas de interface . Discute itables.
• Pobar, Neward (2009): SSCLI 2.0 Internals. O capítulo 5 do livro discute detalhadamente os mapas de slots. Nunca foi publicado, mas disponibilizado pelos autores em seus blogs . O link PDF foi movido desde então. Este livro provavelmente não reflete mais o estado atual do CLR.
• CoreCLR (2006): Despacho de Stub Virtual . In: Livro do Tempo de Execução. Discute mapas de slots e cache para evitar pesquisas caras.
• Kennedy, Syme (2001): Design e Implementação de Genéricos para o .NET Common Language Runtime . ( Link em PDF ). Discute várias abordagens para implementar genéricos. Os genéricos interagem com o envio de métodos, porque os métodos podem ser especializados, portanto, as vtables precisam ser reescritas.

Naturalmente, isso incha o tamanho de todas as instâncias dessa classe por um ponteiro para cada classe pai que ela possui.

Se por "classe pai" você quer dizer "classe base", esse não é o caso no gcc (nem eu espero em nenhum outro compilador).

No caso de C deriva de B deriva de A onde A é uma classe polimórfica, a instância C terá exatamente uma tabela.

O compilador possui todas as informações necessárias para mesclar os dados na tabela de A em B e B em C.

Aqui está um exemplo: https://godbolt.org/g/sfdtNh

Você verá que há apenas uma inicialização de uma vtable.

Copiei a saída do assembly para a função principal aqui com anotações:

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

Fonte completa para referência:

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