Ottimizzazione funzione somma numeri pari

[luigish93]

Salve ragazzi sono nuovo su questo forum vorrei avere un parere da voi se è possibile e se si come fare a diminuire il tempo che impiega questa operazione.

public class tempoprocesso {
	
	public static void main(String[] args) {
		long start = System.nanoTime();
		System.out.println("Start: " + start);
		 
		int totalEven = 0;
		for (int i = 0; i < 10000; i++) {
			if (i % 2 == 0) {
				totalEven = totalEven + i;
			}
		}
		 
		long end = System.nanoTime();
		System.out.println("Fine  : " + end);
		
		long elapsedTime = end - start;
		 
		System.out.println("La durata del processo: "
			+ elapsedTime + " nano secondi");
		}
	}

[MItaly]

Benvenuto sul forum! Ti ricordo che:

• il codice va specificato tra tag [CODE] ... [/CODE], altrimenti perde l'indentazione;
• il titolo di ogni thread dovrebbe contenere una sintetica descrizione del problema, invece che dei generici "aiuto".

Ora correggo io, in futuro imposta correttamente la discussione fin da subito; nel frattempo ti consiglio di dare un'occhiata al regolamento.

[MItaly]

In ogni caso:
una prima ottimizzazione "banale" è rimuovere l'if e considerare direttamente solo i numeri pari:

        for (int i = 0; i < 10000; i+=2)
                totalEven+= i;

(dato che parto da zero, se incremento di due ogni volta ottengo tutti e soli i numeri pari nell'intervallo [0, 10000) ). Il ciclo è in ogni caso O(n), ma il numero di iterazioni dimezza e si evita un branch all'interno del loop.

Ma l'ottimizzazione più sensata è risolvere matematicamente il problema: sappiamo infatti che


(si dimostra facilmente per induzione); da questo, segue che:


Per cui il ciclo può essere sostituito in blocco con

int limit=10000; // o quello che è il limite del tuo for
int m=limit-(2-limit%2);
int totalEven=m*(m+2)/4;

che è chiaramente O(1) (non c'è nessun ciclo); nota che il passaggio a m serve perché il limite del for non include l'estremo destro, mentre la sommatoria delle formule la include, e per gestire correttamente il caso in cui limit sia dispari.

[Andrea1979]

ed oltre all'osservazione di carattere matematico di MItaly, la tendenza da seguire sempre nella scrittura di codice ottimizzato è quella di ridurre al minimo il costo delle operazioni elementari. Qui ci sarebbe da fare un discorso, datasheet del processore alla mano, sul peso (numero cicli) che un'operazione comporta. Ora con le potenze in gioco non è un problema fare qualche migliaio di divisioni modulari e computare un if... ma volendo risparmiare anche su quello:

public static void main (String[] args) {
        long totalEven = 0;
        
        long start = System.nanoTime();               
        for (int i = 0; i < 10000; i++) {
            if (i % 2 == 0) {
                totalEven += i;
            }
        }
        long end = System.nanoTime();
        System.out.println("Elapsed Time: "+(end-start)+"\nSum: "+totalEven);
        
        totalEven = 0;
        
        start = System.nanoTime();        
        for (int i = 0; i < 10000; i+=2) {
            totalEven+=i;
        }
        end = System.nanoTime();
        System.out.println("\n\nElapsed Time: "+(end-start)+"\nSum: "+totalEven);
}

e come risultato di una prova:

Elapsed Time: 264192
Sum: 24995000


Elapsed Time: 88703
Sum: 24995000

come vedi c'è un fattore 3 di differenza...

[MItaly]

Originariamente inviato da Andrea1979
come vedi c'è un fattore 3 di differenza...

La cosa interessante è che se avessimo semplicemente dimezzato il numero di cicli, la differenza dovrebbe essere su un fattore 2; il risparmio ulteriore deriva dal fatto di aver eliminato un if particolarmente scabroso per le CPU pipelined.

Dal Pentium 2 in poi i processori di famiglia x86 sono passati ad un'architettura pipelined superscalare, il che significa che, invece di bloccare tutto il processore ad eseguire una singola operazione per volta, i vari stadi del processore lavorano "a catena di montaggio", per cui l'istruzione successiva viene "attaccata" quando l'istruzione precedente non è ancora stata completamente processata.

Ora, finché l'esecuzione procede normalmente questo non è un problema; le complicazioni iniziano quando ci sono delle istruzioni condizionali: supponiamo che il codice di quel loop venga (JIT-)compilato in una cosa del tipo

; totalEven
    xor edx, edx
; i
    xor eax, eax 
begin:
    and eax,1
    jnz skip
    add edx, eax
skip:
    cmp eax, 10000
    inc eax
    jl begin

(il codice dell'"if(i%2==0) totalEven+=i" sta tra il "begin:" e lo "skip:")

Il processore, arrivato al jnz, per sapere se deve saltare a skip o proseguire sull'add deve sapere il risultato dell'and eax,1; tuttavia, in una CPU pipelined questo non è possibile, dato che, nel momento in cui il processore sta decidendo quale direzione prendere nel branch, l'istruzione precedente non è ancora stata elaborata completamente.

Per questo motivo, i processori moderni quando sono di fronte ad un branch tirano ad indovinare, e proseguono di esecuzione speculativa fino a quando i dati che servivano per il branch non sono finalmente disponibili; a quel punto, se avevano indovinato correttamente bene, l'esecuzione prosegue, altrimenti viene svuotata la pipeline e l'esecuzione riparte dal branch; quest'ultimo caso ovviamente è il più "costoso" in termini di tempo.

Ora, per ridurre questo problema i processori sono dotati di un branch predictor: per ogni salto condizionale, il processore tiene un contatore in cui si memorizza quale delle due direzioni è stata presa più di frequente nelle ultime N iterazioni; per questo motivo, un'espressione condizionale che è quasi sempre uguale non darà praticamente mai problemi, mentre una diversa ad ogni iterazione garantisce quasi sicuramente un gran numero di branch misprediction.

In questo caso, il jnz dell'if(i%2==0) è un caso abbastanza patologico per un branch predictor "ingenuo": infatti ad ogni iterazione la "strada" seguita cambia, per cui il branch predictor non ha appigli per prevedere correttamente da che parte dovrà andare (in realtà poi branch predictor più astuti dovrebbero saper riconoscere questo pattern).

Confronta invece con il jl finale: in questo caso, il jump viene sempre seguito tranne che all'ultima iterazione, per cui è estremamente semplice da prevedere.

---

Ergo: eliminando l'if dal loop e ciclando direttamente solo sui numeri pari non solo si dimezza il numero di iterazioni, ma si elimina un buon numero di potenziali branch mispredictions, ottenendo il guadagno in performance mostrato da Andrea1979.