Performance em ordenação em C ANSI - com e sem variável auxiliar

Sou monitor de uma disciplina de algoritmos e surgiu uma dúvida em relação diferentes abordagens para troca de valores entre duas variáveis - com e sem utilização de variável auxiliar. Mesmo sabendo que o uso de variável auxiliar é aconselhável, uma vez que facilita a leitura do código, fiquei pensando em relação à performance das duas abordagens. Em uma delas, a troca ocorre através de 3 operações aritméticas (uma soma e duas subtrações), na segunda ocorre através da movimentação de valores entre 3 variáveis. Seguem as duas abordagens:

1-

int a=10,b=15;
a=b+a;
b=a-b;
a=a-b;

2-

int a=10,b=15,aux;
aux = a;
a = b;
b = aux;

Para medir a performance dessas abordagens de trocas de variáveis, resolvi testá-las em um contexto em que elas são realizadas muitas vezes. Nada melhor que o bom e velho bubble sort para isso :slight_smile:
Segue abaixo o código que fiz:

[code]#include <time.h>
#include <stdlib.h>
#include <stdio.h>

#define TAMANHO 10000
#define VALOR_MAXIMO 10

int main()
{
clock_t inicio,fim;
double total1,total2;
int a[TAMANHO],copia1[TAMANHO],copia2[TAMANHO];
int i,j,aux,r;

srand(time(0)); //gera uma nova cadeia de n?meros aleat?ria

printf("Produzindo numeros aleatorios\n");

 for(i = 0; i < TAMANHO; i++)
 {
     r = (int) (rand() / (double) RAND_MAX * (VALOR_MAXIMO + 1));   
     a[i] = r;
 }

printf("\tNumeros aleatorios produzidos\n");
 
 printf("Fazendo duas copias\n");
 
 for(i = 0; i < TAMANHO; i++)
 {
     copia1[i] = copia2[i] = a[i];
 }
 printf("\tCopias feitas\n");
 
 printf("Ordenacao sem variavel auxiliar\n");
 
 inicio = clock(); 
 for(i=0; i < TAMANHO; i++)
 {
     for(j=i+1 ; j<TAMANHO; j++)
     {
         if (copia1[j]<copia1[i])
         {
            copia1[i]=copia1[j]+copia1[i];
            copia1[j]=copia1[i]-copia1[j];
            copia1[i]=copia1[i]-copia1[j];
         }                         
     }
 }
 fim = clock();
 total1 = (double)((double)(fim-inicio)/(double)(CLOCKS_PER_SEC/1000.0));
 
 printf("\tOrdenacao sem variavel auxiliar demora %.0f \n",total1);
 
 printf("Ordenacao com variavel auxiliar\n");
   
 inicio = clock(); 
 for(i=0; i < TAMANHO; i++)
 {
     for(j=i+1 ; j<TAMANHO; j++)
     {
         if (copia2[j]<copia2[i])
         {
            aux = copia2[j];
            copia2[j] = copia2[i];
            copia2[i] = aux;   
         }                         
     }
 }
 fim = clock();
 total2 = (double)((double)(fim-inicio)/(double)(CLOCKS_PER_SEC/1000.0));
 
 printf("\tOrdenacao com variavel auxiliar demora %.0f \n",total2);

system("pause>>null");
return 0;

}[/code]

Notem que tentei usar a tomada de tempo em milissegundos, a partir da função clock() do C e da variável CLOCKS_PER_SEC. Não sei se está correto.
A minha surpresa foi que às vezes executo e a primeira abordagem é mais rápida, às vezes a segunda é muito mais rápida, às vezes a diferença entre ambas é despezível. Por que isso ocorre? Errei a forma de tomar o tempo de execução?

Logicamente falando, em termos de arquitetura, qual das abordagens deveria ser mais rápida?

Olá,
a primeira abordagem está incorreta. Ela funciona para valores pequenos, mas para valores grandes (que se aproximam do limite do tipo) pode haver overflow. Há uma forma de fazer a troca sem variável auxiliar (não me lembro agora como era - depois vou dar uma procurada daí posto aqui), mas não é recomendada por depender de tipos inteiros do C.

Att.

Olá,
como havia dito, há uma forma de fazer swap sem o uso de variável auxiliar. Segue o código:

[code]#include <stdio.h>

int main(){
int a = 1;
int b = 2;
printf("%d %d\n", a, b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
printf("%d %d\n", a, b);
}[/code]

Att.

Ola

Compare o assembly de cada opção, quantas operações vc tem em cada forma?

Quantos acessos a memoria? a variavel temporaria é proxima a ponto de cair no cache L3?

Isso tudo conta, mas acredito que o impacto é minimo em um problema trivial.

[quote=Adelar]Olá,
como havia dito, há uma forma de fazer swap sem o uso de variável auxiliar. Segue o código:

[code]#include <stdio.h>

int main(){
int a = 1;
int b = 2;
printf("%d %d\n", a, b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
printf("%d %d\n", a, b);
}[/code]

Att.
[/quote]

É mesmo! Bem lembrado! Eu havia esquecido desta forma de swap. Valeu.
Além disso, não tinha me dado conta do problema de overflow na representação de inteiros, usando a abordagem baseada em operações aritméticas, quando os valores estão próximos ao limite…Valeu mesmo!

[quote=peczenyj]Ola

Compare o assembly de cada opção, quantas operações vc tem em cada forma?

Quantos acessos a memoria? a variavel temporaria é proxima a ponto de cair no cache L3?

Isso tudo conta, mas acredito que o impacto é minimo em um problema trivial. [/quote]

Parece-me que essas abordagens que não usam variável auxiliar precisam necessariamente:
1-Mover o valor da posição de memória de uma das variáveis para um registrador.
2-Mover o segundo valor, da memória para outro registrador.
3-Operar conteúdos de ambos registradores
4-Mover o resultado do acumulador para o endereço de memória que acumulará a soma.

Isso para cada uma das operações entre variáveis. Enquanto para a operação com uso de variável auxiliar eu realizo 3 movimentos de valores entre endereços de memória.

É isso?

Mesmo assim, não sei qual das operações é mais cara.

Outra coisa. Meu método de tomada de tempo está correto? Cada vez que executo a relação de perfomance entre as abordagens muda. Às vezes a primeira é mais rápida que a segunda, às vezes, vice-versa…Como normalizar isso?

Grato pela atenção!

?

10000 é um tamanho muito pequeno para você fazer tal benchmark (mesmo para um método tosquíssimo de ordenação, como o bubblesort). Benchmarks bem feitos precisam de tratamento estatístico, como qualquer medição que se preze. Rodar um benchmark 1 vez só simplesmente não leva a absolutamente nenhuma conclusão.
No seu caso em particular, eu diria que (se ligarmos a otimização do compilador) o tempo gasto seria o mesmo em média.

[quote=entanglement]10000 é um tamanho muito pequeno para você fazer tal benchmark (mesmo para um método tosquíssimo de ordenação, como o bubblesort). Benchmarks bem feitos precisam de tratamento estatístico, como qualquer medição que se preze. Rodar um benchmark 1 vez só simplesmente não leva a absolutamente nenhuma conclusão.
No seu caso em particular, eu diria que (se ligarmos a otimização do compilador) o tempo gasto seria o mesmo em média. [/quote]

Sei disso meu amigo…Minha intenção não era fazer um benchmark estrito…Quer dizer, querer até quero, mas não tenho tempo pra isso. Então rodei meu teste várias vezes e vi que em todas elas a versão que usa manipulação aritmética. Sem dúvidas não é suficiente para determinar a diferença de performance no caso geral, mas dá uma boa sugestão, indicando esta abordagem como a mais rápida em todos os testes.

Mas minhas dúvidas permanecem…Usei um método adequado para tomada de tempo? Não tenho tanta familiaridade assim com a linguagem C.

Além disso…Não consegui entender por que a utilização de operações aritméticas confere mais velocidade que a utilização de operações XOR (mesma quantidade) e que a utilização de transferência de valores para uma variável auxiliar…Em termos de arquitetura, alguém está por dentro de por que isto acontece?

Grato…