Discussion :

[Grasshoper]

Bonjour à toutes et à tous,

En préambule: je découvre le C++ et la priority_queue.

J'ai besoin de recoder un tout petit bout de programme (l'algorithme de dijkstra) afin de calculer des distances dans un graphe. Plus précisément, je teste un grand nombre de graphes de tailles différentes et ce petit bout de programme est appelé pour chaque graphe. Plus précisément la structure de mon programme ressemble à ceci:

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) 
{
    /***********************************
     *DECLARATIONS AND INITS
     ***********************************/
    ...
 
    /*******************************
     * Gather Inputs and Outputs & Alloc structures:
     *******************************/
    ...
 
    //Then perform the search for inflow and outflow nodes (find requested distance):
    for(i=0; i < N; i++) {
        for(j=0; j < N; j++) {
            if(rand_idx[i] < j && rand_idx[i] != N-1) { //only read the upper triangular part and omit the last line.
                const int cur_dis = dijkstra(rand_idx[i], j);
 
                //mexPrintf("distance=%d\n", distance);
                if(cur_dis >= distance) {
                    //assign outputs and returns:
                    //also correct for indexation between MATLAB & C
                    plhs[0] = mxCreateDoubleScalar(rand_idx[i] +1 ); //in
                    plhs[1] = mxCreateDoubleScalar(rand_idx[j] +1 ); //out
                    plhs[2] = mxCreateDoubleScalar(cur_dis); //fdistance
                    return;
                }
            }
        }
   }
 
    //we browsed 'A' without finding the requested distance, thus assign '-1' to outputs 
    plhs[0] = mxCreateDoubleScalar(-1.0); //in
    plhs[1] = mxCreateDoubleScalar(-1.0); //out
    plhs[2] = mxCreateDoubleScalar(-1.0); //fdistance
}

J'appelle donc la fonction dijkstra() un grand nombre de fois, et je retourne mon résultat 'plhs' à MATLAB. Cette fonction compilée est appelée un grand nombre de fois pour des graphes différents. L'algorithme fonctionne, les solutions sont correctes. La fonction dijkstra() utilise une priority_queue en global, avec des structures simples, c'est à dire:

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
vector < vector <int> > graph;
vector < vector <int> > weight;
vector < int> cost;
int N;
 
struct cmp
{
  bool operator()(const int &lhs, const int &rhs) const
  {
    return cost[lhs] > cost[rhs];
  }
};
 
int min(const int a, const int b)
{
	if(a<b)
		return a;
	return b;
}
 
priority_queue <int,vector<int>,cmp> pq;
 
int dijkstra(const int from, const int to)
{
	vector <bool> visited(N, false);
	visited[from] = true;
	cost [from] = 0;
	pq.push(from);
    while(!pq.empty() && !visited[to])
	{
		int current = pq.top();
		pq.pop();
		visited[current] = true;
		for(int i=0;i<graph[current].size();i++)
		{	
			if(!visited[graph[current][i]])
			{
				cost[graph[current][i]] = min( cost[graph[current][i]] ,cost[current] + weight[current][i]);
				pq.push(graph[current][i]);
			}
		}
	}
	return cost[to];
}

Après un grand nombre d'appel j'ai une erreur bad allocation(). Après avoir consulté mon ami Google je me suis penché sur l'utilisation de la RAM par le programme et il me semble que cette erreur est due à l'utilisation complète de la RAM (plus d'allocation possible). Je ne maitrise pas les questions de mémoire dans le stack ou dans le heap, mais je pense que c'est lié à ca. En fait initialement je ne pensais même pas avoir besoin de vider la mémoire (pas de new(), donc pas de delete()), mais il s'avère que si je ne le fait pas ca pompe toute la ram. J'ai donc ajouté un petit bout de code qui permet de résoudre le problème:

Code :

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

1
2
3
4
5
void clean_queue(void) {
    while(!pq.empty()) {
        pq.pop();
    }
}

c'est à dire que je dépile toute la queue à la fin de chaque utilisation de cette fonction. Ca fonctionne beaucoup mieux, plus de problème d'allocation, par contre le fait de dépiler à chaque fois que j'ai fini d'utiliser un graphe particulier c'est effroyablement lent, même sur des petits graphes. En fait c'est même plus sournois que ca: sur les premiers graphes (cad première itérations) ca fonctionne bien, puis ca ralentit progressivement jusqu'à devenir très (TRES) lent. Donc je pense que j'ai seulement déplacé le problème et que vider l'espace mémoire est très couteux.

D'où ma question: quelle solution adopter dans ce cadre pour maintenir une gestion mémoire efficace?

Merci!

[jo_link_noir]

Pour supprimer les éléments, le plus simple est de reconstruire une nouvelle priority_queue: pq = std::priority_queue<....>(); qui va directement vider le vector interne plutôt que des appels à pop() qui possède une complexité non nulle (https://en.cppreference.com/w/cpp/co...rity_queue/pop).

On perd par contre le buffeur d'allocation et push() va ré-allouer de la mémoire qu'elle possédait déjà avant. Cela peut être négligeable, mais une solution est d'hériter de priority_queue et d'implémenter une fonction clear() pour utiliser std::vector::clear() du conteneur interne.

Code :

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

1
2
3
4
5
6
7
struct MyPriotityQueue : std::priority_queue<....>
{
    void clear()
    {
        c.clear();
    }
};

[Matt_Houston]

Il est tout de même bien étrange que cette méthode soit absente. Y'a-t-il un « rationale » à son omission de la bibliothèque standard ?

Je me permets une remarque en rapport avec le titre du sujet : on cause plutôt de « fuite (de) mémoire » lorsque cette dernière ne peut être récupérée, c'est-à-dire que l'on a pas conservé les adresses des blocs alloués. Ici la perte n'est pas définitive, ton programme demande simplement trop de ressources en même temps.

[Bousk]

Pour vider une priority_queue on peut aussi utiliser le swap ou l'assignation avec une queue vide.

[Matt_Houston]

jo_link_noir l'a mentionné : ce n'est pas équivalent à clear car le buffer interne devra être alloué à nouveau, en tout cas on n'impose pas à l'implémentation de le conserver.

[Grasshoper]

Déjà, merci à tous pour vos commentaires!

Alors j'ai regardé les solutions proposées, et voici quelques tests qui montrent (à minima) que je ne fais pas ca comme il faut

Suggestion 1: le swap:

Code :

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

1
2
3
4
5
6
priority_queue <int,vector<int>,cmp> pq, pq2;
 
void clear( void )
{
   swap( pq, pq2 );
}

Suggestion 2: le clear():

Code :

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

1
2
3
4
5
6
7
struct mypq :public priority_queue<int,vector<int>,cmp> {
    void clear(){
        this->c.clear();
    }
};
 
mypq pq;

Et les résultats sur 200 itérations successives (pas de multithreads) en figure. On voit que à chaque nouvelle itération le temps de calcul augmente pour le swap et le clear() mais pas pour matlab qui reste constant (il s'agit des temps de calculs cumulés sur une modeste bécane). Du coup je pense que je vide qu'une partie de la queue, ou il me manque quelque chose quelque part.


Aussi en PJ une autre figure avec le temps pour chaque itération successive. on voit que le swap vide tout mais pas systématiquement....



Merci d'avance pour vos commentaires!