Optimiser l'utilisation des pointeurs [Trucs & Astuces]

**progfou** · 27/02/2006, 10h55

Bonjour à tous et toutes !
Je suis confronté à un problème lié à l'embarqué. J'ai un programme complexe qui utilise beaucoup de pointeurs, voire de pointeurs de pointeurs. Ceci dit, la mémoire est limitée en temps d'accès, et en quantité, ce ui fait un paquet de mouvements du cache vers la DDRAM et vice versa. Du coup, je me retrouve avec un programme qui tourne, mais qui est très très lent. Les options d'optimisations (GCC) sont toutes placées au mieux (je vous ferais grâce des 4 lignes d'optimisation du Makefile

), mais je cherche du coup à réduire le nombre de pointeurs, ou à optimiser leur utilisation.

Qu'est-ce qui peut être fait ?
Merci d'avance pour vos réponses

**Emmanuel Delahaye** · 27/02/2006, 11h10

Envoyé par progman

Bonjour à tous et toutes !
Je suis confronté à un problème lié à l'embarqué. J'ai un programme complexe qui utilise beaucoup de pointeurs, voire de pointeurs de pointeurs. Ceci dit, la mémoire est limitée en temps d'accès, et en quantité, ce ui fait un paquet de mouvements du cache vers la DDRAM et vice versa. Du coup, je me retrouve avec un programme qui tourne, mais qui est très très lent. Les options d'optimisations (GCC) sont toutes placées au mieux (je vous ferais grâce des 4 lignes d'optimisation du Makefile

), mais je cherche du coup à réduire le nombre de pointeurs, ou à optimiser leur utilisation.

Qu'est-ce qui peut être fait ?

Le principe est de réduire le nombre de pointeurs en utilisant une variable locale.

mettons que l'on ait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
struct b
{
   int x;
   int y;
   int z;
};
 
struct a
{
   struct b *pb;
};

Au lieu de faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   pa->pb->x = 1;
   pa->pb->y = 2;
   pa->pb->z = 3;

on fera

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
   struct b *pb = pa->pb;
 
   pb->x = 1;
   pb->y = 2;
   pb->z = 3;

Ce principe est mis en oeuvre un peu partout dans mon code :

http://emmanuel-delahaye.developpez.com/clib.htm

Ceci dit, je doute fort que ce soit la seule cause de ralentissement...

Que dit le profiler ?

**progfou** · 05/03/2006, 09h52

Après une semaine d'investigations, il s'avère que c'est le simulateur qui partait en vrille

.
Ceci dit, je cherche toujours à optimiser, et j'ai un autre programme sous la main que j'aimerais tester, et il a quelques malloc() et autres...
Comment les remplacer ?
Je ne sais pas s'il existe des techniques, ceci dit, je pensais essayer de chercher combien le malloc() alloue au maximum (suivant le fichier d'entrée) afin de déterminer une taille de tableau statique max, avec le même nom que le pointeur renvoyé par malloc...

Existe-t-il plus simple/plus efficace ?

**Emmanuel Delahaye** · 05/03/2006, 09h59

Envoyé par progman

Ceci dit, je cherche toujours à optimiser, et j'ai un autre programme sous la main que j'aimerais tester, et il a quelques malloc() et autres...
Comment les remplacer ?
Je ne sais pas s'il existe des techniques, ceci dit, je pensais essayer de chercher combien le malloc() alloue au maximum (suivant le fichier d'entrée) afin de déterminer une taille de tableau statique max, avec le même nom que le pointeur renvoyé par malloc...

Existe-t-il plus simple/plus efficace ?

malloc() a la réputation d'être lente (encore une fois, seul un profilage peut l'affirmer). Donc il est préférable de ne pas le placer dans les boucles, mais de faire les préallocations à l'avance. Si ce n'est pas possible, il faut écrire son propre allocateur mémoire, optimisé pour l'application.

Il y a un tas de façons de faire. En embarqué, certaines sont déjà fournies avec le système... (memory pool etc.)

**progfou** · 05/03/2006, 10h22

Ce n'est, malheureusement, dans mon cas pas le cas (justement

).
Où trouver des programmes optimisant cette gestion ?
Je suppose que pour maximiser les performances, il est préférable d'aligner les mots en mémoire, déjà...
Ceci dit il est clair que le malloc prend pas mal de temps, et je n'ai pas de profiler suffisament performant sur la plate-forme en question pour me donner les pourcentages, mais gdb met beaucoup de temps à passer cette instruction, et je compare au reste du programme quand je dis ça

.

**Emmanuel Delahaye** · 05/03/2006, 10h30

Envoyé par progman

Où trouver des programmes optimisant cette gestion ?

je suppose...

Je suppose que pour maximiser les performances, il est préférable d'aligner les mots en mémoire, déjà...

Ca, c'est obligatoire, et c'est ce que fait malloc()...

Un allocateur simple (tailles fixes), c'est pas compliqué. (il y en un dans le K&R si je me souviens bien)

On prend un gros bloc mémoire (alloué, static peu importe), on le découpe en morceaux de taille fixe (selon l'appli), on gère un tableau d'index avec un état libre/occupé... On crée les fonction my_malloc(), my_free()...

Ca se fait en 50 lignes de codes... (un peu plus si on fait dans le générique...)

**progfou** · 05/03/2006, 10h33

Je n'ai pas le K&R malheureusement...
Connais-tu un site (anglais ou français, je m'en fiche) avec ce type de code ?
Ca me ferait gagner du temps, même si je comprends bien ce que tu m'as dit

.
Je cherche en même temps, mais si tu en as un dans tes bookmarks, ça serait cool

.

**Emmanuel Delahaye** · 05/03/2006, 10h45

Envoyé par progman

Je n'ai pas le K&R malheureusement...
Connais-tu un site (anglais ou français, je m'en fiche) avec ce type de code ?
Ca me ferait gagner du temps, même si je comprends bien ce que tu m'as dit

.
Je cherche en même temps, mais si tu en as un dans tes bookmarks, ça serait cool

.

Une ébauche rapide :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include "mem.h"
 
int main(void)
{
   /* 128 blocs de 32 bytes */
   mem_init(128, 32);
 
   int * p = mem_malloc(sizeof *p * 3);
 
   if (p != NULL)
   {
      mem_free (p), p = NULL;
   }
 
   mem_trace();
 
   mem_end();
}

avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
/* mem.h */
#ifndef H_MEM
#define H_MEM
#include <stddef.h>
 
void mem_init(size_t block_nb, size_t block_size);
void mem_trace(void);
void mem_end(void);
 
void *mem_malloc(size_t size);
void mem_free (void *p);
 
#endif

Je vais au ciné. Quand je reviens, tu as terminé l'implémentation de mem.c !

**progfou** · 05/03/2006, 12h40

Ca commence mal, mem_init je ne vois pas comment faire déjà...
Alouer se fait par malloc, je tourne en rond.
Je ne sais pas comment créer la fonction équivalente à malloc (c'est mon problème en fait...).

**Emmanuel Delahaye** · 05/03/2006, 14h03

Envoyé par progman

Ca commence mal, mem_init je ne vois pas comment faire déjà...
Alouer se fait par malloc, je tourne en rond.
Je ne sais pas comment créer la fonction équivalente à malloc (c'est mon problème en fait...).

On te donne une taille, suffit d'allouer un bloc de cette taille. Il sera détruit par mem_end(). Evidemment, l'adresse du bloc alloué sera stocké dans un pointeur global privé de mem.c (Pour le moment, c'est un peu barbare, mais pour voir le principe, ça suffit).

Ensuite il faut structurer ce bloc pour avoir des petits blocs allouables. Pour ça, il faut définir à part une structure avec l'adresse et un flag libre/occupé et créer un tableau de ces structures correspondant au nombre de blocs, et l'initialiser avec les adresses des blocs en les marquant 'libre'. Ce tableau est évidemment une globale privée de mem.c.

Une allocation c'est
- vérifier que la taille n'est pas trop grande
- chercher un bloc libre
- le marque 'occuper'
- retourner l'adresse.

Une libération, c'est
- verifier que le bloc était alloué
- le marquer libre

Je ne vois pas ce qu'il y a de difficile. Si tu ne reflechis pas plus que ça, tu n'avanceras jamais.

**progfou** · 05/03/2006, 14h10

J'essaie de faire ça, je reviens pour donner le code, et améliorer l'histoire

.

Merci de ton aide, je ne connais pas bien la gestion de la mémoire en C, tu as remarqué

.

**progfou** · 05/03/2006, 14h36

Envoyé par Emmanuel Delahaye

On te donne une taille, suffit d'allouer un bloc de cette taille. Il sera détruit par mem_end(). Evidemment, l'adresse du bloc alloué sera stocké dans un pointeur global privé de mem.c (Pour le moment, c'est un peu barbare, mais pour voir le principe, ça suffit).

Il est là mon problème, déclarer un pointeur global privé, c'est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
static void *addr;

Non ?
Si oui, alors, je bute sur la suite, c'est à dire, allour un bloc dont la taille est donnée dans le programme.
Car pour faire ça, à part malloc(), je vois pas.
Et je veux le remplacer, ce malloc, alors je tourne en rond.
Il y a sûrement un concept en C que je ne connais pas, et qui est ma réponse.

**Médinoc** · 05/03/2006, 14h42

Je crois que ce que veux dire Emmanuel, c'est "Tu fais un malloc() au début dans le mem_init(), puis tu n'en fais plus jusqu'à la fin".

Après avoir alloué tes données dans le mem_init, tu fais ta propre cuisine quand on te demande de la mémoire en appelant mem_alloc()...

gl · 05/03/2006, 14h43

Envoyé par progman

Si oui, alors, je bute sur la suite, c'est à dire, allour un bloc dont la taille est donnée dans le programme.
Car pour faire ça, à part malloc(), je vois pas.
Et je veux le remplacer, ce malloc, alors je tourne en rond.
Il y a sûrement un concept en C que je ne connais pas, et qui est ma réponse.

Ben oui, il suffit d'allouer avec malloc.

Ce que te propose Emmanuel, si j'ai bien suivi l'echange, c'est d'effectuer une allocation memoire avec malloc d'une taille consequente en debut de programme lors de l'appel a mem_init.
Ensuite, lorsque tu as besoin de memoire dans ton programme, tu fais appel a mem_malloc qui te fournie une adresse contenu dans l'allocation precedente et marque comme non utilise.

En gros plutot que de faire appel a n malloc et n free dans ton code, tu fais une seul malloc en debut et un free a la fin, ensuite tu gere toi-meme ce bloc pour fournir de la memoire lorsque le programme en a besoin

**progfou** · 05/03/2006, 14h47

Alors, je commence à mieux saisir !
Et on ne peut pas définitivement se passer du malloc ?

**Emmanuel Delahaye** · 05/03/2006, 15h12

Envoyé par progman

Il est là mon problème, déclarer un pointeur global privé, c'est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
static void *addr;

Non ?

Oui.

Si oui, alors, je bute sur la suite, c'est à dire, allouer un bloc dont la taille est donnée dans le programme.
Car pour faire ça, à part malloc(), je vois pas.

C'est malloc() qu'il te faut. Il sera appelé 1 fois (ou deux) au debut du programme. Ce n'est pas lui qui va te pénaliser.

Si tu ne veux pas du tout de malloc(), autre strategie : définir un bloc statique coté utilisateur et passer l'adresse , la taille et la taille d'un bloc à mem_init(). Celle-ci se charge de calculer le nombre de blocs.

**Emmanuel Delahaye** · 05/03/2006, 15h13

Envoyé par progman

Alors, je commence à mieux saisir !
Et on ne peut pas définitivement se passer du malloc ?

Si, voir ci-dessus.

**progfou** · 05/03/2006, 16h59

Est-ce que, plutôt que d'utiliser un tableau de structures avec adresse+flag, je ne peux pas utiliser une variable privée qui me donne la première position libre dans le mem ? Cette variable est mise à jour à chaque mem_malloc/mem_free et permet de savoir si la zone mémoire est pleine ou non, sans avoir à passer par une structure complexe.

**Emmanuel Delahaye** · 05/03/2006, 17h50

Envoyé par progman

Est-ce que, plutôt que d'utiliser un tableau de structures avec adresse+flag, je ne peux pas utiliser une variable privée qui me donne la première position libre dans le mem ? Cette variable est mise à jour à chaque mem_malloc/mem_free et permet de savoir si la zone mémoire est pleine ou non, sans avoir à passer par une structure complexe.

Tu fais ce que tu veux, mais moi je t'ai donné une solution qui fonctionne... N'oublie pas que les enchainements allocation/libération doivent pouvoir se faire dans n'importe quel ordre...

**progfou** · 05/03/2006, 18h00

Oui, j'étais en train de bloquer là-dessus.
Je bloque au niveau de la structure, je sais la déclarer, mais faire un tableau de structures, et l'utiliser, je bloque complètement (c'est le genre de trucs que j'ai jamais vraiment sû faire !).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
static void *tab_mem_malloc;
...
struct addr_t {
	void *address;
	unsigned char flag;
};
...
tab_mem_malloc=(struct addr_t *)malloc(block_nb);

Mais lorsque je veux lui donner une adresse et un flag, il me sort du :

warning: dereferencing 'void *' pointer
error: void value not ignored as it ought to be

Quelle est la ligne qui permettrait de donner l'adresse (par exemple), parcequ'entre les flèches et les . je ne sais jamais !
En sachant que la position dans le tableau est stockée via une variable privée globale num_mem_malloc.

Optimiser l'utilisation des pointeurs [Trucs & Astuces]

C

Discussions similaires

Partager

Partager