Aprendendo a otimizar com o Assembly [fechado]

21

Sou estudante do segundo ano da Computer Games Technology. Recentemente, terminei meu primeiro protótipo do meu "tipo" de descobridor próprio (que não usa A * em vez de uma abordagem geométrica / reconhecimento de padrões, o descobridor só precisa do conhecimento sobre o terreno que está em sua visão para tomar decisões, porque eu queria uma IA que pudesse realmente explorar, se o terreno já for conhecido, ele percorrerá o caminho mais curto com facilidade, porque o pathfinder tem uma memória de nós).

De qualquer forma, minha pergunta é mais geral: como começo a otimizar algoritmos / loops / for_each / etc. usando o Assembly, embora dicas gerais sejam bem-vindas. Estou procurando especificamente bons livros, porque é realmente difícil encontrar bons livros sobre esse assunto. Existem alguns artigos pequenos por aí como este , mas ainda não há conhecimento suficiente para otimizar um algoritmo / jogo ...

Espero que haja um bom livro moderno por aí, que eu simplesmente não consegui encontrar ...

niktehpui
fonte
1
Isso não responde diretamente à sua pergunta, mas o A * exploratório (chamado adaptativo) foi investigado e tem um desempenho muito bom (o que significa que você não precisará otimizá-lo usando o ASM). Dê uma olhada no D * Lite .
Jonathan Dickinson

Respostas:

21

Eu serei o oposto aqui e direi que nunca é cedo para aprender sobre otimizações, especialmente otimizações de montagem e, mais importante, depuração na montagem. Eu acredito que você obterá o benefício máximo disso se for um estudante (porque então você tem muito pouco a perder [isto é, tempo / dinheiro]) e tudo a ganhar.

Se você está no setor e não tem a tarefa de mexer na montagem, não o faça. Caso contrário, se você é um estudante ou tem tempo em geral, eu encontraria tempo para aprender a desmontar programas e ver se consigo encontrar uma solução melhor que o compilador. Se não posso, quem se importa! Eu apenas aprendi a escrever, assim como o compilador, e isso é uma enorme vantagem quando você se depara com um bug no código de liberação (sem símbolos de depuração) e olhando para a desmontagem porque é a única coisa que você pode ver.

A resposta

Este é um dos melhores recursos que encontrei para aprender sobre otimizações.

http://www.agner.org/optimize/

O discurso retórico

Se você ler alguns artigos de grandes desenvolvedores (por exemplo, o raciocínio por trás da criação do EASTL e uma inspeção mais detalhada do código o levará a comentários como o fez, porque o GCC é péssimo em incluir essa declaração if que informará o que a maioria dos as pessoas dizem que você confia que o compilador nem sempre está certo, ESPECIALMENTE no desenvolvimento de jogos) e, em seguida, colocam os pés no setor, você descobrirá que as otimizações são comuns e saber o que significa a saída da montagem é uma grande vantagem. Além disso, as pessoas parecem não perceber (especialmente no stackoverflow) que a criação de perfis de jogos é muito difícil e nem sempre precisa.

Há uma ressalva. Você pode gastar tempo otimizando algo e depois perceber que foi um desperdício de tempo. Mas o que você aprendeu? Você aprendeu a não repetir o mesmo erro em uma circunstância semelhante.

O que o SO está adotando agora é, na minha opinião, uma posição religiosa para a afirmação não otimizar até você criar um perfil e não se preocupe, o compilador sabe melhor do que você . Isso dificulta o aprendizado. Conheço especialistas do setor que recebem muito dinheiro bom (e quero dizer MUITO bom dinheiro) para mexer na montagem para otimizar o jogo e depurá-lo porque o compilador é ruim ou simplesmente não pode ajudá-lo, porque, bem, ele não pode (falhas relacionadas à GPU, falhas nas quais é impossível ler os dados envolvidos em um depurador etc. etc.)!

E se alguém que adora fazer isso, ainda não o percebeu completamente, fizer a pergunta aqui e for desligado / desabilitado pelas muitas respostas que o compilador conhece melhor que você! e nunca se torna um daqueles programadores altamente pagos?

Um pensamento final. Se você começar a fazer isso mais cedo, descobrirá que em breve começará a escrever um código que, na pior das hipóteses, não possui melhorias de desempenho porque o compilador a otimizou da mesma maneira ou, na melhor das hipóteses, tem algumas melhorias de desempenho porque agora o compilador pode otimizá-lo . Em ambos os casos, tornou-se um hábito e você não é mais lento ao escrever código dessa maneira do que antes. Alguns exemplos são (existem muitos mais):

  1. Pré-incremento, a menos que você realmente queira pós-incremento
  2. Gravando loops para contêineres usando uma variável de tamanho local constante, em vez de chamar size () no contêiner dentro do loop.

EDIT: Atualização após mais 8 anos no setor. Aprenda montagem. Aprenda como os otimizadores funcionam e a montagem que eles geram (CompilerExplorer é uma ótima ferramenta para isso). Eu já deparei com inúmeras falhas nas compilações de teste (compilações otimizadas para testes internos) nas quais você não pode confiar no depurador, mesmo com símbolos de depuração. O compilador otimizou muitas coisas e o assembly é sua única fonte de informações valiosas para encontrar o bug do despejo de memória. Cada build leva 30 a 40 minutos se você tiver sorte e for o primeiro na fila de build - portanto, você não pode confiar em algumas técnicas tradicionais para isolar o bug. O multiplayer piora as coisas. Conhecer a montagem e ler a montagem otimizada simplesmente o tornará melhor e, em última análise, mais valioso para a equipe.

Samaursa
fonte
1
Bom argumento sobre a otimização de compiladores. Eles são ótimos de se ter, mas estão longe de serem perfeitos, e ao contrário do que algumas pessoas acreditam que geralmente não é difícil encontrar uma otimização simples que um compilador não fez.
Aaaaaaaaaaaa
3
Deve-se notar que há uma diferença entre "aprender a ler montagem" e "aprender a otimizar com montagem". Os dois não são a mesma coisa, e sua resposta realmente não afeta o uso de assembly para implementar otimizações. Ler montagem é uma habilidade útil, pois pode ajudar na depuração e localização de locais onde o compilador não está fazendo algo certo. Mas isso é muito diferente de usar o assembly para escrever rotinas otimizadas, o que exige um conhecimento profundo do agendamento de instruções para uma CPU específica. E também é algo que você não cobriu.
Nicol Bolas
1
Além disso, "acabei de aprender a escrever, bem como o compilador" Não, você não fez. Você observou como uma rotina específica foi compilada para uma CPU específica. Aprender a implementar rotinas de montagem otimizadas requer mais do que ver como o compilador compilou uma rotina. Você precisa entender por que o compilador escolheu esses opcodes nessa ordem para reproduzir esse código C ++ específico. E isso requer conhecimento íntimo da CPU, agendamento de instruções e assim por diante. Generalizar isso requer anos de experiência; você não conseguirá apenas decodificando algumas rotinas.
Nicol Bolas
7
Portanto, -1 para A: na verdade não está respondendo à pergunta sobre como escrever rotinas otimizadas para montagem. B: deturpar como é fácil aprender a vencer o compilador ao escrever rotinas otimizadas para assembly. E C: incentivando um programador a analisar as otimizações no nível da montagem antes das otimizações no nível do algoritmo. Mesmo aqueles "especialistas do setor" altamente remunerados diriam que isso está colocando a carroça na frente dos bois.
Nicol Bolas
2
@Amaursa: ninguém disse que as pessoas não deveriam "entender a desmontagem e como otimizar o código". Este não é um debate religioso; é uma questão de fato simples. As pessoas passaram séculos, otimizando manualmente alguma rotina, apenas para descobrir que isso não significa nada para o desempenho geral. Aprender a otimizar algoritmos é um conjunto de habilidades altamente valioso. Aprender a ler montagem é um conjunto de habilidades semi-valioso. Aprender a escrever rotinas de montagem é um conjunto de habilidades que raramente é usado. Hoje em dia, as melhores otimizações vêm de uma melhor utilização do cache, e não da montagem manual.
Nicol Bolas 14/11
22

A primeira dica que você terá é essa - não.

Os compiladores modernos são realmente muito bons em otimizar o código e terão muito mais chances de fazer um trabalho melhor do que qualquer linguagem assembly autolaminada que você possa escrever.

A exceção seria qualquer caso específico em que você determinou com certeza que o compilador está fazendo um trabalho ruim de otimização, então essa é a segunda dica. Não há diretrizes gerais aqui, você precisa conhecer seu próprio código, saber o que está fazendo, ser capaz de saltar para uma desmontagem e ser capaz de determinar com absoluta certeza que o compilador está fazendo um mau trabalho.

Mesmo neste caso, você ainda pode não querer. Você precisa ter certeza de que não haverá nenhuma sobrecarga de manutenção em andamento para você. Você pode voltar a esse código em seis meses e modificar parte dele, ou pode encontrar um bug extremamente sutil que será mais difícil de corrigir em uma versão em linguagem assembly. Mesmo que você ache que já resolveu todos os problemas, uma vez que seu programa vai para os erros públicos, você nunca pensou que isso poderia acontecer, se tornará uma realidade para você. Isso é bastante revelador (e uma experiência humilhante).

E mesmo que você esteja feliz em aceitar isso, você ainda pode achar que não há absolutamente nenhuma melhoria mensurável de desempenho, pois seu principal gargalo pode estar em algum lugar completamente diferente em seu programa. Então, isso me leva de volta ao número 1 novamente. Não.

Maximus Minimus
fonte
15

Normalmente, a otimização sólida não depende do uso do Assembly ou da micro-otimização com código em linguagens de nível superior. Se você ler muitos trabalhos de pesquisa (como eu faço - ou tentar!), Verá que muitas vezes as melhorias feitas nos algoritmos estão em um nível conceitual mais amplo, "qualitativo", em vez de mais "quantitativo" nível de micro-otimização. Eu enfatizaria que os ganhos em ordem de magnitude são mais prováveis ​​de se observar algoritmos desse ponto de vista ou de vetorizar / paralelizar soluções existentes.

Dito isto, recentemente me deparei com isso , o que pode ser um bom caminho para o aprendizado do ASM x86 especificamente para desenvolvedores de jogos.


TERMO ADITIVO

Duas fontes em cima da minha cabeça:

Além disso, a leitura de trabalhos de pesquisa é uma excelente maneira de seguir os processos de pensamento dos sábios, pois otimizam os algoritmos para obter melhor desempenho. Na maioria das vezes, os ganhos são vistos por:

  • Reduzir o uso das operações mais caras (div, SQRT, trig ops e condicionais, principalmente);
  • Melhorando o desempenho do cache através do uso de estruturas de dados mais eficientes, alinhamento de memória e condições condicionais reduzidas;
  • Reduzir a qualidade da produção em áreas aceitáveis ​​para melhorar o desempenho;
  • Vetorização (SIMD);
  • Paralelização (encadeamento, inclui a transferência de tarefas para a GPU);
  • E, é claro (raramente), montagem codificada à mão. Primeiro, inspecione os assemblies C / C ++ para ver onde o compilador está fazendo escolhas não ideais, é claro. Você encontrará mais disso em artigos mais antigos dos anos 80 e 90, IME.

A pesquisa em leitura também mantém você na vanguarda do seu campo, em vez de esperar que esse conhecimento seja filtrado pelo setor.

Engenheiro
fonte
você fala sobre otimização de algoritmos, mas não fornece informações sobre isso, se seguíssemos seus conselhos e analisássemos isso, você poderia dar alguma orientação?
Skeith
De fato, eu menciono isso; você precisa estudar algoritmos, entendendo o que os cientistas da computação fazem para melhorar qualitativamente o desempenho. Mergulhe nisso o suficiente e, com o tempo, você começa a pensar em termos semelhantes. Esforços incrementais aqui valem muito tempo, ao contrário de passar anos (e vi recentemente isso mencionado em um fórum do ASM) dominando os meandros de (apenas) por exemplo. arquitetura x86. Caça o grande jogo: aprenda a reduzir os problemas até o âmago e, em seguida, decida o que é supérfluo para otimizar. Veja livros de referência acima.
Engenheiro de
@NickWiggill Qual é a sua fonte usual de trabalhos de pesquisa?
kizzx2
3

Eu acho que pode ser muito cedo.

De qualquer forma, é importante entender que o próprio compilador não produz código mais lento que o equivalente ao assembly, você não obtém desempenho simplesmente escrevendo o mesmo código de assembly que o compilador produziria.

Para começar, concentre-se em otimizações sem montagem. Igor Ostrovsky tem alguns bons artigos que demonstram alguns dos princípios básicos: http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

Observe que erros de previsão de ramificação e falhas de cache são contra os quais você deve otimizar principalmente, mesmo se você tiver que pagar fazendo algumas operações aritméticas extras, geralmente vale a pena evitar uma ramificação imprevisível ou ler aleatoriamente a partir de muita memória.

E, claro, o mais importante, otimize seu algoritmo primeiro. Uma implementação lenta de um algoritmo rápido quase sempre será mais rápida do que uma implementação rápida de um algoritmo lento.

aaaaaaaaaaaa
fonte
2

Este livro é excepcionalmente bom para um livro de texto. Mas não é voltado especificamente para a otimização. Linguagem Assembly para processadores x86, 6ª edição

É mais sobre ensinar os fundamentos da montagem, usando o MASM. Depois, no final do livro, ele aborda como alinhar o assembly com o c ++ e integrá-lo a programas maiores.

Coloquei isso aqui porque faz sentido aprender os fundamentos da montagem antes de aprender como otimizar os programas com ela.

Gosto deste livro porque o Irvine ensina como usar as ferramentas necessárias para escrever programas de masm. Ele explica especificamente como usar o IDE (Visual Studio C ++) e o depurador. Cada capítulo possui alguns vídeos dedicados à solução de problemas. Algumas dessas informações estão disponíveis gratuitamente no site listado.

NadtheVlad
fonte
1
"faz sentido aprender os fundamentos da montagem antes de aprender a otimizar programas com ela" - um bom conselho.
Maximus Minimus