Posts Tagged ‘ C ’

Otimização 0.1

Achei bem interessante que nesse tempo que fiquei sem escrever, o blog teve uma quantidade de acessos maior que em tempos de atividade. De qualquer forma, um post de vez em quando não faz mal a ninguém :).

Tem um site de tirinhas chamado Vida de Programador que posta situações corriqueiras (as vezes) de forma engraçada.

Na tirinha de hoje, ele mostrava o código de um programador iniciante:

bool isValid;
...
switch(isValid) {
case true: ...
case false: ...
}

Claro que não faz sentido tanta verborragia pra algo tão simples como uma variável booleana. No entanto, as pessoas se esquecem que os compiladores atuais são muito bons e não vão deixar seu código lento só porque você preferiu que ele fosse “mais legível”.

Uma excelente ferramenta online chamada GCC Explorer mostra a saída assembly do seu compilador preferido com diversos níveis de otimização.

Independente do nível de otimização, o código gerado para o trecho acima será extamente o mesmo que para “if...else” ou o operador ternário “? :“.

int testFunction(bool x) {
  switch (x) {
    case true:
        return 10;
        break;
    case false:
        return 12;
  }
}

int testFunction2(bool x) {
  return x? 10 : 12;
}

E o Assembly gerado (com -O2) será:

testFunction(bool):
	cmpb	$1, %dil
	sbbl	%eax, %eax
	andl	$2, %eax
	addl	$10, %eax
	ret
testFunction2(bool):
	cmpb	$1, %dil
	sbbl	%eax, %eax
	andl	$2, %eax
	addl	$10, %eax
	ret

Se você olhar, não há nenhum jump no assembly gerado. Ele compara a variável com o número 1, subtrai o registro de retorno dele mesmo com borrow, faz um AND com o 2 e depois soma 10. Você não ia pensar que retornar 12 ou 10 significa colocar 2 ou 0 numa variável e depois somar 10, mas o compilador sabe que lógica AND e OR para números inteiros é muito mais rápida que jumps e faz tudo sem que você se preocupe. Esse código seria semelhante a:

int testFunction3(bool x) {
  return 10 + (2 & -(1-x));
}

Mas o GCC consegue diminuir ainda mais o assembly!

testFunction3(bool):
	leal	3(%rdi), %eax
	andl	$2, %eax
	addl	$10, %eax
	ret

Só que ninguém vai querer ler um código tão feio assim que apenas poupa 1 nanossegundo.

Sem dar razão à pessoa que fez um switch para um bool, se o código não é o gargalo do seu programa, não há motivo para mudar. Como escreveu Donald Knuth: otimização prematura é a raiz de todo o mal.

Anúncios

Python + Arduino (Parte 2)

Além de plotar gráficos, com o Python é possível criar interfaces para modificar parâmetros do microcontrolador, enviando dados pela porta serial.

Como já visto na Parte 1 deste assunto, é preciso instalar o PySerial além do Python.

Desta vez eu fiz em uns 30 minutos um programa para enviar ao Arduino um número de 0 a 255 (8-bit) que serve para mudar o valor da resistência de um potenciômetro digital que deveria estar ligado à um amplificador de som.

Estou sem o amplificador no momento, então, para visualizar as mudanças coloquei um led para acender com PWM dentro do programa do arduino.

/*
 * Exemplo de leitura serial com o Arduino
 * Colocar isso dentro de um loop do programa
 */

char palavra[10];
unsigned char valor;

if (Serial.available()) {
    delay(100);
    unsigned char n = 0;
    while (Serial.available() > 0) {
        palavra[n++] = (Serial.read());
        //Cuidado com escrita fora do array
    }
    palavra[n] = '\0';

    valor = atoi(palavra);

    /*Usar o 'valor' para fazer alguma coisa, 
      como acender um Led com PWM*/
}

Outro dia coloco vídeo do sistema funcionando.

Caracteres personalizados

Estava vendo um post do Hack a day que mostrava um relógio num display de texto com os caracteres personalizados.

Cada letra do display de texto, ao menos esses com controlador HD44780 ou similar, é uma pequena matriz de 8 linhas por 5 colunas, sendo que você apenas escolhe o carácter e o controlador preenche a matriz.

Para estilizar os caracteres, você precisa gravar novos na memória volátil do controlador do LCD, sendo que ela tem espaço apenas para 8 (0 a 7 da tabela ASCII, não podem ser impressos). Os outros não podem ser modificados.

A ideia aqui é juntar 3 colunas para formar um número grande. Para isso, é preciso criar os caracteres que vão ser usados para desenhar as partes do número, sendo que precisam ser bem genéricos para que caibam nos 8 espaços da memória.

No caso eu usei 5 caracteres. Os três acima e as versões invertidas dos dois últimos. E criei os números como abaixo:

Para criar cada um dos 5 caracteres estilizados, é preciso enviar ao LCD o formato de cada uma das 8 linhas com números de 0 a 31, onde cada bit acende um ponto da linha. Você pode usar notação binária (por exemplo 0b10101) ou colocar o número decimal correspondente, se achar mais fácil.

Com as bibliotecas do Arduino, pode ser feito algo como:

LiquidCrystal lcd(2, 3, 4, 8, 9, 10, 11);
byte meus_chars[][8] = {{31,31,31,31,31,31,31,31}, 
                        {31,31,0,0,0,0,0,0},   
                        {0,0,0,0,0,0,31,31},
                        {31,31,0,0,0,0,0,31},
                        {31,0,0,0,0,0,31,31}};

for (byte i=0; i<5; i++){
    lcd.createChar(i, meus_chars[i]);
}

//Exemplo de exibição do número 0
lcd.clear();
lcd << '\0' << '\1' << '\0';
lcd.setCursor(0,1);
lcd << '\0' << '\2' << '\0';

Falando nisso, baixe a biblioteca Streaming que faz overload do << para imprimir coisas no LCD ou na Serial.

Abaixo um vídeo dos números no display:
Meu display 16×2 ainda não chegou. Enquanto isso, continuo com esse 8×2.

Tempo de processamento – Funções muito rápidas

Medir o tempo que uma função gasta para ser executada parece ser bem simples, olhando superficialmente.

Teoricamente, só seria necessário gravar o tempo de início e subtrair do tempo do fim.

O problema nesse tipo de medição é que, nos PCs só temos acesso à milisegundos (10⁻³ s) no relógio e uma instrução que seja processada em poucos ciclos de clock dura alguns nanosegundos (10⁻⁹ s).

O que fazer para medir esses nanosegundos?

A primeira solução é usar probabilidade:

pulso

Olhando a imagem, podemos perceber que a medição de tempo pode ser tanto zero ou um, dependendo se a função começou a ser executada próximo do início da borda de subida do pulso de clock.

Assim, mandamos a função ser executada centenas ou milhares de vezes e teremos como encontrar sua duração, com um erro que diminui com o aumento do número de execuções.

Note que o processador conta ciclos de clock, que na função clock() duram 1 milisegundo cada. Por isso, em alguns lugares teremos divisões por 1000.

Exemplo:

#define N 1000000
tempo_inicial = clock() / 1000;
for (i =0; i < N; i++) {
    funcao();
}
tempo_final = clock() / 1000;
duracao = (tempo_final - tempo_inicial)/N;

Essa solução funciona muito bem, mas na medida que você vai aumentando a complexidade ou os dados de entrada vai ser preciso ficar ajustando o número de execuções, para que não demore tempo demais para dar precisão de nanosegundos à uma função que demore microsegundos ou até alguns milisegundos.

Assim, é aconselhado usar um medidor de tempo máximo para executar instruções. Ou seja, antes de executar a função novamente, deve-se conferir se o tempo de execução de esgotou ou não, garantindo um número mais alto de execuções para funções mais rápidas e um número menor (com erro maior) para funções mais demoradas.

Exemplo:

#define tTotal 1000
numExecs = 0;
t1 = clock();
limite = t1 + tTotal;
while ( clock() < limite ) {
    funcao();
    numExecs++;
}
t2 = clock();
duracao = (t2-t1) / (numExecs*1000);

Como o Sistema Operacional está quase sempre realizando operações leves, podemos ter erros de medidas caso a função fosse rodada apenas uma vez, como inicialmente proposto. Com o uso de probabilidade, podemos diluir esse gasto entre todas as medidas, tornando-o desprezível.

Alguns erros de medida podem ser gerados por causa do “warm-up” de cache, entre outras coisas, sendo aconselhado repetir o teste algumas vezes. O valor medido será quase constante após algumas medidas.

Uma Observação:

Caso a função a ser medida seja muito rápida, esse segundo método pode criar um overhead, fazendo com que o tempo total para entradas com poucos dados seja confundido com o gasto de processamento do código do nosso cronômetro.

Para amenizar isso, é possível repetir o bloco sem chamar a função e depois subtrair o tempo gasto do tempo total anterior.

Note que isso só será necessário em funções que durem menos de microsegundos.

Loops em C

A discussão do dia foi sobre o loop while em C, no sentido de diminuir o tempo de processamento.

A ideia que me foi proposta era:


while (condicao1 && condicao2) {
//instrucoes
}


A condição com mais probabilidade de dar zero (olhando as características do programa) deveria ser escrita primeiro ou não faria diferença?

Para nós, seres pensantes, olharíamos o primeiro caso e, se fosse falso, o AND também seria, então não seria preciso olhar o segundo.

Mas, como a linguagem C, além de outras, permite que você atribua valor a uma variável ou execute uma função dentro do WHILE, do FOR e do IF, o processador seria obrigado a processar as duas condições.

No entanto, isso acaba não acontecendo, o que pode ser perigoso se você precisa do valor de uma variável ou que uma função apresente algum dado específico!

Portanto, sim, é válido escolher a melhor ordem para fazer um AND num loop em C e na maioria das linguagens dessa derivada, como C++ e Java. Claro que isso também pode depender do compilador usado, mas esse é o “comportamento padrão”. Isso também não pode ser dito como verdade para todas as linguagens, então é bom prestar atenção

Isso tudo que eu falei também vale par o OR, quando a primeira condição é verdadeira.