Otimização fina de código
Há um tempo atrás num post polêmico do Miguel (ando falando demais no passado né? mas tem coisas que não dá pra deixar passar…) o Raphael escreveu um comentário que me incomodou:
Performance? Dane-se! Python é mais lento que Java? Sem dúvida. Mas performance pura não importa hoje em dia. Hardware hoje já é tão barato que pouco importa se eu tenho que ter 1, 2 ou 3 máquinas para rodar o sistema. O que não pode é ter uma plataforma tão lenta que me obrigue a comprar 20 ou 30, que seria o caso do Ruby. Questão de ordem de grandeza.
É claro que eu tenho plena conciência que o Raphael não acredita 100% na afirmação acima e que ele estava envolvido numa discussão (quase) sem sentido com o Bruno… 
Prova disso é que mais pra frente, em outro comentário ele escreveu:
Eu quero uma stack de protocolo de comunicação SIP que atenda 100 mil usuários simultâneos
Que vai exatamente contra o que ele tinha dito antes! Afinal de contas, neste exemplo desempenho é primordial ou nada funciona. Talvez por isso eu estivesse achando a discussão (quase) sem sentido… Mas… vamos ao que (me) interessa!
O fato é que desempenho importa sim em muitos casos. Em algumas áreas ele é, eu diria, primordial. Mais essencial até que uma boa interface homem computador. Duvida? Pense então em criptografia.
Quase todo mundo hoje em dia sabe o que é criptografia e quase ninguém duvida que ela é essencial para nossa (falsa?) segurança na Internet. O fato que pouca gente sabe é que ainda hoje algoritmos criptográficos são exageradamente pesados. Aliás, para o desespero de alguns, é exatamente aí que está o segredo: não existe, ainda hoje, nenhuma prova formal de que algoritmos criptográficos sejam realmente seguros. O que todo mundo sabe é que é muito difícil quebrá-los com o que se conhece de teoria matemática hoje em dia. E é nessa dificuldade que é baseada boa parte da segurança das comunicações mundiais. Parece frágil isso, não? Definitivamente! E olha que eu nem comecei a falar nas técnicas não-matemáticas para se quebrar um algoritmo criptográfico… Mas isso não é conversa para este post.
Neste post, antes que eu perca o fio da meada de novo, quero falar de desempenho! Como algoritmos criptográficos ainda hoje são muito pesados, é muito comum você achar artigos e artigos na Internet de autores se vangloriando por terem achado um novo método revolucionário de implementar um algoritmo criptográfico que traz um ganho de desempenho de incríveis 5%! Ou ainda pesquisadores gastando meses fazendo testes para descobrir a combinação de flags de otimização a serem usadas no gcc para fornecer um ganho de 3%!
E é ai que eu queria chegar. Estudando um pouco sobre criptografia este semestre eu aprendi com o professor Julio López da Unicamp um método de otimização de código capaz de fazer com que um código rode consideravelmente mais rápido. Pense no seguinte trecho de código, bastante comum em algoritmos criptográficos:
if (a & 0x80)
r ^= b;
Basicamente o que se deseja fazer é testar um bit da variável a. Se este bit for 1 faz-se uma operação de soma em aritmética módulo 2 (um XOR) da variável b sobre um acumulador da resposta r. Este tipo de código, apesar de simples, costuma ser executado de forma muito ineficiente em processadores de propósito geral modernos. Isso porque este processadores são muito rápidos mas não são adivinhos. Para simplificar bastante o assunto, podemos dizer que antes de eles terem idéia do resultado do if eles já estão tentando executar a instrução em seguida (a soma). No entanto, eles podem descobrir alguns ciclos de relógio depois que a soma não deveria ser executada pois o if deu falso. Neste caso eles tem que voltar atrás e desfazer o deslocamento.
Os processadores modernos até tentam adivinhar qual caminho é o certo, mas nem sempre isso dá certo. Descobrir que o que ele estava fazendo estava errado e voltar atrás é algo que penaliza muito o processador. Perde-se às vezes dezenas de ciclos de relógio com isso… Tempo suficiente para executar talvez de 6 a 10 instruções, dependendo do processador. Ou seja, se conseguíssemos eliminar este if do código poderíamos ter um ganho. O código para eliminar o if acima é o seguinte:
r ^= b & (-((a & 0x80) >> 7));
Alguém vai dizer: “Ora bolas, mas agora ao invés de um if, que é em geral uma comparação e um salto condicional, e um XOR eu estou fazendo um XOR, dois AND, um deslocamento e uma inversão de sinal!” Por incrível que pareça isso, muitas vezes, é mais rapido, pois elimina qualquer possibilidade do processador ter que voltar atrás e jogar fora processamento, perdendo dezenas de ciclos de relógio de execução.
É este tipo de truque de programação que muitos pesquisados da área de criptografia passam meses tentando descobrir. Este truque, aliás, é bem conhecido. Ele é muitos outros podem ser vistos no livro Hacker’s Delight. Nunca olhei o livro profundamente mas ele já me foi muito bem recomendado.
E você tem algum truque bacana destes pra nos ensinar?
[…] dezembro 8, 2007 — Leandro Lameiro Motivado pelo Log4Dev, quero contar sobre um truque legal: o xor swap (também conhecido por triple-xor […]
ôôô Léo… Péra um pouco. Já disse o poeta: uma coisa é uma coisa, outra coisa é outra coisa.
O lance de otimizar código explorando características da arquitetura da máquina é legal e tem suas aplicações (Existe um esquema para fazer divisão inteira por 10 que é usado há muito tempo) e sempre vai ter gente forçando esse tipo de limite, quer por questões acadêmicas, quer por questões de competição de mercado.
O problema é a relação custo x performance. Um processador “top”, que acabou de sair do forno, custa 10 vezes mais que um processador “moderno”. Mas a diferença de performance não chega a ser de 10 vezes, não é mesmo?
Essa diferença de preço é meio artificial e pode ser atribuida à forma que as empresas fazem o “product cycle”, mas é outra história.
O ponto: performance para o aplicativo médio já não é um critério relevante. É por isso que as empresas que produzem processadores já estão tirando o foco do quesito “velocidade de processamento” e focando no ponto “performance/watt”. Diria até o seguinte: se não fosse pelos mercados de aplicações científicas e de videogames, as fabricantes de processadores estariam numa situação parecida com a da MS, que tem um produto na mão com recursos que não são desejados pela maioria do mercado consumidor.
De qualquer forma, meu ponto na minha discussão sem sentido é que mesmo as máquinas “menos modernas” já dão conta do recado muito bem dos requisitos de capacidade de processamento. Até mesmo as “centrais SIP com 100 mil acessos simultâneos” não precisam de processadores poderosos. Basta ter meia dúzia de PowerPC, algumas placas em redundância e uma saída de fibra óptica. O hardware de uma central dessas até seria barato. Caro é a tecnologia que vai em cima, e o serviço para gerenciamento disso.
Olá
Tenho um truque legal sim. Incentivado por este post, fiz um post no meu blog ( http://lameiro.wordpress.com ) sobre o xor swap, um truque para trocar 2 variáveis sem usar uma variável temporária.
Abraços e parabéns pelo blog.
Leandro Lameiro
Estava com saudades dos seus posts…
Solta o sapato no Lellis
Grande abraço,
Capitanio
Eita Lullis! hehehehe….
Tava esperando sua resposta à minha provocação.
E tenho que adimitir: uma coisa é uma coisa, outra coisa é outra coisa. Só peguei duas frases suas da mesma discussão mas em contexto diferentes e olha que que eu fiz
De qualquer forma, acho que foi um bom gancho para meu argumento.
Um abraço,
Leonardo Garcia
Domingo, 3AM, o sistema entra em produção daqui algumas horas. Como diferenciar os statements abaixo?
r ^= b & (-((a & 0×80) >> 0×7));
r ^= b & ((-(a & 0×80) >> 07));
r |= r & ((-(b & 0×08) >> 7));
r |= b & ((-(a & 0×80) <> 0×7));
r |= r & ((-(a & 0×80) >> 7));
r ^= b & (-((a & 0×08) <> 7));
r ^= r & (-((b & 0×08) << 0×7));
Para sacrificar a legibilidade de maneira tão atroz só com provas irrefutáveis da necessidade do código acima
Bruno,
Concordo com você! E é por isso que eu dei o meu exemplo em uma classe bem específica de problemas: algoritmos criptográficos.
Nesta classe de problemas eficiência é muito mais importante que legibilidade de código. Quer um exemplo: OpenSSL, a biblioteca de criptografia mais usada no mundo. Se você ler, por exemplo, a especificação do AES, o algoritmo é relativamente simples de entender. Pegue a implementação do AES no OpenSSL porém e veja que existe uma diferença relativamente grande entre o que está na especificação e o que foi implementado.
Como você bem disse, é o tipo de coisa que ninguém vai querer num sistema que irá entrar em produção em algumas horas ou que precise de manutenção constante. Mas em aplicações que rodam em ambientes não muito favoráveis como os algoritmos criptográficos ou os microcontroladores citados pelo Leandro Lameiro acima, estes truques ilegíveis muitas vezes são as únicas saídas.
Um abraço,
Leonardo Garcia
L. Garcia,
Acho que você já tinha deixado isto bem claro no post, foi mais para enfatizar um pouco mais
[ ]’s!!
Bom post. Gerou uma discussão interessante, mas minha vida como programador ainda é muito nova (não, eu entendi tudo aqui), mas prefiro não comentar e depois falar besteira…
Como dizem “é melhor ficar calado e acharem que você é um idiota do que você falar e terem certeza…”
Bom, já falei
Phil,
Não sei quem disse a frase “é melhor ficar calado e acharem que você é um idiota do que você falar e terem certeza…” mas já a escutei várias vezes e conheço várias pessoas que ficam intimidadas por esta idéia.
Mas, na minha opinião, a gente tem sempre que se espressar. É claro que devemos pensar antes de falar porque senão pode sair só besteira mesmo e ai a coisa fica muito feia. Mas se não nos espressamos e falarmos o que pensamos não há possibilidade de nos corrigirmos. Aliás, também não existe possibilidade de influenciarmos os outros e de construírmos idéias novas a partir dos diferentes pontos de vista que só são possíveis devido às diferenças de visão de mundo de cada pessoa.
Não quero forçar-lhe a falar. Acho que temos que fazer aquilo que nos é confortável. Mas da minha parte mesmo você provavelmente sempre ouvirá eu falar ( (quase sempre) depois de pensar no que eu vou falar). Aliás, neste blog mesmo, o primeiro artigo que eu escrevi (que pode ser lido em http://log4dev.com/2006/08/17/redes-e-o-futuro-da-computacao/) foi refutado. E não vi problema nenhum sobre isso. Não parei de escrever. Continuei, com a certeza de que só através de conversas e discussões que o mundo evolui.
Um abraço,
Leonardo Garcia
Sem problemas Leonardo, foi mais uma brincadeira que em si algo sério, mas os assuntos nos comentários ficou mais que resolvido me parece. Nada acrescentar
Abraços!
Phil, a vida é muito curta, solta o verbo!!!
Ótimo exemplo, Bruno!
Hi, hoje em dia o primeiro código pode ser bem mais rápido que o segundo. Se você tiver uma cpu moderna e um compilador moderno, o primeiro if pode ser compilado para um opcode cmov, que não tem branch e nem segura a pipeline. O segundo código tem uma trilha muito longa de dependência de dados, então o código com cmov acaba sendo mais amigável pra cpus com out-of-order execution.