Enfim chegamos à parte que todos esperavam. Como extrair ou últimos ciclos do seu processador. Como evitar fazer qualquer coisa que não seja realmente necessária ao seu código. Mas antes de começar a carnificina, algumas considerações:

• Antes de mais nada, otimização não deve ser feita em todo o seu código. Deve ser feita apenas nos gargalos de desempenho. Após o código ser otimizado, ele costuma ficar muito ilegível ou até mesmo inseguro e instável. Por isso, quanto melhor escolhida a área de otimização, melhor sua otimização.
• Nunca, mas NUNCA mesmo, comece seu projeto já otimizando o código. Essa é uma das receitas para o fracasso total do seu projeto. Código otimizado é mais difícil de ler, de escrever e de depurar. Normalmente você vai perder horas apenas pra entender o que está acontecendo em um bloco de 20 linhas de código.
• Otimização não reduz a complexidade do algorítmo. Usar um algorítmo melhor (de menor complexidade) é quase sempre mais indicado do que otimizar o código (falo quase sempre porque talvez exista algum caso estranho em que isso não seja verdade).

Mas, se depois de fazer tudo isso, seu código ainda não roda em tempo satisfatório, o resto das dicas pode ajudar bastante:

• Antes de mais nada, encontre o gargalo de desempenho. Normalmente um programa gasta 90% do tempo executando 10% do código. Esses 10% devem ser o alvo da sua otimização
• Indique quais variáveis devem ser mantidas em registradores. Geralmente contadores são as variáveis mais acessadas durante a execução de um laço. Se elas forem mantidas nos registradores, você ganhará tempo pois elas não precisam ir para a cache e voltar o tempo todo.
• Sempre que possível, evite calcular duas vezes a mesma coisa. Armazene o resultado(não estou falando de Programação Dinâmica. Estou falando de cálculos simples, como onde deve estar a informação em uma matriz).
• Quando precisar atravessar um vetor em ordem crescente ou decrescente, faça isso com um loop em que o ponteiro é incrementado. Isso é mais eficiente porque quando você acessa uma posição de um vetor, você usa uma multiplicação para isso. Quando você atravessa o vetor incrementando o ponteiro, a multiplicação é trocada por uma multiplicação mais simples (dependendo, pode ser até mesmo um bitshift) e uma soma.
• Não passe muitos parâmetros ou parâmetros grandes para funções. Dê preferência a passagem de ponteiro quando o parâmetro ultrapassar o número de bytes de uma Word (4 bytes em um processador de 32 bits e 8 em um de 64). Com isso, você reduz o overhead do protocolo de chamada de função, que deve alocar memória extra na pilha e identificar os seus parâmetros.
• Sempre que possível e viável, declare suas funções como inline. Funções inline são inseridas diretamente no código, evitando a chamada de função. Mas não faça isso com funções grandes (mais que 7 linhas). Pode gerar erros estranhos e bugs realmente difíceis de achar, além de não melhorar a velocidade do código
• Troque chamadas de funções simples por macros. Uma macro é ainda mais eficiente que uma função inline, mas é menos segura.
• Declare suas variáveis no bloco mais local possível. Assim, somente quando ela for necessária ela será alocada.
• Quando suas condições booleanas forem compostas, coloque elas em ordem de frequência. Isso otimiza pois C fecha as codições booleanas por “curto-circuito”. Quando alguma delas impede que o resultado seja TRUE, ele simplesmente considera FALSE e não testa o resto. Então faz bastante diferenção você verificar primeiro algo que quase nunca acontece e somente depois você verifica o que está sempre determinando a condição booleana.
• Se quiser economizar memória em suas structs, coloque os tipos de dentro dela em ordem decrescente de tamanho (em bytes). Isso vai impedir que o compilador use um alinhamento de 4 ou 8 bytes para toda a estrutura. Mas cuidado porque isso pode reduzir o desempenho do seu programa.
• Se estiver usando algum compilador que defina _GNUC_, ou seja, suporta o padrão GNU para C, especifique atributos (__atributte__) para as suas funções e estruturas indicando o que pode ou não pode acontecer com elas.
• Use assembly. C possui suporte a assembly inline, usando o identificador “asm” (”__asm__” também é válido em compiladores GNUC).

Mais informações: Optimizing C and Cpp e C Coding

Próximo post: ???

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.

A construção de algoritmos genéricos é útil pois evita que você tenha que reescrever código muito semelhante para trabalhar com dados diferentes. Bons exemplos de algoritmos genéricos são o qsort e bsearch, ambos da stdlib.h . Eles são implementações de um algoritmo de ordenação e de busca em vetores de qualquer tipo de dado. Eles funcionam mais ou menos assim:
- Além das informações óbvias, como o vetor a ser ordenado (base) ou item a ser procurado (key) e o tamanho deste vetor (nmemb), eles também pedem que você passe o tamanho em bytes de um item do vetor (size) e uma função de comparação para esses itens (comp). É aqui que começa a parte genérica do algorítmo.

Basicamente, onde numa implementação normal desses algoritmos você colocaria algum operador de comparação, você agora vai colocar uma chamada para a função de comparação. E onde estaria um operador de atribuição, você vai colocar, por exemplo, um memcpy copiando “size” bytes de uma posição para a outra. Dessa forma, seu algorítmo agora é capaz de funcionar para qualquer tipo de dado que você deseje usar. Mas qual a vantagem? Existem várias:

1. Basta escrever o código do algorítmo uma vez, e depois você apenas precisa escrever a função de comparação, muito mais simples do que o algorítmo.
2. Como o código será mais usado (pois está sendo reaproveitado), é cada vez menos provável que existam bugs, pois mais pessoas estarão testando esse código.
3. Você reduz em muito o tempo de desenvolvimento de um projeto se já tiver libs genéricas para coisas como Estruturas de Dados, Serialização, etc.
4. Você pode implementar alguns paradigmas de Orientação à Objetos, que muitas vezes ajudam em grandes projetos

O único problema disso é que o código fica meio “hard coded” e você precisa trabalhar com ponteiros de função que são feios. Mas isso você resolve criando uma camada a mais que esconde toda essa parte. Da até pra esconder mais coisas se você usar macros, mas isso é assunto de um próximo post.

Antes de implementar um algorítmo genérico, recomendo que olhem os posts sobre Ponteiros e Ponteiros de Função pois a base para os algorítmos genéricos são eles.

Mais informações: Boa pergunta… Nunca encontrei nada sobre isso. Deixem um comentário ou mandem um e-mail pra mim.

Próximo post: Tunning

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.

Enfim chegamos ao assunto que causa dor de cabeça à maioria dos programadores iniciantes (e à muitos veteranos também). É complicado trabalhar com a referência ao invés de trabalhar com o objeto.

Basicamente, um ponteiro é a posição de memória onde está a estrutura. Se pensarmos na memória como um vetor, o ponteiro é um índice desse vetor. Em C, um ponteiro simplesmente indica uma posição de memória e nada mais. Todo o resto da informação (como, por exemplo, que tipo de estrutura é apontada) existe apenas em tempo de compilação. Em tempo de execução memória é simplesmente memória e nada mais. Isso permite um maior controle sobre ela. É possível com um simples cast mudar totalmente a forma como ela é tratada. Por exemplo, é possível transformar um vetor de inteiros em um vetor de char. Internamente a única coisa que mudou é quantos bytes tem a estrutura do vetor. Isso também vale para casts de ponteiro de estruturas.

Tá, mas o que eu faço com todas essas mudanças? Simples. Sabendo de tudo isso é possível agora aproveitar-se disso. Por exemplo, você pode fazer uma alocação de centenas de bytes e utilizá-la como vários objetos diferentes em sequência, dessa forma criando um semi-alocador de memória muito mais rápido do que o malloc (o custo do malloc ficará dividido entre os vários objetos). Mas para isso é necessário entender um pouco de aritmética de ponteiros.

Quando você soma 1 a um inteiro, ele simplesmente incrementa o inteiro. Se ele valia 2 passa a valer 3. Com ponteiros é um pouco diferente. Cada vez que você incrementa um ponteiro a seguinte conta é feita (sendo aux o ponteiro e código aux++):

aux += sizeof(*aux)

Ou seja, quando você incrementa o ponteiro ele na verdade é incrementado com o samanho do objeto para o qual ele aponta, em bytes. Vale lembrar que é o mesmo cálculo realizado para acessar a posição de um vetor (esse cálculo é invisível pois você usa [ e ]). Se você usar soma normal, ele fará algo assim:

aux += N*sizeof(*aux)

Com N sendo o número que foi somado ao ponteiro.

Com tudo isso, é possível fazer algumas “bizarrices” não recomendadas, mas que funcionam muito bem se você vai produzir algum software pequeno e que você consegue entender de ponta a ponta:

• Se você colocar em seus objetos uma convesão de que o primeiro byte serve para a identificação do tipo de objeto (todos seus objetos terão um char para id e ele será o primeiro item da estrutura). Dessa forma você criou suporte a algo que o C não suporta: polimorfismo. Sabe em Java quando você cria uma interface e qualquer objeto que atenda essa interface pode ser passado como parâmetro sem problemas de compilação? Pois é. Internamente o princípio é semelhante. Sem contar que também é possível descobrir que tipo de objeto ele é em tempo de execução e pode processá-lo de acordo, como você faz em Java com o comando instanceof.
• Para carregar um vetor de ponta a ponta, é mais eficiente você usar aritmética de ponteiro ao invés de loop, pois no loop você tem o incremento do contador e a multiplicação para chegar ao lugar desejado. Se os dados estão em sequência, précalcule (se possível) o fim do vetor e avance posição a posição usando incremento simples. Isso vai poupar bastante tempo se for feito em uma zona de gargalo computacional.
• Voltando ao exemplo do alocador, se você estruturar um sistema que faça alocação de grandes blocos e depois separe-os em pequenos pedaços, para ter um semi-alocador (ele não aloca na verdade, ele apenas distribui a memória) rápido basta colocar um contador para saber quando o bloco acabou. Você gasta um pouco mais de memória com isso, mas nada muito relevante comparado ao desempenho, desde que você tenha muitos pedidos de blocos pequenos.
• Da pra fazer várias outras mágicas com ponteiros em C, mas com essas três já é possível fazer muita coisa.

Próxima semana: Algoritmos genéricos em C

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.

Para deixar um sistema mais rápido (e muitas vezes mais “macio”) é necessário que você execute várias coisas ao mesmo tempo. Você não precisa fazer com que seu programa simplesmente pare de fazer algo simplesmente porque o usuário clicou em outro botão. Você também pode estar querendo aproveitar um segundo processador da máquina ou mesmo aumentar o número de acessos ao processador (é difícil fazer um jogo rodar quando o Windows come metade do sistema e o anti-vírus mastiga o resto). O que fazer então? Bom, você poderia pedir pro usuário fechar o anti-vírus (o que ele não vai fazer) ou mandar ele apelar pro bom senso e desligar o tocador de mp3, Word, Messenger, Internet Explorer e todas as tranqueiras que ele tem em stand-by para então rodar o seu programa. Esquece… Isso não vai acontecer. O que nós programadores podemos fazer, então? Simples. Podemos dividir o nosso programa em várias threads e aumentar a prioridade delas, aumentando o nosso acesso ao(s) processador(es) e diminuindo o dos outros programas. Mas vamos com calma.

Uma thread é basicamente um outro programa rodando mas que tem os mesmos direitos de acesso à memória que o programa que carrega ela (que seria a thread principal). Esta não é a definição formal. É mais uma utilidade prática do negócio. Como ele tem os mesmos direitos de acesso à memória, compartilhar dados entre os dois programas é fácil. E cada um tem sua própria pilha, então nem precisa se preocupar com um eventual estouro dela (não abusem dessa frase, é possível estourar a pilha, apenas menos provável).

C não possui nenhum suporte nativo à threads (isso é algo que depende muito do kernel do sistema operacional, pois é ele quem coordena os processos - entenda como threads + programas - e verifica quando estes vão pro processador e para qual processador vão). Então é necessário que você utilize uma biblioteca do sistema operacional.

O Windows utiliza o header windows.h (sugestivo, não?), mas qualquer coisa que você compile que tenha incluído esse header irá demorar milênios para compilar, pois esse header é realmente imenso. Para evitar isso, defina a constante WIN32_LEAN_AND_MEAN antes de incluir o header e assim você evitará incluir um monte de coisas nas quais você provavelmente não está interessado.

Linux e MacOS X utilizam a pthread.h. MacOS Clássico não possui suporte nativo, mas difícilmente você irá produzir uma aplicação pra clássico hoje em dia.

Mas e se eu quiser produzir uma aplicação portável entre alguns desses sistemas, o que que eu faço? Vou ter que forçar a portabilidade “no braço” com #ifdef ? Não. Você pode usar uma das seguintes bibliotecas:

• SDL : A biblioteca SDL possui suporte à threads e é portável para esses sistemas que eu citei acima a vários outros.
• pthread : pthread? Sim. A pthread possui ports para Windows também. A vantagem é que a pthread é implementada e possui todas as funcionalidades em qualquer um dos sistemas. A SDL_Thread possui apenas as funcionalidades comuns desses sistemas. (Não coloquei o link porque Pthread é a especificação Posix para Threads. Portanto qualquer implementação que siga essas especificações é uma pthread.)
• pth : A pth é implementação de threads do projeto GNU, que roda em vários sistemas.
• Existem algumas outras, mas essas provávelmente são as três mais poderosas

Mas antes que você pense que threads são a solução para todos os problemas, tome cuidado. Thread é uma ferramenta poderosa, mas é bem complicado de utilizá-la. Recomendo que estude seriamente programação concorrente antes de se aventurar pelos incontáveis erros de sincronismo praticamente indetectáveis que as threads produzem.

Próxima semana: Ponteiros e Aritmética de Ponteiros.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.