View Full Version : [C#] - Prove di parallelismo
Un pelino di storia, giusto per inquadrare i ragionamenti che recentemente si stanno sentendo nel nostro ambiente.
A chi non piace la storia puo' saltare l'intro...
Praticamente tutti, anche i non addetti ai lavori, conoscono la famosa legge di Moore, legge empirica secondo la quale le prestazioni dei microprocessori vengono raddoppiate ogni 18 mesi.
Il trend non si e' ancora fermato, ha dato un solo accenno alla diminuzione recentemente.
Ma mentre una volta per aumentare le prestazioni di un microprocessore era sufficiente riuscire a trovare una sorgente piu' pura di silicio, ed alzare la frequenza del clock, oggi si e' raggiunto quello che e' il limite commerciale ragionevole dei transistor al silicio, che non sembra essere piu' conveniente sopra i 4GHz. Sono gia' parecchi anni infatti che nuotiamo attorno a queste frequenze.
Aumentare semplicemente la frequenza di clock ha l'indubbio vantaggio che tutto il sistema si muove in modo quasi direttamente proporzionale, senza alcun bisogno di cambiare essenzialmente i programmi.
Le prestazioni sono pero' continuate ad aumentare, anche grazie alla semplificazione degli algoritmi hardware, piu' stadi di pipeline e miglior controllo di mutua dipendenza delle singole istruzioni macchina, con la possibilita' di eseguire piu' istruzioni per colpo di clock.
Questi accorgimenti, cresciuti e migliorati con il tempo (il prefetch p.es. c'era gia' sull 8086), non richiedono una riscrittura del software. A parte alcuni minimi accorgimenti, solitamente risolti a livello di compilatore, per lo svincolo delle dipendenze delle istruzioni macchina, i sofware scritti beneficiano in modo automatico ogni volta che un nuovo processore riesce a migliorare questi espedienti.
Anche qui pero' siamo giunti a limiti molto spinti. E' improbabile che all'interno di un core si riesca a beneficiare dell'aggiunta di nuove pipeline. Il pentium 1 e' stato il primo ad introdurre 2 pipline. Il pentium 3 ha introdotto 3 pipeline. Sono state introdotte pipeline indipendenti per il coprocessore matematico e per le istruzioni MMX e simili. Contando pero' che la maggior parte delle operazioni macchina sono svolte tra i normali registri (interi), e che e' difficile trovare sequenze di 4 microistruzioni assolutamente indipendenti, ne consegue che difficilmente si supereranno 4 pipeline per per le istruzioni che coinvolgono la computazione tra interi.
Piu' recentemente e' iniziata la migrazione di piu' core all'interno di ogni microprocessore. Commercialmente si e' a 4, ma le roadmap parlano chiaro. Il futuro per restare nella legge di Moore e' li'. Aggregare piu' core all'interno del singolo microprocessore. Si parla gia' di 20 core, e alcune prove/studi sono state fatte dalla Intel con piu' di 1000 core.
Qui pero' abbiamo un problema. I programmi che sono stati scritti senza accortezze particolari, non potranno beneficiare dell'introduzione di nuovi core. Un minimo di vantaggio ci sara' comunque. Il core dedicato per il singolo processo utente potra' agire indisturbato, senza time-sharing con gli altri processi in esecuzione (Sistema operativo, etc.). Ma e' un effetto minore.
Occorre scrivere sofware che possano muoversi e beneficiare direttamente della presenza di nuovi core.
Scrivere sofware multiprocesso e' una normalmente una pena.
Meglio, adattare un algoritmo tipicamente sequenziale, scritto in un linguaggio imperativo, in modo da sfruttare i core presenti e' difficile e scomodo.
Il piu' delle volte ne risulta un codice "spaghetti" che poco ha a che fare con l'algoritmo stesso. Il tutto e' quasi sempre illeggibile e poco manutenibile.
Sono uscite parecchie librerie atte ad aiutare la programmazione parallela, alcune semplici, alcune complesse.
Facendo tesoro dell'idea secondo la quale il paradigma di programmazione naturale per la programmazione parallela e' quello funzionale, ultimamente si stanno vedendo parecchi sforzi concentrati in questa direzione.
Consiglio mio e' quello di iniziare a studiare, per chi ancora non l'avesse fatto, la programmazione funzionale, per non trovarsi tagliati fuori dal mercato.
Nelle ultime 4 settimane gli annunci relativi alla programmazione funzionale qui a Londra sono aumentati tantissimo.
Io personalmente la programmazione funzionale non l'avevo mai affrontata prima di ottobre 2007. Mi ci sono avvicinato gradualmente. La settimana scorsa ho provato a fare il salto verso la funzionale parallela, e devo dire che sono rimasto stupefatto della semplicita'.
Per chi conosce concetti come Thread, BackgroundWorker, semafori, segnali, Mutex, etc. e tutto quanto serve di contorno per la gestione di una programmazione parallela con linguaggi imperativi non potra' che apprezzare la semplicita'.
Problema: Si hanno una quarantina di milioni di stringhe.
Si vuole contare quante siano le stringhe che soddisfano un determinato requisito, p.es. che iniziano con la lettera 'a'
Esecuzione: Scarico un testo da una sorgente Web nota.
Splitto il testo in tutte le sue singole parole presenti.
Essendo che il testo e' lungo 200.000 parole, replico il tutto per 200 volte, per raggiungere 40.000.000 di parole circa.
Inizio i test.
Il primo e' la versione imperativa sequenziale
Il secondo e' la versione funzionale sequenziale, che fra l'altro ha un suo miglioramento in leggibilita'
Il terzo e' la versione funzionale parallela. La semplicita' di passare dalla seconda alla terza e' stato per me stupefacente.
Random rnd = new Random();
Console.WriteLine("Download");
string text = new WebClient().DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt"); // Great Expectations
string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);
List<string> array = new List<string>();
Console.WriteLine("Prepare");
for (int t = 0; t < 200; t++)
{
array.AddRange(words);
}
int totalLength = array.Count;
Console.WriteLine("Start - Numero di parole che iniziano con 'a', tra un elenco di {0} parole",totalLength);
Stopwatch watch;
for (int iters = 0; iters < 10; iters++)
{
//
// Imperativo sequenziale
//
watch = Stopwatch.StartNew();
int res = 0;
for (int t = 0; t < totalLength; t++)
{
if (array[t].StartsWith("a")) res++;
}
watch.Stop();
Console.WriteLine("Imperativo Sequentiale: {0} ms - Res:{1}", watch.ElapsedMilliseconds,res);
//
// Funzionale Sequentiale
//
watch = Stopwatch.StartNew();
res = array.Count(t => t.StartsWith("a"));
watch.Stop();
Console.WriteLine("Funzionale Sequentiale: {0} ms - Res:{1}", watch.ElapsedMilliseconds,res);
//
// Funzionale Parallelo
//
watch = Stopwatch.StartNew();
res = array.AsParallel().Count(t => t.StartsWith("a"));
watch.Stop();
Console.WriteLine("Funzionale Parallel: {0} ms - Res:{1}", watch.ElapsedMilliseconds,res);
}
Console.ReadKey();
Rislutati sul mio DualCore E6600 (3GHz)
Download
Prepare
Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
Imperativo Sequentiale: 3972 ms - Res:4112600 (non significativo)
Funzionale Sequentiale: 3934 ms - Res:4112600
Funzionale Parallel: 2124 ms - Res:4112600
Imperativo Sequentiale: 3584 ms - Res:4112600
Funzionale Sequentiale: 3967 ms - Res:4112600
Funzionale Parallel: 2087 ms - Res:4112600
Imperativo Sequentiale: 3588 ms - Res:4112600
Funzionale Sequentiale: 3933 ms - Res:4112600
Funzionale Parallel: 2082 ms - Res:4112600
Imperativo Sequentiale: 3594 ms - Res:4112600
Funzionale Sequentiale: 3958 ms - Res:4112600
Funzionale Parallel: 2080 ms - Res:4112600
Imperativo Sequentiale: 3589 ms - Res:4112600
Funzionale Sequentiale: 3969 ms - Res:4112600
Funzionale Parallel: 2095 ms - Res:4112600
L'imperativo sequenziale si attesta sui 3.5 sec.
Il funzionale sequenziale sui 4 sec
Il funzionale parallelo sui 2 sec.
E sarei pronto a scommettere che aumentando il numero di core, il funzionale parallelo continuera' a migliorare i tempi.
DanieleC88
27-04-2008, 14:22
Molto interessante. Dovrò leggiucchiare qualcosa per capire cosa sia questa programmazione funzionale. :)
Cioè in C# basta fare
array.AsParallel()
e lui lo smanazza in parallelo? Figata!
^TiGeRShArK^
28-04-2008, 18:43
Davvero simpatiche le possibilità offerte da PLINQ :D
ecco i risultati su un Q6600 (2.4 ghz):
28/04/2008 18.43.08 Program.ProvaParallel() Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
28/04/2008 18.43.15 Program.ProvaParallel() Imperativo Sequentiale: 6508 ms - Res:4112600
28/04/2008 18.43.21 Program.ProvaParallel() Funzionale Sequentiale: 6698 ms - Res:4112600
28/04/2008 18.43.23 Program.ProvaParallel() Funzionale Parallel: 1844 ms - Res:4112600
28/04/2008 18.43.30 Program.ProvaParallel() Imperativo Sequentiale: 6590 ms - Res:4112600
28/04/2008 18.43.36 Program.ProvaParallel() Funzionale Sequentiale: 6709 ms - Res:4112600
28/04/2008 18.43.38 Program.ProvaParallel() Funzionale Parallel: 1757 ms - Res:4112600
28/04/2008 18.43.45 Program.ProvaParallel() Imperativo Sequentiale: 6513 ms - Res:4112600
28/04/2008 18.43.51 Program.ProvaParallel() Funzionale Sequentiale: 6714 ms - Res:4112600
28/04/2008 18.43.53 Program.ProvaParallel() Funzionale Parallel: 1805 ms - Res:4112600
Grazie per l'interessantissimo thread :D
mcardini
29-04-2008, 08:16
Sto studiando il c# propio ora..... (insieme con i db)
Che namespaces vanno usati per funzionare bene?
Ciao.
Per far funzionare questo esempio occorre scaricare il supporto PLINQ, che e' ancora in beta e non e' ancora inserito nel Framework.
Una volta scaricata la DLL dovrai aggiungerla ai riferimenti del progetto.
Per quanto riguarda gli assembly riferiti sono i seguenti (magari ne metto qualcuno di troppo)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.Net;
Comunque non ti consiglio di considerare questo esempio nel tuo percorso di apprendimento, quanto piu' come curiosita'.
Non ti consiglierei neppure di iniziare dalla parte funzionale del linguaggio, ma non sono un professore, non saprei dirti un percorso corretto per affrontare il tutto.
Personalmente mi sono sempre trovato bene con un'accoppiata:
- {Quello che vuoi imparare} for dummies
- Advanced {Quello che vuoi imparare} for PRO and Geeks.
Davvero simpatiche le possibilità offerte da PLINQ :D
Grazie per l'interessantissimo thread :D
Mi sto divertendo a casa per ora.
Ieri sera ho preso un mio vecchissimo programma C++ per la generazione di frattali, e l'ho trasformato in C# funzionale + parallelo.
Il codice centrale per il parallelismo e' davvero pulito.
Secondo me si puo' riscrivere in modo simile qualcosa anche per programmi di Ray-Tracing o per renderizzatori grafici.
Il punto e' che qui la computazione di ogni pixel e' indipendente dagli altri, ed e' la condizione perfetta per il parallelismo.
var screen = from y in ParallelEnumerable.Range(0, 768)
from x in Enumerable.Range(0, 1024)
select ComputeMandel( x, y );
^TiGeRShArK^
29-04-2008, 09:34
Mi sto divertendo a casa per ora.
Ieri sera ho preso un mio vecchissimo programma C++ per la generazione di frattali, e l'ho trasformato in C# funzionale + parallelo.
Il codice centrale per il parallelismo e' davvero pulito.
Secondo me si puo' riscrivere in modo simile qualcosa anche per programmi di Ray-Tracing o per renderizzatori grafici.
Il punto e' che qui la computazione di ogni pixel e' indipendente dagli altri, ed e' la condizione perfetta per il parallelismo.
var screen = from y in ParallelEnumerable.Range(0, 768)
from x in Enumerable.Range(0, 1024)
select ComputeMandel( x, y );
si infatti avevo visto giusto ieri un articolo in cui era stato applicato al ray-tracing e veniva anche mostrata la distribuzione sui vari core colorando in maniera diversa i pixel prodotti da ciascun core :p
Inutile dire che la distribuzione sui vari core, almeno in questi semplici "esercizietti di stile" è spettacolare....
Dividendo per 4 il tempo ottenuto dalla versione sequenziale si ottiene 1675 che non è poi troppo lontano rispetto al valore medio di 1800 che raggiunge la versione parallela :p
Comunque io giusto ieri avevo iniziato a studiare la programmazione funzionale in c# con questo tutorial:
http://blogs.msdn.com/ericwhite/pages/FP-Tutorial.aspx
che mi pare fatto piuttosto bene :p
LINQ mi ha salvato il culo al lavoro perchè riesco a fare come niente delle elaborazioni su un xml scrivendo pochissimo codice :D
..E dire che ho iniziato a studiarlo solo ieri pomeriggio :p
tomminno
29-04-2008, 10:06
Rislutati sul mio DualCore E6600 (3GHz)
L'imperativo sequenziale si attesta sui 3.5 sec.
Il funzionale sequenziale sui 4 sec
Il funzionale parallelo sui 2 sec.
E sarei pronto a scommettere che aumentando il numero di core, il funzionale parallelo continuera' a migliorare i tempi.
Scusa ma visto che stai facendo una comparazione di prestazioni perchè non hai inserito anche l'imperativo parallelo?
Visto che già sul sequenziale il funzionale si è dimostrato più lento è lecito attendersi una maggior lentezza anche sul parallelo.
mcardini
29-04-2008, 12:09
Davvero bello, ho provato e dato che ho sulla sidebar l'occupazione di cpu multicore (ho un core2) posso propio vedere come con la funzionale paralel occupo tutti e due i core.
Ho notato un'altra cosa, compilando in release per cpu x64 si guadagna qualcosa... ;)
Scusa ma visto che stai facendo una comparazione di prestazioni perchè non hai inserito anche l'imperativo parallelo?
Visto che già sul sequenziale il funzionale si è dimostrato più lento è lecito attendersi una maggior lentezza anche sul parallelo.
Eh gia', come dicevo la programmazione imperativa parallela e' una pena.
Sono state introdotte delle librerie per aiutare la programmazione imperativa parallela in molti linguaggi, come p.es anche nel C++, per il quale ci sono diverse librerie.
Nel C# posso postare una versione "vecchio stile", che dovrebbe essere in assoluto la piu' veloce.
Ma non come scrittura e leggibilita'. La semplicita' di questo algoritmo si perde nei meandri della gestione dei Thread.
Forse con i ThreadPool si potrebbe fare qualcosa di meglio, ma non penso che si possa raggiungere la leggibilita' della imperativa normale o della funzionale.
Come dire, se proprio sono messo male mi metto a giocare con i Thread, ma poiche' non capitera', e che 10% di perdita non dovrebbe essere un problema, mi sa che terro' la funzionale in futuro.
Inoltre la imperativa parallela soffre di alcuni problemi tipo il fatto che innanzitutto non si sa quanti thread lanciare e come suddividere il lavoro, cosa che si puo' aggirare certo, ma e' un altro passo da scrivere.
Inoltre se si fanno bene le cose si creano tanti thread quanti sono i potenziali core a disposizione. E quindi puo' capitare che un Thread finisca in anticipo il lavoro rispetto agli altri, e che quindi uno o piu' core non vengano sfruttati al 100%
Posto 2 versioni. Vecchio stile e nuovo stile
//
// Imperativo Parallelo Thread
//
watch = Stopwatch.StartNew();
List<Computer> tlist=new List<Computer>();
int nparallel=4;
for (int t=0;t<nparallel;t++)
{
int l1=totalLength/nparallel*t;
int l2=totalLength/nparallel*(t+1)-1;
Computer cm=new Computer(array,l1,l2);
tlist.Add(cm);
cm.Start();
}
res = 0;
foreach (Computer cmp in tlist)
{
res += cmp.Join();
}
watch.Stop();
Console.WriteLine("Imperativo Parallelo1: {0} ms - Res:{1}", watch.ElapsedMilliseconds, res);
Per il quale occorre anche dotare la soluzione della classe di gestione
public class Computer
{
private List<string> Domain;
private int lim1;
private int lim2;
private Thread myThread;
public Computer(List<string> p_domain, int p_lim1, int p_lim2)
{
Domain = p_domain;
lim1 = p_lim1;
lim2 = p_lim2;
myThread = new Thread(Exec);
}
public void Start()
{
myThread.Start();
}
public int Join()
{
myThread.Join();
return found;
}
private int found = 0;
private void Exec()
{
for (int t = lim1; t < lim2; t++)
{
if (Domain[t].StartsWith("a")) found++;
}
}
}
E nuovo stile
//
// Imperativo Parallelo new
//
watch = Stopwatch.StartNew();
res=0;
Parallel.For(0, totalLength, t => {
if (array[t].StartsWith("a")) Interlocked.Add(ref res, 1);
});
watch.Stop();
Console.WriteLine("Imperativo Parallelo2: {0} ms - Res:{1}", watch.ElapsedMilliseconds, res);
A causa dei problemi di Shared Memory la variabile contatore deve essere incrementata in regione critica, e questo causa un decremento non indifferente delle potenziali prestazioni.
Se qualcuno ha idea di come migliorare ben venga.
Tutte le prove insieme:
Qui ho un core2duo 1.86GHz
Download
Prepare
Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
Imperativo Sequenziale: 6671 ms - Res:4112600
Funzionale Sequenziale: 6309 ms - Res:4112600
Imperativo Parallelo1: 3088 ms - Res:4112600
Imperativo Parallelo2: 3913 ms - Res:4112600
Funzionale Parallelo: 3520 ms - Res:4112600
----
Imperativo Sequenziale: 6109 ms - Res:4112600
Funzionale Sequenziale: 6308 ms - Res:4112600
Imperativo Parallelo1: 3400 ms - Res:4112600
Imperativo Parallelo2: 3604 ms - Res:4112600
Funzionale Parallelo: 3506 ms - Res:4112600
----
Imperativo Sequenziale: 6047 ms - Res:4112600
Funzionale Sequenziale: 6300 ms - Res:4112600
Imperativo Parallelo1: 3159 ms - Res:4112600
Imperativo Parallelo2: 3628 ms - Res:4112600
Funzionale Parallelo: 3512 ms - Res:4112600
----
Imperativo Sequenziale: 6043 ms - Res:4112600
Funzionale Sequenziale: 6323 ms - Res:4112600
Imperativo Parallelo1: 3228 ms - Res:4112600
Imperativo Parallelo2: 3603 ms - Res:4112600
Funzionale Parallelo: 3497 ms - Res:4112600
Come si puo' vedere in assoluto pilotando a mano i thread si vince.
Ma come espressivita' siamo ben lontani.
Il nuovo costrutto Parallel.For potrebbe aiutare, ma non ho ancora ben capito come superare efficientemente i problemi di Shared Memory.
Forse con un doppio ciclo, uno per la creazione dei lavori e l'altro per l'esecuzione imperativa normale, ma di nuovo si complica la scrittura, e forse non si superano i problemi di cui sopra.
Comunque in ordine abbiamo
Imperativo Parallelo Classico: 3200
Funzionale Parallelo: 3500
Imperativo Parallelo Nuovo: 3600 (Potenzialmente migliorabile)
Imperativo Sequenziale: 6100
Funzionale Sequenziale: 6300
tomminno
29-04-2008, 13:37
Comunque in ordine abbiamo
Imperativo Parallelo Classico: 3200
Funzionale Parallelo: 3500
Imperativo Parallelo Nuovo: 3600 (Potenzialmente migliorabile)
Imperativo Sequenziale: 6100
Funzionale Sequenziale: 6300
Da cui la conclusione ormai assodata che maggiori sono le astrazioni peggiori sono le prestazioni.
Poi ci manca altro che un programmatore non conosca nemmeno più cosa sono i thread e siamo a posto.
Intanto il PLINQ e' ancora in versione Beta ed hanno detto che questa versione non e' stata ottimizzata per le performance.
E poi cosa consigli? Scriviamo in assembly?
^TiGeRShArK^
29-04-2008, 14:30
e non dimentichiamo che un codice reale + semplice e leggibile è anche spesso + performante perchè è possibile ottimizzare meglio a livello algoritmico avendo una visione + chiara del sistema ;)
E tutte le altre opzioni di ottimizzazione oltre quella algoritmica, a parte casi particolari tipo i sistemi embedded/mobili, sono assolutamente controproducenti se non limitate moltissimo in dimensione.
cdimauro
29-04-2008, 14:49
E poi cosa consigli? Scriviamo in assembly?
Suggerisco il linguaggio macchina: non c'è linguaggio che permetta di scendere più a basso livello. :O :Prrr:
tomminno
29-04-2008, 15:00
Intanto il PLINQ e' ancora in versione Beta ed hanno detto che questa versione non e' stata ottimizzata per le performance.
E poi cosa consigli? Scriviamo in assembly?
Dico solo che uno deve saper fare il proprio mestiere.
Adesso anche i thread sono elementi troppo a basso livello?
Dico solo che uno deve saper fare il proprio mestiere.
Adesso anche i thread sono elementi troppo a basso livello?
Non sono necessariamente lo strumento giusto. Non tanto i thread in se, ma le primitive di sincronizzazione che devi usare, che portano a a bug insidiosi e difficili da individuare . E che tendono a rallentare il codice all'aumentare della complessita' e dei core.
In generale con la programmazione funzionale questi problemi si sentono meno e scala meglio. E si evitano bug come quello presente nell'esempio "Imperativo parallelo thread" riportato qui sopra :D ;)
^TiGeRShArK^
29-04-2008, 16:23
Dico solo che uno deve saper fare il proprio mestiere.
Adesso anche i thread sono elementi troppo a basso livello?
..Mai perso una settimana di lavoro per scovare un bug dovuto al multi-threading in un sistema complesso magari su una libreria che stai utilizzando? :fagiano:
tomminno
29-04-2008, 16:36
Non sono necessariamente lo strumento giusto. Non tanto i thread in se, ma le primitive di sincronizzazione che devi usare, che portano a a bug insidiosi e difficili da individuare . E che tendono a rallentare il codice all'aumentare della complessita' e dei core.
In generale con la programmazione funzionale questi problemi si sentono meno e scala meglio. E si evitano bug come quello presente nell'esempio "Imperativo parallelo thread" riportato qui sopra :D ;)
Perchè pensi che invece il codice sottostante del PLINQ non sincronizzi internamente?
Il codice è rallentato ugualmente anzi di più.
tomminno
29-04-2008, 16:39
..Mai perso una settimana di lavoro per scovare un bug dovuto al multi-threading in un sistema complesso magari su una libreria che stai utilizzando? :fagiano:
No, in compenso mi è capitato di perderne 2 perchè il .NET ogni tot ore di lavoro si incartava e toccava andare col task manager sul server a tirare giù il processo aspnet_wp e se si stroncava il sabato o la domenica gli utenti vedevano un bellissimo runtime exception per tutto il week-end.
Alla fine era un bug del framework risolto con un'aggiornamento.
Perchè pensi che invece il codice sottostante del PLINQ non sincronizzi internamente?
Il codice è rallentato ugualmente anzi di più.
A parte che c'e' una grossa differenza anche prestazionale.
Il caso provato ora e' mediamente bilanciato, ma non e' detto che i Thread vengano da te bilanciati in modo ottimo.
Con la distribuzione manuale del lavoro rischi di dividere i compiti in modo non equo, con il risultato che alcuni Thread finiranno prima di altri, e non avrai la massima efficienza.
Con la funzionale invece ogni Thread scoda un pezzo di lavoro da fare in automatico, non appena ha finito quello precedente.
Pensa a moltiplicazioni di matrici sparse o determinanti di matrici con tanti zeri.
E comunque si', i thread in ambiente parallelo sono considerati troppo basso livello.
Ecco un paio di copia-incolla da una conferenza in merito, tenuta da un Prof. del dipartimento di informatica dell'Universita' di Londra, che dal 1983 si occupa di programmazione parallela, con il quale ho avuto il piacere di trascorrere una serata.
The Problems of Threads
● Shared memory.
● Flow control.
What To Do
● Refuse to use multiple threads.
● Never use shared mutable state.
● Always use message passing.
Summary
● Threads are needed but they are not a programmer tool.
● Why bother with an explicit threads API when OpenMP is available?
● Why not use a language that supports parallelism directly?
Sei comunque libero di usare i thread, ma sappi che in giro si sente sempre di piu' parlare dei Thread come il mattone, come l'assembly dal parallelismo, e che un compilatore riuscira' a svolgere il lavoro meglio di qualunque programmatore.
tomminno
29-04-2008, 18:04
Sei comunque libero di usare i thread, ma sappi che in giro si sente sempre di piu' parlare dei Thread come il mattone, come l'assembly dal parallelismo, e che un compilatore riuscira' a svolgere il lavoro meglio di qualunque programmatore.
Direi che i Thread dovranno essere parte del bagaglio di un programmatore ancora per molti anni.
Finché in un articolo tecnico viene definito PLINQ come:
PLINQ allows LINQ developers to take advantage of parallel hardware—including achieving better performance and building more intrinsically scalable software—without needing to understand concurrency or data parallelism
quando poi questo è palesemente falso, visto che precedentemente ti dicono che si lo puoi usare, ma devi togliere tutte le race conditions.
Interessante, se non ho bisogno di conoscere i problemi legati alla concorrenza, come faccio ad eliminiare le race-conditions?
Prova ad usare il codice precedente e a scrivere su un file (lo stesso file) le parole che iniziano con 'a'.
Direi che i Thread dovranno essere parte del bagaglio di un programmatore ancora per molti anni.
Sicuro, esattamente come il goto.
Tutti devono conoscerlo, ma non per forza occorre usarlo.
Comunque grazie per il tuo intervento, come detto prima sei libero di pensare che con i Thread si riescano a risolvere i problemi di parallelismo meglio e piu' efficientemente. Vedremo cosa succedera' in futuro.
Ritorno sull'esempio della Imperativa parallela sfruttando alcune nuove feature della system.threading.
Lo svincolare (o almeno minimizzare) la shared memory ha i suoi vantaggi.
La versione in assoluto piu' performante e' proprio questa, anche se la leggibilita' e' di gran lunga piu' lontana della funzionale parallela.
//
// Imperativo Parallelo 3
//
watch = Stopwatch.StartNew();
res = 0;
nparallel=1000;
Parallel.For(0, nparallel, t =>
{
int l1 = totalLength / nparallel * t;
int l2 = totalLength / nparallel * (t+1);
int local = 0;
for (int u = l1; u < l2; u++)
{
if (array[u].StartsWith("a")) local++;
}
Interlocked.Add(ref res, local);
});
watch.Stop();
Console.WriteLine("Imperativo Parallelo3: {0} ms - Res:{1}", watch.ElapsedMilliseconds, res);
In questa versione suddivido il lavoro in 100 task piu' piccoli, e lascio la gestione della schedulazione dei thread completamente al gestore del parallelismo della parte imperativa.
Ciascuno dei Task ha una propria variabile privata d'appoggio per il conteggio.
Solo alla fine si passa alla shared memory, ma si tratta di solamente 100 somme, dove il loro effetto negativo e' ridotto, e soprattutto improbabilmente i vari task arriveranno insieme e attenderanno per la contesa.
I risultati sono sorprendenti, ma come si puo' vedere inizia ad assomigliare ad uno spaghetti code.
In piu' ha bisogno del 100, che e' un valore tirato un po' a caso, e che soprattutto potrebbe non essere adeguato fra 5-6 anni, e forse neppure adesso su tutte le configurazioni.
Ovviamente la stessa suddivisione fatta sulla versione manuale dei Thread non puo' dare gli stessi risultati. 100 thread contemporanei non sono affatto una carta vincente sul mio povero dual core. Si raggiungevano infatti i risultati peggiori di tutta la sessione, che ho prontamente tolto.
Imperativo Sequenziale: 5907 ms - Res:4112600 (Caso classico, semplice)
Funzionale Sequenziale: 6430 ms - Res:4112600 (semplicissimo, ma occorre conoscere la programmazione funzionale)
Imperativo Parallelo1: 3170 ms - Res:4112600 (Imperativo con gestione manuale dei Thread. Difficilmente comprensibile)
Imperativo Parallelo2: 3522 ms - Res:4112600 (Imperativo con nuove feature, codice semplice)
Imperativo Parallelo3: 2969 ms - Res:4112600 (Imperativo con nuove feature, codice non immediato)
Funzionale Parallelo: 3403 ms - Res:4112600 (semplicissimo, ma occorre conoscere la programmazione funzionale)
^TiGeRShArK^
29-04-2008, 22:01
Interessante, se non ho bisogno di conoscere i problemi legati alla concorrenza, come faccio ad eliminiare le race-conditions?
Prova ad usare il codice precedente e a scrivere su un file (lo stesso file) le parole che iniziano con 'a'.
Nella programmazione funzionale le funzioni pure non hanno side-effects.
Quindi una funzione ad esempio non scriverà mai sullo stesso file ma creerà un altro file.
Che tra l'altro è la cosa + intelligente da fare ;)
La programmazione funzionale è per questo quella su cui si sta spingendo molto proprio nell'ottica del multi-threading visto i molteplici vantaggi che offre in quest'ambito.
Che perda un 10% rispetto alla programmazione ad oggetti è una quisquilia dato che guadagni MOLTISSIMO tempo evitando di bestemmiare per dei bug dovuti al multi-threading.
E a me è capitato di perdere una settimana di lavoro con tutto il team (di 4 persone) per un bug del cazz di multi-threading in Jade.
Se la programmazione funzionale facilita l'utilizzo del' multi-threading, rendendo l'apporccio molto + facile allo sviluppatore, ben venga..
me ne sbatto sinceramente che sia il 10% + lenta (nei micro-benchmark ovviamente) o che faccia 10 punti in + al 3dmark :asd:
E nuovo stile
//
// Imperativo Parallelo new
//
watch = Stopwatch.StartNew();
res=0;
Parallel.For(0, totalLength, t => {
if (array[t].StartsWith("a")) Interlocked.Add(ref res, 1);
});
watch.Stop();
Console.WriteLine("Imperativo Parallelo2: {0} ms - Res:{1}", watch.ElapsedMilliseconds, res);
A causa dei problemi di Shared Memory la variabile contatore deve essere incrementata in regione critica, e questo causa un decremento non indifferente delle potenziali prestazioni.
Se qualcuno ha idea di come migliorare ben venga.
2 idee.
1 - cambiare approccio Fai molte piu' sincronizzazioni del necessario (presumo qualche milionata...). Spezza il problema in n (= numero processori) parti e solvile indipendentemente senza sincronizzazioni. Alla fine "raccogli" il risultato. Qua si vede gia' il vantaggio dell'approccio funzionale, dove separi le due parti, calcolo dei valori sui singoli elementi (map), e riduzione finale ad un unico valore (finale), perche' riesci a rendere indipendenti le due parti dal punto di vista logico, salvando capra (performance) e cavoli (chiarezza del codice). Nel caso che hai mostrato inizialmente tu non si apprezza molto, perche' C# lo ha implementato per una funzione particolare (la somma) ma in generale vale per qualsiasi
2 - Concentrarsi sul vero problema... ho fatto una prova in C++ e ci mette una ventina di secondi a caricare da disco e splittare le parole, e circa tre decimi di secondo a calcolare il risultato :p.
Perchè pensi che invece il codice sottostante del PLINQ non sincronizzi internamente?
E' un discorso analogo a quello della gestione della memoria. Anche un garbage collector non fa altro che allocare e liberare memoria, e in teoria una persona fa meglio, pero' se lo devi fare una riga ogni altra, comincia a diventare una palla e facile sbagliare. Ci sono molti trucchetti che si possono applicare per ottenere buone performance da una parallelizzazione come quella proposta. Applicarli ad ogni occasione diventa pesante per il programmatore che difficilmente lo fara' sempre per cui anche se in teoria il codice automatico non e' ottimale e' in media migliore.
2 idee.
1 - cambiare approccio Fai molte piu' sincronizzazioni del necessario (presumo qualche milionata...). Spezza il problema in n (= numero processori) parti e solvile indipendentemente senza sincronizzazioni. Alla fine "raccogli" il risultato. Qua si vede gia' il vantaggio dell'approccio funzionale, dove separi le due parti, calcolo dei valori sui singoli elementi (map), e riduzione finale ad un unico valore (finale), perche' riesci a rendere indipendenti le due parti dal punto di vista logico, salvando capra (performance) e cavoli (chiarezza del codice). Nel caso che hai mostrato inizialmente tu non si apprezza molto, perche' C# lo ha implementato per una funzione particolare (la somma) ma in generale vale per qualsiasi
Gia', e' proprio quello che ho fatto pochi post fa, ed e' per ora la prestazione migliore
2 - Concentrarsi sul vero problema... ho fatto una prova in C++ e ci mette una ventina di secondi a caricare da disco e splittare le parole, e circa tre decimi di secondo a calcolare il risultato :p.
Chiaro. Una volta pero' scelto il linguaggio C#, ci sono tempi sotto i quali sara' difficile andare. Non scendo comunque a compromessi, per me la velocita' di scrittura del codice, la chiarezza e la manutenibilita' sono comunque indispensabili.
Non sono praticamente da anni su pezzi di critici che hanno bisogno di velocita'. Se quello fosse il target primario sceglierei probabilmente il C++.
Restando sul C# o comunque su linguaggi Managed stavo cercando di capire la strada migliore per poter sfruttare le future prossime architetture hardware.
E mi sa che per ora sto preferendo la funzionale.
Per intendersi, non e' che capita spesso di maneggiare decine di milioni di oggetti. Un approccio automatico che degrada automaticamente dalla parallela alla sequenziale non potra' che essere un vantaggio, quando non sai che macchina hai davanti e magari non hai anche qualche impredicibilita' sui dati che andrai a trattare.
Qualcuno sa se per caso il Java ha in progetto qualche estensione di questo tipo?
tomminno
30-04-2008, 09:11
Sicuro, esattamente come il goto.
Tutti devono conoscerlo, ma non per forza occorre usarlo.
Per quale motivo il goto dovrebbe rimanere nel bagaglio di un programmatore?
Comunque grazie per il tuo intervento, come detto prima sei libero di pensare che con i Thread si riescano a risolvere i problemi di parallelismo meglio e piu' efficientemente. Vedremo cosa succedera' in futuro.
Mascherali come vuoi i thread sono l'unico modo per risolvere parallelamente i compiti all'interno di un processo.
Quindi che li usi tramite PLINQ o API native o librerie, devi sempre conoscerne il funzionamento e le problematiche.
Ritorno sull'esempio della Imperativa parallela sfruttando alcune nuove feature della system.threading.
Lo svincolare (o almeno minimizzare) la shared memory ha i suoi vantaggi.
La versione in assoluto piu' performante e' proprio questa, anche se la leggibilita' e' di gran lunga piu' lontana della funzionale parallela.
Ovviamente la stessa suddivisione fatta sulla versione manuale dei Thread non puo' dare gli stessi risultati. 100 thread contemporanei non sono affatto una carta vincente sul mio povero dual core. Si raggiungevano infatti i risultati peggiori di tutta la sessione, che ho prontamente tolto.
Ma continui a paragonare soluzioni diverse.
Il parallelo più corretto di questa versione è con l'utilizzo di un thread pool (che è lo stesso meccanismo usato da PLINQ)
tomminno
30-04-2008, 09:18
Nella programmazione funzionale le funzioni pure non hanno side-effects.
Quindi una funzione ad esempio non scriverà mai sullo stesso file ma creerà un altro file.
Che tra l'altro è la cosa + intelligente da fare ;)
Il mio era un suggerimento per introdurre una race condition banale (la scrittura contemporanea su file), mai pensato che fosse una buona norma
La programmazione funzionale è per questo quella su cui si sta spingendo molto proprio nell'ottica del multi-threading visto i molteplici vantaggi che offre in quest'ambito.
Che perda un 10% rispetto alla programmazione ad oggetti è una quisquilia dato che guadagni MOLTISSIMO tempo evitando di bestemmiare per dei bug dovuti al multi-threading.
E a me è capitato di perdere una settimana di lavoro con tutto il team (di 4 persone) per un bug del cazz di multi-threading in Jade.
Se la programmazione funzionale facilita l'utilizzo del' multi-threading, rendendo l'apporccio molto + facile allo sviluppatore, ben venga..
me ne sbatto sinceramente che sia il 10% + lenta (nei micro-benchmark ovviamente) o che faccia 10 punti in + al 3dmark :asd:
Quando hai a che fare con server ad alto carico te ne freghi eccome se è di un 10% più lenta perchè significa dover comprare una macchina in più (e quindi almeno 2 macchine visto che come minimo sono 2 in bilanciate) e 2 server ti costano quasi quanto 1 anno di stipendio di un programmatore (che è veramente basso :( ), oltre ad occupare spazio nella server-farm che potrebbe essere usato in maniera più fruttuosa, ad esempio affittando quello spazio ad altri clienti.
Il rapporto costi/benefici va valutato in ottica più ampia.
E' il motivo per cui, dove lavoro, Linq dopo l'entusiasmo iniziale è stato (per il momento) accantonato.
Qualcuno sa se per caso il Java ha in progetto qualche estensione di questo tipo?
Che io sappia, no.
Cioè ci sono librerie di terze parti ovviamente, ma niente del tipo
array.AsParallel....
che sinceramente mi ha lasciato piacevolmente sorpreso.
C'è una libreria che fa da clone di linq, e si chiama quaere ( http://quaere.codehaus.org/ ), ma per quanto apprezzi lo sforzo, mi sembra sempre un accrocchio.
Credo dovrò prendere dimestichezza con .net e c# e abbandonare il mondo java, che secondo me sta perdendo un sacco di colpi (l'altro colpo è javafx).
Per quale motivo il goto dovrebbe rimanere nel bagaglio di un programmatore?
Mascherali come vuoi i thread sono l'unico modo per risolvere parallelamente i compiti all'interno di un processo.
Quindi che li usi tramite PLINQ o API native o librerie, devi sempre conoscerne il funzionamento e le problematiche.
Esattamente come il thread e' l'oggetto base per gestire i compiti di parallelismo, cosi' anche il goto (o if-goto) e' l'oggetto base a cui tutti i controlli di flusso vengono ricondotti dai compilatori.
Il fatto che entrambi siano un risultato finale di qualunque compilazione non implica necessariamente che li si debba conoscere o li si debba per forza usare.
E il mio appunto era proprio questo.
Come il goto e' addirittura giusto che non venga usato, anche i Thread non e' detto che debbano necessariamente essere usati.
E comunque non e' frutto di mie considerazioni. A quella conferenza TUTTI i relatori sono giunti a questa considerazione.
Io resto dell'idea che una gestione automatica da parte di una virtual machine sara' in futuro migliore di quanto possa fare uno sviluppatore manualmente, soprattutto davati all'incognita dell'architettura della macchina e della pesantezza del compito
la JIT compiler decide sara' in grado di degradare l'esecuzione da parallela a sequenziale in modo automatico, pur avendo in input lo stesso codice.
Ti sembra poco?
tomminno
30-04-2008, 12:13
Esattamente come il thread e' l'oggetto base per gestire i compiti di parallelismo, cosi' anche il goto (o if-goto) e' l'oggetto base a cui tutti i controlli di flusso vengono ricondotti dai compilatori.
Il fatto che entrambi siano un risultato finale di qualunque compilazione non implica necessariamente che li si debba conoscere o li si debba per forza usare.
Usare no, sapere che i costrutti continue o break sono la stessa cosa di un goto magari si.
E il mio appunto era proprio questo.
Come il goto e' addirittura giusto che non venga usato, anche i Thread non e' detto che debbano necessariamente essere usati.
E comunque non e' frutto di mie considerazioni. A quella conferenza TUTTI i relatori sono giunti a questa considerazione.
C'è una differenza: mentre il goto non lo usi proprio, relegandolo al codice macchina generato dal compilatore, i thread non puoi non usarli, devi farci per forza affidamento quindi devi conoscerne le problematiche.
Non usando per niente il goto puoi benissimo non sapere che può essere nefasto in abbinamento alle eccezioni ed anche per la distruzione di oggetti.
Con i thread o loro astrazioni i problemi di sincornizzazione li devi comunque conoscere, anche se non li usi direttamente, in quanto non li puoi evitare.
Io resto dell'idea che una gestione automatica da parte di una virtual machine sara' in futuro migliore di quanto possa fare uno sviluppatore manualmente, soprattutto davati all'incognita dell'architettura della macchina e della pesantezza del compito
la JIT compiler decide sara' in grado di degradare l'esecuzione da parallela a sequenziale in modo automatico, pur avendo in input lo stesso codice.
Ti sembra poco?
Speando poi che non decida di degradare l'esecuzione in base al carico della macchina...
Speando poi che non decida di degradare l'esecuzione in base al carico della macchina...
Quali alternative avrebbe?
Piu' recentemente e' iniziata la migrazione di piu' core all'interno di ogni microprocessore. Commercialmente si e' a 4, ma le roadmap parlano chiaro. Il futuro per restare nella legge di Moore e' li'. Aggregare piu' core all'interno del singolo microprocessore. Si parla gia' di 20 core, e alcune prove/studi sono state fatte dalla Intel con piu' di 1000 core.
Qui pero' abbiamo un problema. I programmi che sono stati scritti senza accortezze particolari, non potranno beneficiare dell'introduzione di nuovi core. Un minimo di vantaggio ci sara' comunque. Il core dedicato per il singolo processo utente potra' agire indisturbato, senza time-sharing con gli altri processi in esecuzione (Sistema operativo, etc.). Ma e' un effetto minore.
Occorre scrivere sofware che possano muoversi e beneficiare direttamente della presenza di nuovi core.
Si sale, si sale.
Piano piano ma si sale.
E penso che avremo un andamento esponenziale anche qui, come prima sui MHz, domani sui Core.
http://www.hwupgrade.it/articoli/business/2212/intel-nehalem-ex-il-futuro-dei-server-e-a-8-core_index.html
^TiGeRShArK^
27-05-2009, 11:52
2,3 miliardi di transistor su un singolo core di una cpu fa paura.. :fagiano:
Quando hai a che fare con server ad alto carico te ne freghi eccome se è di un 10% più lenta perchè significa dover comprare una macchina in più (e quindi almeno 2 macchine visto che come minimo sono 2 in bilanciate) e 2 server ti costano quasi quanto 1 anno di stipendio di un programmatore (che è veramente basso :( ), oltre ad occupare spazio nella server-farm che potrebbe essere usato in maniera più fruttuosa, ad esempio affittando quello spazio ad altri clienti.
Il rapporto costi/benefici va valutato in ottica più ampia.
E' il motivo per cui, dove lavoro, Linq dopo l'entusiasmo iniziale è stato (per il momento) accantonato.
ORA, magari... quando Intel caccerà i processori a 192 core, voglio vedere la quantità abissale di prestazioni e tempo che vanno buttate provando a programmarli tutti a mano coi threads :rolleyes:
Cmq complimenti, topic davvero interessante :D
Dovrei studiarmi sti linguaggi funzionali, finora non ne so nulla... però mi ispirano, ho sempre odiato e "schifato" i threads, mi sono sempre sembrati una cosa buttata là e poco chiara... se coi funzionali diventa tutto così pulito, direi che avranno un nuovo supporter :D
Ikon O'Cluster
28-05-2009, 18:04
Per carità... per ora voglio continuare ad usare quello che ho studiato all'esame di programmazione distribuita. Una domanda: la potenza espressiva di questa programmazione funzionale parallela è la stessa?
Se stai chiedendo se la programmazione funzionale ha la stessa potenza espressiva della programmazione imperativa direi di si'.
Diciamo che occorre cambiare un po' l'approccio a come vengono descritte le operazioni.
Almeno, io ho dovuto compiere una giravolta, essendo che ero da sempre abiutato alla programmazione imperativa.
Come il sig. Muhammad ibn Musa Khwarizmi (al secolo Al-Khwārizmī) aveva descritto, un algoritmo e' una sequenza temporale di semplici e note operazioni organizzate al fine di risolvere un problema complesso.
Alcuni passi della programmazione funzionale invece sono piu' descrittivi. Si avvicinano piu' ad un linguaggio di quarta generazione, dove appunto talvolta sembra che tu descriva quello che vuoi ottenere piuttosto che il come vuoi che venga ottenuto.
Se invece ti riferivi al paragone tra la funzionale e la funzionale parallela, come puoi vedere dagli esempi, a parte alcune pensate per come elminare quanto piu' possibile le race-conditions, direi che sono identicamente espressive.
Nel senso che se lo e' la prima lo e' anche altrettanto tanto la seconda.
Ikon O'Cluster
28-05-2009, 18:58
Si intendevo proprio se si potessero fare le stesse cose... Cmq una maggiore semplicità la renderebbe una strada molto percorribile in applicazioni non spinte o eccessivamente complesse. Tuttavia, dato che non so bene come funzioni, rimango perplesso da un paragone prestazionale e user-friendly di questo paradigma funzionale parallelo, con quello classico che utilizza costrutti di alto livello. Insomma esiste secondo voi un vantaggio sostanziale rispetto alla potenza e alla semplicità di costrutti tipici della programmazione imperativa parallela ad alto livello quali monitor, variabili condition, ecc...??? Infondo se volete fare applicazioni parallele in Java vi basta avere una età superiore a 18 mesi (come per i giochini dell'ovetto Kinder :D)...
^TiGeRShArK^
28-05-2009, 19:02
Si intendevo proprio se si potessero fare le stesse cose... Cmq una maggiore semplicità la renderebbe una strada molto percorribile in applicazioni non spinte o eccessivamente complesse. Tuttavia, dato che non so bene come funzioni, rimango perplesso da un paragone prestazionale e user-friendly di questo paradigma funzionale parallelo, con quello classico che utilizza costrutti di alto livello. Insomma esiste secondo voi un vantaggio sostanziale rispetto alla potenza e alla semplicità di costrutti tipici della programmazione imperativa parallela ad alto livello quali monitor, variabili condition, ecc...??? Infondo se volete fare applicazioni parallele in Java vi basta avere una età superiore a 18 mesi (come per i giochini dell'ovetto Kinder :D)...
hai detto bene, se vuoi fare dei giochini paralleli in java non ci vuole niente. :)
Se vuoi fare un'applicazione complessa pesantemente basata sul multi-threading, allora preparati a FORTI mal di testa. ;)
Ikon O'Cluster
28-05-2009, 19:49
Tranquillo lo so lo so... era uno degli esami più tosti :D
^TiGeRShArK^
28-05-2009, 20:18
Tranquillo lo so lo so... era uno degli esami più tosti :D
tieni conto che a me non l'aveva spiegato nessuno all'univ il memory model di java (essenziale da conoscere fin nei minimi dettagli per comprendere come gestire i vari problemi di concorrenza) prima di essere andato al java day a roma... :stordita:
vabbè che ero ad ing. tlc, ma certi argomenti imho sono un pò sottovalutati nelle università italiane mi sa....:fagiano:
Ikon O'Cluster
28-05-2009, 20:36
Si vabbè ma in Java la concorrenzà è concorrenza solo perchè i thread vengono eseguiti in parallelo :) è concorrenza ma c'è poco di programmazione concorrente! Imparare la concorrenza in Java anche da zero, se si ha dimistichezza con i linguaggi in generale, è una cosa che si fa benissimo in 2-3 giorni se proprio vuoi essere esperto! :D
!k-0t1c!
28-05-2009, 20:41
Ho visto solo ora questo thread. Vorrei postare dei dati che ritengo interessanti, raccolti con il programma in F# che segue compilato per il .NET Framework 4 beta1:
parallel
4112600 parole trovate in 442ms
sequential
4112600 parole trovate in 364ms
parallel
4112600 parole trovate in 367ms
sequential
4112600 parole trovate in 365ms
parallel
4112600 parole trovate in 360ms
sequential
4112600 parole trovate in 364ms
parallel
4112600 parole trovate in 358ms
sequential
4112600 parole trovate in 366ms
parallel
4112600 parole trovate in 365ms
sequential
4112600 parole trovate in 366ms
parallel
4112600 parole trovate in 374ms
sequential
4112600 parole trovate in 358ms
parallel
4112600 parole trovate in 352ms
sequential
4112600 parole trovate in 369ms
parallel
4112600 parole trovate in 366ms
sequential
4112600 parole trovate in 374ms
parallel
4112600 parole trovate in 372ms
sequential
4112600 parole trovate in 389ms
parallel
4112600 parole trovate in 365ms
sequential
4112600 parole trovate in 411ms
Questi dati si riferiscono al benchmark suggerito da gugoXX nel primo post.
Per generarli ho usato questo programma:
open System
open System.Net
open System.Linq
open System.Threading
open System.Diagnostics
let fileWords =
use wc = new WebClient()
wc.DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt").Split([| ' '; '\t'; '\n'; '\r'; '-' |], StringSplitOptions.RemoveEmptyEntries)
let wordsToProcess = [| for i in 0..199 -> fileWords |] |> Array.concat
let main() =
for i in 0..9 do
printfn "parallel"
let sw = Stopwatch.StartNew()
let res = System.Linq.ParallelEnumerable.Count(wordsToProcess.AsParallel(), new Func<_,_>(fun s -> s.[0] = 'a'))
sw.Stop()
printfn "%i parole trovate in %ims" res sw.ElapsedMilliseconds
sw.Reset()
printfn "sequential"
sw.Start()
let res' = wordsToProcess |> Array.filter(fun s -> s.[0] = 'a') |> Array.length
sw.Stop()
printfn "%i parole trovate in %ims" res' sw.ElapsedMilliseconds
Console.ReadKey() |> ignore
do main();;
compilato in release, eseguito su un intel T7700 @ 2.40GHz, 32bit con RAM DDRII 667MHz.
Io definirei questi risultati quantomeno curiosi ;)
^TiGeRShArK^
28-05-2009, 20:46
Si vabbè ma in Java la concorrenzà è concorrenza solo perchè i thread vengono eseguiti in parallelo :) è concorrenza ma c'è poco di programmazione concorrente! Imparare la concorrenza in Java anche da zero, se si ha dimistichezza con i linguaggi in generale, è una cosa che si fa benissimo in 2-3 giorni se proprio vuoi essere esperto! :D
beh...
se non impari tutte le minuzie, tipo se e quando utilizzare le variabili volatile, la precedenza nel memory model e qualche altra cosa che sicuramente ora mi sfugge, poi ti potresti beccare bug che non muoiono nemmeno disinfestando il pc col DDT :asd:
^TiGeRShArK^
28-05-2009, 20:47
Ho visto solo ora questo thread. Vorrei postare dei dati che ritengo interessanti, raccolti con il programma in F# che segue compilato per il .NET Framework 4 beta1:
Questi dati si riferiscono al benchmark suggerito da gugoXX nel primo post.
Per generarli ho usato questo programma:
open System
open System.Net
open System.Linq
open System.Threading
open System.Diagnostics
let fileWords =
use wc = new WebClient()
wc.DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt").Split([| ' '; '\t'; '\n'; '\r'; '-' |], StringSplitOptions.RemoveEmptyEntries)
let wordsToProcess = [| for i in 0..199 -> fileWords |] |> Array.concat
let main() =
for i in 0..9 do
printfn "parallel"
let sw = Stopwatch.StartNew()
let res = System.Linq.ParallelEnumerable.Count(wordsToProcess.AsParallel(), new Func<_,_>(fun s -> s.[0] = 'a'))
sw.Stop()
printfn "%i parole trovate in %ims" res sw.ElapsedMilliseconds
sw.Reset()
printfn "sequential"
sw.Start()
let res' = wordsToProcess |> Array.filter(fun s -> s.[0] = 'a') |> Array.length
sw.Stop()
printfn "%i parole trovate in %ims" res' sw.ElapsedMilliseconds
Console.ReadKey() |> ignore
do main();;
compilato in release, eseguito su un intel T7700 @ 2.40GHz, 32bit con RAM DDRII 667MHz.
Io definirei questi risultati quantomeno curiosi ;)
beh..
o hanno fatto un lavoro della madonna col .net 4 o con F# :fagiano:
Si vabbè ma in Java la concorrenzà è concorrenza solo perchè i thread vengono eseguiti in parallelo :) è concorrenza ma c'è poco di programmazione concorrente! Imparare la concorrenza in Java anche da zero, se si ha dimistichezza con i linguaggi in generale, è una cosa che si fa benissimo in 2-3 giorni se proprio vuoi essere esperto! :D
NO, per niente :D
Magari impari le keywords, ma imparare tutti gli hack necessari a fare un programma grande sensato è un'altro paio di maniche...
Ikon O'Cluster
28-05-2009, 21:37
Io ho parlato di gestire la concorrenza non di progettare il software per la nuova versione dello shuttle O.o!!! Anche perchè non lo farei in Java nemmeno se mi pagassero 3 volte di più!
^TiGeRShArK^
28-05-2009, 21:48
già che c'ero ho provato la versione f# con il .net 3.5 e un Q6600 (@3.0 :asd: )
parallel
4112600 parole trovate in 2598ms
sequential
4112600 parole trovate in 516ms
parallel
4112600 parole trovate in 1943ms
sequential
4112600 parole trovate in 374ms
parallel
4112600 parole trovate in 1892ms
sequential
4112600 parole trovate in 374ms
parallel
4112600 parole trovate in 2811ms
sequential
4112600 parole trovate in 382ms
parallel
4112600 parole trovate in 1767ms
sequential
4112600 parole trovate in 375ms
parallel
4112600 parole trovate in 2727ms
sequential
4112600 parole trovate in 378ms
parallel
4112600 parole trovate in 2911ms
sequential
4112600 parole trovate in 382ms
parallel
4112600 parole trovate in 2078ms
sequential
4112600 parole trovate in 381ms
parallel
4112600 parole trovate in 2540ms
sequential
4112600 parole trovate in 376ms
parallel
4112600 parole trovate in 2026ms
sequential
4112600 parole trovate in 381ms
solo che mi sfugge qualcosa dato che la versione sequenziale è molto + veloce di quella parallela.. :fagiano:
P.S. spero che 'sto maledetto server exchange finisca il repair del DB prima che lo mando giù a bestemmie :muro:
!k-0t1c!
28-05-2009, 22:04
Sicuramente tutto quel che riguarda la programmazione in parallelo è altamente ottimizzato sul .NET 4, di questo avevo già avuto riscontro con altri esperimenti.
Il fatto che, tuttavia, la versione parallela sia più lenta me lo spiego solo in un caso: se ParallelEnumerable.Where crea una collection in parallelo. In questo caso il solo costo dei lock basterebbe a dare performance tremende. Alla fine bisogna considerare che quel che si sta facendo non mappa 1 a 1 ogni elemento dall'array di partenza a quello di destinazione (caso in cui la differenza di performance diventerebbe presumibilmente palese).
La differenza sta nelle funzioni di controllo per l'inizio di parola
.StartWith("a")
[0]=='a'
Che ovviamente fanno la stessa cosa, ma la seconda e' decismanete piu' prestante
Funzionale Sequentiale: 803 ms - Res:4112600
Funzionale Parallel: 240 ms - Res:4112600
Si vede che ho un quad-core? :D
^TiGeRShArK^
28-05-2009, 22:25
Io ho parlato di gestire la concorrenza non di progettare il software per la nuova versione dello shuttle O.o!!! Anche perchè non lo farei in Java nemmeno se mi pagassero 3 volte di più!
anche perchè lo vieta esplicitamente la licenza d'uso di java :D
^TiGeRShArK^
28-05-2009, 22:26
La differenza sta nelle funzioni di controllo per l'inizio di parola
.StartWith("a")
[0]=='a'
Che ovviamente fanno la stessa cosa, ma la seconda e' decismanete piu' prestante
Funzionale Sequentiale: 803 ms - Res:4112600
Funzionale Parallel: 240 ms - Res:4112600
Si vede che ho un quad-core? :D
si, ma il mio non lo posso clockare tanto che è al lavoro quindi mi accontento di un 3.0 rock solid. :O
Se l'avessi a casa ti farei vedere io :Perfido:
:D
!k-0t1c!
28-05-2009, 23:11
gugoXX, non colgo il tuo intervento. Ovviamente controllare il carattere invece che chiamare StartsWith è più prestante (anche se magari fallisce il turkey test), ma nel mio codice uso in entrambi i punti lo stesso confronto e la versione parallela non risulta più performante...
gugoXX, non colgo il tuo intervento. Ovviamente controllare il carattere invece che chiamare StartsWith è più prestante (anche se magari fallisce il turkey test), ma nel mio codice uso in entrambi i punti lo stesso confronto e la versione parallela non risulta più performante...
Intendevo dire che la differenza tra i 3000ms di prima e la tua versione da circa 400ms era nella differenza del filtro, non che ci fosse qualcosa di sbagliato, anzi.
In origine (ma anche ora direi) non voleva essere un modo piu' veloce per farequalcosa, ma piuttosto dato lo stesso lavoro confrontare le prestazioni e la complessita' di scrittura tra sequenziale e parallelo
Il come mai pero' la versione parallela in F# non risulti piu' performante proprio non lo so.
Non si puo' applicare la Filter cosi' come l'hai scritta per il sequanziale ad un Array.AsParallel() invece che ad un Array?
Intendo scrivendo proprio lo stesso statement, tranne per il AsParallel() in piu'.
wordsToProcess.AsParallel() |> Array.filter(fun s -> s.[0] = 'a') |> Array.length
Se tanto mi da tanto la AsParallel() restituisce semplicemente una IParallelEnumerable<T> sulla quale si puo' giocare tanto quanto come sulla IEnumerable<T>
!k-0t1c!
29-05-2009, 02:14
In realtà non è così semplice. Array è specifico per gli array, per gli IEnumerable<T> c'è Seq, ma Seq non accetta ParallelQuery (sto testando su .NET 4, per le versioni precedenti la cosa potrebbe essere diversa).
Vorrei tuttavia sottolineare che il codice F# che ho postato per la versione parallela è esattamente l'equivalente del tuo codice C# non solo quanto a funzionalità ma anche quanto a chiamate, infatti chiamo un extension method (che F# non risolve in questa versione a causa di un conflitto tra IEnumerable<T> e ParallelQuery<T>) come metodo statico, quale alla fine è.
^TiGeRShArK^
29-05-2009, 02:20
mmm...
alla luce di questi dati io mi sto convincendo sempre di + che ottimizzare è assolutamente inutile, anzi DANNOSO, se non fatto con cognizione di causa, ovvero con un profiler.
Giusto un paio di giorni fa ho letto un articolo su un blog della sun in cui faceva vedere come un programmatore che secondo lui "ottimizzava" il codice utilizzando uno stringbuffer per concatenare le stringhe al posto dell'operatore + in realtà otteneva risultati PEGGIORI dato che il JIT non è stupido e in realtà sostituiva la concatenazione di stringhe fatta con l'operatore + con uno stringbuilder che è + veloce di uno stringbuffer...
infatti il suggerimento (secondo me assolutamente sacrosanto) che davano era di scrivere codice quanto + stupido (dumb) possibile dato che il JIT non riesce ad ottimizzare passaggi complicati che secondo il programmatore dovrebbero incrementare le prestazioni...
riassumendo in poche parole direi che ci stiamo solo facendo seghe mentali e hce è inutile assumere a priori che che una versione di un programma sia la migliore senza prima testarla.
E questo almeno vale per l'F# e/o per il .net 4. :p
In realtà non è così semplice. Array è specifico per gli array, per gli IEnumerable<T> c'è Seq, ma Seq non accetta ParallelQuery (sto testando su .NET 4, per le versioni precedenti la cosa potrebbe essere diversa).
Vorrei tuttavia sottolineare che il codice F# che ho postato per la versione parallela è esattamente l'equivalente del tuo codice C# non solo quanto a funzionalità ma anche quanto a chiamate, infatti chiamo un extension method (che F# non risolve in questa versione a causa di un conflitto tra IEnumerable<T> e ParallelQuery<T>) come metodo statico, quale alla fine è.
Capito.
alla luce di questi dati io mi sto convincendo sempre di + che ottimizzare è assolutamente inutile, anzi DANNOSO, se non fatto con cognizione di causa, ovvero con un profiler.
Questo e' poco ma sicuro.
E infatti l'aggiunta di un semplice "AsParallel" volge proprio in questa direzione, proprio come dire:
Se c'e' qualcosa da prendere fallo, ma non cambiero' la sintassi e le strutture del pezzo di programma proprio allo scopo di raggiungere un risultato prestazionale.
E soprattutto l'ottimizzazione non va fatta a priori, ma solo laddove serve.
E infatti e' proprio la prima regola, perche' in molti ci sono cascati, ci cascano e ci cascheranno
1. You cannot tell where a program is going to spend its time. Bottlenecks occur in surprising places, so do not try to second guess and put in a speed hack until you've proven that's where the bottleneck is.
Non si puo' dire dove un programma andra' a trascorrere il suo tempo. I colli di bottiglia possono trovarsi in posti impensabili, quindi non cercare di impegnarti prima del tempo nel mettere ottimizzazioni (rifiniture non ortodosse) fino a che non hai provato che il punto critico e' proprio li'.
Le altre, per dovere di cronaca
2. Measure. Do not tune for speed until your performance analysis tool tells you which part of the code overwhelms the rest.
3. Fancy algorithms tend to run more slowly on small data sets than simple algorithms. They tend to have a large constant factor in O(n) analysis, and n is usually small. So don't get fancy unless Rule 2 indicates that n is big enough.
4. Simplify your algorithms and data structures wherever it makes sense because fancy algorithms are more difficult to implement without defects. The data structures in most programs can be built from array lists, linked lists, hash tables, and binary trees.
5. Data dominates. If you have chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.
Da cui derivano poi il decalogo maggiore e quello minore della Unix Philosophy, che e' sempre attuale ed esteso a qualsiasi campo di sviluppo software.
cdimauro
29-05-2009, 08:18
La differenza sta nelle funzioni di controllo per l'inizio di parola
.StartWith("a")
[0]=='a'
Che ovviamente fanno la stessa cosa,
Mumble. Questo non dovrebbe valere solo se la stringa abbia almeno un carattere?
ma la seconda e' decismanete piu' prestante
Dipende dal linguaggio. La chiamata a StartsWith non crea un oggetto, di cui poi bisogna disfarsi dopo l'uso, al contrario dell'operatore [].
Mumble. Questo non dovrebbe valere solo se la stringa abbia almeno un carattere?
Si' certo. Si dovrebbe fare il test del tacchino.
Ma per costruzione dai passi precedenti non abbiamo stringhe vuote (il parametro StringSplitOptions.RemoveEmptyEntries serve proprio per questo)
Dipende dal linguaggio. La chiamata a StartsWith non crea un oggetto, di cui poi bisogna disfarsi dopo l'uso, al contrario dell'operatore [].
Sisi', dicevo con cognizione per il C#, dove nel caso dell'operatore [] su stringhe non viene creato neppure un oggetto, ma il tutto viene risolto con una semplice MOV, senza neppure una chiamata a subroutine
~FullSyst3m~
29-05-2009, 11:15
Molto interessante questo 3d, mi attizza parecchio. :D
Certo che che comunque la ricchezza di librerie di C# è paurosa :eek:
Davvero simpatiche le possibilità offerte da PLINQ
ecco i risultati su un Q6600 (2.4 ghz):
Mi piacerebbe pure a me provare, ho anche io un Q6600, ma over clockato a 3.00Ghz :D
^TiGeRShArK^
29-05-2009, 14:32
Molto interessante questo 3d, mi attizza parecchio. :D
Certo che che comunque la ricchezza di librerie di C# è paurosa :eek:
Mi piacerebbe pure a me provare, ho anche io un Q6600, ma over clockato a 3.00Ghz :D
pure il mio è @3.0 ghz RS ora :p
non lo posso clockare di + perchè è quello del lavoro come dicevo :asd:
Il mio caro vecchio athlon 64 3000+ che ho a casa era un 1800mhz per i suoi primi due giorni di vita dopodichè e diventato un 2520mhz :asd:
~FullSyst3m~
29-05-2009, 15:01
pure il mio è @3.0 ghz RS ora :p
non lo posso clockare di + perchè è quello del lavoro come dicevo :asd:
Il mio caro vecchio athlon 64 3000+ che ho a casa era un 1800mhz per i suoi primi due giorni di vita dopodichè e diventato un 2520mhz :asd:
Tu fai oc ai processori dei computer del lavoro? :D
Il mio appena comprato è diventato un 3.0Ghz per core. Quando avrò una scheda madre migliore vedrò di portarlo a 3.8 :D
^TiGeRShArK^
29-05-2009, 15:03
Tu fai oc ai processori dei computer del lavoro? :D
Il mio appena comprato è diventato un 3.0Ghz per core. Quando avrò una scheda madre migliore vedrò di portarlo a 3.8 :D
e certo :O
ci devo lavorare io me lo clocko come mi pare e piace :p
l'importante è che sia RS :D
~FullSyst3m~
29-05-2009, 15:16
e certo :O
ci devo lavorare io me lo clocko come mi pare e piace :p
l'importante è che sia RS :D
RS?
cdimauro
02-06-2009, 07:07
Rock Solid
~FullSyst3m~
02-06-2009, 09:19
Rock Solid
Thanks.
VS2010, con il Framework4 di prossima uscita sul mercato.
Stanno spingendo tanto in questa direzione
http://img386.imageshack.us/img386/3506/vs2010parallel.tif
Un oretta di lezione.
http://channel9.msdn.com/pdc2008/TL26/
Cool!
tomminno
02-06-2009, 19:47
Giusto un paio di giorni fa ho letto un articolo su un blog della sun in cui faceva vedere come un programmatore che secondo lui "ottimizzava" il codice utilizzando uno stringbuffer per concatenare le stringhe al posto dell'operatore + in realtà otteneva risultati PEGGIORI dato che il JIT non è stupido e in realtà sostituiva la concatenazione di stringhe fatta con l'operatore + con uno stringbuilder che è + veloce di uno stringbuffer...
Sarà magari valido per Java, ma almeno per il .NET 3.5 usare l'operatore + o uno StringBuilder la differenza c'è eccome.
!k-0t1c!
02-06-2009, 20:32
Sarà magari valido per Java, ma almeno per il .NET 3.5 usare l'operatore + o uno StringBuilder la differenza c'è eccome.
Confermo. Su molte concatenazioni la differenza può manifestarsi drasticamente con StringBuilder più veloce anche di 40 volte rispetto all'operatore +
Albitexm
02-06-2009, 23:33
VS2010, con il Framework4 di prossima uscita sul mercato.
Stanno spingendo tanto in questa direzione
Un oretta di lezione.
http://channel9.msdn.com/pdc2008/TL26/
Cool!
Daccordo. Con il nuovo Visual Studio 2010 e il .Net Framework 4, le librerie per le versioni 2008 oltre agli altri strumenti per altre piattaforme, possiamo dire che ultimamente stanno circolando molti mezzi per sfruttare le archittetture multicore. Ma io mi domando: le CPU dualcore è già qualche anno che sono sul mercato e oggi sono alla portata di tutti anche i quadcore.
Come mai solo adesso si inizia ad avere a disposizione degli strumenti multithreading? E prima i programmi come erano scritti?
Forse avevamo dei PC con caratteristiche hardware sfruttate solo parzialmente?
Era forse vero che il 90% delle applicazioni commerciali non sfruttavano tutti i core della macchina?
Daccordo. Con il nuovo Visual Studio 2010 e il .Net Framework 4, le librerie per le versioni 2008 oltre agli altri strumenti per altre piattaforme, possiamo dire che ultimamente stanno circolando molti mezzi per sfruttare le archittetture multicore. Ma io mi domando: le CPU dualcore è già qualche anno che sono sul mercato e oggi sono alla portata di tutti anche i quadcore.
Come mai solo adesso si inizia ad avere a disposizione degli strumenti multithreading? E prima i programmi come erano scritti?
Forse avevamo dei PC con caratteristiche hardware sfruttate solo parzialmente?
Era forse vero che il 90% delle applicazioni commerciali non sfruttavano tutti i core della macchina?
I programmi erano scritti sfruttando cio' che si aveva, ovvero i Thread.
Sempre se lo si faceva.
E ci sono tanti esempi.
Oggi si puo' usare altro, e si puo' raggiungere il risultato piu' comodamente lasciando tempo per concentrarsi su altri aspetti.
!k-0t1c!
02-06-2009, 23:44
CreateThread (http://msdn.microsoft.com/en-us/library/ms682453(VS.85).aspx) esiste su Windows da una vita. Tutte queste librerie non offrono niente di nuovo a livello di sistema. Aggiungono semplicemente astrazioni, semplificano l'interazione tra threads (meglio così che usare le critical sections) etc, ma di fatto sono solo librerie. Tutte le API necessarie esistevano già. Certamente scrivere oggi Array.Parallel.map mi costa molto meno tempo e mi da molti meno problemi che fare l'equivalente 2anni fa e questo fa sperare che l'adozione di algoritmi paralleli diventi più diffusa, ma non sempre è cosa necessaria.
Ad ogni modo bisogna tenere presente che con il calcolo in parallelo si aprono le porte a una nuova classe intera di bugs da cui nemmeno queste librerie spesso proteggono e dunque le cose migliorano, ma bisogna essere cauti.
Ad ogni modo bisogna tenere presente che con il calcolo in parallelo si aprono le porte a una nuova classe intera di bugs da cui nemmeno queste librerie spesso proteggono e dunque le cose migliorano, ma bisogna essere cauti.
Giusto.
Allo scopo segnalo la presenza del
ParallelDebugger
integrato in VS2010 che ho potuto vedere oggi in azione per la prima volta.
Anche perche' debuggare i Thread con gli strumenti di un tempo e' una pena...
Albitexm
03-06-2009, 21:59
CreateThread (http://msdn.microsoft.com/en-us/library/ms682453(VS.85).aspx) esiste su Windows da una vita. Tutte queste librerie non offrono niente di nuovo a livello di sistema. Aggiungono semplicemente astrazioni, semplificano l'interazione tra threads (meglio così che usare le critical sections) etc, ma di fatto sono solo librerie. Tutte le API necessarie esistevano già. :read:
Ohh.. ecco, è a questo che volevo arrivare.
La tua condivisibile affermazione, smentisce un'altra affermazione che ho letto in più post e siti: " le librerie multithreading aprono un nuovo modo di programmazione avanzatissimo..", o "ultima frontiera della programmazione" e
"questa nuova metodologià di programmazione avanzata".
Io di così avanzattissimo o nuovissimo non trovo molto.
Anzi per me dovevano arrivare un po' prima..
cdimauro
03-06-2009, 22:19
http://www.amyresource.it/AGI/AmigaNews/Traduzioni/trad69.html
http://www.amyresource.it/AGI/AmigaNews/Traduzioni/trad72.html
Le librerie per parallelismo esistono da molto tempo, le prime gia' negli anni 50.
Non venivano usate in ambiti commerciali per prodotti per PC perche' ovviamente non sarebbero state sfruttate.
Avrebbero appesantito inutilmente la scrittura del codice perche' era piu' complesso scrivere codice MultiThreading, e avrebbero rallentato addiruttura l'esecuzione, essendo che iniettare il parallelismo su una macchina con un singolo processore (o core) e' addirittura controproducente.
Cio' non toglie che per applicazioni commerciali di particolari tipi non fossero usate. Ci sono tantissimi esempi, anche per prodotti per PC.
Recentemente le possibilita' del MultiCore si sono aperte al grande pubblico, essendo che praticamente tutte le macchine dispongono di 2 o piu' core.
E' quindi forte la pressione per la migrazione al MultiProcess anche per prodotti per PC.
Ma un conto e' scrivere codice a mano per il supporto multiprocess, un conto e' usare librerie che incapsulano e nascondono la complessita' e i problemi.
I.E. un conto e' ordinare un array scrivendo
.OrderBy()
sapendo che verra' eseguita in parallelo su quanti piu' core ho a disposizione.
Un conto e' invece scrivere tutto a mano, con strumenti che gia' si avevano a disposizione (Thread), per poter ottenere le stesso risultato.
L'overherad di scrittura del codice e di debug in questo ultimo caso e' talmente alto che spesso lo si tralasciava, e si propendeva per una semplice soluzione Single-Core.
A me sembra che il "problema" parallelismo sia sottovalutato dalle librerie per il calcolo parallelo. Eseguire due somme in concorso è un'assoluta banalità. In generale se non esistono mutazioni di stato non c'è un problema di concorrenza.
I contesti in cui il parallelismo diventa interessante sono quelli in cui gli stati abbondano e alcuni di questi condizionano l'accessibilità di altri da parte di un sottoinsieme dei flussi di controllo che concorrono all'esecuzione.
Prendiamo il caso del controllo di testi nel secondo post e iniziamo a dire che l'operazione può essere avviata, sospesa, annullata da una pluralità di flussi concorrenti. Che soluzione offre PLINQ a questo problema?
A me sembra che il "problema" parallelismo sia sottovalutato dalle librerie per il calcolo parallelo. Eseguire due somme in concorso è un'assoluta banalità. In generale se non esistono mutazioni di stato non c'è un problema di concorrenza.
I contesti in cui il parallelismo diventa interessante sono quelli in cui gli stati abbondano e alcuni di questi condizionano l'accessibilità di altri da parte di un sottoinsieme dei flussi di controllo che concorrono all'esecuzione.
Prendiamo il caso del controllo di testi nel secondo post e iniziamo a dire che l'operazione può essere avviata, sospesa, annullata da una pluralità di flussi concorrenti. Che soluzione offre PLINQ a questo problema?
Se non ho capito male la domanda, la risposta e' nelle classi
Task e Future (Che sono poi Task che possono restituire un output)
Ovvero 2 strutture che si appoggiano al ThreadPool, la cui gestione pero' e' demandata al framework.
Un esempio potrebbe pero' aiutare, perche' non ho afferrato bene la concorrenzialita' del controllo.
Se Task e Future sono gli stessi di Java - e dovrebbero perchè sono note forme risalenti all'antichità - allora hanno l'affascinante proprietà di non risolvere nulla.
Per la concorrenza del controllo basta semplicemente immaginare che l'esecuzione di quella parte di programma possa ricevere una qualsiasi serie di ordini "avvia", "sospendi", "annulla".
E badiamo che i problemi concreti iniziano dopo che il flusso di esecuzione del modulo è in grado di essere avviato, sospeso e annullato.
Perchè chi avvia, sospende e annulla il modulo è solitamente interessato a ricevere una notifica dell'avvenuto avvio, sospensione, annullamento.
Per mettersi nell'ottica di quello che è problematico nella concorrenza potremmo anche immaginare che quel programma che scarica e analizza il testo abbia dei controlli grafici, tre pulsanti "avvia", "annulla", "sospendi" ognuno dei quali sia gestito da un utente diverso.
Che succede se il modulo è in esecuzione e tu sospendi, io annullo e lui avvia, posto che tutti e tre desideriamo ricevere una notifica dell'avvenuta esecuzione dell'operazione richiesta?
Se Task e Future sono gli stessi di Java - e dovrebbero perchè sono note forme risalenti all'antichità - allora hanno l'affascinante proprietà di non risolvere nulla.
Per la concorrenza del controllo basta semplicemente immaginare che l'esecuzione di quella parte di programma possa ricevere una qualsiasi serie di ordini "avvia", "sospendi", "annulla".
E badiamo che i problemi concreti iniziano dopo che il flusso di esecuzione del modulo è in grado di essere avviato, sospeso e annullato.
Perchè chi avvia, sospende e annulla il modulo è solitamente interessato a ricevere una notifica dell'avvenuto avvio, sospensione, annullamento.
Per mettersi nell'ottica di quello che è problematico nella concorrenza potremmo anche immaginare che quel programma che scarica e analizza il testo abbia dei controlli grafici, tre pulsanti "avvia", "annulla", "sospendi" ognuno dei quali sia gestito da un utente diverso.
Che succede se il modulo è in esecuzione e tu sospendi, io annullo e lui avvia, posto che tutti e tre desideriamo ricevere una notifica dell'avvenuta esecuzione dell'operazione richiesta?
Non ho capito bene l'esempio.
Cosa vorresti che accadesse?
Ferma l'esecuzione dopo cinque secondi.
Non so se ho capito.
static void Main(string[] args)
{
//Console.WriteLine("Download");
//string text = new WebClient().DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt"); // Great Expectations
//File.WriteAllText(@"C:\temp\grexp10.txt", text);
string text = File.ReadAllText(@"C:\temp\grexp10.txt");
string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);
List<string> array = new List<string>();
Console.WriteLine("Prepare");
for (int t = 0; t < 200; t++)
{
array.AddRange(words);
}
int totalLength = array.Count;
Console.WriteLine("Start - Numero di parole che iniziano con 'a', tra un elenco di {0} parole",totalLength);
Stopwatch watch=new Stopwatch();
Future<int> counter = Future<int>.Create(() =>
array.AsParallel().Count(work => work[0]=='a')
);
int ToWait = 1000;
Console.WriteLine("Waiting for {0}ms",ToWait);
Thread.Sleep(ToWait);
counter.Cancel();
Console.WriteLine("Canceled");
Console.WriteLine("Completed? = {0}", counter.IsCompleted);
if (counter.IsCompleted == true)
{
Console.WriteLine("As is completed, the result was: {0}", counter.Value);
}
Console.ReadKey();
}
In questo esempio lancio un Task (Future, ho bisogno di un risultato) che esegue un conteggio in parallelo.
Aspetto tot secondi
e poi lo cancello
Se nel frattempo il task era completato, allora scrivo il risultato, altrimenti non lo scrivo.
Se aspetto 5 secondi, c''e tempo per il task di completare, e l'output e':
Prepare
Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
Waiting for 5000ms
Canceled
Completed? = True
As is completed, the result was: 4112600
Se invece aspetto 1 secondo, non c'e' sufficiente tempo per il task di completare e l'output e'
Prepare
Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
Waiting for 1000ms
Canceled
Completed? = False
Ma questo mi sembra piu' un problema di Threading che di calcolo parallelo.
Immagina ora che il tuo programma non si interrompa dopo 5 secondi ma che debba interrompersi per effetto dell'invocazione di una funzione annulla() e che chi invoca tale funzione voglia sapere quando l'esecuzione del calcolo è effettivamente stata interrotta.
Dopodichè aggiungi una funzione avvia() che avvia il calcolo e, come annulla(), notifica all'invocazione l'avvenuto inizio della computazione.
Infine ci metti un bel sospendi() che sospende il calcolo e notifica l'avvenuta sospensione.
E' un problema di calcolo parallelo esattamente come lo è la suddivisione di una computazione in parti eseguibili in concorso solo che qui le parti comunicano tra loro.
Cioè se prima hai un flusso che esegue una somma da 1 a 10, un flusso che fa la somma da 10 a 20, un flusso che va da 20 a 30 eccetera ora hai un flusso che esegue la somma, uno che la interrompe, uno che la avvia e uno che la sospende.
Non ho capito.
Mi stai chiedendo come fare per sospendere ed eventualmente far ripartire un calcolo parallelo?
Sì, ti sto chiedendo di avviare, sospendere o annullare un calcolo parallelo, posto che avvio, sospensione e annullamento sono eseguito in concorso con il calcolo.
Ammetto per pigrizia :D. Non conosco LINQ e quindi vorrei vedere senza doverlo studiare quali benefici apporti alle computazioni parallele.
Perchè se si tratta semplicemente di rendere parallela una sequenza di fibonacci - per dirne una - per me è Fuffa 2.0
Mi raccomando le notifiche. Se invoco la funzione avvia devo anche sapere quando effettivamente il cacolo è iniziato, se "stoppo" devo sapere quando si ferma e se lo annullo devo sapere quando è terminato.
Grazie :D
Sì, ti sto chiedendo di avviare, sospendere o annullare un calcolo parallelo, posto che avvio, sospensione e annullamento sono eseguito in concorso con il calcolo.
Ammetto per pigrizia :D. Non conosco LINQ e quindi vorrei vedere senza doverlo studiare quali benefici apporti alle computazioni parallele.
Perchè se si tratta semplicemente di rendere parallela una sequenza di fibonacci - per dirne una - per me è Fuffa 2.0
Le sincronizzazioni dall'esterno verso i task, ma anche fra i diversi task si fanno mediante un oggetto chiamato ParallelState e TaskManager, che comunque non li ho mai dovuti toccare.
Oppure per segnali semplici come interruzioni e partenze ancora il ManualResetEvent, utile appunto per sospendere e riprendere Thread, ma anche ora Task.
Ma fuffa perche'?
public void SequencialRayTracer(Scene scene, int[] rgb)
{
for (int y = 0; y < Height; y++)
{
int Stride = y * Width;
Camera = scene.Camera;
for (int x = 0; x < Width; x++)
{
Color color = TraceRay(new Ray(camera.Pos, GetPoint(x,y,camera)));
rgb[x + Stride] = color.ToInt();
}
}
}
public void ParallelRayTracer(Scene scene, int[] rgb)
{
Parellel.For(0, Height, y =>
{
int Stride = y * Width;
Camera = scene.Camera;
for (int x = 0; x < Width; x++)
{
Color color = TraceRay(new Ray(camera.Pos, GetPoint(x, y, camera)));
rgb[x + Stride] = color.ToInt();
}
});
}
Quello a cui si vorrebbe tendere e' un modo non troppo complesso di trattare quelli che prima era una stesura sequenziale in quella che e' una stesura parallela, senza doversi accartocciare tra Thread, ThreadPool, esecutori e i loro rispettivi debug.
Qui per esempio si passa da una stesura ad un altra praticamente senza colpo ferire.
Il concetto del calcolo parallelo e' quello di riuscire a costruire un algoritmo divisibile in unita' di esecuzione indipendenti.
Se per te il problema e' il passaggio di informazione tra queste unita', allora mi sa che il problema non e' diviso correttamente, oppure non si presta ad essere parallelizzato.
Mi raccomando le notifiche. Se invoco la funzione avvia devo anche sapere quando effettivamente il cacolo è iniziato, se "stoppo" devo sapere quando si ferma e se lo annullo devo sapere quando è terminato.
Grazie :D
Prego, ma per te "Quando" cosa significa?
Quanto tempo e' passato dall'inizio dell'esecuzione?
Immagina ora che il tuo programma non si interrompa dopo 5 secondi ma che debba interrompersi per effetto dell'invocazione di una funzione annulla() e che chi invoca tale funzione voglia sapere quando l'esecuzione del calcolo è effettivamente stata interrotta.
Dopodichè aggiungi una funzione avvia() che avvia il calcolo e, come annulla(), notifica all'invocazione l'avvenuto inizio della computazione.
Infine ci metti un bel sospendi() che sospende il calcolo e notifica l'avvenuta sospensione.
E' un problema di calcolo parallelo esattamente come lo è la suddivisione di una computazione in parti eseguibili in concorso solo che qui le parti comunicano tra loro.
Cioè se prima hai un flusso che esegue una somma da 1 a 10, un flusso che fa la somma da 10 a 20, un flusso che va da 20 a 30 eccetera ora hai un flusso che esegue la somma, uno che la interrompe, uno che la avvia e uno che la sospende.
Non sono d'accordo.
Questo è un problema di obiettivi, non c'entra niente col calcolo parallelo.
Solo perchè con quest'ultimo diventa uno scenario possibile non vuol dire che si debba supportare, sarebbe come accettare che una classe prende un pointer e lo setta a NULL, prima che un'altra provi ad usarlo:
Semplicemente non ha senso, e va evitato.
Io mi comporterei così, creando una scaletta di priorità:
avvia < esecuzione/pausa < annulla
Quindi, se uno prova ad avviare o mettere in pausa un thread annullato -> avviso di errore
se provi ad avviare un thread in esecuzione -> avviso di errore
D'altra parte che vuol dire la frase "avvia il thread mentre lo annulli?" :asd:
D'altra parte che vuol dire la frase "avvia il thread mentre lo annulli?" :asd:
E' uno scherzo, vero?
E' uno scherzo, vero?
No. Recati che ne so alla TV e premi 1 mentre premi spegni, che risultato ti attendi?
Non è che un thread non lo puoi toccare e allora può fare 2 cose insieme eh :D
Questo per dire, che in ossequio alla frase che hai in firma mi sembra che la stai facendo troppo complicata :D
E' chiaro come il sole che il risultato è indeterminato. Per via del concorso tra tre flussi di controllo. Dito uno, dito due, televisione. Il dito che arriva prima passa al secondo round e compete con lo stato della televisione.
Non "un thread" ma tre thread. Se il flusso di controllo fosse uno solo non si potrebbe parlare di "mentre". Non c'è "mentre" nella programmazione sequenziale ( = 1 solo flusso di controllo): c'è prima o dopo e basta.
La questione del concorso tra mutazioni di uno stato - che è calcolo parallelo perchè più computazioni sono eseguite nello stesso istante da parte ovviamente di più flussi di controllo ognuno dei quali gestito da un proprio processo o da un proprio thread - ha tante soluzioni ideali.
Una, ad esempio, è l'ordinamento delle invocazioni concorrenti.
Per me non è un problema secondario e io scrivo gestionali che non mi sembra esattamente un campo di nicchia. Ogni volta che accedi ad una base dati hai un problema di mutazioni di stato concorrenti, ogni volta che mandi un'e-mail, che scarichi un aggiornamento, ogni volta che salvi lo stato dell'applicazione hai un problema di mutazioni di stato concorrenti.
E' per questo che mi interessa vedere cosa sia in grado di fare LINQ. Se mi offre Future e Task grazie ma ce li avevo in Java sei anni fa e non mi hanno reso la vita più godibile.
E' chiaro come il sole che il risultato è indeterminato. Per via del concorso tra tre flussi di controllo. Dito uno, dito due, televisione. Il dito che arriva prima passa al secondo round e compete con lo stato della televisione.
Non "un thread" ma tre thread. Se il flusso di controllo fosse uno solo non si potrebbe parlare di "mentre". Non c'è "mentre" nella programmazione sequenziale ( = 1 solo flusso di controllo): c'è prima o dopo e basta.
La questione del concorso tra mutazioni di uno stato - che è calcolo parallelo perchè più computazioni sono eseguite nello stesso istante da parte ovviamente di più flussi di controllo ognuno dei quali gestito da un proprio processo o da un proprio thread - ha tante soluzioni ideali.
Una, ad esempio, è l'ordinamento delle invocazioni concorrenti.
Per me non è un problema secondario e io scrivo gestionali che non mi sembra esattamente un campo di nicchia. Ogni volta che accedi ad una base dati hai un problema di mutazioni di stato concorrenti, ogni volta che mandi un'e-mail, che scarichi un aggiornamento, ogni volta che salvi lo stato dell'applicazione hai un problema di mutazioni di stato concorrenti.
E' per questo che mi interessa vedere cosa sia in grado di fare LINQ. Se mi offre Future e Task grazie ma ce li avevo in Java sei anni fa e non mi hanno reso la vita più godibile.
Mi sta che stai provando a vedere lo strumento sbagliato.
Per risolvere il tuo problema dovresti provare a dare un occhiata a WF, Windows Workflow, intriso di macchine a stati e transazioni.
Ma che non e' calcolo parallelo.
Il concetto di PLinq e della CTP e' quello di prendere collezioni di lavori simili o indipendenti e parallelizzarle in modo piu' semplice che usando a mano gli strumenti Thread e ThreadPool.
Scrivendo anche molto meno.
A me sembra che il "problema" parallelismo sia sottovalutato dalle librerie per il calcolo parallelo. Eseguire due somme in concorso è un'assoluta banalità. In generale se non esistono mutazioni di stato non c'è un problema di concorrenza.
Parallelismo e concorrenza sono due cose un po' differenti. Automatizzare il parallelismo in assenza di effetti collaterali e' piu' facile, ed e' per quello si tende a fare cosi'. Questo peraltro permette di appiattire parallelizzare automaticamente operazioni piu' complesse, come ad esempio l'ordinamento di un array.
I contesti in cui il parallelismo diventa interessante sono quelli in cui gli stati abbondano e alcuni di questi condizionano l'accessibilità di altri da parte di un sottoinsieme dei flussi di controllo che concorrono all'esecuzione.
Nel tuo caso probabilmente sarebbe piu' utile un modello ad eventi come un linguaggio di workflow, o comunque qualcosa di basato su PN o StateChart (la cui validazione e' tra l'altro abbastanza fattibile).
Parallelismo e concorrenza sono due cose un po' differenti.
Forse il problema è questo. Io li ho sempre intesi come sinonimi. Vabbè, comunque ho avuto le mie risposte :). Grazie.
Albitexm
07-07-2009, 02:45
Ho un po' di confusione sull'argomento.
Ce cosa è esattamente "PLINQ" e che differenza c'è tra PLINQ e Task Parallel Library di "Microsoft Parallel Exstensions" ?
Esistono altre librerie odierne per parallelismo?
Nella discussione fate riferimento al C# ma nella documentazione di Task Parallel Library vedo che le primitive sono disponibili anche in C++ e VB. Ho capito male io?
Come mai in MSDN Library di Visual C++ Express vedo riferimenti alla funzione Lambada e altre su parallelismo che in teoria dovrebbero essere beta?
Credo di avere fatto una grande confusione a riguardo. Qualcuno è in grado di chiarirmi e mettermi un po' in ordine le idee su questo argomento?
Ho un po' di confusione sull'argomento.
Ce cosa è esattamente "PLINQ" e che differenza c'è tra PLINQ e Task Parallel Library di "Microsoft Parallel Exstensions" ?
Esistono altre librerie odierne per parallelismo?
Nella discussione fate riferimento al C# ma nella documentazione di Task Parallel Library vedo che le primitive sono disponibili anche in C++ e VB. Ho capito male io?
PLINQ era il nome della TPL fino a giugno 2008.
Ora per PLINQ si intende la sola scrittura funzionale (AsParallel()), ed e' quindi un sottoinsieme della TPL.
Altre librerie esistono, non per C#, gia' dalla notte dei tempi per C e C++ (ma anche per tantissimi altri linguaggi), ma sono ovviamente non-standard nel senso che non fanno parte nativamente del linguaggio, vengono utilizzate sotto forma di #Pragma.
Come mai in MSDN Library di Visual C++ Express vedo riferimenti alla funzione Lambda e altre su parallelismo che in teoria dovrebbero essere beta?
Se non ho capito male c'e' solo un'incomprensione di linguaggio.
Lambda qui sta per "Lambda Calculus", un sistema matematico sviluppato per analizzare le funzioni, le loro applicazioni e in particolare la ricorsione.
http://it.wikipedia.org/wiki/Lambda_calcolo
Non ha nulla a che fare con la dicitura "Alfa" e "Beta" per il rilascio del ciclo dei software...
Si chiamano proprio "Funzioni Lambda"
Peraltro non sono piu' in Beta, le lambda function sono gia' parte del Framework3.5
Neppure la TPL/PLinq e' in versione Beta ma gia' CTP da giugno 2008, ed ulteriormente CTP come parte integrale del Framework4.0, che gia' gira per la comunita' degli sviluppatori, alla ricerca degli ultimi bachi, ma essenzialmente funzionante e probabilmente identico alla definitiva.
Albitexm
11-07-2009, 01:12
PLINQ era il nome della TPL fino a giugno 2008.
Ora per PLINQ si intende la sola scrittura funzionale (AsParallel()), ed e' quindi ...
thanks :)
malocchio
16-07-2009, 15:54
Topic dell'anno gente :read:
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.