Discussion :

[Seabirds]

Salut à toutes et à tous !
Après un petit coup de gprof, il s'avère que mon programme passe beaucoup de temps dans une classe. J'ai implémenté ça sans doute avec les pieds, à l'époque pas si lointaine où je cherchais surtout à faire un truc qui tourne Maintenant que ça tourne, bah faudrait que ça tourne plus rapidement Comme je risque fort de partir dans la mauvaise direction (j'ai par exemple essayé de changer une map par une unordered_map et je crois bien que ça a dégradé les performances ).

Peut-être pourriez-vous y jeter un coup d'oeil et me donner des pistes sur ce qui est à revoir ?

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
template<typename Space, typename Time, typename Value>
class Demography
{
 
public:
 
	using coord_type = Space;
	using time_type = Time;
	using N_type = Value;
	using value_type = double;
 
	Demography(Coords const& x0, N_type N0, time_type t0){
			populations[t0][x0] = N0;
	}
 
	time_type begin_time() const {
		return populations.begin()->first;
	}
 
	time_type end_time() const {
		return (--(populations.end()))->first;
	}
 
	std::vector<coord_type> inhabited_demes(time_type time) const {
		std::vector<coord_type> v;
		if(populations.find( time ) != populations.end()){ // return empty vector if time not found
			for(auto const& it : populations.at(time) ){
	  			v.push_back(it.first);
	  		}
		}
		return v;
	}
 
	value_type operator()(coord_type const& x, time_type t) const {
		return pop_size(x,t);
	}
 
	N_type pop_size(coord_type const& where, time_type time) const {
		return populations.at(time).at(where);
	}
 
 
	N_type& pop_size(coord_type const& where, time_type time) {
		return populations[time][where];
	}
 
 
	N_type flux_from_to(coord_type const& from, coord_type const& to, time_type time) const {
		return flux.at(time).at(to).at(from);
	}
 
 
	N_type& flux_from_to(coord_type const& from, coord_type const& to, time_type time){
		return flux[time][to][from];
	}
 
 
	std::unordered_map<coord_type, N_type> const& flux_to(coord_type const& to, time_type time) const {
		return flux.at(time).at(to);
	}
 
private:
 
	template<typename coord_type, typename time_type, typename N_type>
	friend std::ostream& operator <<(std::ostream& Stream, Demography<coord_type, time_type, N_type> const& demo);
 
	// period//to_deme/from_deme
	std::map<time_type, 
		std::unordered_map<coord_type, 
			std::unordered_map<coord_type, N_type> > > flux;
 
	// period / deme / size 
	std::map<time_type, std::unordered_map<coord_type, N_type> > populations;
 
};

[EDIT]
Je joins la sortie de gprof pour les détails des fonctions gourmandes :

% cumulative self self total
time seconds seconds calls ms/call ms/call name
4.93 2.89 2.89 566124789 0.00 0.00 std::__detail::_Hash_node<std::pair<Coords const, unsigned int>, true>::_M_next() const
4.75 5.68 2.79 282319617 0.00 0.00 void __gnu_cxx::new_allocator<std::pair<Coords const, unsigned int> >::construct<std::pair<Coords const, unsigned int>, std::pair<Coords const, unsigned int> const&>(std::pair<Coords const, unsigned int>*, std::pair<Coords const, unsigned int> const&)
3.39 7.67 1.99 352033237 0.00 0.00 std::__detail::_Mod_range_hashing::operator()(unsigned long, unsigned long) const
2.80 9.31 1.64 282319617 0.00 0.00 std::__detail::_Hash_node<std::pair<Coords const, unsigned int>, true>* std::__detail::_Hashtable_alloc<std::allocator<std::__detail::_Hash_node<std::pair<Coords const, unsigned int>, true> > >::_M_allocate_node<std::pair<Coords const, unsigned int> const&>(std::pair<Coords const, unsigned int> const&)

[Bousk]

Et où dans cette classe passes-tu le plus de temps ?
Parce que par exemple, quand je vois

Code :

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

1
2
3
time_type end_time() const {
		return (--(populations.end()))->first;
	}

Bon, j'ai envie de faire un table flip.
Un truc comme time_type end_time() const { return populations.crbegin()->first; } est déjà bien mieux.
Et de manière généale le choix d'une map peut entraîner des cache-miss. Est-elle vraiment indispensable ?

[Seabirds]

Merci de ta réponse !
J'ai mis les premières lignes de gprof en edit pour ta première question (en espérant que ça y réponde)
La map n'est peut être pas indispensable, je peux peut-être stocker les temps ordonnés dans un vecteur à part, et accéder aux infos via une unordered_map.

[ternel]

L'accès dans une map est en log(N). Le parcours complet dans une map est en NlogN (et non N)
Du coup, il peut y avoir un intérêt à passer par un vecteur si les clés sont toutes présentes (entre deux bornes).
Je pense notamment au temps, mais aussi probablement aux coord_type.

Dans le même genre d'idée, il y a boost::flat_map.

Comme tes structures semblent grosses, vérifie que tu ne bloque pas les déplacements (move semantics)

[Seabirds]

Comme tes structures semblent grosses, vérifie que tu ne bloque pas les déplacements (move semantics)

Merci pour ta réponse ! Pourrais-tu préciser un chouïa cette idée s'il te plait ?

[Bousk]

Les appels sont rapides, c'est juste que tu en as trop.
Du coup, regarde plutôt ton utilisation de cette classe, et en particulier de ces fonctions qui parcourent et copient.

[Seabirds]

Nous avons changé le modèle mathématique sous-jacent à l'utilisation de la classe, ce qui permet de s'économiser les (trop) nombreux appels à la fonction, ce qui règle le problème !
Merci encore pour vos réponse !
Bien cordialement,