Problème de performance au chargement d'une Map

Version imprimable

10/01/2009, 22h23
alen

Problème de performance au chargement d'une Map

Bonjour,
Je suis en train de porter un code PC(VS2008) vers un embarqué ARM9.
Je suis confronté à un petit problème de performance au démarrage de l'appli.
J'ai identifié l'endroit et j'aurai aimé avoir vos avis pour l'optimisation de cette partie de code.
Je charge une map <wstring, wstring> avec des identifiants (clef d'acces wstring) et pour chacun de ces identifiant une string qui lui correspond. Donc pour chaque ligne de cette map j'alloue deux wstring et ce qui est nécessaire pour le map lui-même.
Hors toutes ces wstring existent déjà en mémoire (le fichier à été lu en un seul bloc) et je connais les WCHAR * du début de chacune de ces WCHAR[].
Donc l'idée serait d'avoir un map <WCHAR *, WCHAR*>. Mais evidemment je veux garder un accès rapide sur base d'une clef de type wstring.
Existe t'il un moyen de coder cela sur base des containers standard? Ou faut'il réécrire une classe spécailisé?
Merci
10/01/2009, 22h54
nikko34

il faut que tu recodes la fonction de comparaison et que tu la donnes à ta map? non?
10/01/2009, 23h00
alen

C'est aussi la fonction de comparaison qui sert pour faire la recherche d'une clef?
11/01/2009, 01h12
Arzar

Dans ce cas, pourquoi ne pas faire une map<wstring, wstring*> ?
Tu gagnerais beaucoup en performance pour l'insertion avec le deuxième paramètre en pointeur, tout en retenant une fonction de comparaison efficace, l'odre lexicographique des string, pour tes clés.

Et si c'est toujours trop lent, une map<wstring*, wstring*> peut convenir aussi.

Edit : J'ai écrit trop vite, je voulais proposer une map<wstring, wchar*> en faisant pointer tes wchar* sur la structure originale.

Citation:

Envoyé par alen

C'est aussi la fonction de comparaison qui sert pour faire la recherche d'une clef?

Oui.
En fait, généralement les maps sont implémentées comme des arbres rouge-noir, c'est à dire une variété d'arbres binaires. Quand tu cherches une clé, l'algo de recherche commence par le noeud racine et fait la comparaison : si ta clef est inférieure (par ordre alphabétique pour des wstring) à celle du nœud, l'algo de recherche par vers la branche gauche de l'arbre, si elle est supérieure vers la branche droite et si elle est ni supérieure ni inférieure alors c'est le bon nœud!
11/01/2009, 11h05
koala01

Salut,

Déjà, je me dis qu'il serait peut être utile de préciser ce que tu ressent par "problème de performances"...

S'agit-il "seulement" d'attendre une seconde de plus lors du démarrage, ou s'agit-il réellement d'attendre un temps particulièrement important (plusieurs minutes (heures :aie: :question:) de plus :question:)

Pour ma part à moins que le délais de démarrage ne devienne vraiment *trop* important et de nature à poser de réels problèmes, je serais presque tenté de dire que, si l'application met quelques secondes à démarrer, mais qu'elle a une réactivité malgré tout correcte en fonctionnement, tu cherche peut être à résoudre un problème plus "pressentis", de manière trop objective (du fait de ton habitude à travailler avec un quad core 3GHz, ce qui le rend très réactif, par exemple) que réel...

Ceci dit, il faut savoir que la comparaison de chaines de caractères (quel qu'en soit le type: std::string, std::wstring, char* ou wchar*) est, effectivement, gourmande en temps d'exécution du fait même des algorithmes nécessaires à cette comparaison.

Comme le remplissage d'une std::map, et surtout le placement d'un objet au bon endroit, se fait à coup de comparaison successives, on peut comprendre qu'il faille un certain temps si la clé utilisée demande un temps de comparaison important ;)

Tout cela m'inciterait peut être à te conseiller de voir si tu ne peux pas envisager de manipuler des clés d'un autre type (des valeurs entières, par exemple :question:) car je ne suis pas absolument certain (même si je peux me tromper, n'ayant pas fait de benchmarks sur le sujet) que tu puisse gagner énormément de temps en remplaçant simplement tes chaines std::wstring par des chaines wchar* :aie:
11/01/2009, 15h50
JolyLoic

Citation:

Envoyé par koala01

S'agit-il "seulement" d'attendre une seconde de plus lors du démarrage, ou s'agit-il réellement d'attendre un temps particulièrement important (plusieurs minutes (heures :aie: :question:) de plus :question:)

Il s'agit visiblement de code pour de l'embarqué. Dans ce domaine, le temps de démarrage est souvent plus sensible que pour des programmes classiques. Quand j'appuie sur le bouton start de mon lave vaisselle ou de mon GPS, je veux un feed-back immédiat.

Citation:

Envoyé par alen

Je charge une map <wstring, wstring> avec des identifiants (clef d'acces wstring) et pour chacun de ces identifiant une string qui lui correspond. Donc pour chaque ligne de cette map j'alloue deux wstring et ce qui est nécessaire pour le map lui-même.
Hors toutes ces wstring existent déjà en mémoire (le fichier à été lu en un seul bloc) et je connais les WCHAR * du début de chacune de ces WCHAR[].
Donc l'idée serait d'avoir un map <WCHAR *, WCHAR*>. Mais evidemment je veux garder un accès rapide sur base d'une clef de type wstring.

J'ai l'impression que le contenu de ta map ne bouge pas au cours de l'exécution. Dans ce cas, en plus de stocker des pointeurs afin d'éviter des copies de chaînes, tu pourrais utiliser un fichier déjà trié, et mettre le tout dans un vecteur trié pour recherche dichotomique => pas de coût d'équilibrage de la map, une seule allocation mémoire.
11/01/2009, 18h27
alen

Merci à tous pour vos conseils.
En effet je ne parle pas d'heures ni de minutes de chargement mais d'une phase du boot qui prend 4 secondes. Qui viennent s'ajouter aux 5 secondes de chargement de la DB.
Je travaille sur l'optimisation des deux, en espérant gagner quelques secondes (mon idéal étant sous les 4 sec.) Il s'agit d'un appareil de mesure et même si un écran de démarrage est affiché,10 secondes de boot ne sont pas accepté par les utilisateurs.
Il faut dire que les premiers boots tournaient à 30 secondes ;).

J'ai implémenté une map<WCHAR*,WCHAR*> avec sa fnction dde comparaison, je teste cela demain sur la plateforme...
12/01/2009, 17h28
alen

Voila le résultat pour ceux que cela interresse:
map<string,string> remplacé par map<wchar*,wchar*> avec une seule allocation d'un array de wchar. Je passe de 3.8 sec à 2.2 sec.
12/01/2009, 23h16
loufoque

Si tu utilisais la solution de JolyLoic, ça irait beaucoup plus vite.
13/01/2009, 08h21
alen

Je suis d'accord avec le fait que charger l'ensemble des strings depuis un fichier déjà trié dans un vector est certainement plus rapide. Je garde cette solution comme une amélioration ultérieure. Je me concentre maintenant sur les autres gros consommateurs de temps, chargement de la DB elle-même.

Petit doute à lever: la recherche dans un Map en runtime est bien du type dichotomique? et donc aussi rapide que dans un vecteur trié?

Merci
13/01/2009, 10h26
Sylvain Togni

Citation:

Envoyé par alen

Petit doute à lever: la recherche dans un Map en runtime est bien du type dichotomique? et donc aussi rapide que dans un vecteur trié?

C'est en O(log(n)) dans les deux cas, oui. Avec en pratique un léger avantage pour le vecteur trié car c'est une structure plus simple et les données sont contigües en mémoire.

As tu considéré l'utilisation d'une hash_map (ou unorderered_map), ça s'utilise comme une map, mais l'insertion et l'accès sont plus rapides (O(1) en amorti).
13/01/2009, 15h37
loufoque

Citation:

As tu considéré l'utilisation d'une hash_map (ou unorderered_map), ça s'utilise comme une map, mais l'insertion et l'accès sont plus rapides (O(1) en amorti).

C'est incorrect.
L'insertion est en O(1) amorti et l'accès est O(1) en moyenne, et O(n) dans le pire des cas.