Em geral, vale a pena usar funções virtuais para evitar ramificações?

21

Parece haver equivalentes aproximados de instruções para equacionar o custo de uma ramificação que as funções virtuais têm uma troca semelhante:

  • falta de instrução vs. cache de dados
  • barreira de otimização

Se você olhar para algo como:

if (x==1) {
   p->do1();
}
else if (x==2) {
   p->do2();
}
else if (x==3) {
   p->do3();
}
...

Você pode ter uma matriz de funções membro ou, se muitas funções dependerem da mesma categorização, ou se existir uma categorização mais complexa, use funções virtuais:

p->do()

Mas, em geral, quão caras são as funções virtuais e as ramificações É difícil testar em plataformas suficientes para generalizar, então eu queria saber se alguém tinha uma regra prática (adorável se fosse tão simples quanto 4 ifs é o ponto de interrupção)

Em geral, as funções virtuais são mais claras e eu me inclinaria para elas. Porém, tenho várias seções altamente críticas nas quais posso alterar o código de funções virtuais para ramificações. Eu preferiria ter pensamentos sobre isso antes de fazer isso. (não é uma alteração trivial ou fácil de testar em várias plataformas)

Glenn Teitelbaum
fonte
12
Bem, quais são seus requisitos de desempenho? Você tem números concretos que precisa atingir ou está envolvido em otimização prematura? Os métodos de ramificação e virtual são extremamente baratos no grande esquema das coisas (por exemplo, em comparação com algoritmos ruins, E / S ou alocação de heap).
amon
4
Faça o que for mais legível / flexível / improvável para atrapalhar mudanças futuras e, depois que você estiver trabalhando , faça um perfil e veja se isso realmente importa. Geralmente não.
Ixrec 02/11/2015
1
Pergunta: "Mas, em geral, quão caras são as funções virtuais ..." Resposta: Filial indireta (wikipedia)
rwong
1
Lembre-se de que a maioria das respostas se baseia na contagem do número de instruções. Como otimizador de código de baixo nível, não confio no número de instruções; você deve prová-los em uma arquitetura específica da CPU - fisicamente - sob condições experimentais. As respostas válidas para essa pergunta devem ser empíricas e experimentais, não teóricas.
Rwong #
3
O problema com esta pergunta é que pressupõe que isso seja grande o suficiente para se preocupar. No software real, os problemas de desempenho ocorrem em grandes pedaços, como fatias de pizza de vários tamanhos. Por exemplo, veja aqui . Não pense que você sabe qual é o maior problema - deixe o programa lhe dizer. Corrija isso e deixe que ele lhe diga qual é o próximo. Faça isso meia dúzia de vezes e talvez você descubra onde as chamadas de função virtual valem a pena se preocupar. Eles nunca tiveram, na minha experiência.
Mike Dunlavey

Respostas:

21

Eu queria pular aqui entre essas respostas já excelentes e admitir que adotei a abordagem feia de realmente retroceder ao antipadrão de alterar o código polimórfico em switchesou if/elseramificar com ganhos medidos. Mas não fiz isso por atacado, apenas pelos caminhos mais críticos. Não precisa ser tão preto e branco.

Como aviso de isenção de responsabilidade, trabalho em áreas como raytracing, onde a correção não é tão difícil de alcançar (e muitas vezes é confusa e aproximada de qualquer maneira), enquanto a velocidade é frequentemente uma das qualidades mais competitivas procuradas. Uma redução no tempo de renderização costuma ser uma das solicitações mais comuns do usuário, com a gente constantemente coçando a cabeça e descobrindo como alcançá-la para os caminhos medidos mais críticos.

Refatoração polimórfica de condicionais

Primeiro, vale a pena entender por que o polimorfismo pode ser preferível a partir de um aspecto de manutenção do que a ramificação condicional ( switchou várias if/elseinstruções). O principal benefício aqui é a extensibilidade .

Com o código polimórfico, podemos introduzir um novo subtipo em nossa base de código, adicionar instâncias a alguma estrutura de dados polimórficos e fazer com que todo o código polimórfico existente ainda funcione automagicamente, sem novas modificações. Se você tiver um monte de código espalhado por uma grande base de código que se assemelha à forma de "Se esse tipo for 'foo', faça isso" , você poderá se deparar com um fardo horrível de atualizar 50 seções díspares de código para introduzir um novo tipo de coisa, e ainda acabam perdendo algumas.

Os benefícios de manutenção do polimorfismo diminuem naturalmente aqui se você tiver apenas algumas ou apenas uma seção da sua base de código que precisa fazer verificações desse tipo.

Barreira de otimização

Eu sugeriria não olhar para isso do ponto de vista de ramificação e pipelining, e analisar mais a partir da mentalidade de design do compilador das barreiras de otimização. Existem maneiras de melhorar a previsão de ramificação que se aplicam a ambos os casos, como classificar dados com base no subtipo (se ele se encaixa em uma sequência).

O que difere mais entre essas duas estratégias é a quantidade de informações que o otimizador tem antecipadamente. Uma chamada de função conhecida fornece muito mais informações, uma chamada indireta de função que chama uma função desconhecida em tempo de compilação leva a uma barreira de otimização.

Quando a função que está sendo chamada é conhecida, os compiladores podem obliterar a estrutura e reduzi-la a pedacinhos, alinhando chamadas, eliminando a sobrecarga de aliasing potencial, fazendo um trabalho melhor na alocação de instruções / registros, possivelmente até reorganizando loops e outras formas de ramificações, gerando dificuldades LUTs em miniatura codificadas quando apropriado (algo que o GCC 5.3 recentemente me surpreendeu com uma switchdeclaração usando uma LUT de dados codificada para os resultados, em vez de uma tabela de salto).

Alguns desses benefícios se perdem quando começamos a introduzir incógnitas em tempo de compilação no mix, como no caso de uma chamada de função indireta, e é aí que a ramificação condicional provavelmente pode oferecer uma vantagem.

Otimização de memória

Tomemos um exemplo de um videogame que consiste em processar uma sequência de criaturas repetidamente em um circuito fechado. Nesse caso, podemos ter um contêiner polimórfico como este:

vector<Creature*> creatures;

Nota: por simplicidade, evitei unique_ptraqui.

... onde Creatureé um tipo de base polimórfica. Nesse caso, uma das dificuldades dos contêineres polimórficos é que eles geralmente desejam alocar memória para cada subtipo separadamente / individualmente (por exemplo: usando o lançamento padrão operator newpara cada criatura individual).

Isso geralmente fará a primeira priorização da otimização (se necessário) com base na memória, em vez de ramificação. Uma estratégia aqui é usar um alocador fixo para cada subtipo, incentivando uma representação contígua alocando em grandes pedaços e agrupando memória para cada subtipo que está sendo alocado. Com essa estratégia, pode definitivamente ajudar a classificar esse creaturescontêiner por sub-tipo (assim como endereço), pois isso não apenas melhora a previsão de ramificação, mas também melhora a localidade de referência (permitindo que várias criaturas do mesmo subtipo sejam acessadas de uma única linha de cache antes do despejo).

Desirtualização parcial de estruturas e loops de dados

Digamos que você passou por todos esses movimentos e ainda deseja mais velocidade. Vale a pena notar que cada passo que arriscamos aqui é uma capacidade de manutenção degradante e já estaremos em um estágio de moagem de metal com retornos de desempenho decrescentes. Portanto, é preciso haver uma demanda de desempenho bastante significativa se entrarmos neste território, onde estamos dispostos a sacrificar a capacidade de manutenção ainda mais para obter ganhos de desempenho cada vez menores.

No entanto, o próximo passo a ser tentado (e sempre com a disposição de rever nossas mudanças, se não ajudar em nada) pode ser a destirtualização manual.

Dica de controle de versão: a menos que você seja muito mais experiente em otimização do que eu, pode valer a pena criar uma nova filial neste momento com a disposição de descartá-la se nossos esforços de otimização falharem, o que pode muito bem acontecer. Para mim, é tudo tentativa e erro após esses tipos de pontos, mesmo com um criador de perfil na mão.

No entanto, não precisamos aplicar essa mentalidade por atacado. Continuando nosso exemplo, digamos que este videogame seja composto principalmente de criaturas humanas, de longe. Nesse caso, podemos desvirtualizar apenas criaturas humanas, elevando-as e criando uma estrutura de dados separada apenas para elas.

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures

Isso implica que todas as áreas em nossa base de código que precisam processar criaturas precisam de um loop de caso especial separado para criaturas humanas. No entanto, isso elimina a sobrecarga dinâmica de envio (ou talvez, mais apropriadamente, a barreira de otimização) para humanos, que são, de longe, o tipo de criatura mais comum. Se essas áreas são grandes em número e podemos pagar, podemos fazer o seguinte:

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures
vector<Creature*> creatures;        // contains humans and other creatures

... se pudermos pagar, os caminhos menos críticos podem permanecer como estão e simplesmente processar todos os tipos de criaturas abstratamente. Os caminhos críticos podem processar humansem um loop e other_creaturesem um segundo loop.

Podemos estender essa estratégia conforme necessário e potencialmente obter alguns ganhos dessa maneira, mas vale a pena observar o quanto estamos degradando a capacidade de manutenção no processo. O uso de modelos de função aqui pode ajudar a gerar o código para humanos e criaturas sem duplicar a lógica manualmente.

Desirtualização parcial de classes

Algo que fiz anos atrás, que era realmente nojento, e nem tenho mais certeza de que seja benéfico (isso foi na era C ++ 03), foi a destirtualização parcial de uma classe. Nesse caso, já estávamos armazenando um ID de classe com cada instância para outros fins (acessado por meio de um acessador na classe base que não era virtual). Lá fizemos algo análogo a isso (minha memória é um pouco nebulosa):

switch (obj->type())
{
   case id_common_type:
       static_cast<CommonType*>(obj)->non_virtual_do_something();
       break;
   ...
   default:
       obj->virtual_do_something();
       break;
}

... onde virtual_do_somethingfoi implementado para chamar versões não virtuais em uma subclasse. É nojento, eu sei, fazer um downcast estático explícito para desvirtualizar uma chamada de função. Não tenho ideia de como isso é benéfico agora, pois não tenho tentado esse tipo de coisa há anos. Com uma exposição ao design orientado a dados, achei a estratégia acima de dividir estruturas e loops de dados de maneira quente / fria muito mais útil, abrindo mais portas para estratégias de otimização (e muito menos feias).

Atacado de Desirtualização

Devo admitir que nunca cheguei tão longe aplicando uma mentalidade de otimização, por isso não tenho idéia dos benefícios. Evitei funções indiretas na previsão nos casos em que sabia que haveria apenas um conjunto central de condicionais (por exemplo: processamento de eventos com apenas um evento de processamento de local central), mas nunca comecei com uma mentalidade polimórfica e otimizei todo o caminho até aqui.

Teoricamente, os benefícios imediatos aqui podem ser uma maneira potencialmente menor de identificar um tipo do que um ponteiro virtual (por exemplo, um único byte se você puder se comprometer com a idéia de que existem 256 tipos exclusivos ou menos), além de eliminar completamente essas barreiras de otimização .

Em alguns casos, também pode ajudar a escrever código mais fácil de manter (em comparação com os exemplos otimizados de desirtualização manual acima) se você usar apenas uma switchinstrução central sem precisar dividir suas estruturas de dados e loops com base no subtipo ou se houver um pedido Dependência nesses casos em que as coisas precisam ser processadas em uma ordem precisa (mesmo que isso nos faça ramificar por todo o lugar). Isso seria nos casos em que você não tem muitos lugares que precisam fazer isso switch.

Geralmente, eu não recomendaria isso, mesmo com uma mentalidade muito crítica para o desempenho, a menos que seja razoavelmente fácil de manter. "Fácil de manter" tenderia a depender de dois fatores dominantes:

  • Não ter uma necessidade real de extensibilidade (por exemplo: sabendo com certeza que você tem exatamente 8 tipos de coisas para processar e nunca mais).
  • Não há muitos locais no seu código que precisam verificar esses tipos (por exemplo, um local central).

... no entanto, eu recomendo o cenário acima na maioria dos casos e iterando em direção a soluções mais eficientes por meio da desirtualização parcial, conforme necessário. Ele oferece muito mais espaço para equilibrar as necessidades de extensibilidade e manutenção com desempenho.

Funções virtuais vs. ponteiros de função

Para completar, notei aqui que havia alguma discussão sobre funções virtuais versus ponteiros de função. É verdade que as funções virtuais exigem um pouco de trabalho extra para serem chamadas, mas isso não significa que elas são mais lentas. Contra-intuitivamente, pode até torná-los mais rápidos.

É contra-intuitivo aqui, porque estamos acostumados a medir o custo em termos de instruções, sem prestar atenção à dinâmica da hierarquia de memória, que tende a ter um impacto muito mais significativo.

Se estivermos comparando um classcom 20 funções virtuais versus um structque armazena 20 ponteiros de função e ambos são instanciados várias vezes, a sobrecarga de memória de cada classinstância, neste caso, 8 bytes para o ponteiro virtual em máquinas de 64 bits, enquanto a memória sobrecarga do structé de 160 bytes.

O custo prático pode ter muito mais erros de cache obrigatórios e não obrigatórios na tabela de ponteiros de função em comparação à classe usando funções virtuais (e possivelmente falhas de página em uma escala de entrada suficientemente grande). Esse custo tende a diminuir o trabalho ligeiramente extra de indexar uma tabela virtual.

Também lidei com bases de código C legadas (mais antigas que eu) em que tornar esses structsindicadores de função preenchidos e instanciado várias vezes, na verdade, proporcionaram ganhos de desempenho significativos (mais de 100% de melhoria), transformando-os em classes com funções virtuais e simplesmente devido à redução maciça no uso de memória, ao aumento da facilidade de cache, etc.

Por outro lado, quando as comparações se tornam mais sobre maçãs com maçãs, também encontrei a mentalidade oposta de traduzir de uma mentalidade de função virtual C ++ para uma mentalidade de ponteiro de função de estilo C para ser útil nesses tipos de cenários:

class Functionoid
{
public:
    virtual ~Functionoid() {}
    virtual void operator()() = 0;
};

... onde a classe estava armazenando uma única função desprezível moderada (ou duas, se contarmos o destruidor virtual). Nesses casos, pode definitivamente ajudar em caminhos críticos para transformar isso em:

void (*func_ptr)(void* instance_data);

... idealmente atrás de uma interface de tipo seguro para ocultar os lançamentos perigosos de / para void*.

Nos casos em que somos tentados a usar uma classe com uma única função virtual, ela pode ajudar rapidamente a usar ponteiros de função. Um grande motivo nem sequer é necessariamente o custo reduzido ao chamar um ponteiro de função. É porque não enfrentamos mais a tentação de alocar cada função separada nas regiões dispersas da pilha, se as estivermos agregando a uma estrutura persistente. Esse tipo de abordagem pode facilitar a sobrecarga associada à pilha e à fragmentação da memória se os dados da instância forem homogêneos, por exemplo, e apenas o comportamento variar.

Definitivamente, há alguns casos em que o uso de ponteiros de função pode ajudar, mas muitas vezes eu encontrei o contrário, se estamos comparando várias tabelas de ponteiros de função com uma única tabela, que requer apenas que um ponteiro seja armazenado por instância de classe . Essa vtable geralmente fica em uma ou mais linhas de cache L1, bem como em loops apertados.

Conclusão

Enfim, essa é a minha pequena opinião sobre esse tópico. Eu recomendo se aventurar nessas áreas com cautela. As medições de confiança, não o instinto, e dada a maneira como essas otimizações geralmente degradam a capacidade de manutenção, vão tão longe quanto você pode pagar (e uma rota sensata seria errar no lado da manutenção).

marstato
fonte
Função virtual são indicadores de função, apenas implementados na viabilidade dessa classe. Quando uma função virtual é chamada, ela é procurada primeiro na criança e na cadeia de herança. É por isso que a herança profunda é muito cara e geralmente é evitada em c ++.
Robert Baron
@ RobertBaron: Eu nunca vi funções virtuais sendo implementadas como você disse (= com uma pesquisa em cadeia através da hierarquia de classes). Geralmente, os compiladores geram uma vtable "achatada" para cada tipo de concreto com todos os ponteiros de função corretos e, em tempo de execução, a chamada é resolvida com uma única consulta direta na tabela; nenhuma penalidade é paga por hierarquias profundas de herança.
Matteo Italia
Matteo, essa foi a explicação que um líder técnico me deu muitos anos atrás. Concedido, era para c ++, então ele pode estar levando em consideração implicações de herança múltipla. Obrigado por esclarecer minha compreensão de como as vtables são otimizadas.
Robert Baron
Obrigado pela boa resposta (+1). Gostaria de saber quanto disso se aplica de forma idêntica ao std :: visit, em vez de funções virtuais.
DaveFar 23/01
13

Observações:

  • Em muitos casos, as funções virtuais são mais rápidas porque a consulta da vtable é uma O(1)operação, enquanto a else if()escada é uma O(n)operação. No entanto, isso só é verdade se a distribuição dos casos for plana.

  • Para um único if() ... else, o condicional é mais rápido porque você salva a sobrecarga da chamada de função.

  • Portanto, quando você tem uma distribuição plana de casos, um ponto de equilíbrio deve existir. A única questão é onde está localizado.

  • Se você usar um switch()em vez de else if()escada ou função virtual chamadas, o compilador pode produzir ainda melhor código: ele pode fazer uma filial para um local que é olhou por cima de uma mesa, mas que não é uma chamada de função. Ou seja, você tem todas as propriedades da chamada de função virtual sem toda a sobrecarga da chamada de função.

  • Se um for muito mais frequente que o resto, iniciar um if() ... elsecom esse caso fornecerá o melhor desempenho: Você executará um único ramo condicional predito corretamente na maioria dos casos.

  • Seu compilador não tem conhecimento da distribuição esperada de casos e assumirá uma distribuição plana.

Como seu compilador provavelmente possui boas heurísticas em relação a quando codificar a switch()como uma else if()escada ou como uma pesquisa de tabela. Eu tenderia a confiar em seu julgamento, a menos que você saiba que a distribuição dos casos é tendenciosa.

Então, meu conselho é este:

  • Se um dos casos supera o restante em termos de frequência, use uma else if()escada classificada .

  • Caso contrário, use uma switch()instrução, a menos que um dos outros métodos torne seu código muito mais legível. Certifique-se de não adquirir um ganho de desempenho negligenciável com legibilidade significativamente reduzida.

  • Se você usou switch()e ainda não está satisfeito com o desempenho, faça a comparação, mas esteja preparado para descobrir que essa switch()já era a possibilidade mais rápida.

cmaster - restabelece monica
fonte
2
Alguns compiladores permitem que as anotações digam ao compilador qual caso é mais provável que seja verdadeiro, e esses compiladores podem produzir código mais rápido desde que a anotação esteja correta.
precisa saber é o seguinte
5
uma operação O (1) não é necessariamente mais rápida no tempo de execução do mundo real do que uma O (n) ou mesmo O (n ^ 20).
Whatsisname
2
@whatsisname Foi por isso que eu disse "em muitos casos". Pela definição de O(1)e O(n)existe um kpara que a O(n)função seja maior que a O(1)função para todos n >= k. A única questão é se é provável que você tenha tantos casos. E, sim, vi switch()declarações com tantos casos que uma else if()escada é definitivamente mais lenta que uma chamada de função virtual ou um despacho carregado.
cmaster - reinstala monica em 4/11
O problema que tenho com esta resposta é o único aviso contra a tomada de decisão com base em um ganho de desempenho totalmente irrelevante, oculto em algum ponto do próximo parágrafo. Tudo o resto aqui finge que pode ser uma boa ideia tomar uma decisão sobre as funções virtuais ifvs. switchvs. virtuais com base no desempenho. Em casos extremamente raros , pode ser, mas na maioria dos casos não é.
Doc Brown
7

Em geral, vale a pena usar funções virtuais para evitar ramificações?

Em geral, sim. Os benefícios para a manutenção são significativos (testes em separação, separação de preocupações, modularidade e extensibilidade aprimoradas).

Mas, em geral, quão caras são as funções virtuais e as ramificações É difícil testar em plataformas suficientes para generalizar, então eu queria saber se alguém tinha uma regra prática (adorável se fosse tão simples quanto 4 ifs é o ponto de interrupção)

A menos que você tenha perfilado seu código e saiba que o envio entre filiais ( a avaliação das condições ) leva mais tempo que os cálculos realizados ( o código nas filiais ), otimize os cálculos realizados.

Ou seja, a resposta correta para "qual é o custo das funções virtuais versus ramificação" é medida e descoberta.

Regra geral : a menos que tenha a situação acima (discriminação de ramificação mais cara que cálculos de ramificação), otimize esta parte do código para o esforço de manutenção (use funções virtuais).

Você diz que deseja que esta seção seja executada o mais rápido possível; Quão rápido é isso? Qual é a sua exigência concreta?

Em geral, as funções virtuais são mais claras e eu me inclinaria para elas. Porém, tenho várias seções altamente críticas nas quais posso alterar o código de funções virtuais para ramificações. Eu preferiria ter pensamentos sobre isso antes de fazer isso. (não é uma alteração trivial ou fácil de testar em várias plataformas)

Use funções virtuais então. Isso permitirá que você otimize por plataforma, se necessário, e ainda mantenha o código do cliente limpo.

utnapistim
fonte
Depois de fazer muita programação de manutenção, vou entrar em contato com um pouco de cautela: as funções virtuais são muito ruins para manutenção, exatamente por causa das vantagens que você lista. O principal problema é a sua flexibilidade; você poderia colocar praticamente qualquer coisa lá ... e as pessoas fazem. É muito difícil argumentar estaticamente sobre o envio dinâmico. No entanto, na maioria dos casos específicos, o código não precisa de toda essa flexibilidade, e a remoção da flexibilidade do tempo de execução pode facilitar o raciocínio sobre o código. No entanto, não quero ir tão longe a ponto de dizer que você nunca deve usar expedição dinâmica; isso é um absurdo.
Eamon Nerbonne
As abstrações mais agradáveis ​​com as quais trabalhar são raras (ou seja, uma base de código possui apenas algumas abstrações opacas), mas ainda super robusta. Basicamente: não coloque algo atrás de uma abstração dinâmica de despacho apenas porque ela tem uma forma semelhante para um caso em particular; faça isso apenas se você não puder conceber razoavelmente qualquer razão para se preocupar com alguma distinção entre os objetos que compartilham essa interface. Se você não pode: é melhor ter um auxiliar não encapsulante do que uma abstração com vazamento. E mesmo então; existe uma troca entre flexibilidade de tempo de execução e flexibilidade da base de código.
Eamon Nerbonne
5

As outras respostas já fornecem bons argumentos teóricos. Gostaria de adicionar os resultados de um experimento que realizei recentemente para estimar se seria uma boa ideia implementar uma máquina virtual (VM) usando um switchcódigo grande acima do código operacional ou, melhor dizendo, interpretá-lo como um índice em uma matriz de ponteiros de função. Embora isso não seja exatamente o mesmo que uma virtualchamada de função, acho que é razoavelmente próximo.

Eu escrevi um script Python para gerar aleatoriamente o código C ++ 14 para uma VM com um tamanho de conjunto de instruções escolhido aleatoriamente (embora não uniformemente, amostrando o intervalo baixo mais densamente) entre 1 e 10000. A VM gerada sempre teve 128 registros e nenhum RAM. As instruções não são significativas e todas têm o seguinte formato.

inline void
op0004(machine_state& state) noexcept
{
  const auto c = word_t {0xcf2802e8d0baca1dUL};
  const auto r1 = state.registers[58];
  const auto r2 = state.registers[69];
  const auto r3 = ((r1 + c) | r2);
  state.registers[6] = r3;
}

O script também gera rotinas de despacho usando uma switchinstrução…

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  switch (opcode)
  {
  case 0x0000: op0000(state); return 0;
  case 0x0001: op0001(state); return 0;
  // ...
  case 0x247a: op247a(state); return 0;
  case 0x247b: op247b(state); return 0;
  default:
    return -1;  // invalid opcode
  }
}

… E uma matriz de ponteiros de função.

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  typedef void (* func_type)(machine_state&);
  static const func_type table[VM_NUM_INSTRUCTIONS] = {
    op0000,
    op0001,
    // ...
    op247a,
    op247b,
  };
  if (opcode >= VM_NUM_INSTRUCTIONS)
    return -1;  // invalid opcode
  table[opcode](state);
  return 0;
}

Qual rotina de despacho foi gerada foi escolhida aleatoriamente para cada VM gerada.

Para o benchmarking, o fluxo de códigos op foi gerado por um std::random_devicemecanismo aleatório aleatório ( std::mt19937_64) de twister Mersenne ( ).

O código para cada VM foi compilado com o GCC 5.2.0 usando os comutadores -DNDEBUG, -O3e -std=c++14. Primeiro, foi compilado usando a -fprofile-generateopção e os dados de perfil coletados para simular 1000 instruções aleatórias. O código foi recompilado com a -fprofile-useopção permitindo otimizações com base nos dados de perfil coletados.

A VM foi então exercitada (no mesmo processo) quatro vezes por 50 000 000 ciclos e o tempo para cada execução foi medido. A primeira execução foi descartada para eliminar os efeitos de cache frio. O PRNG não foi reproduzido novamente entre as execuções, para que não executassem a mesma sequência de instruções.

Usando essa configuração, 1000 pontos de dados para cada rotina de expedição foram coletados. Os dados foram coletados em uma APU AMD A8-6600K de quatro núcleos com cache de 2048 KiB executando GNU / Linux de 64 bits sem uma área de trabalho gráfica ou outros programas em execução. A seguir, é mostrado um gráfico do tempo médio da CPU (com desvio padrão) por instrução para cada VM.

insira a descrição da imagem aqui

A partir desses dados, eu poderia ter certeza de que usar uma tabela de funções é uma boa idéia, exceto talvez para um número muito pequeno de códigos operacionais. Não tenho uma explicação para os outliers da switchversão entre 500 e 1000 instruções.

Todo o código fonte da referência, bem como os dados experimentais completos e um gráfico de alta resolução podem ser encontrados no meu site .

5gon12eder
fonte
3

Além da boa resposta do cmaster, que eu votei, lembre-se de que os indicadores de função geralmente são estritamente mais rápidos que as funções virtuais. O despacho de funções virtuais geralmente envolve primeiro seguir um ponteiro do objeto para a tabela, indexar adequadamente e, em seguida, desreferenciar um ponteiro de função. Portanto, a etapa final é a mesma, mas há etapas extras inicialmente. Além disso, as funções virtuais sempre tomam "isso" como argumento, os ponteiros de função são mais flexíveis.

Outra coisa a ter em mente: se o caminho crítico envolve um loop, pode ser útil classificá-lo por destino de despacho. Obviamente, isso é nlogn, enquanto que percorrer o loop é apenas n, mas se você for percorrer muitas vezes isso pode valer a pena. Ao classificar por destino de despacho, você garante que o mesmo código seja executado repetidamente, mantendo-o quente no icache, minimizando as perdas de cache.

Uma terceira estratégia a ter em mente: se você decidir se afastar das funções virtuais / ponteiros de função em direção às estratégias if / switch, também poderá ser bem atendido alternando de objetos polimórficos para algo como boost :: variant (que também fornece a opção caso na forma de abstração do visitante). Objetos polimórficos precisam ser armazenados pelo ponteiro base, para que seus dados estejam em todo o lugar no cache. Isso pode facilmente ter uma influência maior no caminho crítico do que o custo da pesquisa virtual. Considerando que a variante é armazenada em linha como uma união discriminada; tem tamanho igual ao maior tipo de dados (mais uma pequena constante). Se seus objetos não diferem muito em tamanho, essa é uma ótima maneira de lidar com eles.

Na verdade, eu não ficaria surpreso se a melhoria da coerência do cache dos seus dados tivesse um impacto maior do que a sua pergunta original, então eu definitivamente investigaria mais.

Nir Friedman
fonte
Não sei se uma função virtual envolve "etapas extras". Dado que o layout da classe é conhecido em tempo de compilação, é essencialmente o mesmo que um acesso à matriz. Ou seja, há um ponteiro para o topo da classe, e o deslocamento da função é conhecido; basta adicionar isso, ler o resultado e esse é o endereço. Não há muita sobrecarga.
1
Envolve etapas extras. O próprio vtable contém ponteiros de função, portanto, quando você o faz, alcançou o mesmo estado em que iniciou com um ponteiro de função. Tudo antes de você chegar à vtable é um trabalho extra. As classes não contêm suas vtables, elas contêm ponteiros para vtables e, após esse ponteiro, é uma dereferência extra. De fato, às vezes há uma terceira desreferência, pois as classes polimórficas geralmente são mantidas pelo ponteiro da classe base; portanto, é necessário desreferenciar um ponteiro para obter o endereço da tabela (para desreferê-lo ;-)).
Nir Friedman
Por outro lado, o fato de que a vtable é armazenada fora da instância pode realmente ser útil para a localidade temporal, por exemplo, um monte de estruturas díspares de ponteiros de função, onde cada ponteiro de função é armazenado em um endereço de memória diferente. Nesses casos, uma única tabela com um milhão de vptrs pode superar um milhão de tabelas de ponteiros de função facilmente (começando com apenas o consumo de memória). Pode ser uma espécie de reviravolta aqui - não é tão fácil de quebrar. Geralmente, eu concordo que o ponteiro de função geralmente é um pouco mais barato, mas não é tão fácil colocar um acima do outro.
Penso, em outras palavras, onde as funções virtuais começam a superar rápida e grosseiramente os indicadores de função é quando você tem um monte de instâncias de objeto envolvidas (onde cada objeto precisaria armazenar vários indicadores de função ou um único vptr). Os ponteiros de função tendem a ser mais baratos se você tiver, digamos, apenas um ponteiro de função armazenado na memória, que será chamado de carregamento de barco várias vezes. Caso contrário, os ponteiros de função podem começar a ficar mais lentos com a quantidade de redundância de dados e falhas de cache resultantes de muitas memórias redundantemente monótonas e apontando para o mesmo endereço.
É claro que, com os ponteiros de função, você também pode armazená-los em um local central, mesmo que sejam compartilhados por um milhão de objetos separados, para evitar sobrecarregar a memória e obter um monte de erros de cache. Mas então eles começam a se tornar equivalentes aos vpointers, envolvendo o acesso do ponteiro a um local compartilhado na memória para obter os endereços de função reais que queremos chamar. A questão fundamental aqui é: você armazena o endereço da função mais próximo dos dados que você está acessando atualmente ou em um local central? As tabelas vt permitem apenas o último. Ponteiros de função permitem nos dois sentidos.
2

Posso apenas explicar por que acho que esse é um problema XY ? (Você não está sozinho em perguntar a eles.)

Suponho que seu objetivo real é economizar tempo em geral, não apenas entender um ponto sobre falhas de cache e funções virtuais.

Aqui está um exemplo de ajuste de desempenho real , em software real.

Em software real, as coisas são feitas que, não importa quão experiente o programador seja, poderiam ser feitas melhor. Não se sabe o que são até que o programa seja escrito e o ajuste de desempenho possa ser feito. Quase sempre há mais de uma maneira de acelerar o programa. Afinal, para dizer que um programa é ideal, você está dizendo que, no panteão de possíveis programas para resolver seu problema, nenhum deles leva menos tempo. Sério?

No exemplo ao qual vinculei, ele levou originalmente 2700 microssegundos por "trabalho". Uma série de seis problemas foram resolvidos, girando no sentido anti-horário ao redor da pizza. A primeira aceleração removeu 33% das vezes. O segundo removeu 11%. Mas observe, o segundo não era de 11% no momento em que foi encontrado, era de 16%, porque o primeiro problema havia desaparecido . Da mesma forma, o terceiro problema foi ampliado de 7,4% para 13% (quase o dobro), porque os dois primeiros problemas se foram.

No final, esse processo de ampliação permitiu eliminar quase 3,7 microssegundos. Isso representa 0,14% do tempo original ou uma aceleração de 730x.

insira a descrição da imagem aqui

A remoção dos problemas inicialmente grandes fornece uma quantidade moderada de aceleração, mas abre o caminho para a remoção de problemas posteriores. Esses problemas posteriores poderiam inicialmente ter sido partes insignificantes do total, mas depois que os problemas iniciais são removidos, esses pequenos se tornam grandes e podem produzir grandes acelerações. (É importante entender que, para obter esse resultado, nada pode ser desperdiçado, e esta postagem mostra como eles podem ser facilmente).

insira a descrição da imagem aqui

O programa final foi ideal? Provavelmente não. Nenhuma das acelerações teve algo a ver com falhas de cache. As falhas de cache importariam agora? Talvez.

EDIT: Estou recebendo votos negativos de pessoas que se encontram nas "seções altamente críticas" da pergunta do OP. Você não sabe que algo é "altamente crítico" até saber qual fração do tempo representa. Se o custo médio desses métodos chamados for de 10 ciclos ou mais, com o tempo, o método de envio a eles provavelmente não é "crítico", comparado ao que eles estão realmente fazendo. Vejo isso repetidamente, onde as pessoas tratam "a necessidade de cada nanossegundo" como uma razão para serem tostões e tolos.

Mike Dunlavey
fonte
ele já disse que possui várias "seções altamente críticas" que exigem todos os últimos nanossegundos de desempenho. Então isso não é uma resposta para a pergunta que ele fez (mesmo que seria uma grande resposta para alguém da pergunta)
gbjbaanb
2
@gbjbaanb: Se todos os últimos nanossegundos contam, por que a pergunta começa com "em geral"? Isso não faz sentido. Quando os nanossegundos contam, você não pode procurar respostas gerais, o que o compilador faz, o hardware, as variações e as medidas.
gnasher729
@ gnasher729 Não sei, mas por que termina com "seções altamente críticas"? Eu acho que, como o slashdot, sempre se deve ler o conteúdo, e não apenas o título!
Gbjbaanb
2
@gbjbaanb: Todo mundo diz que tem "seções altamente críticas". Como eles sabem? Não sei se algo é crítico até que eu colete, digamos, 10 amostras e a veja em 2 ou mais delas. Em um caso como esse, se os métodos chamados exigirem mais de 10 instruções, a sobrecarga da função virtual provavelmente será insignificante.
Mike Dunlavey
@ gnasher729: Bem, a primeira coisa que faço é obter amostras de pilha e, em cada uma, examinar o que o programa está fazendo e por quê. Então, se ele passa todo o tempo nas folhas da árvore de chamadas, e todas as chamadas são realmente inevitáveis , importa o que o compilador e o hardware fazem. Você só sabe que o envio de métodos importa se as amostras chegarem ao processo de envio de métodos.
Mike Dunlavey