[JAVA] Nested loop & multithreading

[tylerdurden83]

Ragazzi ho 1-2 quesiti sui cicli annidati.

Ad esempio:

for(int i=0;i<10000;i++){
    for(int j=0;j<10000;j++){
          for(int k=0;k<10000;k++){
                fai(i,j,k);
          }
     }
}

Ho fatto in modo che fai viene eseguito in un nuovo thread, ma non basta, il collo di bottiglia rimane il thread principale che scandisce i vari loop e lancia i fai.

Al momento ho questa situazione:



Quindi il main che contiene i loop annidati continua ad essere il collo di bottiglia, non riesce a loopare e startare nuovi worker thread sufficientemente veloce e i worker stanno senza fare nulla quasi tutto il tempo...

Avrei quindi bisogno di parallelizzare la questione a monte diciamo...

Grazie as always,
Rob

[clockover]

Tu vorresti (se non ho capito male) far partire i thread ma farli eseguire in contemporanea (diciamo)...

Guarda il modo più semplice in assoluto è utilizzare un semaforo, ma ancora più semplice è dare uno sguardo al package java.util.concurrent! C'è una classe apposta per fare cose del genere, ma non mi ricordo quale!

Edit
dai uno sguardo alla classe CyclicBarrier

[tylerdurden83]

Non proprio...ti posto il codice...

private void parallelTestAllCombinations(){
  Character bestCharacterConfig = null;
  ExecutorService es = Executors.newFixedThreadPool(8);
  List<Future<Character>> characters = new ArrayList<Future<Character>>();
  for(Item head : this.headSet){
    for(Item shoulder : this.shoulderSet){
      for(Item neck : this.neckSet){
        for(Item back : this.backSet){
          for(Item chest : this.chestSet){
            // altri loop
            for(Item ranged : this.rangedSet){
              for(Item mainHand : this.mainHandSet){
                for(Item offHand : this.offHandSet){
                  bestCharacterConfig=(Character)DeepCopy.copy(this.character);
                  WorkerThread wk = new WorkerThread(bestCharacterConfig,head,shoulder,neck,
                    back,chest,wrist,hand,belt,legs,feet,(Item)ringsArray[ring1],(Item)ringsArray[ring2],
                    trinket,ranged,mainHand,offHand);
                  Future<Character> futureChar = es.submit(wk);
                  characters.add(futureChar);
                }
          	 }
            }
          }
        }
      }
    }
  }
  try {
    for (Future<Character> future : characters) {
        Character e = future.get();
        System.out.println(" [future complete]: " + e);
    }
    es.shutdown();
	} catch (ExecutionException e) {
    throw new RuntimeException(e);
	} catch (InterruptedException ie) {
    throw new RuntimeException(ie);
  }
}

vedrò di fixare l'indentazione. Comunque il problema è che la parte che fa fare ai vari thread è solo quella di "calcolo", nel loop piu interno, e dura meno di quanto impiega a ri-arrivare li diciamo, infatti se vedi dall immagine i thread sono sempre scarichi e il main sempre a lavoro...

[banryu79]

Se ho capito il tuo problema è che nel ciclo più interno dovresti evitare di creare tu esplicitamente i worker e lanciarli, ma dovresti delegare queste due operazioni ad un ThreadPoolExecutor (le incapsuli in Runnable, istanziare un Runnable è un'operazione molto più leggera che istanziare Thread, e passi i Runnable all'executor. Vedi il package java.util.concurrent, e il java tutorial ufficiale in merito, se non ci hai mai lavorato).

@EDIT:
ah, ok, ora ho letto meglio il codice; quindi hai parallelizzato l'operazione eseguita dal worker thread per (presumo) calcolare la singola configurazione-personaggio, ora l'altra operazione "onerosa" è la generazione di tutte le combinazioni possibili di configurazioni-personaggio, che attualmente esegui in un unico thread con tanti cicli for annidati uno dentro l'altro.
Tu vorresti "parallelizzare" anche questa fase, dico bene?

[tylerdurden83]

Sorry non avrei dovuto postare al ritorno da una lunga giornata e una lunga bevuta

Ho corretto il codice inserendo l'intero codice. Sto usando java.util.concurrent, ExecutorService, Future etc etc. Il problema è che i cicli annidati che compongono l'input del Runnable sono più "lenti" dell'elaborazione del Runnable stesso, quindi gli 8 thread worker a cui vengono submit dall'ExecutorService i Runnable stanno in idle quasi tutto il tempo (colore giallo dell'immagine sopra), il collo di bottiglia è rappresentato dal main (sempre verde, quindi che lavora tutto il tempo) che non riesce più velocemente a ciclare i vari Set e inviarli all'ExecutorService.

Quello che sarebbe utile sarebbe parallelizzare non solo l'elaborazione ma l'intera costruzione diciamo.

Faccio un'analogia.
Se consideriamo l'albero:

A
/ \
B C
/\
D E

attualmente succede che:
t0: main thread: leggo A
t1: main thread: leggo B
t2: main thread: leggo D
t3: main thread: start nuovo thread(A,B,D)
t3: (mentre il nuovo thread lavora..)
t4:main thread: leggo A
t5: main thread: leggo B
t6: main thread: leggo E
t7: main thread: start nuovo thread(A,B,E)
t7: (mentre il nuovo thread lavora..)
t8: main thread: leggo A
t9: main thread: leggo C
t10: main thread: start nuovo thread(A,C)

Quando il main thread arriva ad una foglia dell'albero, passa i nodi letti ad un nuovo thread worker che li elabora, e (il main) riprende il traversal dell'albero.
Sarebbe utile invece se:

t0: thread-1: leggo A
t1: thread-1: leggo B
t2: thread-1: leggo D
t3: thread-1: start nuovo thread(A,B,D)
t3: (mentre il nuovo thread lavora..)
t0: thread-2: leggo A
t1: thread-2: leggo B
t2: thread-2: leggo E
t3: thread-2: start nuovo thread(A,B,E)
t3: (mentre il nuovo thread lavora..)
t0: thread-3: leggo A
t1: thread-3: leggo C
t2: thread-3: start nuovo thread(A,C)

[banryu79]

A occhio non è che il collo di bottiglia è la deep copy del character eseguita ad ogni iterazione del ciclo più interno?
Della serie: hai già provato a calcolare prima (fuori dai cicli) il numero totale di istanze Character che dovrai generare, allocarle in una lista e dentro il for più interno andare a pescare le istanze già pronte da passare al worker thread?

[tylerdurden83]

Sorry ci sono un po di problemi a lavoro, buona osservazione, proverò a modificare così il codice appena ho un secondo, ti faccio sapere!

[banryu79]

Originariamente inviato da tylerdurden83

Sorry ci sono un po di problemi a lavoro, buona osservazione, proverò a modificare così il codice appena ho un secondo, ti faccio sapere!

Nota appunto che nel for più interno fai sostanzialmente 3 cose:
1) deep copy di un Character
2) creazione di un WorkerThread
3) submit del WT all'Executor

Ora, esclusa la 3), la 1) e la 2) sono le operazioni che potenzialmente tengono impegnato il tuo main-thread
Il tipo WorkerThread estende Thread? Se sì sarebbe meglio di no, è costoso da istanziare nel main-thread.

[tylerdurden83]

Intanto ti rispondo sul punto 2)

public class WorkerThread implements Callable{

  private Character character;
  private Set<Item> items;

  public WorkerThread(Character character, Item... items){
      this.character=character;
      this.items=new HashSet<Item>();
      this.items.addAll(Arrays.asList(items));
  }

  public Object call() throws Exception {
      for(Item item : this.items){
          this.character.equipItem(item);
      }
      return this.character;
  }
}

[banryu79]

Magari non cambia molto ma non ho potuto fare a meno di notare che internamente a WorkerThread usi un HashSet.

Dato che non mi sembra tu ne abbia strettamente bisogno, memorizza semplicemente in un array di Item gli argomenti in ingresso, così eviti di creare l'HashSet (è pur sempre un oggetto) e i controlli del metodo addAll (se vai a ravanare nelle implementazioni vedrai che va a iterare tutta la collezione per eseguire i singoli add, e per ogni add esegue un if, ti posto l'implementazione che faccio prima, ecco):

// In java.util.AbstractCollection 
// implementazione ereditata da AbstractSet
// a sua volta ereditata da HashSet
...
public boolean addAll(Collection<? extends E> c) {
	boolean modified = false;
	Iterator<? extends E> e = c.iterator();
	while (e.hasNext()) {
	    if (add(e.next()))
		modified = true;
	}
	return modified;
    }
...

Usa l'array liscio, tanto altro non ti occorre:

public class WorkerThread implements Callable{

  private Character character;
  private Item[] items;

  public WorkerThread(Character character, Item... items){
      this.character=character;
      this.items=items;
  }

  public Object call() throws Exception {
      for(Item item : this.items){
          this.character.equipItem(item);
      }
      return this.character;
  }
}

[tylerdurden83]

Quanto mi sento stupido e quanto ti voglio bene?....



Ora vorrei solo capire come fargli usare tutte e al 100% le cpu, ma questo è un altro problema!

[banryu79]

Originariamente inviato da tylerdurden83

Ora vorrei solo capire come fargli usare tutte e al 100% le cpu, ma questo è un altro problema!

Ti consiglio la sottosezione relativa alla programmazione concorrente del forum ufficiale per le tecnologie Java della Sun (Oracle).

[tylerdurden83]

In realtà era un piccolo errorino mio...ora però l'ho sistemato ma con mia grossa amarezza ho scoperto che anche avendo mandato tutte le cpu al 100% non ho ottenuto miglioramenti prestazionali...

Questo è il codice seriale:

private void testAllGearCombinations(){
    Character bestCharacterConfig = null;
    double highestCurrentDps = -1;
    for(Item head : this.headSet){
        this.character.equipItem(head);
        for(Item shoulder : this.shoulderSet){
            this.character.equipItem(shoulder);
            for(Item neck : this.neckSet){
            	// altri loop
                for(Item offHand : this.offHandSet){
                    this.character.equipItem(offHand);
                    if(highestCurrentDps==-1 || highestCurrentDps<this.character.getTotalDps()){
                        highestCurrentDps=this.character.getTotalDps();
                        bestCharacterConfig=(Character)DeepCopy.copy(this.character);
                    }
                }
            }
        }
    }
    System.out.println("["+DateFormat.format(new Date())+"]"+ bestCharacterConfig);
}

Questa la parallela (ho provato vari modi, la deepcopy nel main era un bottleneck, ovviamente la deepcopy nel costruttore del workerthread era la stessa cosa, nel run() no ma mi mandava in outofmemory in tempo zero dato che i runnable non li dealloca fino alla fine del metodo, ho provato a tenere i risultati parziali in una MyTreeSet in cui avevo override add(E e) in modo da levare sempre tutti gli item tranne il primo (dove Comparable mi assicurava che il primo era il migliore etc). Alla fine sono arrivato a:

private void parallelTestAllGearCombinations(){
    ExecutorService es = Executors.newFixedThreadPool(8);
    // una mappa per memorizzare i risultati parziali
    Map<Integer,Character> charMap = new HashMap<Integer,Character>();
    charMap.put(1, this.character);
    charMap.put(2, this.character);
    charMap.put(3, this.character);
    charMap.put(4, this.character);
    charMap.put(5, this.character);
    charMap.put(6, this.character);
    charMap.put(7, this.character);
    charMap.put(8, this.character);
    // una mappa come "fonte" di Character
    Map<Integer,Character> charMap2 = new HashMap<Integer,Character>();
    charMap2.put(1, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    charMap2.put(2, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    charMap2.put(3, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    charMap2.put(4, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    charMap2.put(5, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    charMap2.put(6, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    charMap2.put(7, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    charMap2.put(8, new Character(this.character.getClasses(), this.character.getHitCap(), this.character.getExpertiseCap(), this.character.getCharacterScalingValues()));
    // per ciclare piu rapidamente
    Object[] heads = this.headSet.toArray();
    Object[] shoulders = this.shoulderSet.toArray();
    // altri array
    Object[] offHands = this.offHandSet.toArray();
    WorkerThread wk = null;
    for(int a=0; a<heads.length; a++){
        for(int b=0; b<shoulders.length; b++){
             // altri loop
                for(int n=0; n<offHands.length; n++){
                   wk = new WorkerThread(charMap, charMap2, (Item)heads[a], (Item)shoulders[b], ..., (Item)offHands[n]);
                    es.execute(wk);
                }
        }
    }
    System.out.println("["+DateFormat.format(new Date())+"] Ho finito");
    es.shutdown();
    while (!es.isTerminated()) {
    }
    System.out.println("["+DateFormat.format(new Date())+"] The optimization phase is over");
    for(Character c : charMap.values()){
        System.out.println("["+DateFormat.format(new Date())+"]"+ c);
    }
}

Infine il runnable:

public class WorkerThread implements Runnable{

    private Item[] items;
    private Map<Integer,Character> charMap;
    private Map<Integer,Character> charDaUsareInveceDiNewMap;
    
    public WorkerThread(Map<Integer,Character> charMap, 
    					Map<Integer,Character> charDaUsareInveceDiNewMap, Item... items){
       this.charDaUsareInveceDiNewMap=charDaUsareInveceDiNewMap;
       this.charMap=charMap;
       this.items=items;
    }

    public void run() {
	// facendo affidamento sul fatto che i thread startati dall executorService hanno nomi
             // nel formato pool-1-thread-1, pool-1-thread-2 etc, posso assumere che ogni thread-i
	// è seriale con se stesso, quindi non avrò interferenze
        int chatToUse = Integer.parseInt(Thread.currentThread().getName().substring(Thread.currentThread().getName().lastIndexOf("-")+1));
        Character newCharacter = this.charDaUsareInveceDiNewMap.get(chatToUse);
        for(Item item : this.items){
            newCharacter.equipItem(item);
        }
        if(newCharacter.getTotalDps()>this.charMap.get(chatToUse).getTotalDps()){
            DeepCopy dc = new DeepCopy();
            this.charMap.put(chatToUse, (Character)dc.copy(newCharacter));
        }
        newCharacter.clearAll();
    }
}

Entrambi i modi impiegano circa 30 secondi per completare i calcoli, con la differenza che il parallelo satura 8 cpu (or well 4 cpu + hyperthreading), il seriale solo 1/8...

Dal profiling tutti i thread sembrano lavorare correttamente, niente wait o lock su monitor....

[banryu79]

Prima cosa che mi è saltata all'occhio:

...
Object[] heads = this.headSet.toArray();
Object[] shoulders = this.shoulderSet.toArray();
Object[] offHands = this.offHandSet.toArray();
..
wk = new WorkerThread(charMap, charMap2, (Item)heads[a],(Item)shoulders[b], ..., (Item)offHands[n]);
...

Così al momento in cui istanzi un worker thread devi eseguire un sacco di cast!
Risolvi con il metodo toArray parametrico:

Item[] heads = this.headSet.toArray(new Item[this.headSet.size()]);
Item[] shoulders = this.shoulderSet.toArray(new Item[this.shoulderSet.size()]);
...
wk = new WorkerThread(charMap, charMap2, heads[a], shoulders[b], ...,offHands[n]);

Poi per il resto dovrei guardare con calma: non sono un esperto purtroppo.

@EDIT 1:

// facendo affidamento sul fatto che i thread startati dall executorService hanno nomi
// nel formato pool-1-thread-1, pool-1-thread-2 etc, posso assumere che ogni thread-i
// è seriale con se stesso, quindi non avrò interferenze

Assunzione corretta, ma non so come sia la distribuzione (ovvero al termine dell'esecuzione quanti "thread-1" hanno girato rispetto a "thread-2", rispetto a "thread-3", eccetera... della serie la distribuzione tende ad essere uniforme? E' plausibile ma è meglio non darlo per scontato: verificalo oppure scova nella documentazione qualcosa che lo garantisca, al momento io non lo ricordo) e la distribuzione, se non uniforme, in questo caso non giocherebbe a tuo favore (parlo a livello di prestazioni, non di race-conditions).

[tylerdurden83]

Ora mi leggo bene il tutto, però ti dico che la mappa di 1 Character su cui fare equip per thread-i è dovuta al fatto che:

The Set<Heads> has 4 items in it.
The Set<Necks> has 4 items in it.
The Set<Shoulders> has 4 items in it.
The Set<Backs> has 6 items in it.
The Set<Chests> has 9 items in it.
The Set<Wrists> has 1 items in it.
The Set<Hands> has 2 items in it.
The Set<Belts> has 4 items in it.
The Set<Legs> has 8 items in it.
The Set<Feet> has 3 items in it.
The Set<Fingers> has 2 items in it.
The Set<Trinkets> has 0 items in it.
The Set<Rangeds> has 1 items in it.
The Set<MainHands> has 4 items in it.
The Set<OffHands> has 2 items in it.

[2010-12-02 13:04:05] A total of 5308416 gear combinations will be tested

[2010-12-02 13:04:05] 1 CPUs detected on your system, assigning 5308416 combinations to each CPU

Queste le print dell'ultima run, tuttavia a seconda dei dati di input immessi potrebbero salire anche oltre il mezzo miliardo. Ad ogni modo anche in questo caso di 5 milioni, se genero 5 milioni di Character vado out of memory in tempo zero....

EDIT: attualmente l'unica operazione eseguita serialmente dal main è (oltre a loopare gli array), creare il Runnable (che nel costruttore ha solo 3 creazioni di riferimenti, no elaborazioni) e il submit dello stesso. Tutto il resto avviene in parallelo dentro i thread.
Il thread-i prende dalla mappa1 il Character con id i. Gli equippa tutti i pezzi, calcola il dps, retrieve del Character con id i dalla mappa dei risultati parziali, se quello corrente è meglio ne crea una copia e lo assegna al Character con id i nella mappa dei risultati parziali (la copia è necessaria altrimenti la prossima computazione del thread i lo modificherebbe xke la mappa dei risultati parziali avrebbe un riferimento ad un oggetto che il prox thread modifica)....

EDIT2: la distribuzione dei thread mi sembra assolutamente uniforme x ora...Intanto elimino i cast

[banryu79]

Domanda1: il medoto 'getTotalDps' di Character è computazionalmente rilevante oppure no (magari si limita a restituire solo un valore già calcolato, magari no)?

Domanda2:

[2010-12-02 13:04:05] 1 CPUs detected on your system, assigning 5308416 combinations to each CPU

Da dove sbuca quel valore?

[tylerdurden83]

Ehehe no no è corretto, ora sono sul laptop a lavoro ieri ero a casa sul fisso (core i7). L'ho lanciato al volo solo per farti un copia e incolla della dimensione dei vari Set e delle combinazioni (e quindi eventuali differenti copie di Character) che escono fuori a partire da quei Set.

Non è estremamente pesante, solo qualche if e qualche conto

public double getTotalDps(){
    Map<StatNames,Stat> charStats = this.characterStats;
    double totalCharDps = 0.0;
    int amountOfNthStat = 0;
    for(Stat stat : charStats.values()){
        if(stat.getStatName().compareTo(Stat.HIT)==0 && stat.getAmount()>this.hitCap){
            amountOfNthStat = this.hitCap;
        } else if(stat.getStatName().compareTo(Stat.EXPERTISE)==0 && stat.getAmount()>this.expertiseCap){
            amountOfNthStat = this.expertiseCap;
        } else {
            amountOfNthStat = stat.getAmount();
        }
        totalCharDps = totalCharDps + (amountOfNthStat*this.characterScales.get(stat.getStatName()).getAmount());
    }
    BigDecimal bd = new BigDecimal(Double.toString(totalCharDps));
    bd = bd.setScale(2, BigDecimal.ROUND_HALF_UP);
    totalCharDps=bd.doubleValue();
    return totalCharDps;
}

Una precisazione: (a casa su 8 thread) il main finisce dopo 5 secondi di istanziare i 5 milioni di runnable, gli altri 25 secondi circa che impiega per terminare sono tutti dovuti allo scodamento dei vari runnable da parte del thread pool

[banryu79]

The Set<Heads> has 4 items in it.
The Set<Necks> has 4 items in it.
The Set<Shoulders> has 4 items in it.
The Set<Backs> has 6 items in it.
The Set<Chests> has 9 items in it.
The Set<Wrists> has 1 items in it.
The Set<Hands> has 2 items in it.
The Set<Belts> has 4 items in it.
The Set<Legs> has 8 items in it.
The Set<Feet> has 3 items in it.
The Set<Fingers> has 2 items in it.
The Set<Trinkets> has 0 items in it.
The Set<Rangeds> has 1 items in it.
The Set<MainHands> has 4 items in it.
The Set<OffHands> has 2 items in it.

[2010-12-02 13:04:05] A total of 5308416 gear combinations will be tested

Ti segnalo una schiocchezza: a me viene 10616832 (il doppio: o c'è un set che non viene calcolato e li vale 2 oppure ne è stato lasciato fuori uno)

Non è estremamente pesante, solo qualche if e qualche conto

Ok, comunque fa qualcosa, era per capire l'utilità del calcolo in parallelo di quel metodo per ogni personaggio.

Curiosità mia:

    ...
    BigDecimal bd = new BigDecimal(Double.toString(totalCharDps));
    bd = bd.setScale(2, BigDecimal.ROUND_HALF_UP);
    totalCharDps= bd.doubleValue();
}

a che cosa serve passare il double come String al costruttore di BigDecimal?
Serve per qualche questione di calcolo?

Comunque qui il problema principale è che hai un numero potenzialmente enorme di combinazioni possibili. Non è possibile "scremarle" in qualche modo, con qualche euristica, invece di calcolarle tutte?

Ad esempio, avendo i diversi possibili oggetti equippaggiabili divisi per set di locazioni (sto supponendo che gli item assegnabili alla "Head" possano essere assegnati solo in quella locazione) non è possibile ricavare il migliore oggetto in assoluto per quella locazione? Oppure i migliori 2 o 3? O al contratio determinare quello/i peggiore/i che si possono scartare?