Discussion :

[r0d]

Bonjour,

voilà, j'ai une map, dont les clés sont des string et les éléments sont des petites structures. A un moment donné dans mon programme, je dois désallouer cette map. Or, à ce moment, elle a une taille de l'ordre de 500Mo. Donc la libération prends un certain temps. Du coup, j'aimerais faire un système de progress bar, pour que l'utilisateur ne pense pas que l'appli est plantée.

Alors j'avais pensé faire une boucle qui détruit élément par élément, avec un compteur. Quelque chose comme ça:

Code :

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

1
2
3
4
5
6
int count = 0;
for ( MaMap::iterator it = ma_map.begin(); it != ma_map.end(); ++it )
{
	ma_map.erase( it );
	Step( count ++ ); // gère la barre de progression
}

Mais ça ne marche pas, le erase rends it inutilisable et du coup le ++it suivant envoie mon iterateur dans la stratosphère.

Auriez-vous quelques idées?

[Nogane]

Bonjours,
Je suppose qu'il s'agit d'une std::map?

Est-ce la map qui est grosse ou plutôt les objets contenue?
Les objet sont-ils des pointeurs intelligents?
Dans ce cas il serai possible de faire un parcourt normal avec reset et Step, puis un clear de la map.

Autre solution, en restant sur ton idée de départ:

Code :

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

1
2
3
4
5
6
7
8
 
int count = 0;
MaMap::iterator it = ma_map.begin();
while (  it != ma_map.end())
{
	ma_map.erase( it++ ); //l'opérateur ++ renvoie une copie non incrémenté de it, donc it reste valide
	Step( count ++ ); // gère la barre de progression
}

[Invité]

Salut r0d,

C'est prévu! La fonction erase() renvoie un itérateur sur l'élément qui suit celui que tu supprimes, il faut donc écrire

Code :

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

while(it!=conteneur.end()) it=conteneur.erase(it);

Ce comportement est commun à tous les conteneurs de la STL... tu peux donc conserver ton code, même si tu abandonnes la map (ouais, parce qu'une map indexée par des string, en terme de performance...)

Francois

[Nogane]

j'ai une map, dont les clés sont des string et les éléments sont des petites structures.

Woups, j'avais pas vu ca, du coup j'ai posé des questions pour rien...

C'est prévu! La fonction erase() renvoie un itérateur sur l'élément qui suit celui que tu supprimes, il faut donc écrire

C'est ce que je me suis dit au début, mais apparemment pas la std::map.(en tout cas pas avec la std de minGW, ni dans la doc de cplusplus.com)

Question a part:
Pourquoi une map indexée par des strings est-ce si terrible? L'opérateur < sur des string est rapide, et une map ne fait pas de copie en interne(comme un vector ferait). Alors pourquoi?
Et quel autre alternative pour faire un tableau associatif chaine de caractère -> quelque chose ? unordered_map? le faire soit même?

[r0d]

Je suppose qu'il s'agit d'une std::map?

oui oui, comme on est sur le sous-forum sl/stl, je n'avais pas pensé utile de le préciser.

Est-ce la map qui est grosse ou plutôt les objets contenue?

Ce sont des petits éléments, mais il y en a vraiment beaucoup.

Les objet sont-ils des pointeurs intelligents?

Non. Ce ne sont pas des pointeurs. Si tu veux, ça ressemble à ça:

Code :

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

1
2
3
4
5
6
struct Dum
{
   int x1, x2, x3;
};
 
std::map<std::string, Dum> ma_map;

Autre solution [..]

Merci
Pour l'instant je pars là-dessus, ça à l'air de fonctionner. Merci.

une map indexée par des string, en terme de performance...

Ben là, ce n'est pas si évident que ça. Ce week-end j'ai fait toute une batterie de tests pour comparer les performances de maps indexées par des string par rapport à d'autres types de clés (entiers, enums, etc.), et je n'ai pas obtenu de différences significatives. Bon, je n'ai pas effectués ces tests dans des vrais conditions de tests, ni sur plusieurs machines, ni avec différentes compilos, mais disons que ce point n'est pas si évident que ça. Je n'ai malheureusement trouvé aucune littérature sur le sujet

[Invité]

C'est ce que je me suis dit au début, mais apparemment pas la std::map.(en tout cas pas avec la std de minGW, ni dans la doc de cplusplus.com)

Tu as raison. Je l'ai sur la STL que j'utilise (dinkumware) mais après vérification, je ne le vois pas dans STLport. C'est probablement une extension non standard (c'est un peu bête, soit dit en passant). Pour être portable, il faut donc faire comme tu dis, incrémenter l'itérateur avant, et détruire après (personnellement je préfère faire une copie plutôt qu'une postincrémentation, mais c'est une affaire de goût).

Pourquoi une map indexée par des strings est-ce si terrible? L'opérateur < sur des string est rapide, et une map ne fait pas de copie en interne(comme un vector ferait). Alors pourquoi?
Et quel autre alternative pour faire un tableau associatif chaine de caractère -> quelque chose ? unordered_map? le faire soit même?

Il y a deux aspects :

1- la map n'est pas une bonne implémentation d'un tableau associatif, si celui ci est lu, utilisé puis détruit (ou change très peu dans le temps). Un vecteur trié, avec une recherche binaire (lower_bound, des trucs comme ca) sera toujours plus efficace, en terme de mémoire et de vitesse. La map est utile quand on fait beaucoup d'ajouts et de suppressions, et des recherches entre, ou quand on a de petites structures (ou que la vitesse n'est pas un problème). Son principal avantage, dans ces situations, c'est qu'elle est très facile à mettre en oeuvre.

Si on fait essentiellement un chargement, des tas de recherches, et une destruction (avec un ou deux petits ajouts/destruction au milieu), le vector gagne toujours...

Dans des cas intermédiaires, et pour de gros volumes (surtout si les index ne sont pas des entiers), les tables de hachage fonctionneront mieux (par rapport au vector, elles prennent plus d'espace et vont plus vite, par rapport à la map, elles prennent généralement autant d'espace, et vont nettement plus vite...)

2- l'indexation par des string, c'est lent, parce que toutes les méthodes de recherche/tri rapide reposent sur des comparaisons, et que les comparaisons de string sont lentes (par rapport aux comparaisons d'entier). Par ailleurs, les string ca mange de la mémoire (et du temps lors de l'allocation)...

Sur de petites tables, la question ne se pose pas, mais dès qu'on va sur quelque chose de gros, on a intérêt à réindexer. Souvent on peut s'arranger pour le faire, soit dans les entrées (si on travaille sur des données "mortes", soit au chargement : on indexe les string qu'on va utiliser et on utilise cet index entier). Si c'est impossible, c'est là que le hachage devient très puissant.

Une fois de plus, le problème ne se pose que quand on travaille avec de grosses structures (plusieurs milliers d'enregistrements, je dirais, en fait dès que les approches reposant sur des conteneurs triés commencent à faire la différence). Et la STL fournit les outils qui permettent de traiter cela (les vecteurs triés et les outils de recherche qui vont avec, et le hachage, même s'il n'est pas tout à fait standardisé d'une implémentation à l'autre).

Sur un gros programme qui fait de la "gestion", retravailler les map, les indexations par des string, et les entrées sortie, c'est presque toujours faire un gros gain de vitesse...

Francois

[Nogane]

Merci beaucoup pour ces explications!
Je n'ai jamais utiliser des tableaux associatifs avec de fortes contraintes de mémoire/vitesse, mais au moins quand ca arrivera j'aurais une idée plus précises des différentes possibilités.
C'est vrais qu'au premier abord, je n'aurais pas pensé au vector trié, ou a la "réindexation".

[screetch]

pour revenir sur le "erase" qui renvoie ou pas un iterateur, c'est :

- standard dans vector, list etc, car lorsqu'on fait "erase" les itérateurs suivants sont invalidés
par exemple, le code suivant :

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
#include <vector>
 
int main(int argc, char *argv[])
{
    typedef std::vector<int> vector;
    typedef vector::iterator iterator;
 
    vector v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);
    v.push_back(4);
 
    for(iterator it = v.begin(), end = v.end(); it != end; /*increment in the loop */)
    {
        if(*it == 2)
            v.erase(it++);
        else
            ++it;
    }
    return 0;
}

a deux enormes bugs qui se verront... ou pas. Dépendant de l'implémentation.

la version corrigée de la boucle :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
    // Attention! pas plus malin que la STL; v.end() ne peut pas etre stocké car il pourrait etre invalidé duran la boucle
    for(iterator it = v.begin(); it != v.end; /*increment in the loop */)
    {
        if(*it == 2)
            // NON! it+1 va etre invalidé
            // v.erase(it++);
            it = v.erase(it);
        else
            ++it;
    }
    return 0;
}

- Non standard dans <map>, proposé parfois en extension
le code de map ne pose pas ce probleme puisqu'aucun élément se retrouve invalidé lorsque l'on fait erase. Le code plus haut est donc valable :

Code :

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

v.erase(it++);

et donc erase n'a pas besoin de renvoyer le suivant. Encore que j'aurai préféré qu'il le fasse

[LittleWhite]

Pour la suppression des éléments d'une std::map -> http://cpp.developpez.com/faq/cpp/?p...ssion_elements

( Ou alors j'ai pas compris tout le débat, et je m'en excuse de faire un hors sujet )

[r0d]

En fait, j'espérais secrètement que quelqu'un parle de l'allocateur (sujet sur lequel je suis totalement inculte). Mais sinon si, tu es bien dans le sujet

[Nogane]

Bonne idée l'allocateur!
Si tu utilisé le boost::pool_allocator, je pari que ta suppression irai bien plus vite, étant donné que tu limite la quantité d'allocation/désalocation. (Ya aussi le Small object Allocator, de Loki. Je ne sait pas lequel est mieux).
Tu peu l'utiliser sur la map ET sur les string.
...par contre ca ne change pas la manière de vider ton conteneur...et ca risque de prendre plus de mémoire...

Ou alors, une solution inspiré par les informations de fcharton serais d'utiliser un vector trié(avec par example un std::pair<std::string, MaStructure>). Mais la il faudrait remplacer la string par un char[N], ou... un int. Et comme ca la suppression ce fait en un clin d'oeil car une seul et unique désalocation.

[Invité]

Ou alors, une solution inspiré par les informations de fcharton serais d'utiliser un vector trié(avec par example un std::pair<std::string, MaStructure>). Mais la il faudrait remplacer la string par un char[N], ou... un int. Et comme ca la suppression ce fait en un clin d'oeil car une seul et unique désalocation.

Il me semble qu'on pourrait déjà essayer en gardant les string, et en utilisant un vecteur trié sur une structure qui regrouperait la structure valeur de la map et la string clef.

Code :

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

1
2
3
4
5
 
struct NS {
  string clef;
  int x,y,z;
};

on peut alors lui définir un opérateur de comparaison qui ne porte que sur les clefs

Code :

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

1
2
3
4
bool operator<(const NS &lht) const
{
return clef<lht.clef;
}

et on est maintenant prêts à tout mettre dans un vecteur "normal" (avec des push_back), puis à le trier à la fin

Code :

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

1
2
3
4
5
 
vector<NS> table;
table.reserve(nb);
for(int i=0;i<nb;i++) table.push_back(mavaleur(i));
sort(table.begin(),table.end());

On vit maintenant avec une table triée, et l'on peut y rechercher un élément avec

Code :

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

lower_bound(table.begin(),table.end(),maclef);

ou écrire à la main une petite recherche dichotomique (5 lignes de code environ), et encapsuler tout cela dans une classe si on veut simplifier la syntaxe.

Normalement, ca devrait prendre moins d'espace mémoire qu'un map, ca devrait aller plus vite, et ca se désalloue plus vite. S'il fallait encore une "totoche" pour la désallocation, on pourrait désallouer par bouts (en partant de la fin, pour éviter les réallocations dans le vecteur... Attention, comme les vecteurs ne réduisent pas leur taille, il faut utiliser un truc pour réellement libérer la mémoire occuppée, c'est dans tous les bons bouquins).

Moi, j'essaierai comme ca, il est fort possible que le problème original disparaisse alors, et cela n'impose que très peu de codage.

Ceci dit, en y réfléchissant, je trouve étrange cette histoire de libération mémoire qui met un temps fou... L'allocation ca peut prendre du temps, la libération... rOd, tu ne pourrais pas passer un profileur dessus pour savoir ce qu'il en est exactement (je soupconne ta map, en fait, bien plus que ta libération de mémoire)

Francois

[Goten]

Bonne idée l'allocateur!
Si tu utilisé le boost::pool_allocator, je pari que ta suppression irai bien plus vite, étant donné que tu limite la quantité d'allocation/désalocation. (Ya aussi le Small object Allocator, de Loki. Je ne sait pas lequel est mieux).
Tu peu l'utiliser sur la map ET sur les string.
...par contre ca ne change pas la manière de vider ton conteneur...et ca risque de prendre plus de mémoire...

Ou alors, une solution inspiré par les informations de fcharton serais d'utiliser un vector trié(avec par example un std::pair<std::string, MaStructure>). Mais la il faudrait remplacer la string par un char[N], ou... un int. Et comme ca la suppression ce fait en un clin d'oeil car une seul et unique désalocation.

pool_allocateur est deprecated (pas officiellement mais bon). J'ai entendu parler d'une v2. Au niveau du free c'est trop lent apparemment.
Y'a le smallobjalloc de loki qui est vraiment bien conçu, ça mérite de faire des benchs.

Mais sinon, ça vaut le coup de tester (en priorité) la solution de françois.

[Bakura]

ou écrire à la main une petite recherche dichotomique (5 lignes de code environ), et encapsuler tout cela dans une classe si on veut simplifier la syntaxe.

Ca existe déjà dans la STL (cf std::binary_search).

[Invité]

Ca existe déjà dans la STL (cf std::binary_search).

Non. Binary_search ca renvoie un booléen qui dit si on est dans le conteneur ou pas. Ca ne renvoie pas de référence vers l'élément cherché.

Pour accéder à un élément, avec la STL, il te faut un lower_bound() (cf l'exemple que je citais), qui utilise également une recherche dichotomique. Pour chercher un élément, il te faut un appel à lower_bound() et une comparaison.

Mais il reste des cas où coder cette recherche à la main est utile (par exemple quand tu cherches un intervalle, tu peux aller plus vite qu'avec deux recherches, ou pour exploiter certaines caractéristiques de la distribution de tes clefs.

C'est très facile, le code est simple, et se trouve dans tous les bons livres. Ca fait partie des choses minimales qu'il faut savoir faire soi même.

Francois

[trollichinelle]

Concernant la destruction d'une std::map je constate en ce moment qu'après la destruction ( clear() ) ou l'effacement d'éléments ( erase() ), la mémoire allouée pour la map n'est pas rendue à l'OS, quelqu'un peut il infirmer ou confirmer mon observation?

J'utilise la std::map pour réaliser des dictionnaires d'une taille très importante, je suis donc très concerné par les considérations d'allocation et de libération de mémoire,
J'ai noté la proposition de françois, quel est votre avis sur l'utilisation du map de la STL pour un dictionnaire? quelqu'un a-il des alternatives à proposer?



ps:je teste actuellement google-sparsehash un hash vanté pour sa faible occupation mémoire, mais j'obtiens (pour l'instant) des résultats étrangement proches de ceux avec std::map

[Nogane]

Certaines stl (comme la stl-port) gardes les petite zones mémoire allouées, surement pour limiter le nombre d'allocation, en particulier avec les string. Ca peut être une explication.

[Arzar]

Concernant la destruction d'une std::map je constate en ce moment qu'après la destruction ( clear() ) ou l'effacement d'éléments ( erase() ), la mémoire allouée pour la map n'est pas rendue à l'OS

Edit : Voir le sujet récent :
difference entre clear et swap

[koala01]

Salut,

Je reviens, un peu à la manière des carabiniers d'offenbach, sur la question de base, mais, pourquoi ne pas avoir bêtement recours au fait que, tant qu'il y a un objet dans ta map, begin() est différent de end()

Cela donne peut être un comportement assez lent, mais un

Code :

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

1
2
3
4
5
6
7
8
9
void MaClass:clear()
{
    int count = items.size();
    while(items.begin()!=items.end())
    {
       --count;
       items.erase(items.begin());
    }
}

pourrait faire l'affaire

Pour répondre à la question de nogame concernant l'opérateur < de la classe string (ou des chaines de caractères, de manière générale), il faut savoir que les opérateurs de comparaison (car c'est le cas également pour == et !=) sur les chaines de caractères sont ceux qui prennent potentiellement le plus de temps, car, si deux chaines ont une taille identique, et ne diffèrent que par le dernier caractère qu'elle contiennent, tu passera tous les caractères en revue avant d'obtenir une réponse.

En effet, l'algorithme de comparaison est souvent proche d'un parcours séquentiel de l'ensemble des caractères composant les chaines à tester sous une forme proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
 
entier compteur : 0
tant que compteur < taille
|    si (chaine1[compteur] <> chaine2[compteur]
|        renvoi selon opérateur envisagé
|    sinon
|        compteur : compteur + 1
|    fin si
fin tant
renvoi selon opérateur envisagé (2 chaines identiques)

alors que, sur les types primitifs (un caractère unique étant un type primitif à, la comparaison se fait en quelques tours d'horloge interne au niveau du processeur

[Nogane]

En effet, l'algorithme de comparaison est souvent proche d'un parcours séquentiel de l'ensemble des caractères composant les chaines à tester

En faite j'avais dans l'idée que, les chaines étant généralement différentes dés le premier caractère, le parcours s'arrêtait très tôt, et donc que la comparaison des strings n'était pas si longue.

Mais après avoir testé, je me rend compte que sur mon minGW la comparaison de string est environ 40 fois plus lente que celle des int. Étonnamment cette valeur n'est pas influencée par la disparité des string(si elle sont très différentes ou non).

Évidement cette valeur ne vaut pas grand chose, mais ca donne un ordre d'idée de la perte de perf que l'on peut avoir en comparant des string plutôt que des int.