Optimisation pour les tableaux

Soumis par trax le dim, 08/03/2009 - 12:01

Allocation

Histoire de commencer par le commencement, lire http://clubnix.fr/allocation_dynamique_2_dimensions_C pour plus d'informations.

Le programme suivant va allouer un tableau à deux dimensions de manière dynamique et, afficher le temps de création et de destruction du tableau.

#include <stdio.h>
#include <stdlib.h>
 
 
/*========== parttie relative a la mesure du temps ===========*/
#include <sys/times.h>
#include <unistd.h>
typedef struct tms sTms;
typedef struct{
	int debut,fin;
	sTms sdebut, sfin;
}temps_exec;
 
 
void temp(temps_exec *tmps){
    printf("temps réel :\t %d\ntemps utilisateur :\t %ld\ntemps system :\t %ld\n\n",
		tmps->fin - tmps->debut,
		tmps->sfin.tms_utime - tmps->sdebut.tms_utime,
		tmps->sfin.tms_stime - tmps->sdebut.tms_stime);
}
/*========== parttie relative a la mesure du temps ===========*/
 
 
void badInit(int C, int L){
  int **tab;
  temps_exec temps;
 
  temps.debut = times (&temps.sdebut);
  tab = (int **)malloc (sizeof(int*)*L);
  for(int i = 0 ; i < L ; i++){
    tab[i]=(int *)malloc(sizeof(int)*C);
  }
 
  for (int i = 0 ; i < L ; i++){
	free (tab[i]);
  }
  free (tab);
  temps.fin = times (&temps.sfin);
  temp (&temps);
 
 
}
 
void goodInit(int C, int L){
  int **tab;
  int *tab0;
  temps_exec temps;
 
  temps.debut = times (&temps.sdebut);
  tab = (int **)malloc (sizeof(int*)*L);
  tab0 = (int *)malloc (sizeof(int)*(C*L));
 
  for (int i = 0 ; i < L ; i++){
	tab[i] = &tab0[i*C];
  }
 
  free (tab0);
  free (tab);
  temps.fin = times (&temps.sfin);
  temp (&temps);
 
}
 
int main(){
 
  badInit (10, 1000000);
 
  badInit (1000000, 10);
 
  goodInit (10, 1000000);
 
  goodInit (1000000, 10);
 
 
  return 0;
}

Intéressons nous dans un premier temps à la fonction badInit.

Sa compléxité est en o(n) (n la deuxième dimension du tableau), ce qui ne semble pas dramatique.

Dans un premier temps, allons un tableau de 10 colonnes et 1000000 lignes
Soit 1000010 allocation mémoire. Ces allocations sont des appelles systèmes (donc appelle du kernel) qui sont couteux en temps. La première chose à faire est donc placer la plus petite dimension en premier et d'allouer un tableau de 1000000 et de 10 lignes.

Il est néanmoins possible de faire mieux et de réduire à deux allocations mémoire comme le montre la fonction gootInit (la aussi il faut penser au dimensions).

Voici les temps obtenu

$ ./tab
temps réel :     21
temps utilisateur :      12
temps system :   8
 
temps réel :     6
temps utilisateur :      6
temps system :   0
 
temps réel :     4
temps utilisateur :      2
temps system :   1
 
temps réel :     0
temps utilisateur :      0
temps system :   0

L'allocation à deux malloc permet de gagner du temps lors de la création mais pas seulement.

Parcour de tableau

Soit un tableau tab de 1000000 colonnes et 100 lignes alloué avec la fonction badInit.

Nous pouvons l'initialiser de la manière suivante :

  for (int i = 0 ; i < C ; i++){
        for (int j = 0 ; j < L ; j++){
          tab[j][i] = j;
        }
  }

Si nous parcourons le tableau par les lignes (en lisant la première colonne de chaque ligne, puis la deuxième colonne de chaque ligne...), nous obligeons le système à faire des sauts dans la mémoire.

temps réel :     1327
temps utilisateur :      1314
temps system :   11

Si nous parcourions le tableau dans le sens des colonnes

  for (int i = 0 ; i < L ; i++){
        for (int j = 0 ; j < C ; j++){
          tab[i][j] = j;
        }
  }

Nous obtenons :

temps réel :     77
temps utilisateur :      12
temps system :   65

Ce qui est bien mieux, et encore une fois la complexité algorithmique est la même.

En faisant la même chose sur un tableau initialisé avec la fonction goodInit nous obtenons les temps suivant :

temps réel :     207
temps utilisateur :      205
temps system :   2
 
temps réel :     73
temps utilisateur :      12
temps system :   62

Mais nous n'utilisaton pas le fait que le bloc mémoire soit continue, ce qui pourrait améliorer nos performances :

  for (int i = 0 ; i < C*L ; i++){
        tab[0][i] = i;
  }

Nous n'avons plus qu'une boucle, et toujours de la même compléxité algorithmique.

temps réel :     47
temps utilisateur :      46
temps system :   0

Qui dit mieux ?

Et si c'est possible. Dans les exemples précédents, nous obligions le système à recalculer les index de chaque case soit des multiplications en trop.

  tab0 = &tab[0][0];
  for (int i = 0 ; i < C*L ; i++){
        *tab0 = i;
        tab++;
  }

Soit :

temps réel :     0
temps utilisateur :      0
temps system :   0

Fichier attaché	Taille
tab.c	2.3 Ko

Commentaires

petite faute avec des temps pas logique

Permalien Submitted by tiregram on lun, 21/09/2015 - 19:01.

tab0 = &tab[0][0];
  for (int i = 0 ; i < C*L ; i++){
        *tab0 = i;
        tab++;
  }

à remplacer par

tab0 = &tab[0][0];
  for (int i = 0 ; i < C*L ; i++){
        *(tab0) = i;
        tab0++;
  }

Petite question:
Et si on multithread, le temps n'est pas mieux?

répondre