[C++] Differenza di prestazioni con implementazioni simili
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:
Output compilando con l'opzione [inline]-std=c++14[/inline]:
Output compilando con l'opzione [inline]-std=c++17[/inline]:
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).
#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).
Risposte
Fare 1000 moltiplicazioni non è l'ideale. Ma questo lo sai.
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.
"ghira":
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".
"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.
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?
Generalmente si calcolano le performance con le opzioni che si usano quando si distribuisce il codice. Nel tuo caso anche solo [tt]-O[/tt] 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 [tt]-O0[/tt] (il default) e [tt]-O1[/tt] mentre il vantaggio dovrebbe essere visibile ma ridotto passando ai livelli successivi. A volte [tt]-Os[/tt] produce codici migliori di [tt]-O2[/tt] o [tt]-O3[/tt] 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.
E in effetti... ecco l'output spuntando il flag [inline]-O3[/inline]:
In ogni caso la versione string resta sempre più veloce di quella vector.
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.
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.
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.
"apatriarca":
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!
"apatriarca":
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 [inline]string[/inline] e [inline]vector[/inline] (anche se alla fine ho ottenuto un risultato "controintuitivo"). In ogni caso questa differenza di performance tra [inline]vector[/inline] e [inline]string[/inline] 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 [inline]string[/inline], 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 [inline]string[/inline] con i [inline]vector[/inline], in modo da poter velocizzare il tutto considerando più cifre alla volta. Volendo utilizzare una suddivisione fissa e come tipo [inline]uint64_t[/inline], vado a creare un [inline]vector
I risultati con [inline]vector
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.
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.
"apatriarca":
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:
"utente__medio":
Quello che sto facendo adesso invece è sostituire le [inline]string[/inline]con i [inline]vector[/inline], in modo da poter velocizzare il tutto considerando più cifre alla volta. Volendo utilizzare una suddivisione fissa e come tipo [inline]uint64_t[/inline], vado a creare un [inline]vector[/inline] 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:
big_int n("5577123456789123456789");viene immagazzinato come
vector<uint64_t> = {123456789, 123456789, 5577};Se invece intendi qualche altra cosa, allora non ho capito a cosa ti riferisci.
"apatriarca":
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.
Con il mio pc, compilando con visual studio e con mille cose aperte, la versione string è più rapida in debug mentre più lenta in release (non vi è invece differenza tra versioni del C++). Nota che ho ridotto un po' il tuo codice mettendo dei reserve e usando i template per eliminare la duplicazione. Però l'algoritmo per la moltiplicazione non va bene. Vedo se ho tempo più tardi di scrivere un algoritmo più efficiente.
La mia riscrittura usando i template:
La mia riscrittura usando i template:
#include <iostream>
#include <cstdint>
#include <chrono>
#include <string>
#include <vector>
using namespace std;
using namespace std::chrono;
template < typename NumberRepType >
NumberRepType
addition( const NumberRepType& n1, const NumberRepType& n2 )
{
const uint32_t S1 = size( n1 );
const uint32_t S2 = size( n2 );
const uint32_t SM = max( S1, S2 );
NumberRepType n3;
n3.reserve( SM + 1 ); // reserve representation size
uint32_t n = 0;
for ( uint32_t i = 0; i < SM; ++i )
{
if ( i < S1 )
{
n += ( n1[ i ] - '0' );
}
if ( i < S2 )
{
n += ( n2[ i ] - '0' );
}
n3.push_back( static_cast< uint8_t >( ( n % 10 ) + '0' ) );
n /= 10;
}
if ( n > 0 )
{
n3.push_back( '1' );
}
return n3;
}
template < typename NumberRepType >
NumberRepType
multiplication( const NumberRepType& n1, const NumberRepType& n2 )
{
const uint32_t S1 = size( n1 );
const uint32_t S2 = size( n2 );
NumberRepType n3;
n3.reserve( ( S1 * S2 ) + 1 );
NumberRepType temp;
for ( uint32_t i = 0; i < S1; ++i )
{
temp.clear( );
uint32_t n = 0;
for ( uint32_t j = 0; j < i; ++j )
{
temp.push_back( '0' );
}
for ( uint32_t j = 0; j < S2; ++j )
{
n += ( n1[ i ] - '0' ) * ( n2[ j ] - '0' );
temp.push_back( n % 10 + '0' );
}
n /= 10;
if ( n > 0 )
{
temp.push_back( n + '0' );
}
n3 = addition< NumberRepType >( n3, temp );
}
return n3;
}
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 = multiplication( 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 = multiplication( c, d );
}
auto stop2 = high_resolution_clock::now( );
auto duration2 = duration_cast< milliseconds >( stop2 - start2 );
cout << duration2.count( ) << " ms" << endl;
}
"vict85":
Con il mio pc, compilando con visual studio e con mille cose aperte, la versione string è più rapida in debug mentre più lenta in release (non vi è invece differenza tra versioni del C++).
Vabbè mi sembra di capire che al variare di hardware, compilatore e settaggi, ognuno ottenga un risultato diverso!
"vict85":
Nota che ho ridotto un po' il tuo codice mettendo dei reserve e usando i template per eliminare la duplicazione.
I reserve() nella versione ottimizzata li utilizzo anche io, qui li ho omessi per semplificare.
In ogni caso per quanto riguarda la moltiplicazione non è sufficiente
n3.reserve(n1.size() + n2.size())
?
"vict85":
Però l'algoritmo per la moltiplicazione non va bene. Vedo se ho tempo più tardi di scrivere un algoritmo più efficiente.
Quello postato è il classico algoritmo che si utilizza anche su carta, e le uniche ottimizzazione che mi vengono in mente sono quella di determinare l'ordine dei due fattori al fine di minimizzare il numero di chiamate ad addition() e quella di rimuovere l'aggiunta di zeri finali andando a sommare direttamente a partire dalla cifra in esame.
Inoltre
"utente__medio":
per la moltiplicazione 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.
Ma se hai in mente qualcosa di diverso sarei curioso di sapere di cosa si tratta.
Tu stai memorizzando valori da \(0\) a \(10^{10}-1\) nel tuo intero a \(64\) bit, ma nulla ti impedisce di memorizzare valori da \(0\) a \(2^{64} - 1\). L'unica difficoltà consiste nel riconoscere l'overflow per l'addizione ed estrarre i 64 bit più significativi per la moltiplicazione (ma questo è anche vero nel tuo caso) in C++ in modo portabile. Ovviamente in assembly è immediato, ma a volte il C++ si complica la vita da questo punto di vita.
@apatriarca ok, ora ho capito cosa intendevi nel precedente post. All'inizio avevo anche pensato di sfruttare "l'overflow circolare" degli interi senza segno, ma poi avendo l'impressione di andare a complicare troppo le cose, col rischio peraltro di implementare un codice meno performante, non mi sono più soffermato sulla questione, limitandomi invece a considerare numeri di 9 cifre che in ogni caso, anche con la moltiplicazione, non generano alcun overflow.
In ogni caso domani se ho tempo provo a riflettere concretamente su questo approccio.
In ogni caso domani se ho tempo provo a riflettere concretamente su questo approccio.
Stai facendo molte più somme del necessario. Puoi raggruppare gli addendi in modo da calcolare un cifra del risultato per volta.
Per esempio, se i numeri sono \(\displaystyle a = a_0 + 10a_1 + 100a_2\) e \(\displaystyle b_0 + 10b_1\) allora \(ab = c_0 + 10c_1 + 10^2c_2 + 10^3c_3 + 10^4c_4\) dove:
\(\tilde{c}_0 = a_0b_0\)
\(c_0 = \tilde{c}_0 \pmod{10}\)
\(r_1 = \lfloor \tilde{c}_0 / 10\rfloor\)
\(\tilde{c}_1 = a_1b_0 + a_0b_1 + r_1\)
\(c_1 = \tilde{c}_1 \pmod{10}\)
\(r_2 = \lfloor \tilde{c}_1 / 10\rfloor\)
\(\tilde{c}_2 = a_2b_0 + a_1b_1 + r_2\)
\(c_2 = \tilde{c}_2 \pmod{10}\)
\(r_3 = \lfloor \tilde{c}_2 / 10\rfloor\)
\(\tilde{c}_3 = a_2b_1 + r_3\)
\(c_3 = \tilde{c}_3 \pmod{10}\)
\(c_4 = r_4 = \lfloor \tilde{c}_3 / 10\rfloor\)
Riguardo alla dimensione, hai ragione: \(size(n_1) + size(n_2)\) è effettivamente abbastanza.
Per esempio, se i numeri sono \(\displaystyle a = a_0 + 10a_1 + 100a_2\) e \(\displaystyle b_0 + 10b_1\) allora \(ab = c_0 + 10c_1 + 10^2c_2 + 10^3c_3 + 10^4c_4\) dove:
\(\tilde{c}_0 = a_0b_0\)
\(c_0 = \tilde{c}_0 \pmod{10}\)
\(r_1 = \lfloor \tilde{c}_0 / 10\rfloor\)
\(\tilde{c}_1 = a_1b_0 + a_0b_1 + r_1\)
\(c_1 = \tilde{c}_1 \pmod{10}\)
\(r_2 = \lfloor \tilde{c}_1 / 10\rfloor\)
\(\tilde{c}_2 = a_2b_0 + a_1b_1 + r_2\)
\(c_2 = \tilde{c}_2 \pmod{10}\)
\(r_3 = \lfloor \tilde{c}_2 / 10\rfloor\)
\(\tilde{c}_3 = a_2b_1 + r_3\)
\(c_3 = \tilde{c}_3 \pmod{10}\)
\(c_4 = r_4 = \lfloor \tilde{c}_3 / 10\rfloor\)
Riguardo alla dimensione, hai ragione: \(size(n_1) + size(n_2)\) è effettivamente abbastanza.
"vict85":
Stai facendo molte più somme del necessario. Puoi raggruppare gli addendi in modo da calcolare un cifra del risultato per volta.
Per esempio, se i numeri sono...
Ma in fin dei conti non è equivalente a
"utente__medio":
determinare l'ordine dei due fattori al fine di minimizzare il numero di chiamate ad addition() e a rimuovere l'aggiunta di zeri finali andando a sommare direttamente a partire dalla cifra in esame.
?
Inoltre andando a calcolare un cifra del risultato per volta senza passare per la funzione addition() non si corre il rischio, a causa delle potenziali molteplici addizioni da effettuare, di incorrere in un overflow di cui non è possibile tenere traccia?
P.S.
Sto iniziando a riflettere sull'approccio dell'overflow "circolare" suggerito da apatriarca, ma ho come l'impressione che questa strada conduca ad un codice meno performante (più lento). Sbaglio?
Perché dovrebbe essere più lento?
Nel caso della somma tu hai per ogni cifra qualcosa come:
Nel caso di 32 bit come cifre hai invece
Puoi vedere due versioni di somme al link: https://godbolt.org/z/v7rbEdo6W. Ho rimosso tutta la parte della gestione della memoria e sono semplicemente degli array della dimensione che si suppone già essere abbastanza grande per contenere i valori che ti servono. Il calcolo nel ciclo principale nel tuo caso è il seguente in assembly:
Nell'altro caso è il seguente
Anche senza sapere molto di assembly è chiaro che il secondo codice ha meno operazioni ed è quindi probabilmente più veloce.
Stai inoltre sprecando un sacco di byte memorizzando solo 9 cifre decimali in un intero a 64 bit.. Tanto vale memorizzarlo in 32 bit e fare le operazioni su 64 come ho fatto nel mio caso in basso.
Nel caso della somma tu hai per ogni cifra qualcosa come:
uint64_t sum = a[i] + b[i] + carry; c[i] = sum % 1000000000; carry = sum / 1000000000;
Nel caso di 32 bit come cifre hai invece
uint64_t sum = (uint64_t)a[i] + (uint64_t)b[i] + (uint64_t)carry; c[i] = (uint32_t)sum; // extract low 32 bits carry = (uint32_t)(sum >> 32); // extract high 32 bits
Puoi vedere due versioni di somme al link: https://godbolt.org/z/v7rbEdo6W. Ho rimosso tutta la parte della gestione della memoria e sono semplicemente degli array della dimensione che si suppone già essere abbastanza grande per contenere i valori che ti servono. Il calcolo nel ciclo principale nel tuo caso è il seguente in assembly:
mov rcx, QWORD PTR [r11+rsi*8]
add rcx, QWORD PTR [r9+rsi*8]
add rcx, rdx
mov rdx, rcx
shr rdx, 9
mov rax, rdx
mul rbx
shr rdx, 11
imul rax, rdx, 1000000000
sub rcx, rax
mov QWORD PTR [r8+rsi*8], rcx
Nell'altro caso è il seguente
mov r11d, DWORD PTR [r10+rax*4]
mov ecx, DWORD PTR [r9+rax*4]
add rcx, r11
lea r11, [rcx+rdx]
add edx, ecx
mov edx, edx
mov QWORD PTR [r8+rax*8], rdx
Anche senza sapere molto di assembly è chiaro che il secondo codice ha meno operazioni ed è quindi probabilmente più veloce.
Stai inoltre sprecando un sacco di byte memorizzando solo 9 cifre decimali in un intero a 64 bit.. Tanto vale memorizzarlo in 32 bit e fare le operazioni su 64 come ho fatto nel mio caso in basso.
Sbagli, e anche di molto. Il tuo codice è ben poco performante ed è dominato dalle allocazioni di memoria. Per capire quanto sia pessimo, prova a compilare e lanciare questa versione:
La versione con i vector domina di molto in questa versione.
Nota che le versioni professionali di librerie di questo tipo usano algoritmi ancora migliori (per lo meno quanto i numeri diventano grandi) e utilizzano l'approccio di apatriarca. Io ho usato la versione con gli uint8_t per mostrarti che il tuo codice è centinaia di volte peggio di un codice performante. Raggruppare in gruppi da 9 cifre dovrebbe migliorare le performance di 9 volte. Usare potenze di due è ancora meglio, ma rende meno efficiente il passaggio da e per string. Quindi la scelta su che approccio usare dipende da quanto ti serva convertire da e per string.
#include <chrono>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using namespace std::chrono;
template<typename NumberRepType>
void
multiplication(NumberRepType& result, NumberRepType const& a, NumberRepType const& b)
{
uint32_t const aSize = size(a);
uint32_t const bSize = size(b);
uint32_t const resultSize = aSize + bSize;
result.clear();
uint32_t r = 0;
for (uint32_t S = 0; S < resultSize - 1; ++S)
{
int32_t i = min(aSize - 1, S);
int32_t j = S - i;
uint32_t v = r;
for (; i > -1 && j < bSize; i--, j++)
{
uint32_t const ai = a[i] - '0';
uint32_t const bj = b[j] - '0';
v += ai * bj;
}
result.push_back(static_cast<char>(v % 10) + '0');
r = v / 10;
}
for (; r > 0; r /= 10)
{
result.push_back(static_cast<char>(r % 10) + '0');
}
}
int
main()
{
cout << "calcolo di 12345^1000 (versione string): ";
string a = "1";
string b = "54321";
auto start1 = high_resolution_clock::now();
string result;
result.reserve(5010);
a.reserve(5010);
for (uint32_t i = 0; i < 1000; ++i)
{
multiplication(result, a, b);
swap(result, a);
}
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 = {1};
vector<uint8_t> d = {5, 4, 3, 2, 1};
auto start2 = high_resolution_clock::now();
vector<uint8_t> resultv;
resultv.reserve(5010);
c.reserve(5010);
for (unsigned int i = 0; i < 1000; ++i)
{
multiplication(resultv, c, d);
}
auto stop2 = high_resolution_clock::now();
auto duration2 = duration_cast<milliseconds>(stop2 - start2);
cout << duration2.count() << " ms" << endl;
}
La versione con i vector domina di molto in questa versione.
Nota che le versioni professionali di librerie di questo tipo usano algoritmi ancora migliori (per lo meno quanto i numeri diventano grandi) e utilizzano l'approccio di apatriarca. Io ho usato la versione con gli uint8_t per mostrarti che il tuo codice è centinaia di volte peggio di un codice performante. Raggruppare in gruppi da 9 cifre dovrebbe migliorare le performance di 9 volte. Usare potenze di due è ancora meglio, ma rende meno efficiente il passaggio da e per string. Quindi la scelta su che approccio usare dipende da quanto ti serva convertire da e per string.
A parte tutto questo, stiamo veramente calcolando $a^1000$ moltiplicando per $a$ mille volte?
In qualunque modo facciamo le moltiplicazioni, ne stiamo facendo troppissime. O non ho capito niente?
In qualunque modo facciamo le moltiplicazioni, ne stiamo facendo troppissime. O non ho capito niente?
@ghira: il calcolo non è importante perché lo scopo era quello di confrontare le performance di due codici che fanno la stessa cosa.
"vict85":
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:
#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:
Con quest'implementazione non penso di star facendo più operazioni del necessario, o sbaglio?
"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 [inline]v[/inline] 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:
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?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo