Problème avec une HashMap (STL/SGI)

Version imprimable

Bonjour,

Alors j'aimerais indexer dans une hashMap tout plein de k-mer de plusieurs millions de mots différents.
J'utilise l'extension de la hashMap développée par SGI pour répondre à ce problème.
Voici mon code :
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 ----> inclusion de l'extension SGI #include <ext/hash_map> using namespace std; namespace std { using namespace __gnu_cxx; } ----> utilisation du hasher proposé par SGI struct eqstr{ bool operator()(const char* s1, const char* s2) const { return strcmp(s1,s2)==0; } }; -----> le block associé à la hash int main(int argc, char **argv) { // initialisation hash_map<const char*, int, hash<const char*>, eqstr> hash_kmer; ... ... ullong cpt = 0; uint lg_kmer = k; // k une longueur fixe, plus petite que la taille du plus petit mot... while (cpt < nb_mots) { tousLesMots.getline(mot_actuel, lg_mot+1); for (ullong i = 0 ; i < (lg_mot-lg_kmer) ; i++){ facteur = (mot_actuel.substr(i,lg_kmer)).c_str(); hash_kmer[facteur] ++ ; } cpt++; } ... ... return 0; }
Le problème est que c'est très très lent !
Par exemple, en prenant des mots de longueurs 75 et un k-mer de longueur 22, pour un nombre de mots de 45 millions, il faut 8 heures pour faire tourner le programme (sur une machine puissante).

Au début, je pensais que c'était la gestion des collisions qui prenait beaucoup de temps. De ce fait, j'ai diminué la longueur de k pour avoir moins de collisions. Sauf que, pour le même exemple, mais avec un k de longueur 10 ça met 15 heures, donc deux fois plus de temps.

Je pense que c'est mon implantation qui n'est pas bonne (ou peut-être le hasher que j'utilise). C'est pour cela que je me retourne vers vous car je ne suis pas plus compétant que ça dans les hashMap.
PS : j'ai testé d'autres implantation de hash telles que google-sparse ou google-dense mais ça ne change rien.
De plus dans ce comparatif, SGI n'est pas trop mal située :
http://attractivechaos.awardspace.com/udb.html

Qui aurait une idée de ce problème de lenteur ????

Merci d'avance,

Nicolas P

11/02/2011, 19h22
Arzar
Bonsoir,

Peut-être pourrais tu nous mettre le code complet vu qu'il n'a pas l'air très long ? (avec la balise code). Et nous mettre un lien vers un exemple de base de mots pour qu'on puisse essayer nous-même et voir la cause de la lenteur.

En attendant :
Code:

1 2 3 4 5 6 // ----> utilisation du hasher proposé par SGI struct eqstr{ bool operator()(const char* s1, const char* s2) const { return strcmp(s1,s2)==0; } };
Pourquoi le commentaire parle de "l'utilisation du hasher", alors que la structure eqstr ne définit pas de fonction de hash, juste une fonction de comparaison !?
Code:

1 2 3 4 5 6 while (cpt < nb_mots) { tousLesMots.getline(mot_actuel, lg_mot+1); for (ullong i = 0 ; i < (lg_mot-lg_kmer) ; i++){ facteur = (mot_actuel.substr(i,lg_kmer)).c_str(); hash_kmer[facteur] ++ ; }
humhum. Difficile de juger du code sans connaître la définition de tousLesMots, mot_actuel etc. mais ce bout de code a l’air très suspect quand même. On a l'impression que tu mets dans ta table de hash un pointeur vers un objet temporaire (mot_actuel.substr())

Oui en effet, je me suis trompé dans mon commentaire, ça c'est suelement l'equalKey que j'utilise. Je voulais juste dire que j'utilisais la fonction de hashage par défaut...

Pour mon code, je vous l'envoie tel qu'il est. J'ai voulu couper pour simplifier un peu mais c'était pas une bonne idée finalement :P

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
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
77
78
 
 
#include <iostream>
#include <fstream>
#include <string>
#include <sys/time.h>
#include <ext/hash_map>
extern "C" {
#include <time.h>
}
 
using namespace std;
namespace std { using namespace __gnu_cxx; }
 
#ifndef ullong
#define ullong unsigned long long
#endif
 
ullong getChrono() {
  struct timeval time;
  time_t sec;
  suseconds_t usec;
 
  if (gettimeofday(&time,NULL) != -1) {
    sec = time.tv_sec;
    usec = time.tv_usec;
    return (ullong)sec*1000000+usec;
  }
  return 0;
}
 
struct eqstr{
  bool operator()(const char* s1, const char* s2) const {
    return strcmp(s1,s2)==0;
  }
};
 
int main(int argc, char **argv)
{
  if (argc < 4){
    cerr << "Usage: " << argv[0] <<" read_file read_length threshold" << endl; 
    exit(1);
  }
  ullong start = getChrono();
 
  ifstream reads;
  reads.open(argv[1], ios::in);
  if (! reads.is_open()) {
    cerr << "Cannot open reads file: " << argv[1] << endl;
    exit(2);
  }
  reads.seekg (0, ios::end);
  ullong length = reads.tellg();
  int read_length = atoi(argv[2]);
  char *line = new char[read_length+1];
  reads.seekg (0, ios::beg);
  ullong nb_reads = length/(read_length+1);
  int threshold= atoi(argv[3]);
 
  hash_map<const char*, int, hash<const char*>, eqstr> hash_kmer;
 
  string read_string;
  const char *factor = new char[threshold+1];
  ullong current = 0;
 
  while (current < nb_reads) {
    reads.getline(line, read_length+1);
    read_string = line;
    for (ullong i = 0 ; i < (read_length-threshold) ; i++){
      factor = (read_string.substr(i,threshold)).c_str();
      hash_kmer[factor] ++ ;
    }
    current++;
  }  
  cout << "nb_factors indexed in hash_kmer: " << hash_kmer.size() << endl;
  cerr << "Creation of stl_hash_map: " << (getChrono()-start)/1000000. << " s" << endl;
  return 0;
}

Pour le lien avec un fichier de donnée :
http://www.lirmm.fr/~nphilippe/test

Merci encore

Nicolas P

14/02/2011, 13h54
r0d

Bonjour,

au cas où, ne sait-on jamais: êtes-vous bien certain de compiler avec les optimisations de compilation adéquates?
14/02/2011, 16h04
screetch

c'est deja un miracle que ca marche.
Comme dit plus haut:

Citation:

humhum. Difficile de juger du code sans connaître la définition de tousLesMots, mot_actuel etc. mais ce bout de code a l’air très suspect quand même. On a l'impression que tu mets dans ta table de hash un pointeur vers un objet temporaire (mot_actuel.substr())

le gros avantage c'est que tu n'alloues presque pas de mémoire (en tous cas pas pour les chaines).
Le gros inconvenient c'est que tu stockes probablement toute les chaines dans le meme bloc memoire (elles s'ecrasent les unes les autres). Toute les comparaisons de chaines etc etc sont probablement faussées.

Sinon, tu pourrais afficher une sorte de barre de progres ou de ETA; ca pourrait aider a voir si il y a un probleme de complexité, ou bien si le programme s'arrete periodiquement...
14/02/2011, 16h50
nphilippe1684

C'est possible que ce soit à cause de ça, mais j'suis septique.
Au cas où, voila ma ligne de compilation :
g++ -Wall -Wextra -ansi -g -O2 -funroll-loops buildSTLHash.cpp -o buildSTLHash

En fait c'est vraiment très visuel ! Ça commence à patiner dans la semoule à partir d'un certain moment.
Sur l'exemple que j'ai donné en lien, voici la trace de mon programme pour un k-mer de lg 22.

Au début de l' exécution du programme, ça se comporte très normalement :

10000 reads is included in stl_hash in 0.110646 s
20000 reads is included in stl_hash in 0.214687 s
30000 reads is included in stl_hash in 0.297762 s
40000 reads is included in stl_hash in 0.423303 s
50000 reads is included in stl_hash in 0.609714 s
60000 reads is included in stl_hash in 0.771651 s
70000 reads is included in stl_hash in 0.859677 s
80000 reads is included in stl_hash in 0.976118 s
90000 reads is included in stl_hash in 1.28819 s
100000 reads is included in stl_hash in 1.40297 s
110000 reads is included in stl_hash in 1.49794 s
120000 reads is included in stl_hash in 1.59264 s
130000 reads is included in stl_hash in 1.73249 s
140000 reads is included in stl_hash in 1.85493 s
150000 reads is included in stl_hash in 1.9604 s
160000 reads is included in stl_hash in 2.07579 s
170000 reads is included in stl_hash in 2.61795 s
180000 reads is included in stl_hash in 2.74023 s
190000 reads is included in stl_hash in 2.84681 s
200000 reads is included in stl_hash in 3.01806 s
210000 reads is included in stl_hash in 3.11888 s
220000 reads is included in stl_hash in 3.21828 s
230000 reads is included in stl_hash in 3.31929 s
240000 reads is included in stl_hash in 3.42316 s
250000 reads is included in stl_hash in 3.53848 s
260000 reads is included in stl_hash in 3.65708 s
270000 reads is included in stl_hash in 3.93243 s
280000 reads is included in stl_hash in 4.05486 s
290000 reads is included in stl_hash in 4.18682 s
300000 reads is included in stl_hash in 4.29214 s
310000 reads is included in stl_hash in 4.42333 s

Soit 310 000 reads pour 4 secondes

Et à partir d'un moment :

17960000 reads is included in stl_hash in 1902.34 s
17970000 reads is included in stl_hash in 1907.72 s
17980000 reads is included in stl_hash in 1913.17 s
17990000 reads is included in stl_hash in 1918.09 s
18000000 reads is included in stl_hash in 1924.37 s
18010000 reads is included in stl_hash in 1931.79 s
18020000 reads is included in stl_hash in 1935.82 s
18030000 reads is included in stl_hash in 1940.33 s
18040000 reads is included in stl_hash in 1942.89 s
18050000 reads is included in stl_hash in 1949.09 s
18060000 reads is included in stl_hash in 1954.16 s

Soit 100 000 reads pour 52 secondes. Et c'est de pire en pire...

Peut-être qu'il y a de plus en plus de conflits à gérer ? Mais dans ce cas là, en réduisant la longueur du k-mer je devrais gagner de la vitesse, puisque j'ai moins de clés distinctes, non ?

Je ne suis vraiment pas un spécialiste des hashMap, donc n'hésitez-pas à me donner toutes sortes de suggestions ou d'informations, ça ne me sera que bénéfique.

Merci,

Nicolas P
14/02/2011, 16h56
screetch

il faut vraiment corriger ton problème de chaines temporaires qui sont ecrasées; imagines que maintenant toute tes comparaisons sont faussées, on est pas du tout dans le cas optimal pour un hash_map.

Pour t'expliquer ce qui se passe, les clés sont effacées au fur et a mesure et probablement ecrasées par de nouvelles clés. Tu as un hash_map ou les clés sont donc presque surement changées après insertion, voire pire.
14/02/2011, 18h06
nphilippe1684

Il me semble que j'avais fait un cout des clés et des valeurs sur un petit exemple. Ça correspondait aux bons résultats. Je me suis dis que c'était la valeur pointée qui était recopiée dans la hash mais je comprends bien le problème dans le cas où c'est directement l'adresse qui est stockée. Je vais créer un new char[threshold+1] à chaque fois, on va voir si vous avez eu le nez creux :D
14/02/2011, 18h28
kael kael
Citation:

Envoyé par screetch

le gros avantage c'est que tu n'alloues presque pas de mémoire (en tous cas pas pour les chaines).
Le gros inconvenient c'est que tu stockes probablement toute les chaines dans le meme bloc memoire (elles s'ecrasent les unes les autres). Toute les comparaisons de chaines etc etc sont probablement faussées.

Euh... sauf erreur de ma part, ce n'est pas ce qui se passe.
Dans son code il y a :
Code:

1 2 factor = (read_string.substr(i,threshold)).c_str(); hash_kmer[factor] ++ ;
La fonction c_str() renvoit une nouvelle chaîne à chaque fois (allouée par les propres soins de la fonction). L'espace mémoire alloué pour cette chaîne n'est pas libéré. L'adresse à laquelle est stockée la chaîne n'est donc jamais la même et les clés ne peuvent pas être écrasées.

En revanche, je n'ai aucune idée pour le problème de lenteur. Si vraiment elles ne font pas l'affaire, il faudrait peut-être utiliser une autre structure que les tables de hash, qui ne seraient peut-être pas adaptées à ce problème. ;)
14/02/2011, 18h59
nphilippe1684
Citation:

Envoyé par screetch

il faut vraiment corriger ton problème de chaines temporaires qui sont ecrasées; imagines que maintenant toute tes comparaisons sont faussées, on est pas du tout dans le cas optimal pour un hash_map.

Pour t'expliquer ce qui se passe, les clés sont effacées au fur et a mesure et probablement ecrasées par de nouvelles clés. Tu as un hash_map ou les clés sont donc presque surement changées après insertion, voire pire.

Alors si j'ai alloué un nouveau factor à chaque fois (si j'ai bien compris ce que tu m'as dis), ce qui donne :
Code:

1 2 3 4 char *factor = new char[threshold+1]; strcopy(factor, (read_string.substr(i,threshold)).c_str()); hash_kmer[factor] ++ ;
Mais ça n'a pas l'air de changer grand chose, ce qui laisse (peut-être) à penser que la fonction c_str() fait déjà le boulot de l'allocation (ce qui disait KaelKael).

Par ailleurs, ça explique aussi pourquoi je retrouvais bien mes clés et mes valeurs. En effet, dans le cas où les clés s'effaceraient au fur et à mesure, je ne vois pas comment je pourrais les retrouver à la fin :/
14/02/2011, 18h59
screetch

c_str() ne renvoie pas une nouvelle chaîne, il renvoie en général le pointeur interne.
http://www.cplusplus.com/reference/string/string/c_str/
14/02/2011, 19h03
screetch
Code:

1 2 3 const char *factor = new char[threshold+1]; factor = (read_string.substr(i,threshold)).c_str(); hash_kmer[factor] ++ ;
ce code est toujours faux; tu alloues d'abord factor, puis tu remplaces le pointeur par un autre pointeur, tu ne fais pas vraiment une copie. En gros tu as juste alloué de la memoire, qui est perdue immédiatement. Forcément ca va être plus lent ;)

ca va etre chaud de le faire marcher correctement, a cause des doublons, avec des (cons de) char*.
Au ieu de ca j'avoue que des std::string t'eviteront sans doute des maux de tete.
14/02/2011, 19h13
nphilippe1684

Oui je me suis rendu compte de ma connerie, c'est pour ça que j'ai édité mon message, mais tu as répondu trop vite :/
14/02/2011, 19h16
nphilippe1684
Citation:
Envoyé par screetch

Code:

1 2 3 const char *factor = new char[threshold+1]; factor = (read_string.substr(i,threshold)).c_str(); hash_kmer[factor] ++ ;

ce code est toujours faux; tu alloues d'abord factor, puis tu remplaces le pointeur par un autre pointeur, tu ne fais pas vraiment une copie. En gros tu as juste alloué de la memoire, qui est perdue immédiatement. Forcément ca va être plus lent ;)

ca va etre chaud de le faire marcher correctement, a cause des doublons, avec des (cons de) char*.
Au ieu de ca j'avoue que des std::string t'eviteront sans doute des maux de tete.
Oui ou simplement des char *
14/02/2011, 19h41
nphilippe1684

Si en fait, ça fonctionne beaucoup mieux :ccool:. Ça ne changeait pas grand chose car vu que ça n'écrase pas les anciennes valeurs, bah ça prend plus d'espace et du coup maintenant ça swap. Mais sur un exemple qui ne swap pas, j'ai des temps de construction logique.

Finalement, j'ai les résultats attendus (plus logiques), c'est à dire quelque chose qui se construit vite mais qui est très gourmand en mémoire ;)
La prochaine fois, je ferais un peu plus gaffe au retour des fonctions std::String :D. Cependant, je ne comprends toujours pas comment je pouvais avoir des résultats corrects :calim2:?
Et puis, c'était quand même un miracle que ça passait. En effet, si je ne me trompe pas, au final j'écrasais des pointeurs de type const char * à chaque tour de boucle ? :/
15/02/2011, 10h32
r0d

Citation:

Envoyé par nphilippe1684

Au cas où, voila ma ligne de compilation :
g++ -Wall -Wextra -ansi -g -O2 -funroll-loops buildSTLHash.cpp -o buildSTLHash

Je connais assez mal gcc, mais je pense qu'il est possible d'améliorer cela:
:arrow: -g c'est pour avoir les informations de debug. Pour optimiser, il faut donc l'enlever.
:arrow: sans doute qu'utiliser -O3 au lieu de -O2 sera également plus efficace

Il faudrait également vérifier que vous utilisez une version récente de gcc (en effet, le -funroll-loops qui n'est pas documenté dans les dernières versions me porte à croire que vous en utilisez une ancienne).
15/02/2011, 10h52
screetch

a noter que les infos de debug ne veulent pas dire un code plus lent. Ca veut juste dire qu'on ajoute de quoi retrouver l'emplacement dans le code source a partir du code binaire

@philippe: une grosse optimisation consiste a appeler un allocateur de mémoire le moins souvent possible.

Ici il y a beaucoup d'allocations inutiles et beaucoup de "leaks" mémoire
Pour contrer cela, au lieu d'utiliser std::string ou encore pire, un pointeur char, tu peux créer ta propre classe comme suit:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 class StringPrefix { char m_prefix[kmer+1]; // +1 pour le 0 terminal public: StringPrefix(const char *string) { strncpy(m_prefix, string, kmer); } const char *c_str() const { return m_prefix; } };
et utiliser ca comme clé :

Code:

hash_map<StringPrefix, int, HashStringPrefix, EqStringPrefix > hash_kmer;

Ca veut dire que au lieu d'allouer les chaînes sur le tas, tu vas les copier partout ou tu en as besoin et elles seront automatiquement désallouées.

Il faudra redéfinir un hash cependant, voila comment:
Code:

1 2 3 4 5 6 7 8 struct HashStringPrefix : public hash<const char *> { public: size_t operator()(const HashStringPrefix& s1, const HashStringPrefix& s2) { return operator()(s1.c_str(), s2.c_str()); } };
je suis curieux de voir les nouvelles perfs

Citation:
Envoyé par screetch
@philippe: une grosse optimisation consiste a appeler un allocateur de mémoire le moins souvent possible.

Ici il y a beaucoup d'allocations inutiles et beaucoup de "leaks" mémoire
Pour contrer cela, au lieu d'utiliser std::string ou encore pire, un pointeur char, tu peux créer ta propre classe comme suit:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 class StringPrefix { char m_prefix[kmer+1]; // +1 pour le 0 terminal public: StringPrefix(const char *string) { strncpy(m_prefix, string, kmer); } const char *c_str() const { return m_prefix; } };
À la base, je voulais faire un test rapide, mais finalement je l'ai codé proprement (j'espère). Néanmoins, ce que je veux c pas des préfixes mais des facteurs donc j'ai fait une classe StringFactor :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include "StringFactor.h" StringFactor::StringFactor(const char *string, uint pos, uint kmer_length) { m_factor = new char[kmer_length+1]; // +1 pour le 0 terminal strncpy(m_factor, string.substr(pos,kmer_length),kmer_length); } ~StringFactor()::StringFactor(){ delete [] m_factor; } char *c_str() const { return m_factor; }
Citation:

et utiliser ca comme clé :

Code:

hash_map<StringPrefix, int, HashStringPrefix, EqStringPrefix > hash_kmer;

Ca veut dire que au lieu d'allouer les chaînes sur le tas, tu vas les copier partout ou tu en as besoin et elles seront automatiquement désallouées.

ok On est d'accord là dessus
Citation:
Il faudra redéfinir un hash cependant, voila comment:
Code:

1 2 3 4 5 6 7 8 struct HashStringPrefix : public hash<const char *> { public: size_t operator()(const HashStringPrefix& s1, const HashStringPrefix& s2) { return operator()(s1.c_str(), s2.c_str()); } };
Bon par contre là j'ai pas tout compris, donc j'ai essayé de faire à ma sauce :

Pour l'héritage, après j'ai pas surchargé à ta façon "operator()" mais j'ai redéfini à coté le EqStringFactor (c'est peut-être pour ça que ça compile pas) :
Code:

1 2 3 4 5 6 7 8 struct HashStringFactor : public hash<const char *>{}; struct EqStringFactor{ bool operator()(const StringFactor &s1, const StringFactor &s2) const { return strcmp(s1.c_str(),s2.c_str())==0; } };
Pour l'initialisation :
Code:

1 2 hash_map<StringFactor, int, HashStringFactor, EqStringFactor > hash_kmer;
Et enfin, pour le corps du programe :
Code:

1 2 3 4 5 6 reads.getline(line, read_length+1); for (ullong i = 0 ; i < (read_length-threshold) ; i++){ StringFactor factor = StringFactor(line,i,threshold); hash_kmer[factor] ++ ; }
Après je ne suis pas étonné que ça me renvoie cette erreur à la compilation :
Code:

1 2 3 4 buildSGIHash.cpp:83: erreur: no match for ‘operator[]’ in ‘hash_kmer[factor]’ /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/ext/hash_map:232: note: candidats sont: _Tp& __gnu_cxx::hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc>::operator[](const typename __gnu_cxx::hashtable<std::pair<const _Key, _Tp>, _Key, _HashFcn, std::_Select1st<std::pair<const _Key, _Tp> >, _EqualKey, _Alloc>::key_type&) [with _Key = StringFactor, _Tp = int, _HashFcn = HashStringFactor, _EqualKey = EqStringFactor, _Alloc = std::allocator<int>] make: *** [buildSGIHash.o] Erreur 1
Du coup, je serais tenté de mettre un hash_kmer[factor.c_str] à la place de mon hash_kmer[factor], mais je ne vois plus vraiment l'intérêt. Donc, avant de faire trop de bêtises (déjà que j'ai changé pas mal ton code), je vais attendre de me faire calmer par un expert :D

PS : Je peux envoyer tout le code, si jamais ça peut aider...

dans ton code:
Code:

1 2 3 4 5 6 7 8 StringFactor::StringFactor(const char *string, uint pos, uint kmer_length) { m_factor = new char[kmer_length+1]; // +1 pour le 0 terminal strncpy(m_factor, string.substr(pos,kmer_length),kmer_length); } ~StringFactor()::StringFactor(){ delete [] m_factor; }
m_factor a une taille fixe (kmer_length + 1) et kmer est petit (25?).
Du coup allouer avec new ca a peu d'interet. Il vaut mieux le mettre comme un tableau (char m_factor[kmer_length])

ensuite, substr() crée une allocation aussi, c'est ce que j'essayais d'éviter.

Code:

strncpy(m_factor, string.substr(pos,kmer_length),kmer_length);

Code:

strncpy(m_factor, string.c_str() + pos, kmer_length);

est bien plus efficace car il ne crée pas un string temporaire, donc évite une allocation

Pour le hash, c'est parce que le hashmap attend un hash sur StringFactor. Or toi tu lui donnes un hash capable de hasher les char*, ce n'est pas le même type. C'est pour ca que j'ai ajouté un operator() qui sait comment hasher les StringFactor (note qu'en fait il ne sait pas hasher, mais il sait demander au hash<const char *> de faire le boulot)

pour ton erreur, c'est la seule que tu as? car je vois que non seulement ton hash ne marcherait pas normalement, mais en plus que

Code:

strncpy(m_factor, string.substr(pos,kmer_length),kmer_length);

n'est pas censé compiler.

a priori je vois pas; reposter le code aiderait

Je te mets le code avec tes modifs :

-----> type.h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#ifndef TYPES_H
#define TYPES_H
 
#ifndef ullong
#define ullong unsigned long long
#endif
 
#ifndef uint
#define uint unsigned int
#endif
 
#endif

-----> StringFactor.h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#ifndef STRING_FACTOR_H
#define STRING_FACTOR_H
#include "type.h"
#include <string>
 
using namespace std;
 
class StringFactor {
private:
  char *m_factor; 
public:
  StringFactor(const char *string, uint pos, uint kmer_length);
 
  ~StringFactor();
 
  char *c_str() const;
 
};
#endif

------> StringFactor.cpp

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include "StringFactor.h"
 
StringFactor::StringFactor(const char *string, uint pos, uint kmer_length) {
  char m_factor[kmer_length+1]; // +1 pour le 0 terminal
  strncpy(m_factor, string.c_str()+pos,kmer_length);
}
 
~StringFactor()::StringFactor(){
  // delete [] m_factor;
}
 
char *c_str() const {
  return m_factor;
}

------> buildSGIHash.cpp

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
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
77
78
79
80
81
82
83
84
85
 
#include <iostream>
#include <fstream>
#include <string>
#include <sys/time.h>
#include <ext/hash_map>
#include "type.h"
#include "StringFactor.h"
extern "C" {
#include <time.h>
}
 
using namespace std;
namespace std { using namespace __gnu_cxx; }
 
ullong getChrono() {
  struct timeval time;
  time_t sec;
  suseconds_t usec;
 
  if (gettimeofday(&time,NULL) != -1) {
    sec = time.tv_sec;
    usec = time.tv_usec;
    return (ullong)sec*1000000+usec;
  }
  return 0;
}
 
 
struct HashStringFactor : public hash<const char *>{
 
};
 
struct EqStringFactor{
  bool operator()(const StringFactor &s1, const StringFactor &s2) const {
    return strcmp(s1.c_str(),s2.c_str())==0;
  }
};
 
 
int main(int argc, char **argv)
{
  if (argc < 4){
    cerr << "Usage: " << argv[0] <<" read_file read_length threshold" << endl; 
    exit(1);
  }
  ullong start = getChrono();
 
  ifstream reads;
  reads.open(argv[1], ios::in);
  if (! reads.is_open()) {
    cerr << "Cannot open reads file: " << argv[1] << endl;
    exit(2);
  }
  reads.seekg (0, ios::end);
  ullong length = reads.tellg();
  uint read_length = atoi(argv[2]);
  char *line = new char[read_length+1];
  reads.seekg (0, ios::beg);
  ullong nb_reads = length/(read_length+1);
  uint threshold= atoi(argv[3]);
 
  //ullong nb_elements = (read_length-threshold)*nb_reads;
  hash_map<StringFactor, int, HashStringFactor, EqStringFactor > hash_kmer;
 
  ullong current = 0;
  //  cout << "nb_reads: " << nb_reads << endl; 
  //cout << sizeof(ullong) << endl;
  ullong state = 1;
  while (current < nb_reads) {
    if (current >= state*10000){
      cout << current << " reads is included in stl_hash in " << (getChrono()-start)/1000000. << " s" << endl;
      state++;
    }
    reads.getline(line, read_length+1);
    for (ullong i = 0 ; i < (read_length-threshold) ; i++){
      StringFactor factor = StringFactor(line,i,threshold);
      hash_kmer[factor] ++ ;
    }
    current++;
  }  
  cout << "nb_factors indexed in hash_kmer: " << hash_kmer.size() << endl;
  cerr << "Creation of stl_hash_map: " << (getChrono()-start)/1000000. << " s" << endl;
  return 0;
}

----> Makefile

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
CPP=g++
DBG=# -O0 
CPPFLAGS=-Wall -g $(DBG) -funroll-loops -O2
CFLAGS=-Wall -ansi
OBJ=StringFactor.o buildSGIHash.o
EXE=buildSGIHash
all: $(EXE)
 
buildSGIHash : % : %.o $(OBJ)
        $(CPP) -o $@ $^ 
 
%.o : %.cpp
        $(CPP) $(CPPFLAGS) -c $^
 
%.cpp : %.h
 
%.c : %.h
 
clean: 
        rm -f *.o

Je ne pense pas que ce soit la seule erreur, il en n'indique qu'une mais à mon avis une fois que celle-là sera corrigée, il y aura d'autres surprises.

En tout cas merci beaucoup pour ton soucis d'avoir une implémentation efficace ! ;)

ah oui j'avais dit des betises avec mon hash, je reposte le code corrigé:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#ifndef STRING_FACTOR_H
#define STRING_FACTOR_H
#include "type.h"
#include <string>
 
using namespace std;
 
class StringFactor {
private:
  static const int max_kmer = 30;
  char m_factor[max_kmer];
public:
  StringFactor(const char *string, uint pos, uint kmer_length);
 
  ~StringFactor();
 
  const char *c_str() const;
 
};
#endif

je croyais que ton kmer etait statique donc connu a la compilation. C'est beaucoup plus facile dans ce cas puisque si tu connais la taille tu peux prévoir assez d'espace sans recourir a une allocation dynamique.
Mais comme c'était pas possible, j'ai ajouté une constante max_kmer qui me permet de réserver suffisemment d'espace (peut etre trop mais pas beaucoup)

le CPP:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include "StringFactor.h"
#include <cassert>
#include <cstring>
 
StringFactor::StringFactor(const char *string, uint pos, uint kmer_length) {
  assert(kmer_length < max_kmer);
  strncpy(m_factor, string+pos,kmer_length);
}
 
StringFactor::~StringFactor(){
}
 
const char *StringFactor::c_str() const {
  return m_factor;
}

j'ai juste corrigé quelques erreurs qui seraient apparues si tu avais pu lancer la compilation, pas de gros changement

le principal C++:

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
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
77
78
79
80
81
82
#include <sys/time.h>
#include <ext/hash_map>
#include "type.h"
#include "StringFactor.h"
#include <cstring>
extern "C" {
#include <time.h>
}
 
using namespace std;
namespace std { using namespace __gnu_cxx; }
 
ullong getChrono() {
  struct timeval time;
  time_t sec;
  long usec;
 
  if (gettimeofday(&time,NULL) != -1) {
    sec = time.tv_sec;
    usec = time.tv_usec;
    return (ullong)sec*1000000+usec;
  }
  return 0;
}
 
 
struct HashStringFactor : public hash<const char *>{
 size_t operator()(const StringFactor& s) const { return  hash<const char *>::operator()(s.c_str()); }
};
 
struct EqStringFactor{
  bool operator()(const StringFactor &s1, const StringFactor &s2) const {
    return strcmp(s1.c_str(),s2.c_str())==0;
  }
};
 
 
int main(int argc, char **argv)
{
  if (argc < 4){
    cerr << "Usage: " << argv[0] <<" read_file read_length threshold" << endl; 
    exit(1);
  }
  ullong start = getChrono();
 
  ifstream reads;
  reads.open(argv[1], ios::in);
  if (! reads.is_open()) {
    cerr << "Cannot open reads file: " << argv[1] << endl;
    exit(2);
  }
  reads.seekg (0, ios::end);
  ullong length = reads.tellg();
  uint read_length = atoi(argv[2]);
  char *line = new char[read_length+1];
  reads.seekg (0, ios::beg);
  ullong nb_reads = length/(read_length+1);
  uint threshold= atoi(argv[3]);
 
  //ullong nb_elements = (read_length-threshold)*nb_reads;
  hash_map<StringFactor, int, HashStringFactor, EqStringFactor > hash_kmer;
 
  ullong current = 0;
  //  cout << "nb_reads: " << nb_reads << endl; 
  //cout << sizeof(ullong) << endl;
  ullong state = 1;
  while (current < nb_reads) {
    if (current >= state*10000){
      cout << current << " reads is included in stl_hash in " << (getChrono()-start)/1000000. << " s" << endl;
      state++;
    }
    reads.getline(line, read_length+1);
    for (ullong i = 0 ; i < (read_length-threshold) ; i++){
      StringFactor factor = StringFactor(line,i,threshold);
      hash_kmer[factor] ++ ;
    }
    current++;
  }  
  cout << "nb_factors indexed in hash_kmer: " << hash_kmer.size() << endl;
  cerr << "Creation of stl_hash_map: " << (getChrono()-start)/1000000. << " s" << endl;
  return 0;
}

le seul gros changement c'est le hash. Comme je l'avais dit plus haut, tu as besoin d'une fonction de hash sur un StringFactor, donc une structure du type

Code:

1
2
3
4
struct hash
{
  size_t operator()(const StringFactor& factor) {... }
};

or tu sais déja comment avoir un hash de string, donc on peut le réutiliser et l'adapter, c'est pour ca qu'on hérite de hash<const char *>: pour mettre a disposition dans le hash la fonction de hash des string:

Code:

1
2
3
struct HashStringFactor : public hash<const char *>{
 size_t operator()(const StringFactor& s) const { return  hash<const char *>::operator()(s.c_str()); }
};

donc maintenant on peut hasher des Stringfactor :)
je n'ai pas lancé le programme mais je suis curieux du résultat si tu as moins d'allocations mémoire :)

16/02/2011, 16h06
nphilippe1684

Un grand merci à screetch pour avoir résolu mon problème !