[C] Chiarimento sui Threads

[Balop]

Ciao a tutti, per ora sto imparando ad usare i threads in C, però vorrei un chiarimento a livello teorico da qualcuno che li sa usare:
da quanto ha detto il prof, ho capito che si usano i threads perchè dovrebbero essere meno dispendiosi a livello di risorse perchè sono parti dello stesso processo e inoltre dovebbero lavorare contemporaneamente giusto?
Solo che io ho fatto un programmino per il calcolo dei numeri primi e fra l'uso dei threads e delle normali funzioni non c'è differenza a livello di tempo, dipende dal fatto che ho usato i join (altrimenti non funzionava) giusto?
Io volevo fare in modo che i 4 threads che ho creato mi cercassero contemporaneamente i numeri primi in modo da ridurre ad 1/4 il tempo di ricerca che si avrebbe richiamando 4 volte la funzione ricerca... ma si vede che non ho saputo usarli bene... per questo prima di scervellarmi chiedo se la teoria dei threads è quella che ho capito o no... ed eventualmente se qualcuno mi può anche illuminare su come modificare il programma che ho fatto (poi lo posto) come avevo in mente di farlo io..

Grazie

[tuccio`]

se hai un processore con più core (fisici o logici, cosa molto probabile nel 2011 ) 2 thread possono essere seguiti in maniera parallela, ovviamente tocca al sistema operativo schedularli su processori diversi (se hai più thread che core ovviamente vanno solo a dividersi i core), ovviamente sta a te dividere un compito in modo tale che i thread possano lavorare in maniera abbastanza indipendente da essere efficienti

comunque l'altro vantaggio dei thread rispetto ai processi è che condividono la memoria, che non è cosa da poco

[Balop]

allora facendo un programma come questo:

//------ con i threads
pthread_t thread1;
pthread_t thread2;
pthread_t thread3;
pthread_t thread4;

pthread_create (&thread1,NULL,&trovaprimo,&num1);
pthread_create (&thread2,NULL,&trovaprimo,&num2);
pthread_create (&thread3,NULL,&trovaprimo,&num3);
pthread_create (&thread4,NULL,&trovaprimo,&num4);

pthread_join (thread1, (void *) &primo1);
pthread_join (thread2, (void *) &primo2);
pthread_join (thread3, (void *) &primo3);
pthread_join (thread4, (void *) &primo4);

//------ con le funzioni
int candidate1= (int)trovaprimo(&num1);
int candidate2= (int)trovaprimo(&num2);
int candidate3= (int)trovaprimo(&num3);
int candidate4= (int)trovaprimo(&num4);

con i threads non dovrebbe trovare più velocemente gli n-esimi numeri primi richiesti rispetto all'ultima parte dove si richiama 4 volte la stessa funzione??

[tuccio`]

cosa fa trovaprimo?

[Balop]

Originariamente inviato da tuccio`

cosa fa trovaprimo?

trova l'n-esimo numero primo.
per esempio se come argomento passo 4 mi trova 5, se passo 5 mi trova 7 ecc.. se passo 15000 mi trova il 25000° numero primo, quindi ci sta un po..
per vedere giusta la differenza ieri ho fatto la prova a cercare il 150000°, 149500°, 149000°, 148500°,
entrambi i metodi ci sono stati circa 20 minuti per la ricerca, ma con i threads addirittura c'è stato più che con le funzioni!!
quando invece in teoria ci dovrebbe impiegare il tempo che ci sta per trovare quello maggiore (perchè gli altri threads dovrebbero finire prima..), invece con le funzioni ogni volta deve cominciare da capo..

ti posto l'intero programma dove c'è anche la funzione time per calcolare i tempi ed ho messo anche una printf in modo da fare stampare subito quando trova i numeri..

#include <pthread.h>
#include <stdio.h>
#include <time.h>


void *trovaprimo (void *num){
int n = *((int *)num);
int i;
int candidate=1;

while(1){
int var=1;
for (i=2; i<=(candidate/2); i++){
	if(candidate%i == 0) {
		var=0;
		break;
		}
	}
	if (var){
	n--;
	if(n==0){
	printf("Il %d° numero primo è %d\n", *((int *)num), candidate);
	return (int *)candidate;
	}
	}
candidate++;
}//fine while
}

int main (){
time_t tempo1, tempo2, tempo3, tempo4;
int tempotrascorso1;
int tempotrascorso2;


int num1, num2, num3, num4, primo1, primo2, primo3, primo4;
printf("inserire n-esimo numero prima che si cerca: ");
scanf("%d", &num1);
printf("\ninserire n-esimo numero prima che si cerca: ");
scanf("%d", &num2);
printf("\ninserire n-esimo numero prima che si cerca: ");
scanf("%d", &num3);
printf("\ninserire n-esimo numero prima che si cerca: ");
scanf("%d", &num4);


pthread_t thread1;
pthread_t thread2;
pthread_t thread3;
pthread_t thread4;

pthread_create (&thread1,NULL,&trovaprimo,&num1);
pthread_create (&thread2,NULL,&trovaprimo,&num2);
pthread_create (&thread3,NULL,&trovaprimo,&num3);
pthread_create (&thread4,NULL,&trovaprimo,&num4);

tempo1= time(NULL);
pthread_join (thread1, (void *) &primo1);
pthread_join (thread2, (void *) &primo2);
pthread_join (thread3, (void *) &primo3);
pthread_join (thread4, (void *) &primo4);
tempo2= time(NULL);

printf("\nCon i threads:\n");
printf("Il %d° numero primo è %d\n", num1, primo1);
printf("Il %d° numero primo è %d\n", num2, primo2);
printf("Il %d° numero primo è %d\n", num3, primo3);
printf("Il %d° numero primo è %d\n", num4, primo4);

tempotrascorso1 = difftime(tempo2, tempo1);
printf("Sono trascorsi %d secondi!\n\n", tempotrascorso1);

tempo3= time(NULL);
int candidate1= (int)trovaprimo(&num1);
int candidate2= (int)trovaprimo(&num2);
int candidate3= (int)trovaprimo(&num3);
int candidate4= (int)trovaprimo(&num4);
tempo4= time(NULL);

tempotrascorso2 = difftime(tempo4, tempo3);
printf("\nCon le funzioni:\n");
printf("Il %d° numero primo è %d\n", num1, candidate1);
printf("Il %d° numero primo è %d\n", num2, candidate2);
printf("Il %d° numero primo è %d\n", num3, candidate3);
printf("Il %d° numero primo è %d\n", num4, candidate4);
printf("Sono trascorsi %d secondi!\n\n", tempotrascorso2);

return 0;
}

[WarDuck]

Non tutti gli algoritmi sono parallelizzabili.

In particolare il tuo trova-primo non sfrutta in alcun modo le informazioni generate in precedenza, ogni volta ricomincia da 2 per testare se l'i-esimo numero è primo.

Praticamente esegui 4 volte la funzione per numeri diversi, e non sfrutti nessuna delle informazioni generate prima.

Comunque indenta meglio il codice perché così è illeggibile.

Prima di provare con i thread ti suggerisco di ottimizzare il codice attuale.

[Balop]

Originariamente inviato da WarDuck

Non tutti gli algoritmi sono parallelizzabili.

In particolare il tuo trova-primo non sfrutta in alcun modo le informazioni generate in precedenza, ogni volta ricomincia da 2 per testare se l'i-esimo numero è primo.

Praticamente esegui 4 volte la funzione per numeri diversi, e non sfrutti nessuna delle informazioni generate prima.

Comunque indenta meglio il codice perché così è illeggibile.

Prima di provare con i thread ti suggerisco di ottimizzare il codice attuale.

quindi per usare i threads al meglio si deve cercare di sfruttarli fra di loro.. allora non è come pensavo che lavorassero contemporaneamente...

per quanto riguarda l'indentatura è scritto così perchè uso linux con i semplici file di testo e li scrive senza aggiungere spaziatura automatica.. ero abituato male con eclipse che usavo per il java...

inoltre qualcuno ha qualche suggerimento su come si potrebbero sfruttare i threads in questo esempio?

[tuccio`]

lavorano contemporaneamente, dipende dallo scheduler, onestamente lì è strano che tu non abbia proprio vantaggi, certo non è ottimizzato benissimo, ma comunque già se 2 di quei 4 venissero eseguiti contemporaneamente dovresti avere un vantaggio

comunque... 5 sarebbe il quarto numero primo?

[Balop]

Originariamente inviato da tuccio`

lavorano contemporaneamente, dipende dallo scheduler, onestamente lì è strano che tu non abbia proprio vantaggi, certo non è ottimizzato benissimo, ma comunque già se 2 di quei 4 venissero eseguiti contemporaneamente dovresti avere un vantaggio

comunque... 5 sarebbe il quarto numero primo?

se i numeri primi sono 1 2 3 5 7 11 13 17 19... il 4° numero primo è 5.....
ovviamente ho tenuto conto anche del numero 1 come primo...

comunque bo... non riesco a capire com'è che non abbia vantaggi.....

[tuccio`]

Originariamente inviato da Balop

se i numeri primi sono 1 2 3 5 7 11 13 17 19... il 4° numero primo è 5.....

ex falso sequitur quodlibet ^_^

[Balop]

Originariamente inviato da tuccio`

ex falso sequitur quodlibet ^_^

infatti ho specificato sotto che ho tenuto conto del numero 1 come primo... anche se fooorse... ma vabbè... la cosa importante era un'altra!! =)

[WarDuck]

Originariamente inviato da Balop

quindi per usare i threads al meglio si deve cercare di sfruttarli fra di loro.. allora non è come pensavo che lavorassero contemporaneamente...

per quanto riguarda l'indentatura è scritto così perchè uso linux con i semplici file di testo e li scrive senza aggiungere spaziatura automatica.. ero abituato male con eclipse che usavo per il java...

inoltre qualcuno ha qualche suggerimento su come si potrebbero sfruttare i threads in questo esempio?

Originariamente inviato da Balop

se i numeri primi sono 1 2 3 5 7 11 13 17 19... il 4° numero primo è 5.....
ovviamente ho tenuto conto anche del numero 1 come primo...

comunque bo... non riesco a capire com'è che non abbia vantaggi.....

NOTA: 1 non è un numero primo.

I thread sono semplici esecutori a cui va detto esplicitamente quello che devono fare e comunque la loro utilità dipende dal contesto.

Ad esempio avresti più facilità a vedere i vantaggi del multi-threading nell'ordinamento merge-sort, piuttosto che in questo caso.

Non hai vantaggi perché sostanzialmente il tuo algoritmo non sfrutta il parallelismo, poi ho visto ora che hai messo JOIN, che in sostanza serve per aspettare che gli altri thread finiscano (praticamente lavori sequenzialmente con in più tutto l'overhead dei thread).

Al di là dei thread, se vuoi migliorare le prestazioni del tuo algoritmo dovresti prima di tutto cercare di sfruttare le informazioni che hai.

Se sai che 7 è il 4° numero primo è perché prima hai calcolato gli altri. Dunque ti conviene crearti una tabella (un array ad esempio) di quelli già calcolati.

Per esempio avresti che:

index  1  2  3  4  5
value  2  3  5  7  11

Dunque sia X l'indice che vuoi cercare:

• se X < lunghezza array: ritorna l'elemento array[X]
• se X > lunghezza array: calcola a partire dall'ultimo elemento dell'array

La tua funzione invece riparte sempre da 0 nel calcolare l'i-esimo primo, dunque ti ricalcoli quelli che hai già calcolato.

[Balop]

Originariamente inviato da WarDuck

NOTA: 1 non è un numero primo.

I thread sono semplici esecutori a cui va detto esplicitamente quello che devono fare e comunque la loro utilità dipende dal contesto.

Ad esempio avresti più facilità a vedere i vantaggi del multi-threading nell'ordinamento merge-sort, piuttosto che in questo caso.

Non hai vantaggi perché sostanzialmente il tuo algoritmo non sfrutta il parallelismo, poi ho visto ora che hai messo JOIN, che in sostanza serve per aspettare che gli altri thread finiscano (praticamente lavori sequenzialmente con in più tutto l'overhead dei thread).

Al di là dei thread, se vuoi migliorare le prestazioni del tuo algoritmo dovresti prima di tutto cercare di sfruttare le informazioni che hai.

Se sai che 7 è il 4° numero primo è perché prima hai calcolato gli altri. Dunque ti conviene crearti una tabella (un array ad esempio) di quelli già calcolati.

Per esempio avresti che:

index  1  2  3  4  5
value  2  3  5  7  11

Dunque sia X l'indice che vuoi cercare:

• se X < lunghezza array: ritorna l'elemento array[X]
• se X > lunghezza array: calcola a partire dall'ultimo elemento dell'array

La tua funzione invece riparte sempre da 0 nel calcolare l'i-esimo primo, dunque ti ricalcoli quelli che hai già calcolato.

Intanto grazie per la proposta, ma oltre all'algoritmo che può essere più o meno efficiente (il tuo è palesemente migliore), sto imparando ad usare i threads e a che c'ero volevo vederne l'utilità pratica con questo algoritmo parzialmente modificato da un esempio preso dal libro..

per quanto riguarda i JOIN, li ho dovuti aggiungere perchè altrimenti non sapevo come fare ritornare i valori trovati nel main (ovviamente senza utilizzare quella printf dentro la funzione trovaprimo che era solo per vedere quando trovava i numeri..).
sai come potrei fare ritornare il valore trovato dai threads dentro il main?

[*andre*]

se vuoi trovare i numeri primi fino ad un certo numero, prova ad implementare questo algoritmo http://it.wikipedia.org/wiki/Crivello_di_Eratostene.

Lo puoi dividere efficentemente in vari threads.
I vantaggi o svantaggi dell'utilizzo dei thread conviene che li testi con un numero molto grande di operazioni, se no oltre a non notare vantaggi a volte noti pure un decadimento delle prestazioni.

[tuccio`]

la join fa aspettare il main thread che la chiama aspettando che finiscano i 4, non gli altri.. quindi non è che abbia una spiegazione diversa da "lo scheduler del tuo os fa schifo " magari ha creato troppi thread rispetto ai core che può usare l'os? anche se usi 2 (e non 4) thread è meglio con il flusso singolo che con i thread?

ps: se la cpu che stai usando è l'e8400 (leggo la firma) è probabile che vada meglio con 2 thread anziché 4, certamente 4 thread non potranno andare in parallelo.. se ci metti che comunque l'uso di thread comporta uno overhead dovuto allo scheduling, se non lo ammortizzi eseguendo davvero parallelamente, non hai nessun vantaggio

[Balop]

no ragazzi studio con il portatile e il processore è un i5 450m.
comunque ci avevo pensato anche io che fosse colpa del join (ragà ve l'ho scritto pure nel primo post ma nessuno ci ha fatto caso!! xD)
ma come ho scritto poco sopra, senza usarlo non saprei come fare tornare il valore trovato dentro il main, qualcuno sa come fare?
di pome lo rivedo un po.... vedo di provare con una variabile globale in modo da eliminare i join...

[tuccio`]

non capisco quale sarebbe il problema nel join

[Balop]

Originariamente inviato da tuccio`

non capisco quale sarebbe il problema nel join

i join hanno la funzione di aspettare la fine del thread passato come argomento...
però ora che ci penso, aspetta il thread passato come argomento prima di deallocare le risorse, non prima di essere eseguito...
infatti con la printf messa nella funzione trovaprimo vedo che se passo per esempio 25, 10, 16, 5
mi trova prima il 5° poi il 10° poi il 16° e poi il 25°, quindi i threads funzionano,
invece con le funzioni mi trova i numeri per come glieli passo io, quindi prima il 25° poi il 10° ecc...

[WarDuck]

Ribadisco il concetto: il tuo problema è l'algoritmo che così com'è mi sembra poco parallelizzabile, join o non join, parametri passati o meno tra thread...

[Rsk]

Come ti hanno già suggerito, implementa il crivello di eratostene.
E' facilmente parallelizzabile.
Se hai n core e vuoi utilizzare n thread, puoi suddividere lo spazio dei numeri in n partizioni e assegnare ad ogni thread un set di S/n elementi su cui lavorare, dove S è il limite superiore del tuo insieme.