Multithread langzamer dan singlethread?

[Verwijderd]

Hallo,

Als test voor mezelf om te kijken of ik multi-threading goed kon implementeren heb ik een klein programma geschreven.

Het programma genereert een hoop random reeksen van 0'n en 1'n. De kans op een 1 is p, op een 0 is 1-p. Deze reeksen worden opgedeeld is series van 0'n en 1'n. Bijvoorbeeld 11110001101 heeft 5 deelseries: 1111, 000, 11, 0 en 1. Vervolgens wordt er gekeken naar de gemiddelde lengte van de tweede deelserie.

Een simpel rekensommetje leert dat gegeven genoeg reeksen dat ongeveer 2 is (ongeacht van p).

Wat ik nu probeer is de computer dit zo snel mogelijk uit te laten rekenen voor veel reeksen. In de eerste instantie had ik een singlethread implementatie die redelijk snel was, maar ik dacht dat als ik de reeksen verdeel over meerdere threads (stel t threads) het sneller zou moeten gaan met een factor t. Helaas is dit niet het geval en is het zelfs veel langzamer dan in het singlethread geval.

Weet een van jullie wat er mis gaat?

Dit is mijn code:

C++:

/**
  * Dit is een simulatie van een reeks 0'n en 1'n.
  * Er wordt geteld hoe lang de tweede deelreeks gemiddeld is gegeven de kans op een 1 p is.
  * (eg in de reeks 1110001 is de lengte van de tweede deelreeks gelijk aan 3)
  */

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <vector>

#include <pthread.h>

using namespace std;

int i, p, n;
vector <int> c;

void * run (void * _x)
{
    int x = *(int*) _x;
    for (int i = x; i < n; i++)
    {
        if (c[i] > 0)
            return NULL;
        c[i] = 0;
        bool run = true;
        bool last;
        int k = rand() % 10000;
        if (k > p)
            last = true;
        else
            last = false;
        while (run) {
            k = rand() % 10000;
            if (k > p) {
                if (!last)
                    run = false;
            } else {
                if (last)
                    run = false;
            }
        }
        last = !last;
        run = true;
        while (run) {
            c[i]++;
            k = rand() % 10000;
            if (k > p) {
                if (!last)
                    run = false;
            } else {
                if (last)
                    run = false;
            }
        }
    }
}

int main (int argc, char *argv[])
{
    cout.setf(ios::fixed);
    cout.precision(9);
    
    // Laden van alle data
    int s, t;
    if (argc == 5) {
        stringstream buffer;
        buffer << argv[1] << ' ' << argv[2] << ' ' << argv[3] << ' ' << argv[4];
        buffer >> p >> n >> s >> t;
    } else {
        p = 0;
        n = 0;
        s = 0;
        t = 0;
    }
    while (p < 0 || 10000 < p || n < 1 || 1000000 < n || s < 0 || t < 0) {
        cout << "Select a (integer) value for p [0-10000]: ";
        cin >> p;
        cout << "Select a (integer) value for n [1-1000000]: ";
        cin >> n;
        cout << "Select a (integer) value for s [>0]: ";
        cin >> s;
        cout << "Select a (integer) value for t [>0]: ";
        cin >> t;
    }

    // De test
    c.resize(n);
    pthread_t threads[t];
    i = 0;
    srand(s);
    int pt = n / t;
    int * px = NULL;
    for (int i = 0; i < t; i++)
    {
        px = new int;
        (*px) = pt * i;
        pthread_create(&threads[i], NULL, run, px);
    }
    for (int i = 0; i < t; i++)
        pthread_join(threads[i], NULL);

    // Verwerken van alle data
    double avg = 0;
    for (int i = 0; i < n; i++)
        avg += c[i];
    avg = avg/n;
    double var = 0;
    for (int i = 0; i < n; i++)
        var += pow((c[i] - avg), 2);
    var = var/n;
    cout << "Mean: " << avg << " Variance: " << var << endl;

    return 0;
}

[MLM]

regel 23, je loopt tot n (einde van de hele serie)
je wilt loopen tot x + pt (einde van het deelprobleem)

als jij nu 10 threads start, doet de eerste thread alles, de 2e 9/10e, de 3e 8/10e etc, je komt dus uit op ruim 5x zoveel werk in totaal daarnaast is n vrij klein (max 1M), met redelijke parallellisatie (2-8 gemiddelde nieuwe PC) heb je dus slechts ~125k iteraties per thread (dat is niet veel met zo'n simpel probleem)

je hebt daarnaast een enorme working set (c), die je alleen gaat gebruiken voor sommeren aan het eind, sommeer dan gewoon in een local per thread, en schrijf die weg per thread (dus ipv n ints, heb je dan t ints nodig)

(oh wacht, die variance gaat dan moeilijker worden, maar als je de theoretische uitkomst al hebt (2), dan kan je die ook lokaal oplossen en sommeren, maar dan moet je eens profilen, er is best kans dat n pow's de meeste tijd in je programma opeten

[ Voor 72% gewijzigd door MLM op 08-10-2011 15:10 ]

[Verwijderd]

Maar is het niet zo dat de regel daaronder dat afvangt? Zodra een thread aankomt bij een blok dat al gedaan is stopt hij ermee?

Heel erg bedankt voor de verdere tips om te optimaliseren! Maar het gaat echt over het test-gedeelte, ik vind het vreemd dat dat langer duurt voor meerdere threads. Zou dat kunnen liggen aan dat c in de global scope zit? Of mag dit niet uitmaken?

[ Voor 49% gewijzigd door Verwijderd op 08-10-2011 15:17 ]

[Knutselsmurf]

Ik heb een dergelijk probleem ook eens eerder gehad, maar dan in Delphi. Daar was het probleem, dat de random()-functie je threads blockt. Dit betekent dat alle aanroepen naar de random()-functie op elkaar staan te wachten.

Uiteindelijk heb ik dit opgelost door een variant op de random() te vinden die wel geschikt is voor meerder threads

[MLM]

c in de global scope maakt niet uit, STL containers zijn threadsafe, zolang je de collectie niet bewerkt (items in de container zelf bewerken is daar onafhankelijk van, dat kan al dan niet threadsafe zijn afhankelijk van het type).

wat knutselsmurf zegt kan wel eens het probleem zijn, wederom ga ik zeggen, heb je al geprofiled zodat je weet waar je cycles zitten?

[Verwijderd]

Heel erg bedankt! Het was inderdaad de rand() functie. Best wel een stomme fout achteraf, natuurlijk schrijft die altijd naar hetzelfde geheugen waardoor je een enorme opstopping krijgt. Met rand_r was het te fixen.

Dit is de uiteindelijke code:

C++:

/**
  * Dit is een simulatie van een reeks 0'n en 1'n.
  * Er wordt geteld hoe groot de tweede deelreeks gemiddeld is gegeven de kans op een 1 p is.
  * (eg in de reeks 1110001 is de tweede deelreeks gelijk aan 3)
  */

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>

#include <pthread.h>

using namespace std;

int p, n;
vector <int> c;

struct arg {
    int x;
    unsigned int seed;
};

void * run (void * _para)
{
    arg para = *(arg*) _para;
    for (int i = para.x; i < n; i++)
    {
        if (c[i] > 0)
            return NULL;
        bool run = true;
        bool last;
        double temp = rand_r(&para.seed);
        int k = 10000 * temp / RAND_MAX;
        if (k > p)
            last = true;
        else
            last = false;
        while (run) {
            temp = rand_r(&para.seed);
            k = temp * 10000 / RAND_MAX;
            if (k > p) {
                if (!last)
                    run = false;
            } else {
                if (last)
                    run = false;
            }
        }
        last = !last;
        run = true;
        while (run) {
            c[i]++;
            temp = rand_r(&para.seed);
            k = temp * 10000 / RAND_MAX;
            if (k > p) {
                if (!last)
                    run = false;
            } else {
                if (last)
                    run = false;
            }
        }
    }
}

int main (int argc, char *argv[])
{
    cout.setf(ios::fixed);
    cout.precision(9);
    
    // Laden van alle data
    int s, t;
    if (argc == 5) {
        stringstream buffer;
        buffer << argv[1] << ' ' << argv[2] << ' ' << argv[3] << ' ' << argv[4];
        buffer >> p >> n >> s >> t;
    } else {
        p = 0;
        n = 0;
        s = 0;
        t = 0;
    }
    while (p < 0 || 10000 < p || n < 1 || 1000000 < n || s < 0 || t < 0) {
        cout << "Select a (integer) value for p [0-10000]: ";
        cin >> p;
        cout << "Select a (integer) value for n [1-1000000]: ";
        cin >> n;
        cout << "Select a (integer) value for s [>0]: ";
        cin >> s;
        cout << "Select a (integer) value for t [>0]: ";
        cin >> t;
    }

    // De test
    c.resize(n);
    pthread_t threads[t];
    srand(s);
    int pt = n / t;
    arg * para = NULL;
    for (int i = 0; i < t; i++)
    {
        para = new arg;
        (*para).x = pt * i;
        (*para).seed = rand();
        pthread_create(&threads[i], NULL, run, para);
    }
    for (int i = 0; i < t; i++)
        pthread_join(threads[i], NULL);

    // Verwerken van alle data
    double avg = 0;
    for (int i = 0; i < n; i++)
        avg += c[i];
    avg = avg/n;
    double var = 0;
    for (int i = 0; i < n; i++)
        var += pow((c[i] - avg), 2);
    var = var/n;
    cout << "Mean: " << avg << " Variance: " << var << endl;

    return 0;
}

[liquid_ice]

Ook met je fix ga je nog steeds te ver in je run functie, regel 30:

code:

    for (int i = para.x; i < n; i++)

n is de gehele reeks toch?
moet je um niet tot pt laten lopen?

Hoeveel performance verschil zit er nu tussen de single en milti-threaded applicatie?

Wat voor systeem run je het op? en hoeveel threads gebruik je?
Als je namelijk een simpele single-core CPU hebt kan je CPU zelf toch niet meerdere dingen tegelijk doen, dan kan je lichte multithreading nog wel gebruiken om bottlenecks op te voorkomen. Denk aan HDD, netwerk of UI bijv, maar daar doet jou app niet veel mee.

Het maken van een nieuwe thread is vrij duur, ook is de contexts switches tussen threads is best een stevige overhead.

Ik heb een keer testen gedaan op een veel complexer systeem dat veel met USB, netwerk en HDD deed op een dualcore CPU. We kwamen erachter dat meer dan 4 threads geen nut had.

[MLM]

sidenote: pow(x, 2) == x * x, bespaart veel cycles

[Verwijderd]

liquid_ice schreef op zondag 09 oktober 2011 @ 10:26:
Ook met je fix ga je nog steeds te ver in je run functie, regel 30:

code:

    for (int i = para.x; i < n; i++)

n is de gehele reeks toch?
moet je um niet tot pt laten lopen?

Hoeveel performance verschil zit er nu tussen de single en milti-threaded applicatie?

...

Nee, in de regels daaronder stopt de lus als hij aankomt bij een getal dat al berekend is. Zie regel 32-33.

Op mijn dualcore heb ik getest met 1 en 2 threads. In het geval van 2 threads ging hij over het test-gedeelte twee keer zo snel, zoals verwacht. Indien je geinteresseerd ben kan ik morgen een benchmark doen met een quadcore, mijn verwachting is dat het dan vier keer zo snel gaat.

Het lijkt mij nogal logisch dat het geen zin heeft om meer threads aan te maken dan je rekenkernen hebt. Zo zal dit programma niet sneller gaan draaien op mijn laptop als ik meer dan 2 threads aanmaak omdat ik gewoon niet meer dan 2 rekenkernen heb. Als ik mijn computer zou pakken dan is de verwachte limiet 8 threads omdat die meer kernen heeft.

MLM schreef op zondag 09 oktober 2011 @ 13:46:
sidenote: pow(x, 2) == x * x, bespaart veel cycles

Een simpele benchmark in c++ leert dat dat (bijna) geen verschil maakt. Althans voor n < 1e6. Als n ~ 1e8 dan scheelt het ~2s op mijn laptop, pas rond n ~ 1e10 is er een groot verschil. Op basis van een paar testen concludeer ik dat i*i ~9x zo snel is, maar voor kleine n (<1e7) is het nog verwaarloosbaar.

Ik maak gebruik van dit proggie om te benchen:

C++:

/**
 * Een benchmark van pow vs *
 */

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>

using namespace std;

int main (int argc, char *argv[])
{
    cout.setf(ios::fixed);
    cout.precision(9);

    unsigned long long n;
    if (argc == 2) {
        stringstream buffer;
        buffer << argv[1];
        buffer >> n;
    } else {
        n = 0;
    }
    while (n < 1 || 10000000000 < n)
    {
        cout << "Select a (integer) value for n [1-10000000000]: ";
        cin >> n;
    }
    
    cout << "Benching pow";
    {
        clock_t t1 = clock();
        for (unsigned long long i = 0; i < n; i++)
            unsigned long long x = pow(i, 2);
        clock_t t2 = clock();
        double rs = (t2 - t1);
        rs = rs / CLOCKS_PER_SEC;
        cout << " (in s): " << rs << endl;
    }

    cout << "Benching i*i";
    {
        clock_t t1 = clock();
        for (unsigned long long i = 0; i < n; i++)
            unsigned long long x = i*i;
        clock_t t2 = clock();
        double rs = (t2 - t1);
        rs = rs / CLOCKS_PER_SEC;
        cout << " (in s): " << rs << endl;
    }

    return 0;
}

[ Voor 32% gewijzigd door Verwijderd op 09-10-2011 16:54 ]

[H!GHGuY]

Ik hoop maar dat je zonder optimalisaties gecompileerd hebt.

Een beetje compiler optimaliseert die volledige for loop weg.
Zelfs al laat zet je x en i in een hogere scope, dan nog kan een degelijke compiler er

C++:

i = n;
x = n * n;

van maken.

Bovendien kan een nog slimmere compiler aanroepen van 'pow(i,x)' met x een constante vervangen door de juiste factorisatie.

[ Voor 3% gewijzigd door H!GHGuY op 09-10-2011 20:13 ]

[Verwijderd]

Weet ik, daar houw ik rekening mee. Optimalisatie is -O0

[Orwell]

Een paar dingen:

Als je windows gebruikt, probeer QueryPerformanceCounter():

C++:

__int64 countspersec = 0;
float secpercount = 0.0f;
__int64 starttime = 0;
__int64 curtime = 0;

// Wanneer zijn we begonnen en hoe snel tikt de klok
QueryPerformanceCounter((LARGE_INTEGER*)&starttime);    
QueryPerformanceFrequency((LARGE_INTEGER*)&countspersec);
secpercount = 1.0f/(float)countspersec;

/* doe hier de berekening */

// En bereken tijdsverschil
QueryPerformanceCounter((LARGE_INTEGER*)&curtime);
printf("Time needed: %g sec\n\n",(curtime-starttime)*secpercount);

Die is in mijn ervaring iets minder wisselvallig, en je kan door de wat grotere precisie minder gigantische loops gebruiken. Altijd praktisch.

En je zou die x global(er) kunnen declareren, zodat je ook van het nieuwe variabele maken afbent (minder ruis in de meting .e.d), al verwacht ik dat een compiler er vast wel een static van maakt.

[Verwijderd]

Helaas, ik werk onder GNU/Linux, en dan heb je geen QueryPerformanceCounter. Clock() heeft inderdaad een naam van slechte nauwkeurigheid in de orde van ms, maar ik zit hier te meten in de orde van s. Daarom denk ik dat het hier gerechtigd is om die deviatie te verwaarlozen.

Ik zou ook gebruik kunnen maken van gettimeofday() voor betere nauwkeurigheid, maar voor een verandering in de tweede decimaal achter de komma heeft niet zoveel toegevoegde waarde als je met getallen van een factor 1000 hoger te maken hebt. Dus uit gemaksoverwegingen heb ik voor clock() gekozen.

Die x in scope omhoog maakt geen verschil, er wordt geheugen vrijgemaakt en gelijk overschreven met de uitkomst ipv eerst met 0'n en dan de uitkomst. Voor de volledigheid heb ik het gelijk getest en de ruis valt weg in de deviatie van clock().

[H!GHGuY]

Verwijderd schreef op zondag 09 oktober 2011 @ 22:15:
Helaas, ik werk onder GNU/Linux, en dan heb je geen QueryPerformanceCounter. Clock() heeft inderdaad een naam van slechte nauwkeurigheid in de orde van ms, maar ik zit hier te meten in de orde van s. Daarom denk ik dat het hier gerechtigd is om die deviatie te verwaarlozen.

Ik zou ook gebruik kunnen maken van gettimeofday() voor betere nauwkeurigheid, maar voor een verandering in de tweede decimaal achter de komma heeft niet zoveel toegevoegde waarde als je met getallen van een factor 1000 hoger te maken hebt. Dus uit gemaksoverwegingen heb ik voor clock() gekozen.

Die x in scope omhoog maakt geen verschil, er wordt geheugen vrijgemaakt en gelijk overschreven met de uitkomst ipv eerst met 0'n en dan de uitkomst. Voor de volledigheid heb ik het gelijk getest en de ruis valt weg in de deviatie van clock().

De beste resolutie haal je in linux met clock_gettime(CLOCK_MONOTONIC, ...).

[NC83]

Orwell schreef op zondag 09 oktober 2011 @ 21:05:
Een paar dingen:

Als je windows gebruikt, probeer QueryPerformanceCounter():

C++:

__int64 countspersec = 0;
float secpercount = 0.0f;
__int64 starttime = 0;
__int64 curtime = 0;

// Wanneer zijn we begonnen en hoe snel tikt de klok
QueryPerformanceCounter((LARGE_INTEGER*)&starttime);    
QueryPerformanceFrequency((LARGE_INTEGER*)&countspersec);
secpercount = 1.0f/(float)countspersec;

/* doe hier de berekening */

// En bereken tijdsverschil
QueryPerformanceCounter((LARGE_INTEGER*)&curtime);
printf("Time needed: %g sec\n\n",(curtime-starttime)*secpercount);

Die is in mijn ervaring iets minder wisselvallig, en je kan door de wat grotere precisie minder gigantische loops gebruiken. Altijd praktisch.

En je zou die x global(er) kunnen declareren, zodat je ook van het nieuwe variabele maken afbent (minder ruis in de meting .e.d), al verwacht ik dat een compiler er vast wel een static van maakt.

Je moet alleen wel je perfomance counter aan een thread binden, want ook die API is niet thread safe, en omdat niet alle kernen in een core precies hetzelfde zijn kan dit tot problemen leiden.
Dit zal trouwens bij linux perfomance counters niet anders zijn.
Zodra je de counter aan een thread bindt kun je er zeker van zijn dat de query op dezelfde core gebeurt als waar je code draait in. De query garandeert dit namelijk niet standaard.

QueryPerfomance counter geeft je clock ticks terug trouwens en die moet je dan zelf converteren naar tijd. Dit is ook waarom er een int64 wordt gebruikt LARGE_INTEGER is een union van 2 ints.

[ Voor 6% gewijzigd door NC83 op 10-10-2011 14:41 ]

[.oisyn]

Zodra je de counter aan een thread bindt kun je er zeker van zijn dat de query op dezelfde core gebeurt als waar je code draait in.

Let wel, je bedoelt hier hardware thread, niet software thread. Want je software thread kan altijd nog gepreëmpt worden naar een andere core.

[ Voor 28% gewijzigd door .oisyn op 10-10-2011 14:48 ]

[MLM]

QPC en QPF moet je op dezelfde core pakken, dus je moet eerst SetThreadAffinity gebruiken, maar dan zit je wel mogelijk parallellisatie in de weg (als je dat op teveel threads doet). Maar goed, gezien het toch niet op windows gaat draaien, doet het er niet echt toe.

Maar dan nog kan je een stuk heel stuk besparen door de resultaten te sommeren per thread. Dit is jouw code (een beetje aangepast voor Win32, maar zou zo moeten compilen zonder edits in GCC linux)

C++:

#include <cmath>  
#include <cstdlib>  
#include <iostream>  
#include <sstream>  
//#include <vector> overbodig 

#ifdef _WIN32 //pthread en rand_r implementatie voor win32
#include <windows.h>
typedef HANDLE pthread_t;
#define THREAD_FUNC(name, arg) DWORD CALLBACK name(void *arg)
inline int pthread_create(pthread_t *thread, void *ignored, DWORD (CALLBACK *start_routine)(void *), void *arg)
{
    *thread = CreateThread(0, 0, start_routine, arg, 0, 0);
    return *thread == 0;
}
inline void pthread_join(pthread_t thread, void **ptr)
{
    WaitForSingleObject(thread, INFINITE);
    CloseHandle(thread);
}
inline int rand_r(int *seed)
{
    return( ((*seed = *seed * 214013L + 2531011L) >> 16) & 0x7fff ); //CRT rand()
}
#else
#include <pthread.h> 
#define THREAD_FUNC(name, arg) void *name(void *arg)
#endif

using namespace std;

int p, n, pt; //pt erbij om je loop te bounden 
//vector <int> c; overbodig 

struct arg {  
    int x;  
    int seed;
    double avg; //resultaten per thread 
    double var; 
};  

THREAD_FUNC(run, _para)
{  
    arg &para = *(arg*) _para;  
    double avg = 0.0; 
    double var = 0.0; 
    for (int i = 0; i < pt; i++) //index hoeft niet bijgehouden te worden, gezien c toch niet nodig is 
    { 
        // if (c[i] > 0)  
        //    return NULL;  
        bool run = true;  
        bool last;  
        double temp = rand_r(&para.seed);  
        int k = 10000 * temp / RAND_MAX;  
        if (k > p)  
            last = true;  
        else  
            last = false;  
        while (run) {  
            temp = rand_r(&para.seed);  
            k = temp * 10000 / RAND_MAX;  
            if (k > p) {  
                if (!last)  
                    run = false;  
            } else {  
                if (last)  
                    run = false;  
            }  
        }  
        last = !last;  
        run = true;  
        int c = 0; //local voor c[i] 
        while (run) {  
            c++; //was: c[i]++;  
            temp = rand_r(&para.seed);  
            k = temp * 10000 / RAND_MAX;  
            if (k > p) {  
                if (!last)  
                    run = false;  
            } else {  
                if (last)  
                    run = false;  
            }  
        }  
        avg += c; //running total 
        var += c * c; 
    }  
    para.avg = avg; //totalen per thread 
    para.var = var; 
    
    return 0;
}  

int main (int argc, char *argv[])  
{  
    cout.setf(ios::fixed);  
    cout.precision(9);  
      
    // Laden van alle data  
    int s, t;  
    if (argc == 5) {  
        stringstream buffer;  
        buffer << argv[1] << ' ' << argv[2] << ' ' << argv[3] << ' ' << argv[4];  
        buffer >> p >> n >> s >> t;  
    } else {  
        p = 0;  
        n = 0;  
        s = 0;  
        t = 0;  
    }  
    while (p < 0 || 10000 < p || n < 1 || 100000000 < n || s < 0 || t < 0) {  
        cout << "Select a (integer) value for p [0-10000]: ";  
        cin >> p;  
        cout << "Select a (integer) value for n [1-100000000]: ";  
        cin >> n;  
        cout << "Select a (integer) value for s [>0]: ";  
        cin >> s;  
        cout << "Select a (integer) value for t [>0]: ";  
        cin >> t;  
    }  

    // De test  
    //c.resize(n);  
    pthread_t * threads = new pthread_t[t];  
    srand(s);  
    pt = n / t;  
    arg * para_array = new arg[t]; //array van args, straks nog nodig 
    for (int i = 0; i < t; i++)  
    {  
        arg *para = para_array + i; //ipv new arg 
        (*para).x = pt * i;  
        (*para).seed = rand();  
        pthread_create(&threads[i], NULL, run, para);  
    }  
    double sum_avg = 0.0; //totale som 
    double sum_var = 0.0; 
    for (int i = 0; i < t; i++)  
    { 
        pthread_join(threads[i], NULL);  
        sum_avg += para_array[i].avg; 
        sum_var += para_array[i].var; 
    } 

    delete [] para_array; //opruimen, dat deed je eerste helemaal niet (memory leak!) 
    delete [] threads;

    // Verwerken van alle data  
    /* overbodige loops 
    double avg = 0;  
    for (int i = 0; i < n; i++)  
        avg += c[i];  
    avg = avg/n;  
    double var = 0;  
    for (int i = 0; i < n; i++)  
        var += pow((c[i] - avg), 2);  
    var = var/n;  
    */ 
    double avg = sum_avg / n; //door threads al berekend 
    double var = (sum_var - 2.0 * avg * sum_avg) / n + avg * avg; //welke miljoen pow()s? :) 

    cout << "Mean: " << avg << " Variance: " << var << endl;  

    return 0;  
}

Dat is omdat ∑(i:0->n) { pow(c[i] - avg, 2) } == ∑(i:0->n) { c[i] * c[i] - 2 * c[i] * avg + avg * avg } == ∑(i:0->n) { c[i] * c[i] } - 2 * ∑(i:0->n) { c[i] } * avg + n * avg * avg. Dat lijkt ingewikkelder, maar je ∑'s zijn nu heel simpel te berekenen door de threads (parallel), en dan is de uiteindelijke berekening in de hoofdthread supersimpel. Voordeel, je vector<int> kan je nu weglaten, geheugen complexiteit is nu (zo goed als) O(1). Bonuspunten omdat je hele programma + gebruikte stack/heap nu in je CPU cache past, dus voor een goed gekozen t (== aantal cores in je PC bijvoorbeeld) waarschijnlijk een stuk sneller naarmate je n groter word

Gelijk maar even maximale n opgerekt naar 100 miljoen Gecompiled met VC2010, x86, Release, uitvoer met:
p = 5000
n = 100000000 (100M)
s = 1
t = 16
geeft: Mean = 1.999948760 Variance = 1.999809997
in 3 seconden op mijn i7 970

[ Voor 19% gewijzigd door MLM op 10-10-2011 19:23 . Reden: code fix ]

[Verwijderd]

Dat ziet er inderdaad een stuk efficienter uit, maar als je het nog efficienter wilt dan haal je een stuk van de test weg. Je hoeft immers niet te berekenen hoelang de eerste deelserie is om te kijken wat de lengte van de tweede deelserie is. Daar heb je al een enorme prestatiewinst van meer dan 50%.

Maar dat was het hele punt niet van deze oefening, het ging er vooral om hoe multithreading goed toepasbaar was, en ik ben blij voor het voorbeeld dat je hebt gegeven want het laat goed zien hoe je efficient met geheugen omgaat Ik moet toegeven dat je die variantie mooi hebt berekend.