Le prestazioni del Fork/Join framework di Java 7: quando conviene?

Nel post precedente abbiamo visto come utilizzare il Fork/Join framework introdotto da Java 7 per sfruttare il multithreading nella risoluzione di problemi che possono essere approcciati applicando una strategia di tipo divide-and-conquer. In questo articolo vediamo invece se e quando il suo utilizzo migliora effettivamente le performance rispetto al tradizionale approccio sequenziale. In particolare, il problema che abbiamo affrontato per illustrare il funzionamento del framework era quello del conteggio del numero di occorrenze di un certo valore x all’interno di un array di interi. Utilizzando il fork/join framework abbiamo suddiviso il problema in sottoproblemi di dimensione minore ed eseguito il conteggio delle occorrenze su ciascun sottoproblema con un diverso thread, in base al numero di processori disponibili sulla macchina, calcolando poi il risultato finale assemblando i vari risultati parziali ottenuti sui singoli sottoproblemi.

Quello che facciamo adesso è confrontare le performance di questa soluzione con quelle della soluzione classica che prevede di scorrere sequenzialmente tutti gli elementi dell’array ed aggiornare il contatore delle occorrenze, senza ricorrere al multithreading.
Effettueremo questo test su diverse dimensioni dell’array di input, eseguendo su ciascuna delle dimensioni prese in considerazione 5 runs, in modo da analizzare come l’efficacia dell’approccio multithreading varia a seconda della grandezza dell’input da elaborare. Le dimensioni dell’array di input che testiamo sono:

  • 1 Milione di elementi
  • 5 Milioni di elementi
  • 10 Milioni di elementi
  • 20 Milioni di elementi
  • 35 Milioni di elementi

Per prima cosa dobbiamo modificare il codice dell’articolo precedente, aggiungendo la fase di caricamento dell’array, in cui lo popoliamo con elementi che generiamo casualmente. Per farlo utilizziamo un blocco di inizializzazione statico:

static {
	Random random = new Random();
	for( int i = 0; i< SEARCH_ARRAY.length; i++) {
		SEARCH_ARRAY[i] = random.nextInt(100);
	}
}

Inoltre, rispetto al codice dell'altra volta, dobbiamo inserire l'acquisizione degli istanti di partenza e di terminazione della computazione, sia della procedura parallela basata sul fork/join framework sia di quella basata sul loop classico:

// Lancio l'esecuzione con il fork/join framework
long startTime = System.nanoTime();
int numOfOcc = pool.invoke(new RecursiveCountOfX(0, n - 1, dim));

System.out.printf("Numero totale di occorrenze dell'elemento " + TO_FIND + ": " + numOfOcc + "\n");
long endTime = System.nanoTime();
System.out.println("Soluzione Fork/Join:  " + ((endTime - startTime)/1000000.0) + " milliseconds");

Il codice completo del programma utilizzato per effettuare i test diventa quindi il seguente:

import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class ForkJoinFindXOccurrences {

    public static int   numOfThreads;
    public static final int[] SEARCH_ARRAY = new int[35_000_000];
    public static final int   TO_FIND      = 1;

    static {
        Random random = new Random();
        for( int i = 0; i< SEARCH_ARRAY.length; i++) {
            SEARCH_ARRAY[i] = random.nextInt(100);
        }
    }

    public static void main(final String[] args) {

        System.out.println("Numero di processori: " + Runtime.getRuntime().availableProcessors());
        numOfThreads = Runtime.getRuntime().availableProcessors();

        System.out.println("Numero di elementi dell'array: " + SEARCH_ARRAY.length);

        int dim = SEARCH_ARRAY.length / numOfThreads;

        final ForkJoinPool pool = new ForkJoinPool(numOfThreads);

        final int n = SEARCH_ARRAY.length;

        // Lancio l'esecuzione con il fork/join framework
        long startTime = System.nanoTime();
        int numOfOcc = pool.invoke(new RecursiveCountOfX(0, n - 1, dim));

        System.out.printf("Numero totale di occorrenze dell'elemento " + TO_FIND + ": " + numOfOcc + "\n");
        long endTime = System.nanoTime();
        System.out.println("Soluzione Fork/Join:  " + ((endTime - startTime)/1000000.0) + " milliseconds");

        // Calcolo il risultato con un loop classico
        numOfOcc = 0;
        long startTime2 = System.nanoTime();
        for (int k :SEARCH_ARRAY) {
            if (k == TO_FIND) {
                numOfOcc++;
            }
        }

        System.out.printf("Numero totale di occorrenze dell'elemento "
                          + TO_FIND + ": " + numOfOcc + "\n");
        long endTime2 = System.nanoTime();
        System.out.println("Soluzione loop classico:  " + ((endTime2 - startTime2)/1000000.0) + " milliseconds");
    }


    static class RecursiveCountOfX extends RecursiveTask {

        int start, end, dim;

        public RecursiveCountOfX(final int start, final int end, final int dim) {
            this.start = start;
            this.end = end;
            this.dim = dim;
        }

        @Override
        public Integer compute() {

            if ((this.end - this.start) < this.dim) {
                int ris = 0;
                for (int i = this.start; i <= this.end; i++) {
                    if (SEARCH_ARRAY[i] == TO_FIND) {
                        ris++;
                    }
                }

                return ris;
            }

            final int mid = (this.start + this.end) / 2;

            final RecursiveCountOfX subTask1 = new RecursiveCountOfX(this.start, mid, this.dim);

            subTask1.fork();

            final RecursiveCountOfX subTask2 = new RecursiveCountOfX(mid + 1, this.end, this.dim);

            return subTask2.compute() + subTask1.join() ;
        }
    }
}

Provando ad eseguire il programma su una dimensione iniziale dell'array di input di 1 milione di elementi, otteniamo il seguente risultato:

Numero di processori: 4
Numero di elementi dell'array: 1000000
Numero totale di occorrenze dell'elemento 1: 9962
With Fork/Join:  12.847316 milliseconds
Numero totale di occorrenze dell'elemento 1: 9962
With classic loop:  3.085275 milliseconds

Da questo singolo run sembra emergere una significativa differenza a favore della semplice esecuzione basata su un normale ciclo for che scorre tutti gli elementi e li confronta con il valore di cui dobbiamo contare le occorrenze.
Prima di procedere con l'analisi dei risultati ottenuti su una serie di 5 runs per ciascuna dimensione di input, proviamo ad aumentare la dimensione dell'array a 5 milioni di elementi e vediamo se si può notare fin da subito qualche differenza:

Numero di processori: 4
Numero di elementi dell'array: 5000000
Numero totale di occorrenze dell'elemento 1: 49886
With Fork/Join:  11.151486 milliseconds
Numero totale di occorrenze dell'elemento 1: 49886
With classic loop:  8.995929 milliseconds

Possiamo immediatamente vedere come il divario tra i tempi di esecuzione delle due soluzioni si sia significativamente ridotto, sebbene l'approccio basato su un classico ciclo for resti più performante anche su questa dimensione dell'array di input.

Nella figura seguente sono illustrati i risultati dei test di esecuzione delle due procedure, ciascuna delle quali è stata eseguita 5 volte su una dimensione dell'array di input di 1, 5, 10, 20 e 35 milioni di elementi.

Java7 Fork-Join framework performance

Dall'esecuzione di questi test e dal calcolo della media dei tempi di esecuzione per ciascuna dimensione dell'array di input, possiamo sostanzialmente notare come le performance del fork/join framework si rivelino man mano sempre migliori, rispetto all'approccio iterativo standard, al crescere della dimensione dell'array di input. Nella figura, per ciascuna dimensione di input, è evidenziata in verde la soluzione che richiede il minor di tempo di esecuzione mentre quella che richiede un effort computazionale superiore è evidenziata in rosso quando risulta essere significativamente più lenta, oppure in giallo quando risulta essere solo di poco più lenta rispetto all'altra.
Su un array costituito da un milione di elementi l'utilizzo del fork/join framework risulta inefficiente e significativamente più lento rispetto alla semplice iterazione sugli elementi dell'array. Questo perché il costo della suddivisione in sottoproblemi e l'instanziazione dei diversi threads a cui vengono allocati influisce troppo rispetto al costo della risoluzione del singolo sottoproblema, per cui approcciare il problema in modo iterativo con un singolo thread risulta ancora conveniente. Aumentando la dimensione dell'array a 5 milioni di elementi, come avevamo già visto in precedenza, riduce il gap nelle prestazioni che restano ancora però a svantaggio del fork/join framework, seppure di poco(infatti è in giallo nella tabella). Aumentando ancora la dimensione dell'array di input a 10 milioni di elementi notiamo invece come l'utilizzo del fork/join framework inizi a dare i suoi frutti ed a risultare conveniente rispetto ad iterare sequenzialmente sugli elementi dell'array. In questo caso il costo relativo alla creazione dei threads e all'assemblaggio dei risultati parziali incide in maniera minore sul costo dell'esecuzione del task sui sottoproblemi e, di conseguenza, la parallellizazione del calcolo fornisce un risultato migliore rispetto all'approccio iterativo. Queste operazioni di "messa in funzione" del fork/join framework e della creazione dei suoi diversi threads vengono via via sempre più ammortizzate al crescere della dimensione del problema e quindi, riducendo il loro impatto in relazione all'effort richiesto per il calcolo della soluzione sul sottoproblema assegnato al thread, si ottiene un vantaggio significativo nel parallelizzare la computazione su più threads rispetto ad avere un solo thread che itera sull'intero array.

Provando ad aumentare ulteriormente la dimensione dell'array di input fino al limite concesso dalla macchina utilizzata prima di ottenere un OutOfMemoryError si ottiene un ulteriore conferma sull'analisi del comportamento effettuata.

Numero di elementi dell'array: 44000000
Numero totale di occorrenze dell'elemento 1: 438809
With Fork/Join:  28.117031 milliseconds
Numero totale di occorrenze dell'elemento 1: 438809
With classic loop:  67.360796 milliseconds

Leave a Reply

Your email address will not be published. Required fields are marked *