Discussion :

[Ange_blond]

Bonjour,

Je suis actuellement en train de tester les hashmap pour essayer d'améliorer du code basé sur des grandes map dont le temps de recherche commence a devenir tres long...

J'ai trouvé que sous VS, il suffit de se faire un petit include de hash_map et d'utiliser stdext::hash_map
Par contre, rien à voir avec ce que SGI propose a savoir : hash_map


Dans la hash_map de VS, il n'est meme pas fait reference à la fonction de hashage, alors que l'implementation de SGI demande une fonction de hashage directement dans le constructeur.

D'apres mes tests, la hash_map de VS est meme 2 fois moins performante qu'une simple map...

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
 
#include <hash_map>
#include <time.h>
#include <iostream>
 
struct greater_str {
	bool operator()(const std::string x, const std::string y) const {
		if ( x.compare(y) > 0)
         return true;
 
      return false;
   }
};
 
 
int main()
{
 
	unsigned intmax = 1e07;
 
 
 
	//declare maps
	typedef stdext::hash_map<std::string, int, stdext::hash_compare<std::string, greater_str> > HashMap;
	typedef std::map<std::string , int, greater_str > Map;
 
	HashMap hmap;
	Map map;
 
 
	//add a lot of content
 
	for(unsigned int i=0 ; i < intmax ; ++i)
	{
		srand (osg::Timer::instance()->tick());
 
 
		//generate a string
		std::string string(10,' ');
		for(unsigned int j =0 ; j<9 ; ++j)
			string[j] = (char)(rand() % 30 + 'a');
 
		if(i == intmax*0.9)
			string = "trouvemoi";
 
		hmap.insert(std::make_pair(string, i));
		map.insert(std::make_pair(string, i));
 
	}
 
 
	osg::Timer_t hstart = osg::Timer::instance()->tick();
	Map::iterator it = map.find("trouvemoi");
	double hres = osg::Timer::instance()->delta_u(hstart, osg::Timer::instance()->tick());
 
	std::cout << "Hmap : " << hres << "µs, index " << it->second << std::endl;
 
	osg::Timer_t mstart = osg::Timer::instance()->tick();
	HashMap::iterator it2 = hmap.find("trouvemoi");
	double mres = osg::Timer::instance()->delta_u(mstart, osg::Timer::instance()->tick());
 
	std::cout << "map : " << mres << "µs, index " << it2->second << std::endl;
 
 
	return 1;
}

Note : ce code utilise les timer d'OpenScenGraph pour plus de simplicité, mais le résultat est sans appels :

Hmap : 6.50609µs, index 9000000
map : 1.80725µs, index 9000000

Alors avant tout, est ce que vous etes d'accord avec moi sur le fait que la hashmap de Visual Studio n'a rien d'une hashmap ?

Où puis-je trouver une hashmap digne de ce nom en c++ ? (opensource necessairement)

Merci.

Cordialement,
Ange_blond.

[Goten]

Quelle version de VS? Car dans le tr1 y'a unordered_map (std::tr1::unordered_map). Sinon y'a boost::unordered.

[nikko34]

tu as tr1::unordered_map ou son équivalent boost boost::unordered_map

[Arzar]

Bonjour,

Dans la hash_map de VS, il n'est meme pas fait reference à la fonction de hashage, alors que l'implementation de SGI demande une fonction de hashage directement dans le constructeur.
[...]
Alors avant tout, est ce que vous etes d'accord avec moi sur le fait que la hashmap de Visual Studio n'a rien d'une hashmap ?

Euuu, non, pas d'accord du tout. On peut naturellement fournir sa propre fonction de hash pour stdext::hash_map, sinon quel intérêt ? C'est quasiment le même mécanisme que pour std::unordered_map d'ailleurs, il faut créer une fonction-objet possédant certaine fonctions membres à la signature bien précise, et passer le type de la fonction-objet comme paramètre template de la hash_map.

Par exemple :

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
 
struct MyHash
{
   static const size_t bucket_size = 4;
   static const size_t min_buckets = 8;
 
   size_t operator()(const std::string& s) const
   {
      //bizarrement dans VS2010, std::unordered_map possède une 
      // spécialisation de la fonction de hashage pour std::string que j'ai
     // extraite et recopié ci-dessous, mais stdex::hash_map ne semble 
    // pas en avoir. Peut être un oubli de MS ?
      size_t _Val = 2166136261U;
      size_t _First = 0;
      size_t _Last = s.size();
      size_t _Stride = 1 + _Last / 10;
 
      for(; _First < _Last; _First += _Stride)
         _Val = 16777619U * _Val ^ (size_t)s[_First];
      return (_Val);
    }
 
    bool operator()(const std::string& s1, const std::string& s2) const
    {
        if ( s1.compare(s2) > 0)
	   return true;
 
	return false;
    }
};
 
typedef stdext::hash_map<std::string, int, MyHash > HashMap;

Autre chose, faire des mesures sur une durée aussi courte (1µs !!) n'est pas très significatif.
Chez moi, les timings fluctuent énormément d'une exécution sur l'autre, et surtout ce n'est ni la map, ni la hash_map qui est la plus rapide, en fait c'est celle que je mesure en premier qui gagne à tous les coups ! Il suffit d'inverser l'ordre de mesure pour changer la donne.

[Ange_blond]

Merci de vos réponses :-)

En effet, std::tr1::unordered_map est ce que je cherchais.

Par contre d'apres les 1ers tests, les perfo ne sont pas meilleures qu'une simple std::map, ce qui me surprend.

les tests ont été fait sur un grand set de donnée avec des nombreux "find" dans les map donc cette fois ci les résultats sont plus fiables.

Que conseilleriez vous pour avoir une grande (>150 000) map avec un temps d'acces tres rapide ? Nous constatons que le temps de "find" est de 0.1ms au début, pour plus de 30ms lorsque la map est populée... ce qui évidement fait chuter les performances de maniere drastique...

Merci.

[Goten]

T'utilises quoi comme hash?

[atttchoum]

Bonjour,

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
	osg::Timer_t hstart = osg::Timer::instance()->tick();
	Map::iterator it = map.find("trouvemoi");
	double hres = osg::Timer::instance()->delta_u(hstart, osg::Timer::instance()->tick());
 
	std::cout << "Hmap : " << hres << "µs, index " << it->second << std::endl;
 
	osg::Timer_t mstart = osg::Timer::instance()->tick();
	HashMap::iterator it2 = hmap.find("trouvemoi");
	double mres = osg::Timer::instance()->delta_u(mstart, osg::Timer::instance()->tick());
 
	std::cout << "map : " << mres << "µs, index " << it2->second << std::endl;
}

Juste pour dire que tu affiches les résultats de hmap la place de ceux de map et vice versa .

[Ange_blond]

Bonjour,

Juste pour dire que tu affiches les résultats de hmap la place de ceux de map et vice versa .

Bonne remarque

Je vais continuer les tests dans ce cas

T'utilises quoi comme hash?

j'ai laissé la fonction de hash par défaut

[Arzar]

Curieux en effet.
A chaque fois que j'ai remplacé une map par une unordered_map, j'ai toujours gagné en perf.

Sinon, avec std::unordered_map tu as deux leviers pour tuner les performances :
1) la fonction de hash (mais pour des std::string, unordered_map fournit déjà une fonction de hash spécialisée)
2) La fonction membre rehash(size_type n) qui permet de forcer le rehash avec un nombre de bucket désiré. Mais normalement, il n'y a pas vraiment besoin de le faire car unoredred_map se rehash automatiquement.

Une bonne description de unordered_map ici :
http://www.engin.umich.edu/class/eec...containers.pdf

Edit :

Juste pour dire que tu affiches les résultats de hmap la place de ceux de map et vice versa .

D'oh !! J'avais pas vu non plus

[Ange_blond]

Sinon j'ai trouvé ceci : http://code.google.com/p/google-sparsehash/

(Je suis peut etre pas le seul à galerer sur les perfos des maps)

Je n'ai pas encore testé mais ça semble etre une alternative plutot correcte

[Ange_blond]

Bon, il s'avere que ma std::map est plus rapide que les hash_map que j'ai testés (dont de nombreux tests de fonctions de hashage ).

Mon soucis de perfo se trouvait ailleurs, ma map n'était pas utilisée comme il faut au final.

Ceci étant, merci de votre aide si rapide et détaillée

[camboui]

Je n'ai pas compris la conclusion: std::map est plus performant parce que tu l'utilisais mal ?

[Arzar]

+1 avec camboui.

Ange_blond tu pourrais détailler un peu ton cas dans lequel une map est plus rapide qu'une hash_map ? Par exemple en donnant une description rapide du nombre d'éléments, du type de la clé, de la fonction de hash et de la part respective d'insertion/lookup/suppression ?

Car j'ai toujours constaté l'inverse, donc ça serait instructif de montrer un cas dans lesquels les map ont toujours l'avantage.

[Ange_blond]

Alors en fait, j'ai constaté que sur un cas de test comme le code fourni plus haut, la hash map est en effet plus performante.

Dans mon cas à moi, j'ai bidouillé des hashmap trouvé sur le net avec des fonction de hashage trouvé sur le net, pour au final me rendre compte que ce que je mesurais (temps d'un "find") n'était en fait pas seulement l'opération de find mais englobait du code qui lui par contre, était lent.
Enfin, j'ai remis en place la map d'origine car je n'ai noté aucune différence notable avec la hashmap sur mon dernier test (1 seul test, je n'avais pas le temps de faire plus)

Donc je n'ai pas vraiment de stats à donner, désolé, car j'ai du agir tres vite et boucler ce soucis avant de passer à la suite...