Ottimizzare una banale ricerca con i Thread

[JavaFurbix]

Salve, sto cercando di apprendere qualcosa su i threads.

Quindi mi cimento a fare esperimenti.


Ho un array con 1.000.000 di elementi. Ora volevo verificare quante volte si presenta un numero.

Come ottimizzare il programma con i thread cercando di farne partire 3 o 5 e ridurre i tempi di scansione dell'array rispetto ad un programma che scansiona ad 1 posizione per volta in modo crescente o banalmente senza threads. ?!?

public class VerificaNumeriEstrattiConThreads implements Runnable  {      
private static int contatore = 0;      
private int intervalloMin;      
private int intervalloMax;      
private int numeroDaVerificare;      
private int[] array;        
    
public VerificaNumeriEstrattiConThreads(int numeroDaVerficiare,int[] array, int intervalloMin,int intervalloMax)      
{          
this.numeroDaVerificare = numeroDaVerficiare;          this.array = array;          
this.intervalloMin = intervalloMin;          this.intervalloMax = intervalloMax;      
}        

@Override      public void run()       
{          
for(int i= intervalloMin; i <= intervalloMax; i++)          {              
if(array[i] == numeroDaVerificare)  
{                  
incrementaContatore();              
}          
}                
}      

private synchronized void incrementaContatore()      {          
contatore++;      
}            
public static int getContatore()      
{          
return contatore;      
}            
      
public static void main(String[] args) throws InterruptedException      
{          
NumeriEstratti esnum = new NumeriEstratti(10);            
Thread t1 = new Thread(new VerificaNumeriEstrattiConThreads(1, esnum.getArray(), 0, 2));          
Thread t2 = new Thread(new VerificaNumeriEstrattiConThreads(1, esnum.getArray(), 3, 5));          
Thread t3 = new Thread(new VerificaNumeriEstrattiConThreads(1, esnum.getArray(), 6, 9));                    System.out.println(esnum.toString());          
t1.start();          
t2.start();          
t3.start();                    
t1.join();          
t2.join();          
t3.join();                    
System.out.println(VerificaNumeriEstrattiConThreads.getContatore());                
} 

In questo esempio NumeriEstratti è l'array che in questo esempio per motivi pratici è stato ridotto a grandezza10.


Si può fare di meglio ??? La cosa più bruttina da fare è assegnare ad ogni thread un intervallo da controllare. Ma questo solo se si conosce la grandezza dell'array apriori.

Mettiamo caso esistesse un ArrayList di oggetti o semplicemente di Integer come è possibile farlo in quel caso che è dinamico ??

Come si può ottimizzare la soluzione quì sopra proposta??

[andbin]

Originariamente inviato da JavaFurbix
Come ottimizzare il programma con i thread cercando di farne partire 3 o 5 e ridurre i tempi di scansione dell'array rispetto ad un programma che scansiona ad 1 posizione per volta in modo crescente o banalmente senza threads. ?!?

Se hai un processore multi-core sì, puoi di certo avere vantaggi nell'usare più thread concorrenti. Se hai solo un single-core no, nel senso che avere più thread non dà vantaggi, anzi presumibilmente il contrario.
Ma è chiaro che uno può usare la applicazione su più macchine anche ben diverse. Quindi per fare le cose bene si dovrebbe determinare il numero appropriato di thread in base alla macchina.
Per lavori molto "cpu-bound" (intensivi per la CPU), il numero di thread appropriato è ... tah dah .... lo stesso numero di unità operative.

Originariamente inviato da JavaFurbix
La cosa più bruttina da fare è assegnare ad ogni thread un intervallo da controllare. Ma questo solo se si conosce la grandezza dell'array apriori.

L'idea di assegnare ad ogni thread una porzione dei dati da controllare .... beh, è questa in fondo la soluzione ... non è che è "bruttina".

Chi gestire il "pool" di thread comunque deve sapere la dimensione dell'array. Potrebbe non saperlo poi il thread che compie il lavoro.

[JavaFurbix]

Intendevo anche com è scritto il codice, anse se banale ... Se la sua forma(architettura) era corretto.


Cmq ritornando al discorso dei core della CPU ... Vero si ma in parte perchè da quando è nata la tecnologia Hyper-Threading (molto diffusa) che io sappia l'ultilizzo dei threads in applicazioni porta sempre vantaggi ...

[DonFrignolo]

Quello che dice andbin in teoria è vero, solo che nel nostro caso abbiamo a che fare con la JVM che si occupa di associare le risorse alla CPU o alle CPU quindi se abbiamo a che fare con una JVM che non è ottimizzata per il multi core farà eseguire sempre e comunque tutto ad uno stesso core e a quel punto Hyper-Threading e roba varia va a farsi benedire.

Cmq per ottimizzare il tuo programma io utilizzerei le code. Nel senso che metterei il mio array in una coda e poi farei partire un numero arbitrario di thread es. da min 2 max 10 che attingono tutti dalla stessa coda. Quando la coda è vuota termino i threads.

[andbin]

Originariamente inviato da JavaFurbix
Vero si ma in parte perchè da quando è nata la tecnologia Hyper-Threading (molto diffusa) che io sappia l'ultilizzo dei threads in applicazioni porta sempre vantaggi ...

Io intendo in generale "unità operative" distinte. Che poi ci siano 2 processori fisici montati sulla scheda madre (con 2 socket fisici, come c'erano una volta e credo ne esistano ancora) o 1 processore multi-core o un processore single-core con Hyper-Threading ..... beh, la questione non cambia.
Poter avere realmente più esecuzioni in parallelo contemporanee ... questo si deve intendere.

Originariamente inviato da DonFrignolo
quindi se abbiamo a che fare con una JVM che non è ottimizzata per il multi core

In generale sì è vero. Ma un approccio tipico e anche già utilizzato dalle JVM è quello di "mappare" i thread Java sui thread "nativi" del S.O. Quindi se il S.O. supporta più unità operative, ne beneficia anche la JVM.

[JavaFurbix]

Originariamente inviato da DonFrignolo
...

Cmq per ottimizzare il tuo programma io utilizzerei le code. Nel senso che metterei il mio array in una coda e poi farei partire un numero arbitrario di thread es. da min 2 max 10 che attingono tutti dalla stessa coda. Quando la coda è vuota termino i threads.

...

mi fai un esempio?? non ho ben capito

[DonFrignolo]

Ecco qui, cmq basta googlare un po....

public class WorkQueue
{
    private final int nThreads;
    private final PoolWorker[] threads;
    private final LinkedList queue;

    public WorkQueue(int nThreads)
    {
        this.nThreads = nThreads;
        queue = new LinkedList();
        threads = new PoolWorker[nThreads];

        for (int i=0; i<nThreads; i++) {
            threads[i] = new PoolWorker();
            threads[i].start();
        }
    }

    public void execute(Runnable r) {
        synchronized(queue) {
            queue.addLast(r);
            queue.notify();
        }
    }

    private class PoolWorker extends Thread {
        public void run() {
            Runnable r;

            while (true) {
                synchronized(queue) {
                    while (queue.isEmpty()) {
                        try
                        {
                            queue.wait();
                        }
                        catch (InterruptedException ignored)
                        {
                        }
                    }

                    r = (Runnable) queue.removeFirst();
                }

                // If we don't catch RuntimeException, 
                // the pool could leak threads
                try {
                    r.run();
                }
                catch (RuntimeException e) {
                    // You might want to log something here
                }
            }
        }
    }
}