Optimização de código (performance)

[Happening]

Boas, estou a tentar optimizar código. Já fiz uma condensação de funções ou seja o que tinha em 2 pus numa e já vi outro método que é o inlining de funções. Queria saber se era possivel fazer um inlining definindo uma macros para a seguintes funções:

Função 1:

void tabela_apaga(tabela_dispersao *td)
{
int i;
concelho *temp;
if(td!=NULL){
 if(td==NULL) return TABDISPERSAO_INVALIDA;
for(i=0;i<td->tamanho;i++)
{
 while(td->concelhos[i]!=NULL)
 {			    //Estava em duas funções separadas mas para aumento da performance utilizámos a mesma função de modo a termos menos chamadas a uma função

  temp=td->concelhos[i]->proximo;
  free(td->concelhos[i]->distrito);
  free(td->concelhos[i]->nomeConc);
  free(td->concelhos[i]->menorFreguesia->nome);
  free(td->concelhos[i]->menorFreguesia);
  free(td->concelhos[i]);
  td->concelhos[i]=temp;
 }
 td->concelhos[i]=NULL;
}

return TABDISPERSAO_OK;
 free(td->concelhos);
 free(td);
}
}

Função 2:

int tabela_adiciona(tabela_dispersao *td, const char *distritoNome, const char *nomeC, const freguesia *freg)
{
int x;
int first = 0;
concelho *pointer;
if(td==NULL) return TABDISPERSAO_INVALIDA;
x = td->hfunc( nomeC, td->tamanho);
pointer=td->concelhos[x];
first = (pointer == NULL);
while(!first && pointer->proximo != NULL){
 if(strcmp(pointer->nomeConc, nomeC) == 0)
  break;
 else
  pointer = pointer->proximo;
}
if (!first && strcmp(pointer->nomeConc, nomeC) == 0)
{
 pointer->nHabitantes = pointer->nHabitantes + freg->nHabitantes;
 if (freg->nHabitantes < pointer->menorFreguesia->nHabitantes)
 {
  pointer->menorFreguesia->nome = (char*)realloc(pointer->menorFreguesia->nome,(strlen(freg->nome)+1)*sizeof(char));
  strcpy(pointer->menorFreguesia->nome, freg->nome);
  pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
 }
}
else
{
 pointer = (concelho*) malloc (sizeof(concelho));
 if(pointer==NULL) return TABDISPERSAO_ERRO;
 pointer->distrito = (char*) malloc((strlen(distritoNome)+1)*sizeof(char));
 if(pointer->distrito==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->distrito, distritoNome);

 pointer->nomeConc = (char*) malloc((strlen(nomeC)+1)*sizeof(char));
 if(pointer->nomeConc==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->nomeConc, nomeC);

 pointer->nHabitantes = freg->nHabitantes;

 pointer->menorFreguesia = (freguesia*) malloc (sizeof(freguesia));
 if(pointer->menorFreguesia == NULL) return TABDISPERSAO_ERRO;
 pointer->menorFreguesia->nome = (char*) malloc((strlen(freg->nome)+1)*sizeof(char));
 if(pointer->menorFreguesia->nome == NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->menorFreguesia->nome, freg->nome);
 pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
 pointer->proximo = NULL;
}
if (first) td->concelhos[x] = pointer;
if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
 td->maiorConcelho = pointer;

return TABDISPERSAO_OK;
}

Edited May 26, 2012 at 07:44 PM by pmg
LP no GeSHi

[bsccara]

Inlining de funções raramente dá benefícios (repara que não escrevi 'grandes') em termos de velocidade. A única coisa que evitas são as instruções de call e ret, algumas para criar e destruir o 'stack frame' (se usado) e a passagem de parâmetros. Tudo junto para aí menos de 50 ciclos de CPU, excluíndo acesso à memória.

Se queres optimizar o algoritmo começa por fugir dos 'realloc' (custam uma alocação, cópia e libertação) e indo mais além cria um alocador próprio. Num caso meu consegui um aumento de velocidade de 5x apenas com um alocador de memória próprio.

Isto partindo do princípio que o código que mostraste é o mais eficiente para resolver o problema.

[Happening]

Disseram-me que a solução utilizando a tabela hash era muito eficiente e que utilizando sempre um apontador para o maior concelho fazia desta a solução mais eficiente. Um colega meu resolveu o problema por árvore binária e o tempo dele ia de 15 mili a 30 mili. O código todo está no tópico Tabela Hash (se quiseres ir lá ver)

Então propões que eu faça uma substituição dos realloc's por uma função própria? Isso não era o mesmo que utilizar free e malloc? É que não estou a ver outra maneira de fazer o mesmo que o realloc sem ser com free e realloc...

Obrigado 🙂

Edited May 27, 2012 at 10:40 AM by Happening

[bsccara]

O que escrevi foi que se a tua implementação é a mais eficiente para resolver o problema (não digo que sim nem não, não a estudei) e precisas que execute mais rapidamente o próximo alvo de optimização são as funções que usas e não escreveste. Como usas alocação dinâmica de memória, que é uma operação 'cara', as funções 'malloc', 'free' e 'realloc' são o alvo óbvio para optimização. Inlining de funções só compensa se as funções chamadas forem muito pequenas (meia dúzia de instruções) e chamadas num ciclo curto.

A possibilidade de obter ganhos reimplementando as funções de alocação dinâmica depende da existência dum padrão de utilização dessas funções que permita simplificar os algoritmos usados por essas funções. No caso que te indiquei o meu código alocava milhares de pequenos blocos, pouco a pouco, que eram depois libertados todos em bloco. A utilização de funções minhas, que funcionam por cima das funções 'malloc' e 'free', permitiram a aceleração que te indiquei.

Quando queres optimizar código para velocidade tens de antes de mais verificar onde estão os 'hotspots', ou seja, os locais do código que mais tempo de CPU gastam. Para isso deves usar um 'profiler'. Mediante os resultados obtidos é que decides o que optimizar (se tal compensar). Se não existirem 'hotspots' aparentes é altura de mudar o algoritmo ou resignares-te.

[Happening]

Ok então 1º uso um 'profiler', localizo os hotspots. OK mas se verificar que são nas funções free, malloc, realloc eu não faço ideia de como escrever uma função minha para substituir uma dessas funções...

Podes postar um exemplo? :/

[bsccara]

Não existe uma 'chapa 5' para isso, por isso é que as funções implementadas na bibliotecas são 'caras', pois são feitas para o caso genérico em que não se sabe qual é o (ou não existe um) padrão de utilização.

Se concluíres que estás a passar a maior parte do tempo nas funções de alocação terás de estudar a sua utilização no teu algoritmo, possivelmente instrumentalizando o código de maneira a escrever para um ficheiro uma linha por cada chamada a essas funções (com os parâmetros) e depois estudando esse ficheiro à procura de padrões. Cada caso é um caso e o meu era um caso limite, por isso consegui optimizar tanto essas funções.

No teu caso e olhando por alto, parece-me que tens uma optimização óbvia; usas uma estrutura com vários ponteiros para blocos alocados dinamicamente. Em vez de fazeres uma chamada ao malloc para cada bloco, calcula o tamanho total e aloca apenas um bloco, usando aritmética de ponteiros para obter ponteiros para cada um dos sub-blocos. Como o teu campo 'menorFreguesia->nome' pode mudar de tamanho, mete-o no fim do bloco; assim quando fôr preciso mudar o tamanho dele podes fazer realloc de todo o bloco sem ter de mudar os outros ponteiros.

A regra com funções 'caras' é simples; quanto menos vezes usadas melhor.

[Happening]

Já percebi aquilo que me estás a dizer. O problema é que o "custo" da velocidade é traduzido em memória do programa a executar e penso que não é a melhor solução por isso acho que me vou

resignar

🙂

De qualquer forma obrigado 🙂

[bsccara]

O problema é que o "custo" da velocidade é traduzido em memória do programa a executar...

Olha que a agregação de blocos de memória alocada dinamicamente reduz o consumo de memória do sistema pois cada bloco individual precisa de alguma campos escondidos para a implementação do alocador de memória. Se fizeres 100000 chamadas à malloc para 1000 bytes cada e medires a memória do SO disponível e a comparares com uma única chamada para 100000000 bytes verás que a memória disponível será um pouco maior no segundo caso.

Se queres dizer que o código será mais complexo também não me parece. Em vez de :

obj = malloc(sizeof(estrutura));
obj->nome = malloc(strlen(nome_passado) + 1);
obj->morada = malloc(strlen(morada_passada) + 1);
obj->localidade = malloc(strlen(localidade_passada) + 1);

se fizeres

obj = malloc(sizeof(estrutura) + (strlen(nome_passado) + 1) + (strlen(morada_passada) + 1) + strlen(localidade_passada) + 1);
obj->nome = (char *)obj + sizeof(estrutura);
obj->morada = (char *)(obj->nome) + (strlen(nome_passado) + 1);
obj->localidade = (char *)(obj->morada) + (strlen(morada_passada) + 1);

qual achas que executará mais depressa e consumirá menos memória ? Já para não falar numa possível melhor localidade dos dados, o que ajuda imenso os caches do CPU.

[Happening]

Realmente nunca tinha pensado nisso nem tinha visto alocações assim "essas pequenas brincadeiras" com o código podem melhorar imenso. O trbalho já foi entregue mas fica para referencia futura 🙂

Muito Obrigado 🙂