RISOLTO Efficienza permutazioni C++

[Andretti60]

Premature optimization is the root of all evil -- DonaldKnuth
Un buon articolo che tratta questo argomento:

https://wiki.c2.com/?PrematureOptimization

E lo dice uno che negli anni 80 passava il tempo ottimizzando codice assembly per processori 680x0, continuo tuttora a ottimizzare codice per lavoro (i clienti vogliono applicazioni il più possibile reattive)

Ma tornando a questo caso in particolare. Quello che hai notato è un peggioramento del tempo di esecuzione dovuto al fatto di chiamare il metodo di una classe invece di chiamare direttamente una funzione. Sono due cose diverse, diversi compilatori sono capaci di ottimizzare meglio o peggio. Ma il grosso problema del tuo codice sta nel codice stesso, dove chiami una funzione in un ciclo chiuso (tight loop) miliardi di volte. Questo porterà sempre problemi di efficienza, è una tecnica che si evita. Pensa se la funzione che chiami non faccia parte del tuo assembly, se addirittura non sia neanche nella memoria del tuo programma (per esempio sia parte di un servizio), chiamate Out-Process sono da usare con molta precauzione.

 

[DispatchCode]

Ma tornando a questo caso in particolare. Quello che hai notato è un peggioramento del tempo di esecuzione dovuto al fatto di chiamare il metodo di una classe invece di chiamare direttamente una funzione. Sono due cose diverse, diversi compilatori sono capaci di ottimizzare meglio o peggio. Ma il grosso problema del tuo codice sta nel codice stesso, dove chiami una funzione in un ciclo chiuso (tight loop) miliardi di volte. Questo porterà sempre problemi di efficienza, è una tecnica che si evita. Pensa se la funzione che chiami non faccia parte del tuo assembly, se addirittura non sia neanche nella memoria del tuo programma (per esempio sia parte di un servizio), chiamate Out-Process sono da usare con molta precauzione.

E' vero quanto dici: la chiamata ad un metodo in C++ ha dell'overhead aggiuntivo.
Comunque nei nostri risultati si nota molto meno, e anzi, sono inferiori i tempi che fanno uso di una classe rispetto a quelli che non la usano. Quindi non credo che il problema sia questo o solo questo.

Pensa se la funzione che chiami non faccia parte del tuo assembly, se addirittura non sia neanche nella memoria del tuo programma (per esempio sia parte di un servizio)

Non ho capito che intendi con questa parte. Fai riferimento ad esempio a un servizio di rete, o in generale, a qualcosa che non è sulla macchina in cui gira il programma?

 

[M1n021]

E provare ad installare una distribizione Linux, cosi' che tu abbia un compilatore un po' piu' recente?
Sebbene se ci sia modo di farlo anche in Windows (clang):
LLVM Download Page

Grazie dei consigli, appena ho un po' di tempo provo ad installare un compilatore più recente!

Ma detto ciò appoggio in toto sull'assembly. 😁 L'aspetto utile ad impararlo è che ti porta a conoscere altre cose che hanno a che fare con la CPU e in generale con l'architettura del pc (e anche con l'OS, in un certo senso... da un argomento iniziale vai poi ad esplorare).

Detto ciò, aggiungo altro: se vuoi essere SICURO che venga generato il codice in un certo modo (usando SSE ad esempio) puoi usare le intrinsics di Intel, le trovi qui: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

Tutte cose condivisibili, ma che necessitano di un certo impegno in termini di tempo e non solo! 😅

Ma il grosso problema del tuo codice sta nel codice stesso, dove chiami una funzione in un ciclo chiuso (tight loop) miliardi di volte. Questo porterà sempre problemi di efficienza, è una tecnica che si evita.

Scusa, assodato che probabilmente quasi sempre esiste un algoritmo migliore che non fa uso della "forza bruta", ma se lo scopo è quello di voler risolvere un problema testando le diverse permutazioni possibili, non è una scelta obbligata quella di ricorrere ad un ciclo che generi tutte le sequenze possibili?

 

[Andretti60]

Non ho capito che intendi con questa parte. Fai riferimento ad esempio a un servizio di rete, o in generale, a qualcosa che non è sulla macchina in cui gira il programma?

InProc significa che il codice gira nella stessa area della memoria del programma principale, come per esempio una libreria (statica o dinamica). OutProc invece è un servizio, non necessariamente di rete, può girare nello stesso computer, per esempio in Windows può essere un semplice servizio di sistema, che ovviamente gira nella sua memoria. Tutte le chiamate outProc richiedono un grosso context switching e tutti i parametri devono passare il marshaling, sono quindi chiamate molto costose dal punto di vista del tempo.

Scusa, assodato che probabilmente quasi sempre esiste un algoritmo migliore che non fa uso della "forza bruta", ma se lo scopo è quello di voler risolvere un problema testando le diverse permutazioni possibili, non è una scelta obbligata quella di ricorrere ad un ciclo che generi tutte le sequenze possibili?

Il mio discorso vuole essere più generale.
Prendi per esempio questo snippet dal tuo codice:

do
    {
        ++cont;
    }
    while(a.permutazione_S_successiva_());

Cosa vuoi fare in quel loop? Se vuoi solo contare il numero di permutazioni, è estremamente inefficiente, quello dovrebbe essere fatto in una sola chiamata della classe, un metodo che ritorna il numero di permutazioni, mettendo quindi il ciclo interno alla classe. Se vuoi fare qualcos’altro (che è la cosa più probabile) allora il discorso ottimizzazione si sposta, in quanto quando si ottimizza si va prima ad esaminare quali parti del codice prendono più tempo di esecuzione, se quel “qualcos’altro” citato prima prende il 90% del tempo di esecuzione, ottimizzare il metodo della permutazione non serve a nulla.
Prendi il mio commento come una considerazione “filosofica” su come vada ottimizzato il codice.

 

[DispatchCode]

InProc significa che il codice gira nella stessa area della memoria del programma principale, come per esempio una libreria (statica o dinamica). OutProc invece è un servizio, non necessariamente di rete, può girare nello stesso computer, per esempio in Windows può essere un semplice servizio di sistema, che ovviamente gira nella sua memoria. Tutte le chiamate outProc richiedono un grosso context switching e tutti i parametri devono passare il marshaling, sono quindi chiamate molto costose dal punto di vista del tempo.

Ah ok, ora ho capito che intendi.

Tutte cose condivisibili, ma che necessitano di un certo impegno in termini di tempo e non solo! 😅

Assolutamente, era un discorso più ampio il mio. ;)

Grazie dei consigli, appena ho un po' di tempo provo ad installare un compilatore più recente!

Se sei su Windows con MSYS hai già la versione più recente. Se lo stai già usando, fai un update.
Altrimenti puoi anche scaricare Clang e/o MSVC.

 

[BrutPitt]

Stavo per dirti la stessa cosa: se puoi, prova ad utilizzare la sua versione di g++, la 8 e qualcosa, così vediamo.
Non ho controllato che set supporti la sua CPU, ma è anche probabile che non supportasse qualche estensione; sicuramente i compilatori un pò più vecchi vanno a produrre codice meno efficiente però.

Infatti (ci pensavo ieri sera) il set di istruzioni (i.e. SSE4 etc), non riguarda il "pacchetto" ottimizzazioni, ma quello delle architetture... ed essendo specifico della macchina, non e' automatico: in quanto inficierebbe la portabile sulla stessa piattaforma x86_64.

A quanto ricordo Clang produce anche codice migliore però.

Si', anche se dipende dai contesti.
Intanto questi sono i risultati che ho ottenuto, utilizzando anche l'opzione del linker -flto (LinkerTimeOprimization), con g++ v.11 e v.12 sempre sulla stessa macchina (e tutti compilati con l'opzione -O3):

g++11
perm. succ. con classe   479001600 1390ms
perm. succ. senza classe 479001600 727ms
std::next_permutation    479001600 1708ms
g++11 -flto
perm. succ. con classe   479001600 959ms
perm. succ. senza classe 479001600 789ms
std::next_permutation    479001600 1079ms
g++12
perm. succ. con classe   479001600 1187ms
perm. succ. senza classe 479001600 1607ms
std::next_permutation    479001600 2690ms
g++12 -flto
perm. succ. con classe   479001600 759ms
perm. succ. senza classe 479001600 795ms
std::next_permutation    479001600 2653ms

La cosa di cui mi meravigliavo e' come la STD fosse diventata cosi' piu' lenta in g++ v.12, rispetto alla versione precedente.
Cosi' compilando disabilitando le "eccezioni" (-fnon-call-exceptions):

g++11 -flto -fnon-call-exceptions
perm. succ. con classe   479001600 932ms
perm. succ. senza classe 479001600 799ms
std::next_permutation    479001600 1036ms
g++12 -flto -fnon-call-exceptions
perm. succ. con classe   479001600 643ms
perm. succ. senza classe 479001600 698ms
std::next_permutation    479001600 923ms

Praticamente i tempi di esecuzione v.11, rimangono invariati, mentre cambiano quelli della STD della v.12

Tutto questo fatto esclusivamente per semplice curiosita'. 😉

Aggiungo...
Dall' articolo postato da @Andretti60 ... cito:

1. Make it work.
2. Make it right.
3. Make it fast.

Sacrosanto!

 

[DispatchCode]

Mi sono ricordato di questo bellissimo - a mio avviso - articolo che ho letto qualche anno da. Scritto da Matt Godbolt, il creatore di Compiler Explorer.

Optimizations in C++ Compilers.

Visto ciò di cui stiamo disquisendo mi sembra possa essere rilevante.