[C++] Differenza di prestazioni con implementazioni simili

[utente__medio]

Salve, come da titolo vorrei capire come mai i due blocchi nel main() richiedano tempi così elevati e diversi tra di loro per essere eseguiti:

Codice:

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

using namespace std;
using namespace std::chrono;

string addition1(const string &s1, const string &s2)
{
    string s3;
    unsigned int n = 0;
    for(unsigned int i = 0; i < s1.size() || i < s2.size(); ++i)
    {
        n /= 10;
        if(i < s1.size())
        {
            n += s1[i] - '0';
        }
        if(i < s2.size())
        {
            n += s2[i] - '0';
        }
        s3.push_back(n % 10 + '0');
    }
    if(n >= 10)
    {
        s3.push_back('1');
    }
    return s3;
}

string multiplication1(const string &s1, const string &s2)
{
    string s3;
    string temp;
    for(unsigned int i = 0; i < s1.size(); ++i)
    {
        temp.resize(0);
        unsigned int n = 0;
        for(unsigned int j = 0; j < i; ++j)
        {
            temp.push_back('0');
        }
        for(unsigned int j = 0; j < s2.size(); ++j)
        {
            n = (s1[i] - '0') * (s2[j] - '0') + n / 10;
            temp.push_back(n % 10 + '0');
        }
        if(n >= 10)
        {
            temp.push_back(n / 10 + '0');
        }
        s3 = addition1(s3, temp);
    }
    return s3;
}

vector<uint8_t> addition2(const vector<uint8_t> &v1, const vector<uint8_t> &v2)
{
    vector<uint8_t> v3;
    uint8_t n = 0;
    for(unsigned int i = 0; i < v1.size() || i < v2.size(); ++i)
    {
        n /= 10;
        if(i < v1.size())
        {
            n += v1[i];
        }
        if(i < v2.size())
        {
            n += v2[i];
        }
        v3.push_back(n % 10);
    }
    if(n >= 10)
    {
        v3.push_back(1);
    }
    return v3;
}

vector<uint8_t> multiplication2(const vector<uint8_t> &v1, const vector<uint8_t> &v2)
{
    vector<uint8_t> v3;
    vector<uint8_t> temp;
    for(unsigned int i = 0; i < v1.size(); ++i)
    {
        temp.resize(0);
        uint8_t n = 0;
        for(unsigned int j = 0; j < i; ++j)
        {
            temp.push_back(0);
        }
        for(unsigned int j = 0; j < v2.size(); ++j)
        {
            n = v1[i] * v2[j] + n / 10;
            temp.push_back(n % 10);
        }
        if(n >= 10)
        {
            temp.push_back(n / 10);
        }
        v3 = addition2(v3, temp);
    }
    return v3;
}

int main()
{
    cout << "calcolo di 12345^1000 (versione string): ";
    string a = "54321";
    string b = "1";
    auto start1 = high_resolution_clock::now();
    for(unsigned int i = 0; i < 1000; ++i)
    {
        b = multiplication1(a, b);
    }
    auto stop1 = high_resolution_clock::now();
    auto duration1 = duration_cast<milliseconds>(stop1 - start1);
    cout << duration1.count() << " ms" << endl;
    //-----------------------------------------------------------
    cout << "calcolo di 12345^1000 (versione vector): ";
    vector<uint8_t> c = {5, 4, 3, 2, 1};
    vector<uint8_t> d = {1};
    auto start2 = high_resolution_clock::now();
    for(unsigned int i = 0; i < 1000; ++i)
    {
        d = multiplication2(c, d);
    }
    auto stop2 = high_resolution_clock::now();
    auto duration2 = duration_cast<milliseconds>(stop2 - start2);
    cout << duration2.count() << " ms" << endl;
}

Output compilando con l'opzione -std=c++14:

Codice:

calcolo di 12345^1000 (versione string): 366 ms
calcolo di 12345^1000 (versione vector): 1090 ms

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

Output compilando con l'opzione -std=c++17:

Codice:

calcolo di 12345^1000 (versione string): 1409 ms
calcolo di 12345^1000 (versione vector): 1370 ms

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

In pratica, tralasciando i diversi approcci e le varie ottimizzazioni possibili, e tenendo conto del fatto che le versioni string e vector sono praticamente equivalenti dal punto di vista algoritmico, mi chiedo come mai le prestazioni tra le due versioni siano così diverse tra loro e come mai la situazione cambia ulteriormente al variare dello standard.

Se può essere utile utilizzo codeblocks 20.03 MinGW (GCC 8.1.0).

[ghira]

Fare 1000 moltiplicazioni non è l'ideale. Ma questo lo sai.

[apatriarca]

L'implementazione della libreria standard è diversa tra le varie versioni dello standard. Dovresti però confrontare performance solo con le ottimizzazioni attivate. Alcune implementazioni della libreria standard sono infatti imbarazzatamente lente in debugging ed èin pratica quello che stai testando.

[utente__medio]

Fare 1000 moltiplicazioni non è l'ideale. Ma questo lo sai.

Sono cosciente che esistono metodi più performanti, d'altronde questo stesso algoritmo presenta ampi margini di ottimizzazione, ma qui la questione è puramente "informatica".

L'implementazione della libreria standard è diversa tra le varie versioni dello standard. Dovresti però confrontare performance solo con le ottimizzazioni attivate. Alcune implementazioni della libreria standard sono infatti imbarazzatamente lente in debugging ed èin pratica quello che stai testando.

Premetto che non sono molto pratico con queste cose, infatti il mio rapporto con la programmazione si limita ad un semplice esercizio di logica. In ogni caso ti ringrazio per la dritta.
Spulciando tra le opzioni di compilazione ho notato che esistono vari flag di ottimizzazione, quale dovrei attivare nello specifico?

[apatriarca]

Generalmente si calcolano le performance con le opzioni che si usano quando si distribuisce il codice. Nel tuo caso anche solo -O dovrebbe essere sufficiente, ma siccome stai facendo dei test puoi provarne diverse e vedere come cambiano le performance. Mi aspetto il più grosso salto di performance tra -O0 (il default) e -O1 mentre il vantaggio dovrebbe essere visibile ma ridotto passando ai livelli successivi. A volte -Os produce codici migliori di -O2 o -O3 ma di solito no. In effetti è anche possibile mettersi a abilitare e disabilitare le singole ottimizzazione ma per la tua esplorazione mi fermerei alle opzioni con i numeri e quello con la s.

[utente__medio]

E in effetti... ecco l'output spuntando il flag -O3:

Codice:

calcolo di 12345^1000 (versione string): 109 ms
calcolo di 12345^1000 (versione vector): 144 ms

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


In ogni caso la versione string resta sempre più veloce di quella vector.

[apatriarca]

I miei risultati sono abbastanza diversi rispetto ai tuoi. Con le ottimizzazioni la versione con vector impiega circa la metà del tempo dell'altra e c'è una differenza abbastanza limitata tra le due versioni dello standard. Il comportamento è stato simile tra GCC 9.3.0 e CLANG 10. Tuttavia dipende molto anche dalla particolare architettura su cui stai girando il tuo programma (il mio processore è probabilmente più veloce perché i tempi sono di molto inferiori: 40-90ms con ottimizzazioni e sotto i 500ms in debug).

Non ti saprei dire perché nel tuo caso string sia più performante di vector nonostante le operazioni aggiuntive. Puoi provare a guardare il codice assembly prodotto o forse a usare un profiler. Ma il codice è comunque quello che è e forse non ne vale più di tanto la pena.

[utente__medio]

Tuttavia dipende molto anche dalla particolare architettura su cui stai girando il tuo programma (il mio processore è probabilmente più veloce perché i tempi sono di molto inferiori: 40-90ms con ottimizzazioni e sotto i 500ms in debug).

Effettivamente ho un modesto pentium dual core con più di 10 anni sul groppone!

Non ti saprei dire perché nel tuo caso string sia più performante di vector nonostante le operazioni aggiuntive. Puoi provare a guardare il codice assembly prodotto o forse a usare un profiler. Ma il codice è comunque quello che è e forse non ne vale più di tanto la pena.

Per il codice in sé in effetti non ne vale la pena, in quanto il mio intento era semplicemente quello di quantificare la differenza di prestazioni tra string e vector (anche se alla fine ho ottenuto un risultato "controintuitivo"). In ogni caso questa differenza di performance tra vector e string presumo persista anche al di fuori del codice in questione; sinceramente non conosco l'assembly, ma penso che non sia poi così difficile da capire/imparare, quindi quando avrò tempo e voglia proverò a capirci qualcosa.

Per quanto riguarda la genesi di questo codice, sto cercando di implementare una libreria per i "big int", o meglio "re-implementare", in quanto tempo fa avevo già fatto qualcosa di simile con le string, implementando le quattro operazioni mediante i classici metodi su carta che vengono insegnati a scuola (con alcune ottimizzazioni). Quello che sto facendo adesso invece è sostituire le string con i vector, in modo da poter velocizzare il tutto considerando più cifre alla volta. Volendo utilizzare una suddivisione fissa e come tipo uint64_t, vado a creare un vector<uint64_t> in cui immagazzinare le cifre (a partire da destra) del big int in questione in gruppi di lunghezza massima fissa pari a 9 (valore scelto per scongiurare l'overflow durante il prodotto tra due gruppi di cifre). Per l'addizione e la sottrazione non vedo ampi margini di miglioramento rispetto agli algoritmi classici insegnati a scuola, per la moltiplicazione invece potrei adottare algoritmi come quello di Karatsuba, ma a quel punto presumo che dovrei abbandonare la suddivisione fissa e adottare una suddivisione in gruppi di lunghezza variabile.
I risultati con vector<uint64_t> (che poi intendo sostituire con un'allocazione dinamica "a mano") e una suddivisione fissa a 9 cifre, rispetto alla vecchia versione con le string (in cui ovviamente si ricorre ad una suddivisione fissa ad 1 cifra), sono molto promettenti, ma se avete un diverso approccio da consigliarmi sono tutto orecchi!

[apatriarca]

Alcuni pensieri:
1. A meno che tu non debba stampare questi numeri molto spesso, non ha senso usare una notazione decimale per i tuoi numeri. Le "cifre" possono benissimo essere numeri a 32/64 bit. Le cifre a 32 bit hanno il vantaggio che sia la loro somma che il loro prodotto sono memorizzabili in 64 bit.
2. Il confronto di performance tra string e vector nel tuo caso non è molto importante per due ragioni: le tue performance sono basate in parte su un architettura di processore ormai datata e le due classi non forniscono le stesse funzionalità. Il primo punto diventa abbastanza ovvio confrontando le performance con un processore più moderno (di circa 2-3 anni fa) per cui le ottimizzazioni del tuo processore sono state pensate. Immagino tu possa ottenere un vantaggio dei vector anche sul tuo processore giocando un po' con le opzioni e forse facendo qualche piccola modifica al codice ma continua a non avere senso perché nella versione definitiva della libreria non puoi usare string, ma sono vector.

[utente__medio]

1. A meno che tu non debba stampare questi numeri molto spesso, non ha senso usare una notazione decimale per i tuoi numeri. Le "cifre" possono benissimo essere numeri a 32/64 bit.

Se intendi questo:

Quello che sto facendo adesso invece è sostituire le stringcon i vector, in modo da poter velocizzare il tutto considerando più cifre alla volta. Volendo utilizzare una suddivisione fissa e come tipo uint64_t, vado a creare un vector<uint64_t> in cui immagazzinare le cifre (a partire da destra) del big int in questione in gruppi di lunghezza massima fissa pari a 9 (valore scelto per scongiurare l'overflow durante il prodotto tra due gruppi di cifre).

è quello che sto implementando. Per esempio:

Codice:

big_int n("5577123456789123456789");

viene immagazzinato come

Codice:

vector<uint64_t> = {123456789, 123456789, 5577};

Se invece intendi qualche altra cosa, allora non ho capito a cosa ti riferisci.

2. Il confronto di performance tra string e vector nel tuo caso non è molto importante per due ragioni: ... ma continua a non avere senso perché nella versione definitiva della libreria non puoi usare string, ma sono vector.

Sì, ovviamente in questa nuova versione non posso che utilizzare i vector. Quella sulla differenza di performance riscontrata era una curiosità mia personale (scaturita dai risultati "controintuitivi" ottenuti) che non c'entra nulla con questa nuova libreria.