[C++] Efficienza sottrazione binaria

Fai una domanda Tutte le categorie
utente__medio11
utente__medio11
4 dic 2024, 14:23
Ciao, da qualche tempo ho ripreso la mia libreria sui big int per apportare qualche ottimizzazione.
Premetto che per addizione, sottrazione e moltiplicazione già eseguo i calcoli in base $2^32$, ma per la divisione ho optato per la base $2$. Di questa scelta se ne potrà poi discutere, ma per il momento vorrei soffermarmi su un'altra questione, ossia la differenza di efficienza tra due versioni di sottrazione binaria in colonna.

Di seguito il codice con tanto di test sulla velocità:
#include <iostream>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <vector>

using namespace std;
using namespace std::chrono;

vector<uint_fast8_t> sottazione_binaria_vecchia(const vector<uint_fast8_t> &v1, const vector<uint_fast8_t> &v2)
{
    vector<uint_fast8_t> v3 = v1;
    uint64_t i = 0;
    for(uint_fast8_t r = 2; i < v1.size(); ++i)
    {
        r = 2 + v3[i] - v2[i] - (r < 2);
        v3[i] = r % 2;
    }
    while(--i && !v3[i]);
    v3.resize(i + 1);
    return v3;
}

vector<uint_fast8_t> sottazione_binaria_nuova(const vector<uint_fast8_t> &v1, const vector<uint_fast8_t> &v2)
{
    vector<uint_fast8_t> v3 = v1;
    uint64_t i = 0;
    for(uint_fast8_t flag = 0; i < v1.size(); ++i)
    {
        if(v2[i] != flag)
        {
            flag = v3[i] = !v3[i];
        }
    }
    while(--i && !v3[i]);
    v3.resize(i + 1);
    return v3;
}

vector<uint_fast8_t> converti_stringa(char *s)
{
    vector<uint_fast8_t> v;
    for(; *s; v.push_back(*s++ - '0'));
    reverse(v.begin(), v.end());
    return v;
}

int main()
{
    char s1[] = "1010101110101011100010011010010101101000011010001111001111111010101000101010111101010010101010101010100101010001110101001010001110101010010010111000111100010100011111111010001010001100011001010";
    char s2[] = "1010100101001010101000001110100101110100010111010101010010000111110010111000110101001011010010100001111001001010101010100001011010010000001110010110101000001111111110100101010001010101001010101";
    vector<uint_fast8_t> v1 = converti_stringa(s1);
    vector<uint_fast8_t> v2 = converti_stringa(s2);

    unsigned int n = 1'000'000;

    auto start_1 = high_resolution_clock::now();
    vector<vector<uint_fast8_t>> w1;
    w1.resize(n);
    for(unsigned int i = 0; i < n; w1[i++] = sottazione_binaria_vecchia(v1, v2));
    auto stop_1 = high_resolution_clock::now();
    cout << duration_cast<milliseconds>(stop_1 - start_1).count() << " ms (vecchio)" << endl;

    auto start_2 = high_resolution_clock::now();
    vector<vector<uint_fast8_t>> w2;
    w2.resize(n);
    for(unsigned int i = 0; i < n; w2[i++] = sottazione_binaria_nuova(v1, v2));
    auto stop_2 = high_resolution_clock::now();
    cout << duration_cast<milliseconds>(stop_2 - start_2).count() << " ms (nuovo)" << endl;

    if(w1.back() != w2.back())
    {
        return -1;
    }
}

In particolare mi aspetterei che la nuova versione, basata su poche operazioni elementari, sia abbastanza più veloce di quella vecchia, invece provando varie combinazioni di ottimizzazione del compilatore e di scelta del tipo (ipotizzo che [inline]uint_fast8_t[/inline] dovrebbe essere il più adatto sulla carta, o sbaglio?), ottengo che le performance sono sovrapponibili, se non addirittura migliori per la vecchia versione.

Che ne pensate?
Risposte
apatriarca
apatriarca
6 dic 2024, 11:31
Più tardi di fornisco una risposta più completa, ma ti consiglio di iniziare a cercare branch prediction, instruction pipelining e vectorization.
utente__medio11
utente__medio11
6 dic 2024, 14:05
Ok grazie. In effetti già avevo trovato qualcosa del genere:
https://stackoverflow.com/questions/315 ... 382#315382

Ho provato a modificare il codice rimuovendo l'if, e compilando con -O3 la nuova versione diventa più veloce di quella vecchia di circa 1/3.
Dopo con calma posto il codice aggiornato.
apatriarca
apatriarca
6 dic 2024, 16:14
Provando il tuo codice sul mio computer, la seconda versione è più veloce anche senza modifiche. Tuttavia io non mi preoccuperei più di tanto di ottimizzazioni di questo tipo quando il problema più grosso è nella rappresentazione del numero. Inoltre [tt]uint_fast8_t[/tt] potrebbe avere un numero di bit maggiore di [tt]8[/tt] e quindi la tua rappresentazione potrebbe usare numeri a [tt]32[/tt] bit per ogni singolo bit del numero che rappresenti. Quando vuoi che qualcosa abbia una specifica dimensione in memoria utilizza i tipi come [tt]uint8_t[/tt].
utente__medio11
utente__medio11
6 dic 2024, 18:32
"utente__medio":
Ho provato a modificare il codice rimuovendo l'if, e compilando con -O3 la nuova versione diventa più veloce di quella vecchia di circa 1/3.
Dopo con calma posto il codice aggiornato.

Ecco il codice:
#include <iostream>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <vector>

using namespace std;
using namespace std::chrono;

vector<uint_fast8_t> sottazione_binaria_vecchia(const vector<uint_fast8_t> &v1, const vector<uint_fast8_t> &v2)
{
    vector<uint_fast8_t> v3(v1.size());
    uint64_t i = 0;
    for(uint_fast8_t r = 2; i < v1.size(); ++i)
    {
        v3[i] = (r = 2 + v1[i] - v2[i] - (r < 2)) % 2;
    }
    while(--i && !v3[i]);
    v3.resize(i + 1);
    return v3;
}

vector<uint_fast8_t> sottazione_binaria_nuova(const vector<uint_fast8_t> &v1, const vector<uint_fast8_t> &v2)
{
    vector<uint_fast8_t> v3(v1);
    uint64_t i = 0;
    for(uint_fast8_t flag = 0; i < v1.size(); ++i)
    {
        if(v2[i] != flag)
        {
            flag = v3[i] = !v3[i];
        }
    }
    while(--i && !v3[i]);
    v3.resize(i + 1);
    return v3;
}

vector<uint_fast8_t> sottazione_binaria_nuova_2(const vector<uint_fast8_t> &v1, const vector<uint_fast8_t> &v2)
{
    vector<uint_fast8_t> v3(v1.size());
    uint64_t i = 0;
    for(uint_fast8_t flag = 0; i < v1.size(); ++i)
    {
        flag ^= (flag ^ v2[i]) & (flag ^ (v3[i] = flag ^ v2[i] ^ v1[i]));
    }
    while(--i && !v3[i]);
    v3.resize(i + 1);
    return v3;
}

vector<uint_fast8_t> converti_stringa(char *s)
{
    vector<uint_fast8_t> v;
    for(; *s; v.push_back(*s++ - '0'));
    reverse(v.begin(), v.end());
    return v;
}

int main()
{
    char s1[] = "1010101110101011100010011010010101101000011010001111001111111010101000101010111101010010101010101010100101010001110101001010001110101010010010111000111100010100011111111010001010001100011001010";
    char s2[] = "1010100101001010101000001110100101110100010111010101010010000111110010111000110101001011010010100001111001001010101010100001011010010000001110010110101000001111111110100101010001010101001010101";
    vector<uint_fast8_t> v1 = converti_stringa(s1);
    vector<uint_fast8_t> v2 = converti_stringa(s2);

    unsigned int n = 1'000'000;

    auto start_1 = high_resolution_clock::now();
    vector<vector<uint_fast8_t>> w1;
    w1.resize(n);
    for(unsigned int i = 0; i < n; w1[i++] = sottazione_binaria_vecchia(v1, v2));
    auto stop_1 = high_resolution_clock::now();
    cout << duration_cast<milliseconds>(stop_1 - start_1).count() << " ms (vecchio)" << endl;

    auto start_2 = high_resolution_clock::now();
    vector<vector<uint_fast8_t>> w2;
    w2.resize(n);
    for(unsigned int i = 0; i < n; w2[i++] = sottazione_binaria_nuova(v1, v2));
    auto stop_2 = high_resolution_clock::now();
    cout << duration_cast<milliseconds>(stop_2 - start_2).count() << " ms (nuovo)" << endl;

    auto start_3 = high_resolution_clock::now();
    vector<vector<uint_fast8_t>> w3;
    w3.resize(n);
    for(unsigned int i = 0; i < n; w3[i++] = sottazione_binaria_nuova_2(v1, v2));
    auto stop_3 = high_resolution_clock::now();
    cout << duration_cast<milliseconds>(stop_3 - start_3).count() << " ms (nuovo_2)" << endl;

    if(w1.back() != w2.back() || w1.back() != w3.back())
    {
        return -1;
    }
}

Secondo te quell'if può essere sostituito in modo più efficiente rispetto a quello da me utilizzato alla riga 45?


Inoltre, in riferimento a (nuovo), guarda come cambia l'output con e senza la condizione
|| w1.back() != w3.back()

nell'if finale del main():
947 ms (vecchio)
1006 ms (nuovo)
657 ms (nuovo_2)

Process returned 0 (0x0)   execution time : 3.133 s

947 ms (vecchio)
829 ms (nuovo)
659 ms (nuovo_2)

Process returned 0 (0x0)   execution time : 2.959 s

:?


"apatriarca":
Tuttavia io non mi preoccuperei più di tanto di ottimizzazioni di questo tipo quando il problema più grosso è nella rappresentazione del numero.

In che senso?


"apatriarca":
Inoltre uint_fast8_t potrebbe avere un numero di bit maggiore di 8 e quindi la tua rappresentazione potrebbe usare numeri a 32 bit per ogni singolo bit del numero che rappresenti. Quando vuoi che qualcosa abbia una specifica dimensione in memoria utilizza i tipi come uint8_t.

Lo so, ma quello che mi interessa è la velocità, visto peraltro che dubito che possano insorgere problemi legati al consumo di memoria.
Perché secondo te dovrei preferire [inline]uint8_t[/inline] a [inline]uint_fast8_t[/inline]?
apatriarca
apatriarca
10 dic 2024, 15:25
Prima di tutto credo sia opportuno osservare che sul mio computer ho ottenuto i seguenti risultati con uno dei due compilatori
348 ms (vecchio)
271 ms (nuovo)
377 ms (nuovo_2)

e con l'altro
347 ms (vecchio)
255 ms (nuovo)
443 ms (nuovo_2)

È quindi evidente come questo genere di ottimizzazioni sia molto dipendente dal computer sul quale è eseguito, sul compilatore e le sue opzioni. Insomma, sul mio computer la versione con l'if sembra la più efficiente. Puoi dare una occhiata qui per vedere in che modo i compilatori trasformano il tuo codice in istruzioni per il compilatore: https://godbolt.org/z/fYx4GMshd.
utente__medio11
utente__medio11
10 dic 2024, 21:19
"apatriarca":
Prima di tutto credo sia opportuno osservare che sul mio computer ho ottenuto i seguenti risultati...

Ma quei risultati sono stati ottenuti compilando con [inline]-O2[/inline] o [inline]-O3[/inline]?
Chiedo perché io invece ottengo un comportamento simile con le ottimizzazioni del compilatore disabilitate.


"apatriarca":
È quindi evidente come questo genere di ottimizzazioni sia molto dipendente dal computer sul quale è eseguito, sul compilatore e le sue opzioni. Insomma, sul mio computer la versione con l'if sembra la più efficiente.

Non me l'aspettavo... il discorso sul "branch mispredictions" non vale più!?
A questo punto quale delle tre implementazioni dovrei scegliere? E più in generale quali regole di programmazione dovrei darmi per ottimizzare le prestazioni?

Capisco che il tutto dipenda da vari fattori, ma, visto che il mio è un PC molto datato, se volessi orientarmi verso l'efficienza su CPU moderne, quali principi di massima dovrei adottare?
apatriarca
apatriarca
10 dic 2024, 21:59
Il comportamento è più o meno lo stesso indipendentemente dal livello di ottimizzazione. Il problema è che tutte e tre le implementazioni hanno la stessa complessità e un numero relativamente simile di istruzioni per cui quello migliore dipende dalla macchina e dal compilatore. Un discorso diverso riguarda invece cose come fare operazioni su cifre 32 bit in contemporanea invece che avere un singolo bit per ogni byte come nel tuo caso. In quel caso è possibile sfruttare le operazioni del processore per ottenere prestazioni molto superiori a quelle che stai ottenendo. Un piccolo test mi ha portato a tempi intorno ai 60ms e probabilmente si può fare anche molto di meglio.
utente__medio11
utente__medio11
11 dic 2024, 01:13
"apatriarca":
Un discorso diverso riguarda invece cose come fare operazioni su cifre 32 bit in contemporanea invece che avere un singolo bit per ogni byte come nel tuo caso. In quel caso è possibile sfruttare le operazioni del processore per ottenere prestazioni molto superiori a quelle che stai ottenendo. Un piccolo test mi ha portato a tempi intorno ai 60ms e probabilmente si può fare anche molto di meglio.

Se ti riferisci al fatto di effettuare i calcoli in base $2^32$, riprendo quello che ho scritto nel post iniziale:
"utente__medio":
da qualche tempo ho ripreso la mia libreria sui big int per apportare qualche ottimizzazione.
Premetto che per addizione, sottrazione e moltiplicazione già eseguo i calcoli in base $2^32$, ma per la divisione ho optato per la base $2$. Di questa scelta se ne potrà poi discutere, ma per il momento vorrei soffermarmi su un'altra questione, ossia la differenza di efficienza tra due versioni di sottrazione binaria in colonna.

Dove la sottrazione in base $2$ è utilizzata nella divisione in base $2$ per evitare continui cambi di base.

Nella divisione in colonna, la singola cifra $c$ del quoziente è data dal massimo valore di $c$ per cui $c*d<=n$ (dove $d$ è il divisore e $n$ è la parte del dividendo considerata). La suddetta disequazione va ovviamente risolta per tentativi (che a loro volta necessitano di moltiplicazioni e/o sottrazioni tra big int), tranne che per la base $2$, dove infatti tutto si riduce ad un semplice confronto tra $n$ e $d$. E' per questo motivo che per la divisione avrei optato per la base $2$.
Che ne pensi? Secondo te dovrei comunque provare ad implementare la divisione in colonna in base $2^32$ e poi confrontare i tempi?
apatriarca
apatriarca
11 dic 2024, 18:32
È certamente possibile fare la divisione in base diversa da 2. Ci sono diversi algoritmi, ognuno adatto a specifiche situazioni come si può osservare nella libreria GMP. Tuttavia, per iniziare io partirei da qualcosa come quello descritto in questo articolo o in qualche libreria per grandi numeri più semplice di GMP (che come ho detto ha divisioni specializzate per casi specifici e quindi è meno comprensibile).
utente__medio11
utente__medio11
11 dic 2024, 18:48
Qualche idea su come implementare la divisione in colonna in base $2^32$ già ce l'avrei, e appena ho tempo provo a giocarci un po'.
Quello che chiedevo è se secondo te una "buona" implementazione della divisione in colonna in base $2^32$ è sicuramente più veloce della corrispettiva in base $2$, oppure potrebbero giocarsela?
apatriarca
apatriarca
11 dic 2024, 18:54
Credo sia sicuramente più veloce.
utente__medio11
utente__medio11
11 dic 2024, 19:20
Ok!

"utente__medio":
Qualche idea su come implementare la divisione in colonna in base $ 2^32 $ già ce l'avrei, e appena ho tempo provo a giocarci un po'.

Appena lo faccio, ti aggiorno.
utente__medio11
utente__medio11
26 dic 2024, 15:32
Ho buttato giù un po' di codice; in particolare le funzioni che si occupano della divisione tra big int in base $2$ e $2^32$ sono rispettivamente [inline]division_2_RR()[/inline] e [inline]division_2to32_RR()[/inline] (dove "R" sta per "Reversed", e "RR" indica che sia l'input che l'output presentano le cifre in ordine inverso).

Ecco il codice:

Ovviamente le prestazioni variano in base ai valori del dividendo e del divisore, ma la divisione in base $2^32$ effettivamente risulta sempre più veloce di quella in base $2$ (per esempio per la prima coppia di stringhe nel main() è più veloce di circa 265 volte, per la seconda coppia di stringhe è più veloce di circa 9 volte, per la terza coppia di stringhe i tempi sono quasi sovrapponibili).

L'algoritmo di fondo è lo stesso in entrambi i casi (e più o meno coincide con quello della classica divisione in colonna), le differenze invece sono costituite dall'individuazione delle singole cifre del quoziente (che in base $2$, potendo assumere solo i valori $0$ e $1$, sono determinate attraverso un semplice confronto, mentre in base $2^32$ vanno trovate attraverso un procedimento a tentativi) e dalla sottrazione tra le cifre del dividendo "abbassate" e il prodotto della cifra del quoziente appena trovata col divisore.

Per spiegare il procedimento iterativo per l'individuazione delle singole cifre del quoziente in base $2^32$, riprendo e aggiorno un post di un mio vecchio topic:
Consideriamo la seguente divisione in colonna in base $10$ ($r_i$ e $d_i$, con $i_(max)=5$, indicano rispettivamente le singole cifre di $R$ e $D$ a partire da quelle evidenziate):

[size=130]$\overbrace{\underbrace{3}_(r_0)45201}^R8743566:\overbrace{\underbrace{8}_(d_1)7154}^D$[/size]

Il nostro scopo è quello di calcolare $q=[R/D]=[345201/87154]=3$.

Si parte da un valore di primo tentativo $q_1=q_(max)=[a_1/d_1]=[(10*r_0+r_1)/d_1]=[34/8]=4$ a scendere.

Per testare $q_j$ non vado a fare il calcolo per intero verificando che $q_j*D<=R$, ma avanzo una cifra alla volta.
Cerco di spiegare meglio quello che intendo... detti $b_i=q_j*d_i$ e $a_(i>1)=(a_(i-1)-b_(i-1))*10+r_(i)$:

- se $a_iq$, e quindi diminuisco $q_j$ di un'unità, ossia $q_(j+1)=q_j-1$;
- invece se $a_i-b_i>=q_j$ o $i>i_(max)$, allora deduco che $q_j<=q$, e quindi, avendo già testato tutti i valori $q_j$ più grandi, concludo che $q_j=q$;
- altrimenti incremento $i$.

Riprendendo l'esempio numerico sopra postato, per la determinazione di $q$ si ha:
# $q_1=[a_1//d_1]=[34//8]=4$ :
## $a_1=34$ e $b_1=q_1*d_1=4*8=32$, essendo $a_1>=b_1$ e $a_1-b_1 ## $a_2=(a_1-b_1)*10+r_2=25$ e $b_2=q_1*d_2=4*7=28$, essendo $a_2 # $q_2=q_1-1=3$ :
## $a_1=34$ e $b_1=q_2*d_1=3*8=24$, essendo $a_1-b_1>=q_2$ posso concludere che $q=q_2=3$.

Un ragionamento simile l'ho fatto in base $2^32$, ma invece di partire da $q_max$ e scendere di un'unità, ho adottato una ricerca binaria, con $q_(max)=[a_1/d_1]$ come in precedenza, e

$a_1-b_1=q_(min)=>a_1-q_(min)*d_1=q_(min)=>q_(min)=[a_1/(d_1+1)]$.


Se riscontrate qualche bug o avete qualche suggerimento per migliorare il codice (sia relativamente all'algoritmo generale della divisione in colonna sia relativamente alla ricerca binaria), fatemi sapere.
Rispondi
Per rispondere a questa discussione devi prima effettuare il login.