Discussion :

[tabouret]

Bonjour,

Voila étant en dernière année de master informatique, on nous demande de coder des algorythmes de découverte de réseaux.

On se sert donc d'un fichier de la forme :
0 1
0 2
1 2
...

Où chaque lignes représente un lien et chaque numéro représente un noeud du réseau.

Les algos marchent bien pas de souci pour ça le seul souci c'est la rapidité : pour un réseau de 117 millions de liens (donc un fichier avec 117 millions de lignes), l'algo ci-dessous met 5 minutes et 20 secondes rien qu'à rentrer le fichier en mémoire RAM, la où mon prof met lui 26 secondes.

J'ai un i5 avec 6 GO de RAM, un SSD et les 4 coeurs montent tous à 50% de charge quand l'algo ci-dessous tourne.La lecture disque semblerait se faire à 2 Mio/s.

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
 
void printSize(char* input){
	FILE* f;
	char c;
	unsigned long n1,n2,nbVertices=0,nbEdges=0;
 
	if((f = fopen(input,"r"))==NULL){
        	perror("File not found");
       	 exit(1);
    	}
 
	while((c=fgetc(f))!=EOF){			//case where first two lines begin with %
		if(c=='%')
			while((c=fgetc(f))!='\n');
		else
			break;
	}
	fseek(f,-1,SEEK_CUR);				//one char has been read, got to go back
 
	while(fscanf(f,"%ld %ld",&n1,&n2)!=EOF){
		nbVertices = max(nbVertices,n1,n2);
		nbEdges++;
	}
 
	nbVertices++;					//adding vertice 0
 
	printf("\n%ld vertices %ld edges",nbVertices, nbEdges);
}

Voila ma question est donc :

Remplacer fopen() par open() va-t il améliorer la rapidité ?

Ou sinon si vous avez d'autres idées pour améliorer la rapidité de mise en mémoire principale...

D'autres fonctions que open?()
Création de threads ou processus pour essayer d'aller plus vite?
gcc -09 change t-il quelque chose à la done?
...

Merci beaucoup

[tabouret]

Problème résolu.

-O9 dans gcc et je met 20 secondes à lire le fichier de 117 millions de lignes.

L'emploi de printf() semble vraiment très gourmand si j'en met un, je passe à plus d'une minute.

Merci.

[Matt_Houston]

Tu peux probablement aller encore plus vite en :

• chargeant tout le fichier en mémoire système (lecture d'une traite dans un gros buffer, sans analyse) ;
• réalisant l'analyse de chaîne depuis la mémoire.

Et si tu veux vraiment être à la pointe, tu confies l'opération d'entrée / sortie à libuv et tu réalises l'analyse dans la callback.

Pour répondre à ta question initiale, il ne faut attendre aucune différence de performance entre fopen et open : la seconde est probablement wrappée par la première.

L'emploi de printf() semble vraiment très gourmand si j'en met un, je passe à plus d'une minute.

Oui, ça c'est sûr.. particulièrement si un flush a lieu (dû à la présence d'un '\n' dans la chaîne à imprimer).

[Sve@r]

Remplacer fopen() par open() va-t il améliorer la rapidité ?

Bonjour
Pas pour des lectures de lignes. J'ai réussi à aller plus vite avec open() mais je lisais des fichiers binaires et je jouais sur la quantité lue dans read.

Ou sinon si vous avez d'autres idées pour améliorer la rapidité de mise en mémoire principale...

Remplacer tes fgetc() par des fgets() (puisque tu dis lire des "lignes" c'est le plus approprié). Et bien entendu éliminer tes fseek() inutiles et tes printf()...

[dalfab]

Bonjour,

La différence entre open() et fopen() est que le second est bufferisé. C'est pourquoi on utilise systématiquement open() pour accéder à un driver qui n'est pas un block-driver. Si on lit des blocs plus grands que la taille du buffer, les fread() de fopen() seront plus lents (car tout transite par le buffer). Si inversement on lit des données de petite taille, le système de cache de fopen() optimisera se seront les read() de open() qui seront plus lents.
Le buffer de fopen() fait normalement 4K donc :
* des blocs de moins de 1K sont normalement plus rapides avec fopen()
* des blocs de plus de 4K sont plus rapides avec open() (si très grands on peut avoir un gain du simple au double)
* des blocs de 1K à 4K, les deux sont équivalents.

[Médinoc]

Si tu lis byte par byte comme dans le code actuel, alors il n'y a pas photo, fopen() + [f]getc() sera beaucoup plus rapide que open() + read(1).
Mais si tu optimises plus la lecture, y compris — si le fichier est garanti tenir en mémoire — obtenir la taille du fichier puis le lire d'un bloc*... faut voir. S'il y a des copies de buffer lors de l'appel unique à fread() il y aura un overhead tangible par rapport à un read() nu, sinon il sera négligeable.

*ce qui nécessite de l'ouvrir en mode binaire, pour être conforme à la norme