optimiser les prédicats

Version imprimable

Supposons un prédicat (ou foncteur) comme ceci:
Code:

1 2 3 4 5 6 7 8 9 10 struct pred { bool operator(Ob const & rl,Ob const & rr) const { resource tmp_r; int il=rl.foo(tmp_r); int ir=rr.foo(tmp_r); return il < ir; } };
En gros cela signifie que j'ai besoin d'une resource assez "lourde" mais qui reste temporaire et à usage local uniquement.

Afin d'éviter sa construction et destruction à chaque passage dans le foncteur, je pense qu'il est préférable de faire comme ceci:
Code:

1 2 3 4 5 6 7 8 9 10 11 struct pred { resource tmp_r; bool operator(Ob const & rl,Ob const & rr) const { tmp_r.clear(); int il=rl.foo(tmp_r); int ir=rr.foo(tmp_r); return il < ir; } };
Ceci étant, ce n'est peut-être pas encore assez satisfaisant car les foncteurs sont toujours passés par valeur à l'intérieur des méandres de la SL, avec recopie probable de la resource tmp_r à chaque fois.

Il y a une troisième solution:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 struct pred { resource & tmp_r; pred(resource & r=resource()):tmp_r(r) {} bool operator(Ob const & rl,Ob const & rr) const { tmp_r.clear(); int il=rl.foo(tmp_r); int ir=rr.foo(tmp_r); return il < ir; } };
Cette troisième écriture semble bonne car la resource n'est créée qu'une fois puis "déplacée" à chaque copie du prédicat, mais elle ne me satisfait pourtant pas pleinement (sans que je puisse dire pourquoi).
A priori je préfère la 2ème écriture, mais les compilateurs sont-ils assez intelligents dans l'optimisation en mode release pour comprendre que les fonctions de la SL, fonctions inline pour la plupart, une fois mises à "plat" (ou défactorisées, je ne sais pas comment dire), le prédicat passé par valeur est en fait toujours le même ? Sont-ils capables de comprendre qu'il suffit de "déplacer" le predicat plutôt que d'en faire une copie à chaque appel de fonction ?

23/10/2009, 02h07
JolyLoic

Ta troisième solution rend le prédicat non copiable... Elle ne marchera pas. Et si on la faisait marcher (par exemple, en utilisant un shared_ptr au lieu d'une référence pour partager la ressource entre différentes copies du prédicat), elle marcherait, il faudrait juste faire attention à ce que deux threads n'exécutent pas un prédicat avec la même ressource en même temps.

Il faut qu'il soit copiable, bien sur...
Voilà, j'ajoute le copy constructor

Code:

pred(pred const & r):tmp_r(r.tmp_r) {}

Et on désactivera aussi explicitement l'operator assign.

Je vais essayer d'exprimer ma question d'un point de vue plus général.
Supposons un objet Ob. Lorsque cet objet Ob est instantié il crée et utilise une resource locale (que je souhaite conceptuellement comme non partagée ni copiable même si techniquement elle pourrait l'être). Je voudrais que cet resource locale ne soit pas réinstantiée à chaque copie de l'instance de l'objet Ob (la resource est unique pour une instance de Ob et de ses copies éventuelles).
Voilà pour le cas général.

Pour en revenir à mon exemple, j'essaie d'imaginer un moyen d'éviter la contrainte de copie imposée lors d'un passage de paramètre par valeur (comme c'est le cas pour les fonctions de la SL).
Dans bien des cas c'est un "déplacement" qu'il faudrait faire plutôt qu'une copie. J'ai cru comprendre qu'il aura dans une future version de C++ ce genre de possibilité ("move" avec l'operator &&) mais ce n'est pas encore d'actualité. Et puis je suppose que le code de la SL ne sera pas réécrit en remplaçant les copies des prédicats par des déplacements, le problème restera.

Cependant...

Et j'en parlais au début, ne suffit-il pas de faire confiance au compilateur et à ses optimisations ?
Exemple:
Code:

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 inline void foo3(resource r) { cout << r << endl;//assume an existing operator<< for resource } inline void foo2(resource r) { cout << "foo2 enter" << endl; foo3(r); cout << "foo2 exit" << endl; } inline void foo1(resource r) { cout << "foo1 enter" << endl; foo2(r); cout << "foo1 exit" << endl; } int main() { resource r; foo1(r); return 0; }
En effet, on pourrait croire que les appels successifs aux différentes foo impliquent une copie du paramètre, or une bonne optimisation générerait un code équivalent à ceci:
Code:

1 2 3 4 5 6 7 8 9 10 int main() { resource r; cout << "foo1 enter" << endl; cout << "foo2 enter" << endl; cout << r << endl;//assume an existing operator<< for resource cout << "foo2 exit" << endl; cout << "foo1 exit" << endl; return 0; }
Et là il n'y a plus aucune copie de la resource r.

Citation:

Envoyé par camboui

Dans bien des cas c'est un "déplacement" qu'il faudrait faire plutôt qu'une copie. J'ai cru comprendre qu'il aura dans une future version de C++ ce genre de possibilité ("move" avec l'operator &&) mais ce n'est pas encore d'actualité. Et puis je suppose que le code de la SL ne sera pas réécrit en remplaçant les copies des prédicats par des déplacements, le problème restera.

Je ne pense pas qu'un déplacement soit une bonne idée dans ce cas. On peut d'ailleurs s'en rendre compte dès maintenant grâce aux auto_ptr qui déplace leur ressource lors d'une copie.... et ben ça assert très très vite si on les passe au algo de la STL. :mrgreen: Il suffit d'un sort() par exemple.

Citation:

Envoyé par camboui

Pour en revenir à mon exemple, j'essaie d'imaginer un moyen d'éviter la contrainte de copie imposée lors d'un passage de paramètre par valeur (comme c'est le cas pour les fonctions de la SL).

Il me semble que cette description ressemble beaucoup au reference_wrapper de boost (et maintenant du TR1) qui ont justement été inventé pour feinter et passer par référence tout en gardant une apparence de passage par valeur.
Code:

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 #include <array> #include <functional> class BigRessource { public: BigRessource():c(){printf("Ctor BR\n");} ~BigRessource(){printf("Dtor BR\n");} private: char c[5000]; // big ! // Pour s'assurer qu'il n'y a vraiment aucune copie... BigRessource(const BigRessource& br){}; BigRessource& operator=(const BigRessource& br){}; }; struct Pred : public std::binary_function<int, int, bool> { Pred():br_(){} bool operator()(int i1, int i2) { //... return i1 < i2; } BigRessource br_; }; int main() { std::array<int, 4> v = {4, 5, 6, 8}; Pred pred; std::sort(v.begin(), v.end(), std::ref(pred)); return 0; }
C'est très proche de ta solution finalement. Sauf qu'au lieu d'avoir une référence dans le prédicat sur la ressource, on a un pointeur sur le prédicat dans le reference_wrapper, ce qui permet de garder l'écriture du prédicat de manière plus naturelle AHMA.

HS : L'implémentation de reference_wrapper vaut vraiment le coup d'œil. Pour une fois avec du code venant de boost, c'est étonnamment simple, élégant et court. D'ailleurs la voici dans son intégralité(sans les workaround pour les vieux compilos)
Code:

1 2 3 4 5 6 7 8 9 10 11 template<class T> class reference_wrapper { public: typedef T type; explicit reference_wrapper(T& t): t_(&t) {} operator T& () const { return *t_; } T& get() const { return *t_; } private: T* t_; };
Un opérateur de conversion vers un T&... c'est magnifique et je savais même pas que le C++ était capable de ça. :applo:

27/10/2009, 11h43
camboui
J'ai failli applaudir comme toi, mais... bouahhhh, snif, mais pourquoi ça compile pas sous VS2005 :cry:
Code:

1 2 c:\program files\microsoft visual studio\vc98\include\algorithm(633) : error C2064: term does not evaluate to a function
J'ai utilisé <boost/ref.hpp> au lieu de <functional> puisque que ton code est pour VS2008, mais ça devrait fonctionner quand même :calim2:
C'est comme s'il ne voyait pas le Pred::operator() via reference_wrapper (qui, lui, n'en a pas).

Ah mince.
Effectivement, j'ai testé std::ref avec vs2010 beta 2 dans laquelle std::reference_wrapper<T> dispose d'un opérateur() qui transmet à l'opérateur() du T sous-jacent. Par contre il semblerait bien que boost::reference_wrapper n'en ait pas, lui. :aie:

Il y a peut être une solution avec boost.bind, mais c'est tout de suite moins sexy... (non testé)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Pred { public: template <typename T> bool operator()(const T& t1, const T& t2) { return t1 < t2; } private: BigRessource br_; }; Pred pred; std::sort(v.begin(), v.end(), boost::bind<bool>(boost::ref(pred), _1, _2)); // ou std::sort(v.begin(), v.end(), boost::bind<bool>(boost::ref(Pred()), _1, _2));

27/10/2009, 11h58
camboui
C'est fou ça 8O

Bon, j'ai modifié le header boost/ref.hpp en ajoutant simplement ceci dans reference_wrapper:
Code:

1 2 3 4 5 template<typename V> bool operator()(V const & rl, V const & rr) { return t_->operator()(rl,rr); }
Et ça marche !

Mais... Ils testent leur code les gars de chez boost ?!?! :aie:

Ben oui, mais...
Code:

1 2 3 4 5 6 template<typename V> bool operator()(V const & rl, V const & rr) { return t_->operator()(rl,rr); }
C'est pas très générique tout ça. :mrgreen:
C'est peut être pour ça qu'ils l'ont pas mis...

D'ailleurs dans vs2010 l'implémentation générique de l'opérateur()... ouch
En théorie c'est "relativement" simple :
Code:

1 2 3 4 5 // template variadique pour avoir un nombre quelconque de paramètre template <class... ArgTypes> typename result_of<T(ArgTypes...)>::type operator() (ArgTypes&&...) const; // + une pincée de perfect forwarding
Mais en pratique y'a du préprocesseur de partout c'est terrifiant. :aie:

27/10/2009, 12h22
camboui

En tout cas, merci arzar :applo: (j'aime ton smiley)

Je fais faire un petit copier/coller de ce reference_wrapper si simple pour mon petit usage personnel :D
C'est un beau moyen pour "convertir" un passage par valeur en référence.

...

Pour en revenir à mon premier post, la troisième écriture de prédicat ne me plaisait guère, bien que fonctionnelle.
Je vais donc garder la deuxième, bien plus élégante comme tu le disais aussi, avec un petit predicate_wrapper perso directement inspiré de reference_wrapper.
Mais quand même, pourquoi boost propose-t-il du code inutilisable ?
29/10/2009, 15h47
Médinoc

C'est un template variadique ça, non?

@Camboui: Vue l'orthographe de "BigRessource", je doute que le code avec les foncteurs soit un exemple fourni par boost. Je pense qu'ils n'avaient tout simplement pas prévu un tel usage de reference_wrapper...
29/10/2009, 18h46
camboui

Pourtant, si je comprends bien la doc de boost c'est fait pour contourner la contrainte de passage par valeur des prédicats, entre autres, des algos de la STL.

Citation:

reference_wrapper is primarily used to "feed" references to function templates (algorithms) that take their parameter by value. It provides an implicit conversion to T&, which usually allows the function templates to work on references unmodified.

Je me demande d'ailleurs ce que ça donnerait de passer les iterator comme ça. De jolis crashs je pense :aie:
29/10/2009, 19h07
Arzar

En fait je me suis rendu compte en cherchant la mailing de list de boost que l'ajout d'un opérateur() a été discuté plusieurs fois, par exemple ici

Pour résumé le lien plus haut, ça n'a jamais vraimment aboutit, apparemment:
- par flemme :aie:
- car on peut contourner l'absence de l'opérateur assez facilement avec un boost.bind comme je l'ai montré plus haut.
- parce que l'implémentation de l'opérateur() en C++98 est assez pénible - il faut se cogner du préprocesseur pour émuler le nombre variable de paramètre
- parce que les astuces de métaprog utilisée pour connaitre le type de retour demanderait d'inclure la moitié de boost (type_traits, MPL, bind...) ce qui chagrine un peu vu qu'à l'heure actuelle reference_wrapper est indépendant de tout le reste.
29/10/2009, 19h14
Goten

Ouai c'est ça surtout, le fait qu'on peut s'en sortir avec boost.bind, ça évite de sortir toute l'artillerie lourde.

Pourtant ça ne parait pas insumontable à faire sans usine à gaz derrière

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class T,class B>
class reference_wrapper
{ 
    T *t_ptr;
public:
    typedef T type;
 
    explicit reference_wrapper(T & t):t_ptr(&t) {}
    operator T& () const { return *t_ptr; }
	template<typename V>
	B operator()(V const & r) const { return (*t_ptr)(r); }
	template<typename V>
	B operator()(V const & rl, V const & rr) const { return (*t_ptr)(rl,rr); }
};
 
template<class T,class B> inline reference_wrapper<T,B> const ref(T & t)
{ 
    return reference_wrapper<T,B>(t);
}
 
template<class T,class B> inline reference_wrapper<T const,B> const cref(T const & t)
{
    return reference_wrapper<T const,B>(t);
}

Testé et vérifié dans certains cas usuels de la STL. Je pense même que c'est bon pour tous les types de prédicats de la STL.