Eu entrevistei recentemente na Amazon. Durante uma sessão de codificação, o entrevistador perguntou por que eu declarei uma variável em um método. Expliquei meu processo e ele me desafiou a resolver o mesmo problema com menos variáveis. Por exemplo (isso não foi da entrevista), comecei com o Método A e depois o aprimorei para o Método B, removendo int s
. Ele ficou satisfeito e disse que isso reduziria o uso de memória por esse método.
Eu entendo a lógica por trás disso, mas minha pergunta é:
Quando é apropriado usar o Método A vs. Método B e vice-versa?
Você pode ver que o método A terá maior uso de memória, uma vez que int s
é declarado, mas só precisa realizar um cálculo, ou seja a + b
. Por outro lado, o Método B possui menor uso de memória, mas precisa realizar dois cálculos, ou seja, a + b
duas vezes. Quando uso uma técnica sobre a outra? Ou, uma das técnicas é sempre preferida à outra? Quais são as coisas a considerar ao avaliar os dois métodos?
Método A:
private bool IsSumInRange(int a, int b)
{
int s = a + b;
if (s > 1000 || s < -1000) return false;
else return true;
}
Método B:
private bool IsSumInRange(int a, int b)
{
if (a + b > 1000 || a + b < -1000) return false;
else return true;
}
fonte
int s
enquanto estavam totalmente bem com esses números mágicos para os limites superior e inferior?Respostas:
Em vez de especular sobre o que pode ou não acontecer, vejamos, não é? Vou precisar usar o C ++, já que não tenho um compilador de C # à mão (embora veja o exemplo de C # do VisualMelon ), mas tenho certeza de que os mesmos princípios se aplicam independentemente.
Incluiremos as duas alternativas que você encontrou na entrevista. Também incluiremos uma versão usada
abs
conforme sugerido por algumas das respostas.Agora compile-o sem nenhuma otimização:
g++ -c -o test.o test.cpp
Agora podemos ver exatamente o que isso gera:
objdump -d test.o
Podemos ver nos endereços da pilha (por exemplo, o
-0x4
inmov %edi,-0x4(%rbp)
versus o-0x14
inmov %edi,-0x14(%rbp)
) queIsSumInRangeWithVar()
usam 16 bytes extras na pilha.Como
IsSumInRangeWithoutVar()
não aloca espaço na pilha para armazenar o valor intermediário,s
ele precisa recalculá-lo, resultando nessa implementação em duas instruções a mais.Engraçado,
IsSumInRangeSuperOptimized()
parece muitoIsSumInRangeWithoutVar()
, exceto que se compara a -1000 primeiro e 1000 segundo.Agora vamos compilar apenas com as otimizações mais básicas:
g++ -O1 -c -o test.o test.cpp
. O resultado:Você olha para isso: cada variante é idêntica . O compilador é capaz de fazer algo bastante inteligente:
abs(a + b) <= 1000
é equivalente aa + b + 1000 <= 2000
considerarsetbe
fazer uma comparação não assinada; portanto, um número negativo se torna um número positivo muito grande. Alea
instrução pode realmente executar todas essas adições em uma instrução e eliminar todos os ramos condicionais.Para responder à sua pergunta, quase sempre o que otimizar não é a memória ou a velocidade, mas a legibilidade . Ler código é muito mais difícil do que escrevê-lo, e ler código que foi modificado para "otimizar" é muito mais difícil do que ler código que foi escrito para ficar claro. Na maioria das vezes, essas "otimizações" têm um nível insignificante ou, nesse caso, exatamente zero impacto real no desempenho.
Vamos medir! Eu transcrevi os exemplos para Python:
Execute com o Python 3.5.2, isso produz a saída:
A desmontagem em Python não é muito interessante, pois o "compilador" do bytecode não faz muito em termos de otimização.
O desempenho das três funções é quase idêntico. Podemos ficar tentados a seguir
IsSumInRangeWithVar()
devido ao seu ganho marginal de velocidade. Embora eu adicione como estava tentando parâmetros diferentestimeit
, às vezesIsSumInRangeSuperOptimized()
saiu mais rápido, por isso suspeito que possam ser fatores externos responsáveis pela diferença, e não qualquer vantagem intrínseca de qualquer implementação.Se esse é realmente um código crítico de desempenho, uma linguagem interpretada é simplesmente uma escolha muito ruim. Executando o mesmo programa com pypy, recebo:
O simples uso de pypy, que usa a compilação JIT para eliminar grande parte da sobrecarga do interpretador, resultou em uma melhoria de desempenho de 1 ou 2 ordens de magnitude. Fiquei bastante chocado ao ver que
IsSumInRangeWithVar()
é uma ordem de magnitude mais rápida que as outras. Então mudei a ordem dos benchmarks e corri novamente:Parece que não é nada sobre a implementação que a torna mais rápida, mas a ordem em que eu faço o benchmarking!
Eu adoraria aprofundar isso mais profundamente, porque sinceramente não sei por que isso acontece. Mas acredito que o argumento já foi levantado: micro-otimizações, como declarar ou não um valor intermediário como variável, raramente são relevantes. Com uma linguagem interpretada ou um compilador altamente otimizado, o primeiro objetivo ainda é escrever um código claro.
Se uma otimização adicional for necessária, faça benchmark . Lembre-se de que as melhores otimizações não provêm dos pequenos detalhes, mas da imagem algorítmica maior: o pypy será uma ordem de magnitude mais rápida para a avaliação repetida da mesma função que o cpython, porque usa algoritmos mais rápidos (compilador JIT x interpretação) para avaliar o programa. E há também o algoritmo codificado a ser considerado: uma pesquisa em uma árvore B será mais rápida que uma lista vinculada.
Depois de garantir que você esteja usando as ferramentas e os algoritmos certos para o trabalho, esteja preparado para mergulhar profundamente nos detalhes do sistema. Os resultados podem ser muito surpreendentes, mesmo para desenvolvedores experientes, e é por isso que você deve ter uma referência para quantificar as alterações.
fonte
Para responder à pergunta declarada:
Há duas coisas que você precisa estabelecer:
Para responder à primeira pergunta, você precisa saber quais são os requisitos de desempenho para seu aplicativo. Se não houver requisitos de desempenho, não há motivo para otimizar de uma maneira ou de outra. Os requisitos de desempenho ajudam você a chegar ao lugar de "bom o suficiente".
O método que você forneceu por si só não causaria problemas de desempenho por si só, mas talvez em um loop e processando uma grande quantidade de dados, você precise começar a pensar um pouco diferente sobre como está abordando o problema.
Detectando o que está limitando o aplicativo
Comece a analisar o comportamento do seu aplicativo com um monitor de desempenho. Fique de olho no uso da CPU, disco, rede e memória enquanto estiver em execução. Um ou mais itens serão atingidos ao máximo enquanto todo o resto é usado moderadamente - a menos que você atinja o equilíbrio perfeito, mas isso quase nunca acontece).
Quando você precisa olhar mais profundamente, normalmente usa um criador de perfil . Existem perfiladores de memória e de processos , e eles medem coisas diferentes. O ato de criar um perfil tem um impacto significativo no desempenho, mas você está instrumentando seu código para descobrir o que está errado.
Digamos que você veja o uso da CPU e do disco em um pico. Você primeiro procuraria por "pontos de acesso" ou código chamado com mais frequência do que o resto ou leva uma porcentagem significativamente mais longa do processamento.
Se não conseguir encontrar pontos de acesso, você começará a olhar para a memória. Talvez você esteja criando mais objetos do que o necessário e sua coleta de lixo esteja funcionando horas extras.
Recuperando o desempenho
Pense criticamente. A seguinte lista de alterações está na ordem de quanto retorno do investimento você obterá:
Em situações como essa, você deve aplicar o método científico. Crie uma hipótese, faça as alterações e teste-a. Se você atingir suas metas de desempenho, estará pronto. Caso contrário, vá para a próxima coisa na lista.
Respondendo a pergunta em negrito:
Honestamente, este é o último passo na tentativa de lidar com problemas de desempenho ou memória. O impacto do método A versus o método B será realmente diferente dependendo do idioma e da plataforma (em alguns casos).
Praticamente qualquer linguagem compilada com um otimizador parcialmente decente irá gerar código semelhante com qualquer uma dessas estruturas. No entanto, essas suposições não permanecem necessariamente verdadeiras em linguagens proprietárias e de brinquedos que não possuem um otimizador.
Precisamente qual terá um impacto melhor depende se
sum
é uma variável de pilha ou uma pilha de heap. Esta é uma opção de implementação de idioma. Em C, C ++ e Java, por exemplo, primitivas numéricas como umint
são variáveis de pilha por padrão. Seu código não tem mais impacto na memória atribuindo a uma variável de pilha do que você teria com um código totalmente embutido.Outras otimizações que você pode encontrar nas bibliotecas C (principalmente as mais antigas), nas quais é possível decidir entre copiar uma matriz bidimensional primeiro ou através da primeira, é uma otimização dependente da plataforma. Requer algum conhecimento de como o chipset que você está direcionando otimiza melhor o acesso à memória. Existem diferenças sutis entre arquiteturas.
Resumindo, a otimização é uma combinação de arte e ciência. Requer um pensamento crítico, bem como um certo grau de flexibilidade na maneira como você aborda o problema. Procure grandes coisas antes de culpar pequenas coisas.
fonte
"isso reduziria a memória" - em, não. Mesmo se isso fosse verdade (o que, para qualquer compilador decente, não é), a diferença provavelmente seria insignificante para qualquer situação do mundo real.
No entanto, eu recomendaria usar o método A * (método A com uma pequena alteração):
mas por duas razões completamente diferentes:
dando à variável
s
um nome explicativo, o código se torna mais claroevita ter a mesma lógica de somação duas vezes no código, para que o código se torne mais SECO, o que significa menos propenso a erros de alterações.
fonte
sum
variável, levando assim a zero uso de memória. E mesmo se não, isso é apenas uma única palavra de memória em um método "folha". Considerando o quão incrivelmente desperdiçado em Java ou C # pode ser devido ao seu modelo de GC e objeto, umaint
variável local literalmente não usa nenhuma memória perceptível. Isso é micro-otimização inútil.sum
seria um detalhe de implementação e duvido que alguém possa argumentar de forma convincente se um truque bobo como evitar um localint
levaria a isso ou essa quantidade de uso de memória a longo prazo. A legibilidade da OMI é mais importante. A legibilidade pode ser subjetiva, mas, FWIW, pessoalmente, prefiro que você nunca faça o mesmo cálculo duas vezes, não para uso da CPU, mas porque eu só preciso inspecionar sua adição uma vez quando estou procurando por um bug.Você pode fazer melhor do que os dois com
A maioria dos processadores (e, portanto, compiladores) pode fazer abs () em uma única operação. Você não apenas tem menos somas, mas também menos comparações, que geralmente são mais caras em termos de computação. Ele também remove a ramificação, o que é muito pior na maioria dos processadores, porque impede que o pipelining seja possível.
O entrevistador, como outras respostas disseram, tem vida vegetal e não tem negócios em conduzir uma entrevista técnica.
Dito isto, sua pergunta é válida. E a resposta para quando você otimiza e como é quando você prova que é necessário e cria um perfil para provar exatamente quais partes precisam . Knuth disse que a otimização prematura é a raiz de todos os males, porque é muito fácil tentar encontrar seções sem importância, ou fazer alterações (como o do entrevistador) que não surtiram efeito, enquanto perdiam os lugares que realmente precisam. Até que você tenha provas concretas de que é realmente necessário, a clareza do código é o alvo mais importante.
Editar FabioTurati indica corretamente que esse é o sentido lógico oposto ao original (meu erro!) E que isso ilustra um impacto adicional da citação de Knuth, onde corremos o risco de quebrar o código enquanto tentamos otimizá-lo.
fonte
a+b
emif
e fazê-lo duas vezes. Você entende errado "Ele ficou satisfeito e disse que isso reduziria o uso de memória por esse método" - ele foi gentil com você, escondendo sua decepção com essa explicação sem sentido sobre memória. Você não deve levar a sério a pergunta aqui. Você conseguiu um emprego? Meu palpite que você não fez :-(abs()
e também possui uma únicareturn
, em vez de ter uma quando a condição for verdadeira ("if branch") e outra quando for falsa ( "else branch"). Quando você alterar um código como este, tenha cuidado: existe o risco de escrever inadvertidamente uma função que retorna true quando deve retornar false e vice-versa. Foi exatamente o que aconteceu aqui. Eu sei que você estava se concentrando em outra coisa, e você fez um bom trabalho nisso. Ainda assim, isso poderia ter facilmente custar-lhe o trabalho ...adds
e o ARM predicou reverse-sub (rsblt
= reverse-sub se menos-tha), mas todo o resto requer várias instruções extras para implementarabs(a+b)
ouabs(a)
. godbolt.org/z/Ok_Con mostra x86, ARM, AArch64, PowerPC, MIPS e RISC-V asm output. É apenas transformando a comparação em uma verificação de faixa(unsigned)(a+b+999) <= 1998U
que o gcc pode otimizá-la como na resposta de Phil.IsSumInRange(INT_MIN, 0)
. O código original retornafalse
porqueINT_MIN+0 > 1000 || INT_MIN+0 < -1000
; mas o código "novo e aprimorado" retornatrue
porqueabs(INT_MIN+0) < 1000
. (Ou, em alguns idiomas, isso gerará uma exceção ou terá um comportamento indefinido. Verifique as listagens locais.)O hardware é barato; programadores são caros . Portanto, o custo do tempo que vocês dois desperdiçaram nessa questão é provavelmente muito pior do que qualquer uma das respostas.
Independentemente disso, a maioria dos compiladores modernos encontraria uma maneira de otimizar a variável local em um registrador (em vez de alocar espaço na pilha); portanto, os métodos são provavelmente idênticos em termos de código executável. Por esse motivo, a maioria dos desenvolvedores escolheria a opção que comunica a intenção com mais clareza (consulte Escrevendo código realmente óbvio (ROC) ). Na minha opinião, esse seria o método A.
Por outro lado, se este for puramente um exercício acadêmico, você poderá ter o melhor dos dois mundos com o Método C:
fonte
a+=b
é um truque interessante, mas eu tenho que mencionar (apenas no caso de não estar implícito no resto da resposta), da minha experiência com métodos que mexem com parâmetros podem ser muito difíceis de depurar e manter.if
verificação, mas esqueceu de reverter o resultado da comparação; sua função está retornando agoratrue
quando nãoa + b
está no intervalo. Ou adicionar um para o exterior da condição ( ), ou distribuir os testes, invertendo, para obter ou para tornar o fluxo de verificação de intervalo muito bem,!
return !(a > 1000 || a < -1000)
!
return a <= 1000 && a >= -1000;
return -1000 <= a && a <= 1000;
<=
/>=
, não<
/>
(com<
/>
, 1000 e -1000 são tratados como fora do intervalo, o código original os trata como dentro do intervalo).Eu otimizaria para facilitar a leitura. Método X:
Métodos pequenos que fazem apenas uma coisa, mas são fáceis de raciocinar.
(Essa é uma preferência pessoal. Gosto de testes positivos em vez de negativos. Seu código original está testando se o valor NÃO está fora do intervalo.)
fonte
a
eb
paranumber1
enumber2
auxiliares de legibilidade de qualquer forma. Além disso, sua nomeação das funções é inconsistente: por queIsSumInRange
codificar o intervalo se oIsValueInRange
aceita como argumento?Em resumo, não acho que a questão tenha muita relevância na computação atual, mas, de uma perspectiva histórica, é um exercício de pensamento interessante.
É provável que o seu entrevistador seja fã do Mês do Homem Mítico. No livro, Fred Brooks defende que os programadores geralmente precisam de duas versões das principais funções em sua caixa de ferramentas: uma versão com otimização de memória e uma versão com otimização de CPU. Fred baseou isso em sua experiência na liderança do desenvolvimento do sistema operacional IBM System / 360, onde as máquinas podem ter apenas 8 kilobytes de RAM. Nessas máquinas, a memória necessária para variáveis locais em funções pode ser potencialmente importante, especialmente se o compilador não as otimizar efetivamente (ou se o código foi escrito diretamente na linguagem assembly).
Na era atual, acho que seria difícil encontrar um sistema em que a presença ou ausência de uma variável local em um método faria uma diferença notável. Para que uma variável seja importante, o método precisaria ser recursivo com a recursão profunda esperada. Mesmo assim, é provável que a profundidade da pilha seja excedida causando exceções de estouro de pilha antes que a própria variável causasse um problema. O único cenário real em que pode haver um problema é com matrizes muito grandes alocadas na pilha em um método recursivo. Mas isso também é improvável, pois acho que a maioria dos desenvolvedores pensaria duas vezes sobre cópias desnecessárias de matrizes grandes.
fonte
Após a atribuição s = a + b; as variáveis aeb não são mais usadas. Portanto, nenhuma memória é usada para s se você não estiver usando um compilador completamente danificado pelo cérebro; a memória usada de qualquer maneira para aeb é reutilizada.
Mas otimizar essa função é um absurdo total. Se você pudesse economizar espaço, seriam talvez 8 bytes enquanto a função estiver em execução (que é recuperada quando a função retornar), de modo absolutamente inútil. Se você pudesse economizar tempo, seriam números únicos de nanossegundos. Otimizar isso é uma total perda de tempo.
fonte
Variáveis de tipo de valor local são alocadas na pilha ou (mais provável para esses pequenos pedaços de código) usam registros no processador e nunca conseguem ver nenhuma RAM. De qualquer forma, eles têm vida curta e nada para se preocupar. Você começa a considerar o uso de memória quando precisa armazenar em buffer ou enfileirar elementos de dados em coleções que são potencialmente grandes e duradouras.
Depende do que você mais gosta na sua aplicação. Velocidade de processamento? Tempo de resposta? Pegada de memória? Manutenção? Consistência no design? Tudo depende de você.
fonte
stackalloc
e agoraSpan<T>
. Possivelmente útil em um hot spot, após a criação de perfil. Além disso, alguns dos documentos sobre estruturas sugerem que os tipos de valor podem estar na pilha, enquanto os tipos de referência não . De qualquer forma, na melhor das hipóteses, você pode evitar um pouco de GC.Como outras respostas disseram, você precisa pensar no que está otimizando.
Neste exemplo, suspeito que qualquer compilador decente geraria código equivalente para os dois métodos, portanto a decisão não teria efeito no tempo de execução ou na memória!
O que isso afeta é a legibilidade do código. (O código é para os humanos lerem, não apenas os computadores.) Não há muita diferença entre os dois exemplos; quando todas as outras coisas são iguais, considero a brevidade uma virtude; portanto, provavelmente escolhia o Método B. Mas todas as outras coisas raramente são iguais e, em um caso mais complexo do mundo real, isso pode ter um grande efeito.
Coisas a considerar:
fonte
Como muitas das respostas apontaram, tentar ajustar essa função com os compiladores modernos não fará diferença. Um otimizador provavelmente pode descobrir a melhor solução (faça um voto positivo para a resposta que mostrou o código do assembler para provar isso!). Você declarou que o código na entrevista não era exatamente o código que você foi solicitado a comparar; portanto, talvez o exemplo real faça um pouco mais de sentido.
Mas vamos dar uma outra olhada nesta questão: esta é uma pergunta de entrevista. Portanto, a verdadeira questão é: como você deve responder assumindo que deseja tentar conseguir o emprego?
Vamos supor também que o entrevistador sabe do que está falando e está apenas tentando ver o que você sabe.
Eu mencionaria que, ignorando o otimizador, o primeiro pode criar uma variável temporária na pilha, enquanto o segundo não, mas faria o cálculo duas vezes. Portanto, o primeiro usa mais memória, mas é mais rápido.
Você pode mencionar que, de qualquer maneira, um cálculo pode exigir uma variável temporária para armazenar o resultado (para que seja comparado), portanto, se você nomear essa variável ou não, isso não fará diferença.
Eu mencionaria então que, na realidade, o código seria otimizado e provavelmente o código de máquina equivalente seria gerado, pois todas as variáveis são locais. No entanto, depende de qual compilador você está usando (não faz muito tempo que eu poderia obter uma melhoria de desempenho útil declarando uma variável local como "final" em Java).
Você pode mencionar que a pilha, em qualquer caso, vive em sua própria página de memória, portanto, a menos que sua variável extra faça com que a pilha transborde, ela não alocará mais memória. Se transbordar, desejará uma página totalmente nova.
Eu mencionaria que um exemplo mais realista pode ser a opção de usar um cache para armazenar os resultados de muitos cálculos ou não, e isso levantaria uma questão de CPU vs memória.
Tudo isso demonstra que você sabe do que está falando.
Gostaria de dizer ao final que seria melhor focar na legibilidade. Embora seja verdade neste caso, no contexto da entrevista, pode ser interpretado como "Não sei sobre desempenho, mas meu código parece uma história de Janet e John ".
O que você não deve fazer é traçar as instruções breves habituais sobre como a otimização do código não é necessária; não otimize até que você crie um perfil do código (isso apenas indica que você não pode ver um código incorreto), o hardware custa menos do que os programadores e, por favor, não cite Knuth "prematuro blá blá ...".
O desempenho do código é um problema genuíno em muitas organizações e muitas organizações precisam de programadores que o entendam.
Em particular, com organizações como a Amazon, parte do código tem grande influência. Um trecho de código pode ser implantado em milhares de servidores ou milhões de dispositivos e pode ser chamado bilhões de vezes por dia todos os dias do ano. Pode haver milhares de trechos semelhantes. A diferença entre um algoritmo ruim e um bom pode facilmente ser um fator de mil. Faça os números e multiplique tudo isso: faz a diferença. O custo potencial para a organização do código que não executa pode ser muito significativo ou até fatal se um sistema ficar sem capacidade.
Além disso, muitas dessas organizações trabalham em um ambiente competitivo. Portanto, você não pode simplesmente dizer aos seus clientes para comprar um computador maior se o software do seu concorrente já funcionar bem no hardware que ele possui ou se o software for executado em um telefone celular e não puder ser atualizado. Alguns aplicativos são particularmente críticos para o desempenho (jogos e aplicativos móveis vêm à mente) e podem viver ou morrer de acordo com sua capacidade de resposta ou velocidade.
Pessoalmente, durante mais de duas décadas, trabalhei em muitos projetos nos quais os sistemas falharam ou foram inutilizáveis devido a problemas de desempenho e fui chamado para otimizar esses sistemas e, em todos os casos, devido a códigos incorretos, escritos por programadores que não entendiam o impacto do que eles estavam escrevendo. Além disso, nunca é um pedaço de código, está sempre em todo lugar. Quando eu chego, é muito tarde para começar a pensar em desempenho: o estrago já foi feito.
Entender o desempenho do código é uma boa habilidade para ter da mesma maneira que entender a correção e o estilo do código. Isso sai da prática. Falhas de desempenho podem ser tão ruins quanto falhas funcionais. Se o sistema não funcionar, não funcionará. Não importa o porquê. Da mesma forma, desempenho e recursos que nunca são usados são ruins.
Portanto, se o entrevistador perguntar sobre desempenho, eu recomendaria tentar demonstrar o máximo de conhecimento possível. Se a pergunta parecer ruim, indique educadamente por que você acha que não seria um problema nesse caso. Não cite Knuth.
fonte
Você deve primeiro otimizar a correção.
Sua função falha para valores de entrada próximos ao Int.MaxValue:
Isso retorna verdadeiro porque a soma ultrapassa -400. A função também não funciona para a = int.MinValue + 200. (adiciona incorretamente até "400")
Não saberemos o que o entrevistador estava procurando, a menos que ele ou ela grite, mas "o excesso é real" .
Em uma situação de entrevista, faça perguntas para esclarecer o escopo do problema: Quais são os valores máximos e mínimos permitidos de entrada? Depois de ter esses itens, você poderá lançar uma exceção se o chamador enviar valores fora do intervalo. Ou (em C #), você pode usar uma seção {} marcada, que lançaria uma exceção no estouro. Sim, é mais trabalhoso e complicado, mas às vezes é preciso.
fonte
Sua pergunta deveria ter sido: "Preciso otimizar isso?".
As versões A e B diferem em um detalhe importante que torna A preferível, mas não está relacionado à otimização: você não repete o código.
A "otimização" real é chamada eliminação comum de subexpressão, que é o que praticamente todo compilador faz. Alguns fazem essa otimização básica, mesmo quando as otimizações estão desativadas. Portanto, isso não é realmente uma otimização (o código gerado quase certamente será exatamente o mesmo em todos os casos).
Mas se não é uma otimização, por que é preferível? Tudo bem, você não repete o código, quem se importa!
Bem, antes de tudo, você não tem o risco de errar acidentalmente metade da cláusula condicional. Mas o mais importante, alguém que lê esse código pode gritar imediatamente o que você está tentando fazer, em vez de uma
if((((wtf||is||this||longexpression))))
experiência. O que o leitor começa a ver é oif(one || theother)
que é uma coisa boa. Não raramente, acontece que você é essa outra pessoa lendo seu próprio código três anos depois e pensando "WTF isso significa?". Nesse caso, é sempre útil se o seu código comunicar imediatamente qual era a intenção. Com uma subexpressão comum sendo nomeada corretamente, esse é o caso.Além disso, se a qualquer momento no futuro você decidir que, por exemplo, precisa mudar
a+b
paraa-b
, precisa mudar umlocalização, não duas. E não há risco de (novamente) errar o segundo por acidente.Sobre sua pergunta real, para o que você deve otimizar, primeiro o código deve estar correto . Esta é a coisa absolutamente mais importante. Código incorreto é código ruim, mais ainda que, apesar de incorreto, "funcione bem" ou, pelo menos, pareça que funciona bem. Depois disso, o código deve ser legível (legível por alguém não familiarizado com ele).
Quanto à otimização ... certamente não se deve escrever deliberadamente código anti-otimizado, e certamente não estou dizendo que você não deve pensar no design antes de começar (como escolher o algoritmo certo para o problema, não o menos eficiente).
Mas para a maioria dos aplicativos, na maioria das vezes, o desempenho obtido após a execução de código legível e correto usando um algoritmo razoável por meio de um compilador de otimização é bom, não há necessidade real de se preocupar.
Se não for esse o caso, ou seja, se o desempenho do aplicativo realmente não atender aos requisitos, e somente então , você deve se preocupar em fazer otimizações locais como a que você tentou. De preferência, porém, você reconsideraria o algoritmo de nível superior. Se você chamar uma função 500 vezes em vez de 50.000 vezes devido a um algoritmo melhor, isso terá um impacto maior do que salvar três ciclos de clock em uma micro otimização. Se você não parar por várias centenas de ciclos em um acesso aleatório à memória o tempo todo, isso terá um impacto maior do que fazer alguns cálculos baratos extras, etc., etc.
A otimização é uma questão difícil (você pode escrever livros inteiros sobre isso e não tem fim), e gastar tempo otimizando cegamente algum ponto específico (sem nem mesmo saber se esse é o gargalo!) Geralmente é perda de tempo. Sem criação de perfil, é muito difícil corrigir a otimização.
Mas, como regra geral, quando você está voando às cegas e só precisa / deseja fazer alguma coisa , ou como uma estratégia padrão geral, sugiro otimizar a "memória".
A otimização da "memória" (em particular a localização espacial e os padrões de acesso) geralmente traz um benefício, porque, diferentemente de uma vez, quando tudo era "mais ou menos o mesmo", hoje em dia o acesso à RAM está entre as coisas mais caras (falta de leitura do disco!) que você pode, em princípio, fazer. Já o ALU, por outro lado, é barato e fica mais rápido a cada semana. A largura de banda e a latência da memória não melhoram quase tão rapidamente. Uma boa localidade e bons padrões de acesso podem facilmente fazer uma diferença de 5x (20x em exemplos extremos e controversos) no tempo de execução, em comparação com padrões de acesso ruim em aplicativos com muitos dados. Seja gentil com seus caches e você será uma pessoa feliz.
Para colocar o parágrafo anterior em perspectiva, considere quanto custa as diferentes coisas que você pode fazer. A execução de algo como
a+b
leva (se não for otimizado) um ou dois ciclos, mas a CPU geralmente pode iniciar várias instruções por ciclo e canalizar instruções não dependentes de forma mais realista, apenas custa cerca de meio ciclo ou menos. Idealmente, se o compilador é bom no agendamento e, dependendo da situação, pode custar zero.A busca de dados ("memória") custa 4-5 ciclos, se você tiver sorte e estiver em L1, e cerca de 15 ciclos, se não tiver tanta sorte (acerto em L2). Se os dados não estiverem no cache, são necessárias várias centenas de ciclos. Se o seu padrão de acesso aleatório exceder os recursos do TLB (fácil de fazer com apenas ~ 50 entradas), adicione mais algumas centenas de ciclos. Se o seu padrão de acesso aleatório realmente causar uma falha na página, custará alguns dez mil ciclos na melhor das hipóteses e vários milhões na pior.
Agora pense bem, qual é a coisa que você deseja evitar com mais urgência?
fonte
Depois de obter a funcionalidade direita primeiro . Então, a seletividade se preocupa com micro otimizações.
Como uma pergunta de entrevista sobre otimizações, o código provoca a discussão usual, mas perde o objetivo de nível superior de O código está funcionalmente correto?
C ++ e C e outros consideram o
int
estouro como um problema doa + b
. Não está bem definido e C chama de comportamento indefinido . Não está especificado para "quebrar" - mesmo que esse seja o comportamento comum.IsSumInRange()
Espera-se que uma função chamada seja bem definida e tenha desempenho correto para todos osint
valores dea,b
. O crua + b
não é. A solução CA poderia usar:O código acima pode ser optimizada utilizando um tipo de número inteiro mais larga do que
int
, se estiverem disponíveis, como abaixo ou distribuir asum > N
,sum < -N
testes dentro daif (a >= 0)
lógica. No entanto, essas otimizações podem não levar a um código emitido "mais rápido", dado um compilador inteligente, nem valer a manutenção extra de serem inteligentes.Mesmo usando
abs(sum)
é propenso a problemas quandosum == INT_MIN
.fonte
De que tipo de compiladores estamos falando e que tipo de "memória"? Como no seu exemplo, assumindo um otimizador razoável, a expressão
a+b
geralmente precisa ser armazenada em um registro (uma forma de memória) antes de fazer essa aritmética.Portanto, se estivermos falando de um compilador burro que encontra
a+b
duas vezes, ele alocará mais registros (memória) no seu segundo exemplo, porque seu primeiro exemplo pode apenas armazenar essa expressão uma vez em um único registro mapeado para a variável local, mas nós neste momento, estamos falando de compiladores muito tolos ... a menos que você esteja trabalhando com outro tipo de compilador bobo que empilhe todas as variáveis em todo o lugar; nesse caso, talvez o primeiro faça com que a tristeza otimize mais do que o segundo*.Tudo isso é extremamente especulativo, de maneiras bastante tolas, sem medições / desmontagens e, mesmo nos piores cenários, esse não é um caso de "memória versus desempenho" (porque mesmo entre os piores otimizadores que consigo pensar, não estamos falando sobre qualquer coisa, exceto memória temporária, como pilha / registro), é puramente um caso de "desempenho", e entre qualquer otimizador razoável os dois são equivalentes, e se um não estiver usando um otimizador razoável, por que é obcecado com a otimização de natureza tão microscópica e medidas especialmente ausentes? É como o foco no nível de montagem de alocação de registro / seleção de instrução, que eu nunca esperaria que alguém que visse manter produtivo ao usar, digamos, um intérprete que empilhe tudo.
Quanto a esta questão, se eu posso lidar com isso de maneira mais ampla, geralmente não acho os dois diametralmente opostos. Especialmente se os seus padrões de acesso forem seqüenciais e, dada a velocidade do cache da CPU, geralmente uma redução na quantidade de bytes processados sequencialmente para entradas não triviais se traduz (até certo ponto) em vasculhar esses dados mais rapidamente. É claro que existem pontos de ruptura em que, se os dados são muito, muito menores em troca de muito mais instruções, pode ser mais rápido processar sequencialmente em forma maior em troca de menos instruções.
Mas eu descobri que muitos desenvolvedores tendem a subestimar o quanto uma redução no uso de memória nesses tipos de casos pode traduzir em reduções proporcionais no tempo gasto no processamento. É muito humanamente intuitivo converter custos de desempenho em instruções, em vez de acessar a memória, a ponto de alcançar grandes LUTs, em alguma tentativa inútil de acelerar alguns cálculos pequenos, apenas para encontrar o desempenho prejudicado com o acesso adicional à memória.
Para casos de acesso sequencial por meio de uma matriz enorme (sem falar em variáveis escalares locais, como no seu exemplo), segui a regra de que menos memória para sequenciar traduz-se em maior desempenho, especialmente quando o código resultante é mais simples do que o contrário, até que não até que minhas medições e criador de perfil me digam o contrário, e isso importa, da mesma forma que eu suponho que ler sequencialmente um arquivo binário menor no disco seja mais rápido que um arquivo maior (mesmo que o menor exija mais instruções) ), até que essa suposição não seja mais aplicada em minhas medidas.
fonte