Quando os custos das chamadas de funções ainda são importantes nos compiladores modernos?

Depende do seu domínio.

Se você está escrevendo código para um microcontrolador de baixa potência, então o custo da chamada de método pode ser significativo. Mas se você estiver criando um site ou aplicativo normal, o custo da chamada do método será insignificante comparado ao resto do código. Nesse caso, sempre valerá a pena se concentrar em algoritmos e estruturas de dados corretos em vez de micro-otimizações, como as chamadas de método.

E também há questão de compilador inlining os métodos para você. A maioria dos compiladores é inteligente o suficiente para funções embutidas onde é possível.

E por último, há uma regra de ouro de desempenho: SEMPRE PERFIL PRIMEIRO. Não escreva código "otimizado" com base em suposições. Se você estiver incomum, escreva os dois casos e veja qual é o melhor.

A sobrecarga de chamada de função depende inteiramente do idioma e de qual nível você está otimizando.

Em um nível ultrabaixo, chamadas de função e, mais ainda, chamadas de método virtual podem ser caras se levarem a erro de desvio de filial ou falhas de cache de CPU. Se você escreveu assembler , você também saberá que precisa de algumas instruções extras para salvar e restaurar registros em torno de ligar. Não é verdade que um compilador “suficientemente inteligente” seria capaz de embutir as funções corretas para evitar essa sobrecarga, porque os compiladores são limitados pela semântica da linguagem (especialmente em torno de recursos como o despacho do método de interface ou bibliotecas carregadas dinamicamente). p>

Em um nível alto, linguagens como Perl, Python, Ruby fazem muita contabilidade por chamada de função, tornando essas comparativamente caras. Isso é agravado pela meta-programação. Uma vez, aumentei o software Python 3x apenas usando as chamadas de função de um loop muito quente. No código de desempenho crítico, as funções auxiliares inline podem ter um efeito notável.

Mas a grande maioria dos softwares não é tão extremamente crítica quanto ao desempenho que você seria capaz de perceber a sobrecarga das chamadas de função. Em qualquer caso, escrever código limpo e simples é compensado:

• Se o seu código não é crítico para o desempenho, isso facilita a manutenção. Mesmo em softwares críticos para desempenho, a maioria do código não será um “ponto de acesso”.

• Se o seu código é crítico para o desempenho, um código simples facilita a compreensão do código e identifica oportunidades de otimização. Os maiores ganhos geralmente não vêm de micro-otimizações como funções inline, mas de melhorias algorítmicas. Ou frases diferentes: não faça a mesma coisa mais rápido. Encontre uma maneira de fazer menos.

Note que "código simples" não significa "fatorado em mil funções minúsculas". Cada função também introduz um pouco de sobrecarga cognitiva - é mais difícil razão sobre código mais abstrato. Em algum momento, essas funções minúsculas podem fazer tão pouco que não usá-las simplificaria seu código.

Quase todos os ditados sobre o código de ajuste para o desempenho são casos especiais da lei de Amdahl . A declaração curta e bem-humorada da lei de Amdahl é

If one piece of your program takes 5% of runtime, and you optimize that piece so that it now takes zero percent of runtime, the program as a whole will only be 5% faster.

(otimizar coisas abaixo de zero por cento do tempo de execução é totalmente possível: quando você se senta para otimizar um programa grande e complicado, é bem provável que ele descubra que está gastando pelo menos parte de seu tempo de execução em coisas t precisa fazer em tudo .

Mas, se há um truque que você pode fazer que faz all a função chamar mais rápido, esse truque provavelmente vale a pena. Desenvolvedores de compiladores gastam muito tempo otimizando função "prólogos" e "epílogos", porque isso beneficia todos os programas compilados com esse compilador, mesmo que seja apenas um pouquinho para cada.

E, se você tem motivos para acreditar que um programa está gastando muito do seu tempo de execução apenas fazendo chamadas de função, então você deve começar a pensar se algumas dessas chamadas de função são desnecessárias. Aqui estão algumas regras básicas para saber quando você deve fazer isso:

• Se o tempo de execução por invocação de uma função for menor que um milissegundo, mas essa função for chamada centenas de milhares de vezes, provavelmente ela deve estar alinhada.

• Se um perfil do programa mostrar milhares de funções, e nenhuma delas exigir mais do que 0.1% de tempo de execução, então a sobrecarga de chamada de função provavelmente é significativa em termos agregados. / p>

• Se você tiver " código de lasanha ," no qual existem muitas camadas de abstração que dificilmente trabalhar além de despachar para a próxima camada, e todas essas camadas são implementadas com chamadas de método virtual, então há uma boa chance de a CPU estar perdendo muito tempo nas barracas de pipeline indireto. Infelizmente, a única cura para isso é se livrar de algumas camadas, o que geralmente é muito difícil.

Eu vou contestar esta citação:

There's almost always a tradeoff between writing readable code and writing performant code.

Esta é uma declaração realmente enganosa e uma atitude potencialmente perigosa. Existem alguns casos específicos em que você tem que fazer uma troca, mas em geral os dois fatores são independentes.

Um exemplo de uma troca necessária é quando você tem um algoritmo simples versus um mais complexo, mas com maior desempenho. Uma implementação hashtable é claramente mais complexa do que uma implementação de lista vinculada, mas a pesquisa será mais lenta, portanto, talvez seja necessário negociar a simplicidade (que é um fator de legibilidade) para o desempenho.

Em relação à sobrecarga de chamada de função, transformar um algoritmo recursivo em um iterativo pode ter um benefício significativo, dependendo do algoritmo e da linguagem. Mas isso é novamente um cenário muito específico e, em geral, a sobrecarga das chamadas de função será insignificante ou otimizada.

(Algumas linguagens dinâmicas, como o Python, possuem uma sobrecarga significativa de chamada de método. Mas, se o desempenho se tornar um problema, você provavelmente não deveria estar usando o Python em primeiro lugar.)

A maioria dos princípios para código legível - formatação consistente, nomes de identificador significativos, comentários apropriados e úteis etc. não afetam o desempenho. E alguns - como o uso de enums em vez de strings - também têm benefícios de desempenho.

A sobrecarga da chamada de função não é importante na maioria dos casos.

No entanto, o maior ganho do código inlining é otimizar o novo código após inlining .

Por exemplo, se você chamar uma função com um argumento constante, o otimizador pode agora fazer uma dobra constante do argumento onde ele não pôde antes de inlining a chamada. Se o argumento for um ponteiro de função (ou lambda), o otimizador pode agora inline as chamadas para aquele lambda também.

Este é um grande motivo pelo qual as funções virtuais e os ponteiros de função não são atraentes, pois você não pode inline-los a menos que o ponteiro de função real tenha sido dobrado constantemente até o local da chamada.

Supondo que o desempenho é importante para o seu programa e, de fato, tem muitas e muitas chamadas, o custo ainda pode ou não ser relevante, dependendo do tipo de chamada.

Se a função chamada for pequena e o compilador for capaz de incorporá-la, o custo será essencialmente zero. Compiladores modernos / implementações de linguagem possuem JIT, otimizações de tempo de link e / ou sistemas de módulo projetados para maximizar a capacidade de funções embutidas quando isso é benéfico.

OTOH, há um custo não óbvio para as chamadas de função: sua mera existência pode inibir as otimizações do compilador antes e depois da chamada.

Se o compilador não puder raciocinar sobre o que a função chamada faz (por exemplo, despacho virtual / dinâmico ou uma função em uma biblioteca dinâmica), pode ser que suponha pessimicamente que a função poderia ter algum efeito colateral - lançar um exceção, modificar o estado global ou alterar qualquer memória vista através de ponteiros. O compilador pode ter que salvar valores temporários para memória de volta e relê-los após a chamada. Ele não poderá reordenar as instruções em torno da chamada, portanto, pode não ser capaz de vetorizar loops ou desviar computações redundantes de loops.

Por exemplo, se você chamar desnecessariamente uma função em cada iteração de loop:

for(int i=0; i < /* gasp! */ strlen(s); i++) x ^= s[i];

O compilador pode saber que é uma função pura e movê-lo para fora do loop (em um caso terrível como este exemplo, até mesmo corrige o algoritmo acidental O (n ^ 2) como O (n)):

for(int i=0, end=strlen(s); i < end; i++) x ^= s[i];

E, quem sabe, até mesmo reescrever o loop para processar elementos de 4/8/16 de uma vez usando instruções de largura / SIMD.

Mas se você adicionar uma chamada a algum código opaco no loop, mesmo que a chamada não faça nada e seja super barata, o compilador deve assumir o pior - que a chamada acessará uma variável global que aponta para o mesmo memória como s altera seu conteúdo (mesmo que seja const em sua função, pode ser diferente de const em qualquer outro lugar), impossibilitando a otimização:

for(int i=0; i < strlen(s); i++) {
    x ^= s[i];
    do_nothing();
}

Este artigo antigo pode responder à sua pergunta:

Guy Lewis Steele, Jr.. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.

Resumo:

Folklore states that GOTO statements are "cheap", while procedure calls are "expensive". This myth is largely a result of poorly designed language implementations. The historical growth of this myth is considered. Both theoretical ideas and an existing implementation are discussed which debunk this myth. It is shown that the unrestricted use of procedure calls permits great stylish freedom. In particular, any flowchart can be written as a "structured" program without introducing extra variables. The difficulty with the GOTO statement and the procedure call is characterized as a conflict between abstract programming concepts and concrete language constructs.

• Em C ++, tenha cuidado ao projetar chamadas de função que copiam argumentos, o padrão é "passar por valor". A sobrecarga da chamada de função devido a registros de salvamento e outras coisas relacionadas a quadros de pilha podem ser sobrecarregadas por uma cópia não intencional (e potencialmente muito cara) de um objeto.

• Existem otimizações relacionadas a quadros de pilha que você deve investigar antes de desistir do código altamente fatorado.

• Na maioria das vezes, quando tive que lidar com um programa lento, descobri que fazer mudanças algorítmicas gerou muito mais acelerações do que as chamadas de função em linha. Por exemplo: outro engenheiro refez um analisador que preencheu uma estrutura de mapa de mapas. Como parte disso, ele removeu um índice em cache de um mapa para um logicamente associado. Esse foi um bom movimento de robustez de código, no entanto ele tornou o programa inutilizável devido a um fator de 100 de lentidão devido à execução de uma consulta de hash para todos os acessos futuros versus o uso do índice armazenado. A criação de perfil mostrou que a maior parte do tempo foi gasto na função hash.

Como os outros dizem, você deve medir primeiro o desempenho do seu programa, e provavelmente não encontrará diferença na prática.

Do function call costs still matter in modern compilers?

Observe as palavras-chave "função" e "compiladores". Sua cotação é sutilmente diferente:

Remember that the cost of a method call can be significant, depending on the language.

Isto está falando sobre métodos , no sentido orientado a objeto.

Em particular, precisamos saber sobre despacho estático vs despacho dinâmico . Eu vou ignorar otimizações para o momento.

Em uma linguagem como C, geralmente chamamos funções com despacho estático . Por exemplo:

int foo(int x) {
  return x + 1;
}

int bar(int y) {
  return foo(y);
}

int main() {
  return bar(42);
}

Quando o compilador vê a chamada foo(y) , ele sabe a qual função o nome foo está se referindo, então o programa de saída pode ir direto para a função foo , que é bem barata. Isso é o que despacho estático significa.

A alternativa é despacho dinâmico , onde o compilador não sabe qual função está sendo chamada. Por exemplo, aqui está um código Haskell (já que o equivalente C seria confuso!):

foo x = x + 1

bar f x = f x

main = print (bar foo 42)

Aqui, a função bar está chamando seu argumento f , que pode ser qualquer coisa. Portanto, o compilador não pode simplesmente compilar bar para uma instrução de salto rápido, porque não sabe para onde ir. Em vez disso, o código que geramos para bar cancelará a referência f para descobrir para qual função ele está apontando e, em seguida, passará para ele. Isso é o que envio dinâmico significa.

Ambos os exemplos são para funções . Você mencionou métodos , que podem ser considerados como um estilo particular de função despachada dinamicamente. Por exemplo, aqui está um pouco do Python:

class A:
  def __init__(self, x):
    self.x = x

  def foo(self):
    return self.x + 1

def bar(y):
  return y.foo()

z = A(42)
bar(z)

A chamada y.foo() usa o despacho dinâmico, pois está procurando o valor da propriedade foo no objeto y e chamando o que encontrar; ele não sabe que y terá a classe A ou que a classe A contém um método foo , por isso não podemos simplesmente ir direto para ela.

OK, essa é a ideia básica. Note que o despacho estático é mais rápido que o despacho dinâmico independentemente de compilar ou interpretar; tudo o mais sendo igual. A desreferenciação incorre em um custo extra de qualquer forma.

Então, como isso afeta os compiladores modernos e otimizadores?

A primeira coisa a notar é que o despacho estático pode ser otimizado mais strongmente: quando sabemos para qual função estamos indo, podemos fazer coisas como inlining. Com o despacho dinâmico, não sabemos se estamos pulando até o tempo de execução, por isso não há muita otimização que possamos fazer.

Em segundo lugar, é possível em algumas línguas inferir onde alguns despachos dinâmicos terminarão, e assim otimizá-los para o despacho estático. Isso nos permite realizar outras otimizações, como inlining, etc.

No exemplo acima do Python, tal inferência é bastante inútil, uma vez que o Python permite que outro código substitua classes e propriedades, portanto é difícil deduzir muito do que será válido em todos os casos.

Se a nossa linguagem nos permitir impor mais restrições, por exemplo, limitando y à classe A usando uma anotação, poderíamos usar essas informações para inferir a função de destino. Em linguagens com subclasses (que são quase todas as linguagens com classes!) Isso não é suficiente, pois y pode ter uma (sub) classe diferente, então precisaríamos de informações extras como as anotações final do Java para saber exatamente quais função será chamada.

Haskell não é uma linguagem OO, mas podemos inferir o valor de f inlining bar (que é estaticamente despachado) em main , substituindo foo por% código%. Como o destino de y in foo é estatisticamente conhecido, a chamada se torna estaticamente despachada e provavelmente será alinhada e otimizada completamente (já que essas funções são pequenas, é mais provável que o compilador as incorpore; embora possamos ' conte com isso em geral).

Por isso, o custo se resume a:

• O idioma envia sua chamada estaticamente ou dinamicamente?
• Se for o último, a linguagem permite que a implementação deduza o alvo usando outras informações (por exemplo, tipos, classes, anotações, inlining, etc.)?
• Quão agressivamente o despacho estático (inferido ou não) pode ser otimizado?

Se você estiver usando uma linguagem "muito dinâmica", com muito despacho dinâmico e poucas garantias disponíveis para o compilador, todas as chamadas incorrerão em um custo. Se você estiver usando uma linguagem "muito estática", um compilador maduro produzirá um código muito rápido. Se você está no meio, então pode depender do seu estilo de codificação e de quão inteligente é a implementação.

Sim, uma predição de ramificação perdida é mais cara no hardware moderno do que há décadas, mas os compiladores ficaram muito mais inteligentes ao otimizar isso.

Como exemplo, considere o Java. À primeira vista, a sobrecarga da chamada de função deve ser particularmente dominante nesta linguagem:

• funções minúsculas são difundidas devido à convenção JavaBean
• funções padrão para virtual e geralmente são
• a unidade de compilação é a classe; o tempo de execução suporta o carregamento de novas classes a qualquer momento, incluindo subclasses que substituem métodos monomórficos anteriores

Horrorizado por essas práticas, o programador médio de C previa que Java deveria ser pelo menos uma ordem de magnitude mais lenta que C. E há 20 anos ele estaria certo. No entanto, os benchmarks modernos colocam o código Java idiomático dentro de alguns por cento do código C equivalente. Como isso é possível?

Uma das razões é que as chamadas in-line das funções JVMs modernas são normais. Faz isso usando inline especulativo:

1. O código recém-carregado é executado sem otimização. Durante esse estágio, para cada site de chamada, a JVM controla quais métodos foram realmente chamados.
2. Assim que o código for identificado como hotspot de desempenho, o tempo de execução usará essas estatísticas para identificar o caminho de execução mais provável e in-line, prefixando-o com uma ramificação condicional, caso a otimização especulativa não se aplique.

Ou seja, o código:

int x = point.getX();

é reescrito para

if (point.class != Point) GOTO interpreter;
x = point.x;

E, é claro, o tempo de execução é inteligente o suficiente para passar por essa verificação de tipo, desde que o ponto não seja atribuído ou elidá-lo se o tipo for conhecido pelo código de chamada.

Em resumo, se até mesmo o Java gerenciar o preenchimento automático de métodos, não há nenhuma razão inerente para que um compilador não suporte inlining automático, e todos os motivos para isso, porque inlining é altamente benéfico em processadores modernos. Portanto, dificilmente posso imaginar qualquer compilador mainstream moderno ignorando essa estratégia básica de otimização, e presumiria um compilador capaz disso, a menos que se prove o contrário.

Remember that the cost of a method call can be significant, depending on the language. There's almost always a tradeoff between writing readable code and writing performant code.

Isso é, infelizmente, altamente dependente de:

• o conjunto de ferramentas do compilador, incluindo o JIT, se houver,
• o domínio.

Em primeiro lugar, a primeira lei de otimização de desempenho é perfil primeiro . Existem muitos domínios em que o desempenho da parte do software é irrelevante para o desempenho de toda a pilha: chamadas de banco de dados, operações de rede, operações do SO, ...

Isso significa que o desempenho do software é completamente irrelevante, mesmo que não melhore a latência; a otimização do software pode resultar em economia de energia e economia de hardware (ou economia de bateria para aplicativos móveis), o que pode importar.

No entanto, eles normalmente NÃO podem ser atraídos, e muitas vezes as melhorias algorítmicas superam as micro-otimizações por uma grande margem.

Portanto, antes de otimizar, você precisa entender para o que está otimizando ... e se vale a pena.

Agora, com relação ao desempenho de software puro, isso varia muito entre os toolchains.

Existem dois custos para uma chamada de função:

• o custo do tempo de execução,
• o custo do tempo de compilação.

O custo do tempo de execução é bastante óbvio; Para executar uma função, é necessário um certo volume de trabalho. Usando C no x86 por exemplo, uma chamada de função exigirá (1) registros de derramamento na pilha, (2) empurrando argumentos para os registradores, executando a chamada e depois (3) restaurando os registros da pilha. Consulte este resumo das convenções de chamada para ver o trabalho envolvido .

Este registro de derramamento / restauração leva um tempo não trivial (dezenas de ciclos de CPU).

Em geral, é esperado que esse custo seja trivial comparado ao custo real de execução da função, no entanto, alguns padrões são contraproducentes aqui: getters, funções protegidas por uma condição simples, etc ...

Além de intérpretes , um programador irá, portanto, esperar que o seu compilador ou JIT otimize as chamadas de função que são desnecessárias; embora essa esperança às vezes não dê frutos. Porque os otimizadores não são mágicos.

Um otimizador pode detectar que uma chamada de função é trivial e in-line a chamada: essencialmente, copiar / colar o corpo da função no site de chamada. Isso nem sempre é uma boa otimização (pode induzir um inchaço), mas, em geral, vale a pena porque o inlining expõe o contexto , e o contexto permite mais otimizações.

Um exemplo típico é:

void func(condition: boolean) {
    if (condition) {
        doLotsOfWork();
    }
}

void call() { func(false); }

Se func estiver embutido, o otimizador perceberá que a ramificação nunca foi obtida e otimizará call para void call() {} .

Nesse sentido, as chamadas de função, ocultando informações do otimizador (se ainda não estiverem alinhadas), podem inibir certas otimizações. Chamadas de função virtual são especialmente culpadas por isso, porque a desvirtualização (provando qual função é chamada em tempo de execução) nem sempre é fácil.

Em conclusão, meu conselho é escrever claramente primeiro, evitando pessimização algorítmica prematura (complexidade cúbica ou piores mordidas rapidamente), e então apenas otimizar o que precisa ser otimizado.

"Remember that the cost of a method call can be significant, depending on the language. There's almost always a tradeoff between writing readable code and writing performant code."

Under what conditions is this quoted statement still valid nowadays given the rich industry of performant modern compilers?

Eu só vou dizer que nunca. Eu acredito que a citação seja imprudente para simplesmente jogar lá fora.

Claro que não estou falando a verdade completa, mas não me importo em ser tão sincero assim. É como no filme Matrix, eu esqueci se era 1 ou 2 ou 3 - eu acho que foi o único com a atriz italiana sexy com os grandes melões (eu realmente não gostava de nenhum, mas o primeiro), quando o oracle lady disse a Keanu Reeves: "Eu acabei de dizer o que você precisava ouvir", ou algo assim, é o que eu quero fazer agora.

Os programadores não precisam ouvir isso. Se eles tiverem experiência com profilers em suas mãos e a cotação for de certa forma aplicável a seus compiladores, eles já saberão disso e aprenderão da maneira apropriada, desde que compreendam sua saída de criação de perfil e por que determinadas chamadas de folha são hotspots, através da medição. Se eles não tiverem experiência e nunca tiverem criado seu código, essa é a última coisa que precisam ouvir, que devem começar a comprometer supersticiosamente como escrevem código a ponto de colocar tudo em branco antes mesmo de identificar pontos críticos, na esperança de que tornar-se mais performante.

De qualquer forma, para uma resposta mais precisa, isso depende. Algumas das muitas condições já estão listadas entre as boas respostas. As condições possíveis que apenas escolhem uma linguagem já são enormes, como C ++, que teria que ser distribuído dinamicamente em chamadas virtuais e quando pode ser otimizado e sob quais compiladores e até mesmo linkers, e isso já garante uma resposta detalhada, sem falar em tentar para lidar com as condições em todas as linguagens e compiladores possíveis. Mas vou adicionar em cima, "quem se importa?" porque mesmo trabalhando em áreas de desempenho crítico como raytracing, a última coisa que eu vou começar a fazer na frente são os métodos manuais antes de eu ter qualquer medida.

Eu acredito que algumas pessoas são excessivamente zelosas ao sugerir que você nunca deve fazer qualquer micro-otimização antes da medição. Se otimizar para a localidade de referência conta como uma micro-otimização, então eu começo a aplicar essas otimizações logo no início com uma mentalidade de design orientada a dados em áreas que eu sei que serão críticas ao desempenho (raytracing code, por exemplo), porque senão sei que terei que reescrever grandes seções logo depois de ter trabalhado nesses domínios por anos. A otimização da representação de dados para ocorrências de cache geralmente pode ter o mesmo tipo de melhorias de desempenho que as melhorias algorítmicas, a menos que estejamos falando como tempo quadrático para linear.