Newsgroup: it.comp.lang.c
Titolo: Un caso curioso

Salve a tutti.
Mi č capitato un fatto curioso e, almeno per me, inspiegabile. Ho scritto
una banalissima routine di bubble-sort che opera su un array di interi
allocato dinamicamente e generato casualmente. Ho scritto due versioni del
programma, una che ingloba tutto nel main, un'altra che invece usa delle
funzioni. Il punto č questo: la versione che richiama le funzioni č sempre
piů rapida dell'altra versione, contrariamente a quanto avevo supposto. Io
immaginavo che chiamare una funzione richiedesse un certo overhead, mentre a
quanto pare non č cosě. Il fenomeno si presenta sia con compilatori Borland
che Microsoft, e sia a 16 che a 32 bit (a 32 bit č inoltre possibile
lavorare con array molto grandi, ed il fenomeno č ancora piů sensibile).
Qualcuno mi sa dare una spiegazione?
Grazie!
Lorenzo
Ecco i sorgenti (in ANSI C):
/**************************
Sort1.c - Versione con funzioni
**************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
void sort(int vett[], int dimVett);
int scan(int vett[], int dimVett);
int *array, i, dim, swaps;
unsigned long storedtime;
void main(void)
{ 
 printf("Inserire la dimensione del vettore: ");
 scanf("%d", &dim);
 array=(int*)malloc(dim * sizeof(int));
 if(array==NULL)
  printf("Spazio insufficiente.\n");  
 else { 
  printf("Allocazione di %d bytes (%1.2f Mb) riuscita.\n", dim*sizeof(int),
      (dim*sizeof(int)/1048576.0));
  printf("Generazione di un array di %d numeri in corso...\n", dim);
  srand((unsigned)time(NULL));
 
  for(i=0; i<dim; i++)
   array[i]=rand();
 
  printf("Ordinamento dell'array in corso...\n");
  storedtime = time(NULL);
  sort(array, dim);
  storedtime = time(NULL) - storedtime;
 
  free(array);
 
  printf("Ordinamento completato.\n");
  printf("Scansioni dell'array effettuate: %d\n", swaps);
  printf("Tempo impiegato: %lu secondi\n", storedtime);
 }
}
void sort(int vett[], int dimVett)
{
 int swapped;
 do {
  swapped=scan(vett, dimVett);
  swaps++;
 } while(swapped == TRUE);
}
int scan(int vett[], int dimVett)
{
 int i, tempval, swapped = FALSE;
 for(i=0; i<(dimVett-1); i++)
  if(vett[i]>vett[i+1]) {
   tempval=vett[i];
   vett[i]=vett[i+1];
   vett[i+1]=tempval;
   swapped=TRUE;
  }
 return(swapped);
}
/*** end of file ***/
/**************************
Sort2.c - Versione senza funzioni
**************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
int *array, i, swapped, dim, swaps=0, tempval;
unsigned long storedtime;
void main(void)
{
 printf("Inserire la dimensione del vettore: ");
 scanf("%d", &dim);
 array=(int*)malloc(dim * sizeof(int));
 if(array==NULL)
  printf("Spazio insufficiente.\n");
 else
  printf("Allocazione di %d bytes (%1.2f Mb) riuscita.\n", dim*sizeof(int),
      (dim*sizeof(int)/1048576.0));
  printf("Generazione di un array di %d numeri in corso...\n", dim);
  srand((unsigned)time(NULL));
  for(i=0; i<dim; i++)
   array[i]=rand();
  printf("Ordinamento dell'array in corso...\n");
  storedtime = time(NULL);
  do {
   swapped=FALSE;
   for(i=0; i<(dim-1); i++)
    if(array[i]>array[i+1]) {
     tempval=array[i];
     array[i]=array[i+1];
     array[i+1]=tempval;
     swapped=TRUE;
    }
   swaps++;
  } while(swapped == TRUE);
  storedtime = time(NULL) - storedtime;
  free(array);
  printf("Ordinamento completato.\n");
  printf("Scansioni dell'array effettuate: %d\n", swaps);
  printf("Tempo impiegato: %lu secondi\n", storedtime);
 }
}
/*** end of file ***/
---
"...un tipo perso dietro le nuvole e la poesia..."
Lorenzo "Loz" Novara
E-Mail: 
l...@iol.it
Web: 
http://loz.freeweb.org

Supponendo che le istruzioni siano le stesse, può dipendere
dall'ottimizzazione del compilatore.
Ovvero:
nelle funzioni c'è sicuramente un overhead, ma minimo in quanto le richiami
solo all'inizio delle operazioni e perciò 2 volte se non ho visto male e
comunque molto ottimizzabile (solo 2 prametri). L'ottimizzazione del
compilatore viene solitamente fatta a livello di funzione, per cui
suddividendo il codice in più funzioni, ognuna è meglio ottimizzabile che
una sola che le comprende.
Nel tuo caso particolare sappi che:
Ogni variabile locale può essere sostituita da un registro. In una funzione
con poche variabili, ognuna è un registro, per cui evita tutte le operazioni
di lettura/scrittura della memoria (ciò è valido per variabili contatore,
temporanee per swap ecc.)
Le variabili globali invece non sono usate nei registri, per cui ogni
modifica del valore va fatto anche in memoria (mov), da cui il decremento
delle prestazioni.
Se tu dichiarassi le variabili i, swapped, dim, swaps e tempval come locali
al main, le prestazioni sarebbero uguali (o leggermente migliori) in quanto
sarebbero ottimizzate.
Alessandro Monti