[C++] Differenza di prestazioni con implementazioni simili

[utente__medio]

Sbagli, e anche di molto. Il tuo codice è ben poco performante ed è dominato dalle allocazioni di memoria. Per capire quanto sia pessimo...

Ho già ripetuto più volte che il codice postato all'inizio era solo un mezzo per chiedere lumi circa le performance "controintuitive" riscontrate tra vector e string; in ogni caso penso sia inutile che io perda tempo a fare inutili precisazioni e che sia meglio postare direttamente il codice ottimizzato:

Codice:

#include <iostream>
#include <chrono>
#include <cstdint>
#include <vector>

using namespace std;
using namespace std::chrono;

vector<uint32_t> multiplication_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    const vector<uint32_t> &v_1 = v1.size() < v2.size() ? v1 : v2;
    const vector<uint32_t> &v_2 = v_1 == v1 ? v2 : v1;
    vector<uint32_t> v3(v_1.size() + v_2.size(), 0);
    for(unsigned int i = 0; i < v_1.size(); ++i)
    {
        uint64_t r1 = 0;
        uint64_t r2 = 0;
        v3.resize(i);
        for(unsigned int j = 0; j < v_2.size() || r1 || r2; ++j)
        {
            if(j < v_2.size())
            {
                r1 += (uint64_t)v_1[i] * v_2[j];
            }
            r2 += v3[v3.size()] + r1 % 1000000000;
            v3.push_back(r2 % 1000000000);
            r1 /= 1000000000;
            r2 /= 1000000000;
        }
    }
    return v3;
}

void print_10(const vector<uint32_t> &v)
{
    for(unsigned int i = 0; i < v.size(); ++i)
    {
        if(i)
        {
            for(int32_t j = 99999999; j && j >= v[v.size() - 1 - i]; j /= 10)
            {
                cout << "0";
            }
        }
        cout << v[v.size() - 1 - i];
    }
    cout << endl;
}

int main()
{
    cout << "calcolo di 12345^1000 (versione vector ottimizzata base 10): ";
    vector<uint32_t> a = {12345};
    vector<uint32_t> b = {1};
    auto start1 = high_resolution_clock::now();
    for(unsigned int i = 0; i < 1000; ++i)
    {
        b = multiplication_10(a, b);
    }
    auto stop1 = high_resolution_clock::now();
    auto duration1 = duration_cast<milliseconds>(stop1 - start1);
    cout << duration1.count() << " ms" << endl;
    print_10(b);
}


Output:

Testo nascosto, fai click qui per vederlo

Codice:

calcolo di 12345^1000 (versione vector ottimizzata base 10): 2 ms

30980916979571261678037792640547069821046036601263871423172603964432880446620608
46921638204797951863536177399422240269688598440386160524113311366171137540029427
91772720296320086301939317723959165750831660314625504906217694965268441368838284
91469899680820312066142708028389393562630538115386600687343726225365416760557989
41423155494189268546531047348336572287590039126299044550768543719716900090002922
31442640702405997349818652846007594672121952993600612240375288011172203296667256
96103967654224628215610071281098978353840302864126825283500458106807878522509659
21789617648423284361266990316368590121427804100038121975738472719701414718604485
59701917501364026826498681300417013008430237787456258392796158010957510644217069
98341913428129617946641478177778534617429438982842385866806060632693349145018235
12239084719922296603840279509341320330116129246617953872657843763736914650433910
69947270507908425989612108500884562232290869386787877493097701502859303071373757
98655553418051305869563741235177332696717875374591544971368987407514335651644993
48432070402708303140803815093836661660356285937395020277788919864363825187404391
66973596854885177857972177954369036272112372120342169211179441034974532201077985
02955733113425832358515283713193528314018013484978895836581392051714102432880542
73520458521176241545142042871027819038633452778882009889151826115545711661170538
36747195908282969788810091869993349713112267938558757495744359548488837018005043
40690662067911606624152430636860695557307662212093813837874302080738361232336551
74575751749331919935735057962393028640196663750515631155647068114586019547125009
66722593376174534528998418559797925572480799490873627279344223127796375553240572
15862646352988229249067464618561571347927535747106152891191398219533463769254976
60439255056416164625808728071677859168160485698031944035324637075340851589197234
49415021308596978472922475070959635686086272975863164803202569864125951706329194
84682164033661640489555929737222661905985234140148505838990396502711735660674750
18401069005143388746198994486546761245453653960305361484058030629364813564938166
77996142347736230549290495923638437033343172179181801753570878708654257297687835
26965343706996729232760606845658227256991400912979153167112235978039183655623558
98974562226281554721134128093680325493342116410019082065191222152604701943612903
09012247981704105777443919500572258770469577053059340743175489359094192490153869
68801837378836637000835706292471984808215940621442162785226511155294831484513417
52199992248704863885652427271790306569255537274573369763448958846105089050305523
89745067153053340339925663961641409046696655149031934108909967069140051370963337
42293240129209862323592579138243170317263223252880934191859024800749271249770266
97005663041724543518495369422176498807371766396344183276476753948925774528804843
05655939076362259220197812625222643643191577117100739643427218343227279208350495
80217315761848037089866403378986967045064502829656583826962255738198354622836756
35667056382976855279913816549680982420288449166338344372060236443053987567633619
13498399705896830636029425918669043084740115869198785908560762760382332445251211
23130345477189333775791288130929475816834573933825566780851556546207567350921324
84252238947178033958197247843877788771142111236322569477645881902111263631757196
58176061228259719565346549780300325616948182208870465891192349276710668441048641
29975170039721209641075115717792256013191312063969737958364103235501978884662125
34511083901139702691409815298297037003389820841696983552075032727515727567122502
94394271855766758729580875496156304085099464372152797873952740789997020284489294
85834734357491174993595291833627475607319515601968664863128650348891298074261373
11630439976466542171620548090996899637416145616614625955318606438025388953080883
19814146640625180562801649749164640860829007177519736517996763714855878556975798
53551247141335832576720350019360024777873472945177760531417791020722451271496295
35007942765141973975166467388687997634230267335326011501002931165248908784123116
24139545280293494422725269869365974996851368188630938826921834561289870180189609
527587890625

Process returned 0 (0x0)   execution time : 0.118 s
Press any key to continue.


Con quest'implementazione non penso di star facendo più operazioni del necessario, o sbaglio?

prova a compilare e lanciare questa versione: ...

Così su due piedi sembra che restituisca un risultato errato; non so se può entrarci in qualche modo quanto detto in precedenza, ossia che la variabile v nel for più interno possa essere potenzialmente soggetta ad overflow.

--------------------------------------------------------------------------------------------------------------------------

Utilizzando l'approccio suggerito da apatriarca nel suo ultimo post, presumo che la funzione multiplication() si riduca a:

Codice:

vector<uint32_t> multiplication_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    const vector<uint32_t> &v_1 = v1.size() < v2.size() ? v1 : v2;
    const vector<uint32_t> &v_2 = v_1 == v1 ? v2 : v1;
    vector<uint32_t> v3(v_1.size() + v_2.size(), 0);
    for(unsigned int i = 0; i < v_1.size(); ++i)
    {
        uint64_t r1 = 0;
        uint64_t r2 = 0;
        v3.resize(i);
        for(unsigned int j = 0; j < v_2.size() || r1 || r2; ++j)
        {
            if(j < v_2.size())
            {
                r1 += (uint64_t)v_1[i] * v_2[j];
            }
            r2 += v3[v3.size()] + (uint32_t)r1;
            v3.push_back((uint32_t)r2);
            r1 >>= 32;
            r2 >>= 32;
        }
    }
    return v3;
}

Giusto?

Non ho la certezza che questa versione funzioni, in quanto devo ancora implementare una funzione per stamparne correttamente il risultato in base 10.
In ogni caso, come prevedibile, risulta molto più performante dell'omologa "in base 10"; lo scetticismo espresso nei precedenti post, infatti, non si riferiva a questo approccio, in cui comunque non si verifica alcun overflow e ci si limita a sostituire l'operatore modulo con il casting e la divisione con il right-shift, ma quello che prevedeva di sfruttare "l'overflow circolare" degli interi senza segno, ma molto probabilmente ho capito io male.

Oltre ad un'apposita funzione per stampare i risultati, ipotizzo che bisogna anche prevedere un apposito "costruttore" da stringa, che invece di dividere la stringa in gruppi fissi di 9 cifre, divida la stringa in gruppi di 9 o 10 cifre in base a quando si verifica l'overflow. Giusto?

[apatriarca]

Sì è corretto. Entrambe le funzioni di conversione vanno implementate perché si possa usare questo metodo. Tuttavia la creazione direttamente da numeri interi diventa più semplice. Non mi è chiaro quale dovesse essere il tuo metodo che faceva uso dell'overflow, ma intendevo quello che ti ho poi mandato.

[vict85]

prova a compilare e lanciare questa versione: ...

Così su due piedi sembra che restituisca un risultato errato; non so se può entrarci in qualche modo quanto detto in precedenza, ossia che la variabile v nel for più interno possa essere potenzialmente soggetta ad overflow.

Ho controllato, il problema non è nell'overflow ma in varie altre parti. Prima di tutto ho sbagliato a inizializzare i vettori e lo swap. Ma anche correggendo quello, ho scritto il codice supponengo che l'array fosse scritto al contrario. Ma non vale la pena correggerlo, ho scritto il codice per capire quanto le allocazioni influissero sulle performance. Sarebbe stato più semplice usare un profiler.

[ghira]

@ghira: il calcolo non è importante perché lo scopo era quello di confrontare le performance di due codici che fanno la stessa cosa.

Ok, grazie. Volevo solo controllare perché mi ricordo di aver visto colleghi informatici anni fa che hanno dovuto calcolare la 47millesima potenza di qualcosa e qualcuno l'ha fatto con 47mila moltiplicazioni...

[vict85]

@ghira: il calcolo non è importante perché lo scopo era quello di confrontare le performance di due codici che fanno la stessa cosa.

Ok, grazie. Volevo solo controllare perché mi ricordo di aver visto colleghi informatici anni fa che hanno dovuto calcolare la 47millesima potenza di qualcosa e qualcuno l'ha fatto con 47mila moltiplicazioni...

Con una libreria di questo tipo pow non è disponibile, e trovo sia anche molto abusato dai principianti (usarlo per calcolare potenze basse è senza senso). Qualcosa come \(x^{1000}\) si può comunque fare con meno moltiplicazioni, o usando https://en.wikipedia.org/wiki/Exponenti ... y_squaring oppure con altri metodi simili.

[ghira]

Qualcosa come \(x^{1000}\) si può comunque fare con meno moltiplicazioni, o usando https://en.wikipedia.org/wiki/Exponenti ... y_squaring oppure con altri metodi simili.

Certamente. Era per questo che chiedevo.

[vict85]

@utente__medio il tuo uso del resize e del v3[v3.size()] mi confonde un po'. Se al posto delle parentesi avessi usato la funzione at avresti generato una eccezione. Il codice non fa nulla di sbagliato dal punto di vista della memoria, è solo un uso strano dell'interfaccia vector. Il tuo codice è assolutamente equivalente a questo, più leggibile:

Codice:

vector< uint32_t >
multiplication_10b( const vector< uint32_t >& v1, const vector< uint32_t >& v2 )
{
    const vector< uint32_t >& v_1 = v1.size( ) < v2.size( ) ? v1 : v2;
    const vector< uint32_t >& v_2 = v_1 == v1 ? v2 : v1;
    vector< uint32_t > v3( v_1.size( ) + v_2.size( ), 0 );
    uint64_t size = 0;
    for ( unsigned int i = 0; i < v_1.size( ); ++i )
    {
        uint64_t r1 = 0;
        uint64_t r2 = 0;
        size = i;
        for ( unsigned int j = 0; j < v_2.size( ) || r1 || r2; ++j )
        {
            if ( j < v_2.size( ) )
            {
                r1 += (uint64_t)v_1[ i ] * v_2[ j ];
            }
            r2 += v3[ size ] + r1 % 1000000000;
            v3[ size++ ] = r2 % 1000000000;
            r1 /= 1000000000;
            r2 /= 1000000000;
        }
    }
    v3.resize( size );
    return v3;
}

Ho cambiato solo poche righe del tuo codice e riformattato (il mio IDE riformatta automaticamente). Ho anche controllato il risultato stavolta.

Comunque è solo una questione di leggibilità del codice.

[utente__medio]

Ecco il codice aggiornato:

Codice:

#include <iostream>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <string>
#include <vector>

using namespace std;
using namespace std::chrono;

const uint32_t N = 1000000000;

vector<uint32_t> from_2_to_10(vector<uint32_t> v_2)
{
    vector<uint32_t> v_10;
    do
    {
        uint64_t r = 0;
        unsigned int i = 0;
        for(unsigned int j = 0; j < v_2.size(); ++j)
        {
            r = (r << 32) + v_2[j];
            if(i || r / N)
            {
                v_2[i++] = r / N;
                r %= N;
            }
        }
        v_2.resize(i);
        v_10.push_back(r);
    }
    while(v_2.size());
    return v_10;
}

vector<uint32_t> from_10_to_2(vector<uint32_t> v_10)
{
    vector<uint32_t> v_2;
    do
    {
        uint64_t r = 0;
        unsigned int i = 0;
        for(unsigned int j = 0; j < v_10.size(); ++j)
        {
            r = r * N + v_10[j];
            if(i || r >> 32)
            {
                v_10[i++] = r >> 32;
                r = (uint32_t)r;
            }
        }
        v_10.resize(i);
        v_2.push_back(r);
    }
    while(v_10.size());
    return v_2;
}

vector<uint32_t> from_string_10(const string &s, bool flag = true)
{
    vector<uint32_t> v_10;
    unsigned int i = 0;
    while(i < s.size())
    {
        unsigned int j_max = v_10.size() ? 9 : s.size() % 9;
        v_10.push_back(0);
        for(unsigned int j = 0; j < j_max; ++j)
        {
            v_10.back() = v_10.back() * 10 + (s[i++] - '0');
        }
    }
    if(flag)
    {
        reverse(v_10.begin(), v_10.end());
    }
    return v_10;
}

vector<uint32_t> from_string_2(const char *s)
{
    return(from_10_to_2(from_string_10(s, false)));
}

vector<uint32_t> multiplication_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
    const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
    vector<uint32_t> v3(w1.size() + w2.size(), 0);
    for(unsigned int i = 0; i < w1.size(); ++i)
    {
        uint64_t r1 = 0;
        uint64_t r2 = 0;
        v3.resize(i);
        for(unsigned int j = 0; j < w2.size() || r1 || r2; ++j)
        {
            if(j < w2.size())
            {
                r1 += (uint64_t)w1[i] * w2[j];
            }
            r2 += v3[v3.size()] + r1 % N;
            v3.push_back(r2 % N);
            r1 /= N;
            r2 /= N;
        }
    }
    return v3;
}

vector<uint32_t> multiplication_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
    const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
    vector<uint32_t> v3(w1.size() + w2.size(), 0);
    for(unsigned int i = 0; i < w1.size(); ++i)
    {
        uint64_t r1 = 0;
        uint64_t r2 = 0;
        v3.resize(i);
        for(unsigned int j = 0; j < w2.size() || r1 || r2; ++j)
        {
            if(j < w2.size())
            {
                r1 += (uint64_t)w1[i] * w2[j];
            }
            r2 += v3[v3.size()] + (uint32_t)r1;
            v3.push_back((uint32_t)r2);
            r1 >>= 32;
            r2 >>= 32;
        }
    }
    return v3;
}

void print_10(const vector<uint32_t> &v_10)
{
    for(unsigned int i = 0; i < v_10.size(); ++i)
    {
        if(i)
        {
            for(int32_t j = N / 10 - 1; j && j >= v_10[v_10.size() - 1 - i]; j /= 10)
            {
                cout << "0";
            }
        }
        cout << v_10[v_10.size() - 1 - i];
    }
    cout << endl;
}

void print_2(vector<uint32_t> v_2)
{
    reverse(v_2.begin(), v_2.end());
    print_10(from_2_to_10(v_2));
}

int main()
{
    cout << "calcolo di 12345^1000 (versione vector ottimizzata base 10): ";
    vector<uint32_t> a = from_string_10("43695595240774383441671015625");//12345^7
    vector<uint32_t> b = from_string_10("12345");
    auto start1 = high_resolution_clock::now();
    for(unsigned int i = 0; i < 993; ++i)
    {
        a = multiplication_10(a, b);
    }
    auto stop1 = high_resolution_clock::now();
    auto duration1 = duration_cast<milliseconds>(stop1 - start1);
    cout << duration1.count() << " ms" << endl << endl;
    print_10(a);
    //-----------------------------------------------------------------------
    cout << endl << "calcolo di 12345^1000 (versione vector ottimizzata base 2): ";
    vector<uint32_t> c = from_string_2("43695595240774383441671015625");//12345^7
    vector<uint32_t> d = from_string_2("12345");
    auto start2 = high_resolution_clock::now();
    for(unsigned int i = 0; i < 993; ++i)
    {
        c = multiplication_2(c, d);
    }
    auto stop2 = high_resolution_clock::now();
    auto duration2 = duration_cast<milliseconds>(stop2 - start2);
    cout << duration2.count() << " ms" << endl << endl;
    print_2(c);
}

- innanzitutto ho scritto le due funzioni from_2_to_10() e from_10_to_2() per convertire il vector da base 2 a base 10 (o forse sarebbe più corretto dire da base 2^32 a base 10^9) e viceversa. In pratica ho implementato una rudimentale divisione intera per poi calcolare i resti;
- poi ho implementato il "costruttore" da stringa in base 2, ossia la funzione from_string_2(), che a sua volta sfrutta la funzione from_10_to_2() e il "costruttore" da stringa in base 10 from_string_10(), il quale divide la stringa a partire da destra in gruppi di 9 cifre (escluso l'ultimo gruppo che avrà una generica lunghezza <=9);
- infine le funzioni print_2() e print_10() stampano i risultati ottenuti dalla moltiplicazione rispettivamente in base 2 e 10.

Il tutto sembra funzionare, ma volevo chiedervi se secondo voi va bene come approccio.

Il codice non fa nulla di sbagliato dal punto di vista della memoria, è solo un uso strano dell'interfaccia vector. Il tuo codice è assolutamente equivalente a questo, più leggibile: ...

In effetti così è più leggibile, purtroppo a volte la brutta abitudine di risparmiare sulle righe di codice prende il sopravvento!

[utente__medio]

Ne approfitto per chiedere altre due cose:

- per quanto riguarda l'addizione ho scritto due versioni, una più concisa e una (in teoria) più efficiente; compilando con il flag -O la versione concisa è leggermente più lenta, mentre compilando con il flag -O3 i risultati si invertono. Queste le due versioni (per semplicità posto la versione in base 10):

Codice:

vector<uint32_t> addition_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
    const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
    vector<uint32_t> v3;
    v3.reserve(w2.size() + 1);
    uint64_t r = 0;
    unsigned int i = 0;
    for(; i < w1.size() || r; ++i)
    {
        if(i < w1.size())
        {
            r += (uint64_t)w1[i] + w2[i];
        }
        else if(i < w2.size())
        {
            r += (uint64_t)w2[i];
        }
        v3.push_back(r % N);
        r /= N;
    }
    for(; i < w2.size(); ++i)
    {
        v3.push_back(w2[i]);
    }
    return v3;
}

vector<uint32_t> addition_10b(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
    const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
    vector<uint32_t> v3;
    v3.reserve(w2.size() + 1);
    uint64_t r = 0;
    for(unsigned int i = 0; i < w2.size() || r; ++i)
    {
        r += uint64_t(i < w1.size() ? w1[i] : 0) + uint64_t(i < w2.size() ? w2[i] : 0);
        v3.push_back(r % N);
        r /= N;
    }
    return v3;
}

Al netto delle prestazioni controintuitive riscontrate compilando con -O3, quale versione mi conviene inserire nella libreria che sto scrivendo?

- per quanto riguarda la sottrazione ho scritto le seguenti funzioni:

Codice:

const uint32_t N = 1000000000;
const uint64_t M = (uint64_t)numeric_limits<uint32_t>::max() + 1;

vector<uint32_t> subtraction_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    vector<uint32_t> v3;
    v3.reserve(v1.size());
    uint64_t r = N;
    for(unsigned int i = 0; i < v1.size(); ++i)
    {
        r = N + v1[i] - (r < N);
        if(i < v2.size())
        {
            r -= v2[i];
        }
        v3.push_back(r % N);
    }
    for(unsigned int i = v3.size() - 1; i && !v3[i]; --i)
    {
        v3.pop_back();
    }
    return v3;
}

vector<uint32_t> subtraction_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
    vector<uint32_t> v3;
    v3.reserve(v1.size());
    uint64_t r = M;
    for(unsigned int i = 0; i < v1.size(); ++i)
    {
        r = M + v1[i] - (r < M);
        if(i < v2.size())
        {
            r -= v2[i];
        }
        v3.push_back((uint32_t)r);
    }
    for(unsigned int i = v3.size() - 1; i && !v3[i]; --i)
    {
        v3.pop_back();
    }
    return v3;
}

L'approccio utilizzato va bene o fareste qualcosa di diverso? E per la "traduzione" da base 10 a base 2 si può fare di meglio?

[vict85]

Ho notato che questo codice fa qualcosa che probabilmente non è quello che immagini:

Codice:

const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;

infatti il confronto w1 == v1 fa il confronto tra vector e non di puntatori. Per confrontare i puntatori devi scrivere &w1 == &v1.

Per capire, guarda
https://godbolt.org/z/8zfx5r1MP
e noterai che che viene chiamata l'uguaglianza di vector, mentre con &w1 == &v1 si confrontano due registri.

Per quanto riguarda la sottrazione non vedo alcun sistema per gestire i numeri negativi. Insomma, se \(v_1 < v_2\) ti viene un risultato poco sensato.

Per l'addizione, sei sicuro che le due funzioni diano lo stesso risultato? A occhio mi sembra che la seconda non stia tenendo conto del riporto finale.