Notas sobre optimizações II: O código

Creio que essa revisão do primeiro artigo sobre optimizações acabará ficando grande, por isso separei-a em algumas partes. Primeiro, o código, claro.

O script que usei para os benchmarks está no artigo anterior a este, e vamos usar patches algumas vezes. O código em si é aquele para ler arquivos de configuração, mas com algumas alterações. Além disso, eu usei aquele mesmo código do primeiro artigo para criar um arquivo de configuração aleatório.

Instruções para obter o código

Infelizmente, me parece que o wordpress.com não permite fazer upload de .tar.gz ou qualquer coisa do tipo, então vou ter que passar os códigos por aqui mesmo. Além disso, boa parte dos códigos são repetidas, mudam apenas algumas linhas. Por isso, vou usar patches. Copie o texto do patch em um editor de texto e siga as instruções.

Pegue o código para ler arquivos de configurações e salve-o com o nome que quiser, digamos list.c e o patch a baixo de original-list.patch:

69,82d68
<   current = options;
<   while(current != NULL)
<   {
<     printf("%s: %s\n", current->var, current->value);
<     current = current->next;
<   }
< 
<   current = options;
<   while( (current = get_option(current, "message")) ) /* yes, it's a =, not a == */
<   {
<     printf("%s found: %s\n", current->var, current->value);
<     current = current->next;
<   }
< 

Depois para aplicar patch list.c original-list.patch. Agora copie esse arquivo para list-sem_reverse.c (lembrando que você pode escolher o nome que quiser, tanto para o código como para o patch) e salve o texto abaixo como list-list-sem_reverse.patch:

36,40d35
< /* Reverses the list. Useful because as we push() things, they will be in the
<  * opposite order from the config file, so if we want to access it in the same
<  * way, we should reverse it. Returns the reversed list. */
< struct option *reverse(struct option *begin);
< 
145,175d139
< struct option *reverse(struct option *begin)
< {
<   struct option *prev = NULL;
<   struct option *curr = begin;
<   struct option *next = NULL;
< 
<   /* if begin is null, there is no next (segfault) */
<   if(begin==NULL)
<   {
<     return(NULL);
<   }
<   next = curr->next;
< 
<   /* if next is null, this is a single list. return as it is. */
<   if(next==NULL)
<   {
<     return(curr);
<   }
< 
<   /* otherwise, reverse it */
<   while(next!=NULL)
<   {
<     next = curr->next;
<     curr->next = prev;
<     prev = curr;
<     curr = next;
<   }
< 
<   return(prev);
< }
< 
257d220
<   *options = reverse(*options);

Para aplicar: patch list-sem_reverse.c list-list-sem_reverse.patch

Temos dois arquivos por enquanto list.c que é uma implementação usando listas (ah, jura?) e list-sem_reverse.c na qual nós não invertemos a lista após lermos toda ela. Eu fiz isso para termosas opções na mesma ordem em que foram colocadas no arquivo de texto, mas isso não é necessário.

É essa versão sem reverse que servirá de base para a versão usando arrays e uma usando árvores binárias. Copie list-sem_reverse.c para array.c e salve o seguinte texto como list-sem_reverse-array.patch:

3a4
> #define MAX 200001
16d16
<   struct option *next;
17a18,19
> static struct option options[MAX];
> static int count = 0;
34c36
< int new_option(struct option **options, char *var, char *value);
---
> int new_option(char *var, char *value);
39c41
< int parse_line(struct option **options, char *line);
---
> int parse_line(char *line);
47c49
< struct option *get_option(struct option *options, const char *option_name);
---
> int get_option(const char *option_name);
50c52
< int parse_file(struct option **options, const char *file_name);
---
> int parse_file(const char *file_name);
59c61
<     parse_file(&options, "file-config.cfg");
---
>     parse_file("file-config.cfg");
61c63
<     parse_file(&options, argv[1]);
---
>     parse_file(argv[1]);
119c121
< int new_option(struct option **options, char *var, char *value)
---
> int new_option(char *var, char *value)
121,133c123,124
<   struct option *new = malloc(sizeof(struct option));
<   if(new == NULL)
<   {
< #ifdef DEBUG
<     fprintf(stderr, "error allocating %u bytes of memory in 'new_option'\n",
<             sizeof(struct option));
< #endif
<     return(ERR_ALLOC_OPT);
<   }
< 
<   new->var = var;
<   new->value = value;
<   new->next = *options;
---
>   options[count].var = var;
>   options[count].value = value;
135c126
<   *options = new;
---
>   count++;
140c131
< int parse_line(struct option **options, char *line)
---
> int parse_line(char *line)
175c166
<   return(new_option(options, var, value));
---
>   return(new_option(var, value));
178c169
< struct option *get_option(struct option *options, const char *option_name)
---
> int get_option(const char *option_name)
180c171
<   struct option *current = options;
---
>   int i;
182c173
<   while(current != NULL)
---
>   for(i = 0; i < MAX; i++)
184c175
<     if(strcmp(current->var, option_name) == 0)
---
>     if(strcmp(options[i].var, option_name) == 0)
186c177
<       return(current);
---
>       return(i);
188d178
<     current = current->next;
191c181
<   return(NULL);
---
>   return(-1);
194c184
< int parse_file(struct option **options, const char *file_name)
---
> int parse_file(const char *file_name)
210c200
<     int ret = parse_line(options, line);
---
>     int ret = parse_line(line);

Para aplicar: patch array.c list-sem_reverse-array.patch

E agora copie list-sem_reverse.c novamente, mas agora para tree.c e salve o texto abaixo como list-sem_reverse-tree.patch

16c16,17
<   struct option *next;
---
>   struct option *lft;
>   struct option *rgt;
121,122c122,124
<   struct option *new = malloc(sizeof(struct option));
<   if(new == NULL)
---
>   struct option *current = *options;
> 
>   if(current == NULL)
123a126,128
>     struct option* new = malloc(sizeof(struct option));
>     if(new == NULL)
>     {
125,126c130,131
<     fprintf(stderr, "error allocating %u bytes of memory in 'new_option'\n",
<             sizeof(struct option));
---
>       fprintf(stderr, "error allocating %u bytes of memory in 'new_option'\n",
>               sizeof(struct option));
128,129c133,138
<     return(ERR_ALLOC_OPT);
<   }
---
>     }
> 
>     new->var = var;
>     new->value = value;
>     new->lft = NULL;
>     new->rgt = NULL;
131,133c140,141
<   new->var = var;
<   new->value = value;
<   new->next = *options;
---
>     *options = new;
>   }
135c143,149
<   *options = new;
---
>   else
>   {
>     if(strcmp(var,current->var) == -1)
>       new_option(&(current->lft), var, value);
>     else
>       new_option(&(current->rgt), var, value);
>   }
184,185c198,200
<     if(strcmp(current->var, option_name) == 0)
<     {
---
>     if(strcmp(current->var, option_name) == -1)
>       return(get_option(current->lft, option_name));
>     else if (strcmp(current->var, option_name) == 0)
187,188c202,203
<     }
<     current = current->next;
---
>     else
>       return(get_option(current->rgt, option_name));

Para aplicar: patch tree.c list-sem_reverse-tree.patch

Agora temos as quatro versões: listas, listas sem inverter, árvores e arrays.

Para compilar:

gcc list.c -O2 -o list
gcc list-sem_reverse.c -O2 -o list-sem_reverse
gcc array.c -O2 -o array
gcc tree.c -O2 -o tree

Além disso, para o teste do uso de memória, temos que adicionar

system("ps ux | grep <nome do executável>");

antes do return da função main.

Para os testes de pesquisar “message”, precisamos adicionar

get_option("message");

no array.c e

get_option(options,"message");

nos demais arquivos, mas faça isso apenas na hora de testar uma dessas coisas (e não esqueça de recompilar) ou isso vai acabar alterando os resultados.

Publicidade

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: