Differenza di prestazioni tra codici simili

Nippolo

il 18 nov 2021, 00:11

21 risposte

21 Risposte - Pagina 2

A
Alexv
Molto attivo
Iscritto da
giu, 2018
Messaggi:
646
Re: Differenza di prestazioni tra codici simili
19 nov 2021, 21:06
shodan ha scritto:
Ma giusto per curiosità: che dovrebbe fare questo codice? Che algoritmo sarebbe?
Sembra un algoritmo di hashing.
PiGi78 ha scritto:
Ciao

Purtroppo non sono esperto di C++ perché non mi piace più di tanto, per cui l'ho studiato solo anni fa...

Se ricordo bene, però, c'erano delle differenze sia nell'uso della memoria (uno dei due garantiva l'uso di una memoria contigua e l'altro no) sia nella modalità di utilizzo degli iteratori (le stringhe corte erano più veloci dei vector)

Può essere che siano queste due cose che cambino le prestazioni?
Potrebbe essere che in un PC moderno si evidenzino di più i pregi dei vector (quindi memoria contigua) e nel PC più vecchio la questione degli iteratori (quindi stringhe più veloci)

Non so, la mia è solo un'ipotesi basata sui ricordi che ho del C++...
Sicuramente sono implementati in modo diverso. Anche perché le string si possono ottimizzare per determinati tipi (char 8 bit, wchar 16 bit), mentre il vector è un template che deve contenere qualunque cosa. Però a seconda delle operazioni una classe può avere la meglio all'altra. Comunque le string sono contigue in memoria, il che permette accessi random e spostamenti in blocco in memoria. Tant'è che puoi accedere al puntatore al primo elemento con i metodi c_str() e data() e usarla come una stringa C (array di char). Le stringhe corte, come hai detto, sono più veloci perché allocate in modo statico.
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Differenza di prestazioni tra codici simili
19 nov 2021, 21:15
PiGi78 ha scritto:
Ciao

Purtroppo non sono esperto di C++ perché non mi piace più di tanto, per cui l'ho studiato solo anni fa...

Se ricordo bene, però, c'erano delle differenze sia nell'uso della memoria (uno dei due garantiva l'uso di una memoria contigua e l'altro no) sia nella modalità di utilizzo degli iteratori (le stringhe corte erano più veloci dei vector)

Può essere che siano queste due cose che cambino le prestazioni?
Potrebbe essere che in un PC moderno si evidenzino di più i pregi dei vector (quindi memoria contigua) e nel PC più vecchio la questione degli iteratori (quindi stringhe più veloci)

Non so, la mia è solo un'ipotesi basata sui ricordi che ho del C++...
Grazie per gli input, ci ragionerò!

shodan ha scritto:
Ma giusto per curiosità: che dovrebbe fare questo codice? Che algoritmo sarebbe?
Per evitare equivoci, specifico di riferirmi al codice postato al seguente messaggio:
https://www.iprogrammatori.it/forum-programmazione/viewtopic.php?p=8681332#p8681332
E' un'implementazione della classica moltiplicazione che si fa su carta. Lo stesso algoritmo viene implementato utilizzando come contenitore per le cifre una volta le string e una volta i vector. Il main() nello specifico calcola 12345^1000.
Ovviamente lo so che esistono metodi più performanti e questo stesso algoritmo presenta ampi margini di ottimizzazione, ma il punto è capire il motivo delle strane prestazioni riscontrate.
shodan
Molto attivo
Iscritto da
apr, 2010
Messaggi:
744
Re: Differenza di prestazioni tra codici simili
19 nov 2021, 22:13
My 2 cents.
Facendo delle prove spannometriche, in debug ottengo tempi + o - come quelli lamentati ma con un sostanziale pareggio. In release i tempi sono tra gli 80 e i 90 ms a seconda di come gli gira al momento.
In altre parole, se i tempi mostrati si riferiscono al debug rideteci sopra.

Per quanto riguarda string e vector.
Per lo standard C++ entrambi devono garantire l'accesso contiguo agli elementi contenuti, pertanto ottenendo un puntatore all'inizio del container, entrambi devono raggiungere la fine semplicemente incrementando il puntatore.
Vero che le std::string hanno un piccolo buffer interno per le piccole stringhe, ma non ricordo che sia richiesto dallo standard,
e comunque dati i valori in gioco, quell'ottimizzazione si perde già alla terza iterazione (VC++ prevede 16 caratteri se non ricordo male).
Invece lo standard (sempre se non ricordo male) vieta esplicitamente una ottimizzazione simile per il vector che deve essere sempre allocato nell'heap.

Tra l'altro una std::string è praticamente equivalente a un std::vector<char> dal punto di vista funzionale. E non di rado è più comodo (proprio per questioni di debug e intendo visualizzazione del contenuto) usare una std::string piuttosto che un vector<char> (specifico che parlo di buffer di ricezione o trasmissione, non di asciiz string per qualche API del SysOp o di libreria).

Altro aspetto di cui tenere conto è il numero di allocazioni che vengono effettuate e che sono parecchie nel codice mostrato.
E non c'è una strategia univoca: si potrebbe raddoppiare la dimensione precedentemente allocata o si potrebbe aggiungere un numero fisso alla quantità esistente, ma alla fine occorre sempre ricopiare il contenuto del vecchio buffer in quello nuovo e deallocare il vecchio. Qui però si entra nella specifica implementazione di libreria che differisce da compilatore a compilatore e nessuno garantisce che nella stessa libreria si applichi la stessa strategia.

Infine i cache misses, ma qui davvero si apre un mondo.
shodan
Molto attivo
Iscritto da
apr, 2010
Messaggi:
744
Re: Differenza di prestazioni tra codici simili
19 nov 2021, 22:22
Il main() nello specifico calcola 12345^1000.
Però a me non tornano i conti. Con due cicli e b=1 non ottengo 12345^2, mentre con un singolo ciclo e b=2 non ottengo 12345*2
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Differenza di prestazioni tra codici simili
19 nov 2021, 22:57
shodan ha scritto:
My 2 cents.
Facendo delle prove spannometriche, in debug ottengo tempi + o - come quelli lamentati ma con un sostanziale pareggio. In release i tempi sono tra gli 80 e i 90 ms a seconda di come gli gira al momento.
In altre parole, se i tempi mostrati si riferiscono al debug rideteci sopra.
A me invece viene da piangere!
Purtroppo non essendo del settore certe cose proprie non le conosco!
Ecco l'output attivando il flag -O3:
```
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.

shodan ha scritto:
Però a me non tornano i conti. Con due cicli e b=1 non ottengo 12345^2, mentre con un singolo ciclo e b=2 non ottengo 12345*2
Il risultato va letto partendo dalla fine del vector/string.
shodan
Molto attivo
Iscritto da
apr, 2010
Messaggi:
744
Re: Differenza di prestazioni tra codici simili
19 nov 2021, 23:26
Nippolo ha scritto:
In ogni caso la versione string resta sempre più veloce di quella vector.
A me succede il contrario, ma a mani basse proprio.
Il che non mi stupisce dato che usiamo compilatori diversi che ottimizzano in modo diverso e che hanno librerie diverse.
Insomma stiamo confrontando mele e pere.

shodan ha scritto:
Il risultato va letto partendo dalla fine del vector/string.
Già fatto. I conti non tornano lo stesso.
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Differenza di prestazioni tra codici simili
19 nov 2021, 23:57
shodan ha scritto:
Già fatto. I conti non tornano lo stesso.
Anche gli input vanno inseriti in ordine inverso, non a caso
```
string a = "54321";
```
Se poi nonostante ciò ti restituisce comunque risultati sbagliati non so che dirti, a me sembra funzionare.
Fammi sapere.

Devi accedere o registrarti per scrivere nel forum

21 risposte