[C++] Differenza di prestazioni con implementazioni simili

[utente__medio11]

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:

#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 [inline]-std=c++14[/inline]:

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 [inline]-std=c++17[/inline]:

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).

[apatriarca]

Questo thread sta diventando molto lungo e credo sia opportuno fare due piccoli commenti:
1. Quando si inizia a lavorare su algoritmi più o meno complicati una comprensione (almeno di base) sulla complessità computazionali è molto utile.
2. In questo forum non siamo certamente esperti di questo genere di algoritmi, ma esistono diversi articoli e qualche libro che descrive algoritmi per questo genere di operazioni. Un punto di partenza potrebbe essere quello di guardare una libreria come GMP che descrive che algoritmi usano: https://gmplib.org/manual/Algorithms.
3. Siccome l'implementazione ottimale per determinati processori non è necessariamente la stessa per altri, libreria come GMP fanno uso di implementazioni diverse in base al sistema.

[utente__medio11]

"apatriarca":Un punto di partenza potrebbe essere quello di guardare una libreria come GMP che descrive che algoritmi usano: https://gmplib.org/manual/Algorithms.

Ottimo, appena possibile gli darò un'occhiata.

Grazie comunque per i vari consigli che mi avete dato!