Program wielowątkowy działa dłużej niż działający na jednym wątku.

0

Witam,
Próbowałem rozwiązać zadanie z ProjectEuler przy wykorzystaniu ExecutorService, Callable etc.
Program pokazuje prawidłowy wynik jednak program wielowątkowy trwa 10 razy dłużej niż program wykonujący się w jednym wątku...
Czy może ktoś mógłby mi to wyjaśnić ?
Poniżej zamieszczam klasy składające się na program wielowątkowy i klasa jednowątkowa:

//Collatz.java
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;



public class Collatz {
	final int MAX_NUMBER = 1000000;
	int max = 0, step, maxStep;
	double temp;
	long start,stop;
	ExecutorService exec = Executors.newCachedThreadPool();
	FutureColatzCallback<String> ft;
	Callable<String> task = new Callable<String>() {
		
		public String call() throws Exception {
			start = System.currentTimeMillis();
			for(int i = 1; i <= MAX_NUMBER; i++) {
				temp = i;
				step = 0;
				while( temp > 1) {
					++step;
					if ((temp % 2) == 0) 
						temp = temp/2;
					else
						temp = 3*temp+1;
					
					if(step > maxStep ) {
						max = i;
						maxStep = step;
					}
				}
			}
			stop = System.currentTimeMillis();
			String returnMessage = "Liczba to: "+max+ " ilość kroków " + maxStep + " wynik znaleziony w " + (stop - start) + "mils"; 
			return returnMessage;
		}
	};
	Collatz() {
		ft = new FutureColatzCallback<String>(task);
		exec.execute(ft);
	}

}

 
//FutureColatzCallback.java
import java.util.concurrent.Callable;
import java.util.concurrent.FutureTask;

import javax.swing.JOptionPane;

class  FutureColatzCallback<V> extends  FutureTask<V> {

  public FutureColatzCallback(Callable<V> callable) {
    super(callable);
  }

  public void done() {
    String result = "Wynik: ";
    if (isCancelled()) result += "Cancelled.";
    else try {
      result += get();
    } catch(Exception exc) {
        result += exc.toString();
    }
    JOptionPane.showMessageDialog(null, result);
    System.exit(0);
  }

}
 
/*The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.
*/

public class Problem14 {
	
	public static void main(String[] args) {
		new Collatz();
	}
}

No i teraz klasa jedno wątkowa:

 
public class NoProblem14 {
	
	public static void main(String args[]){
		final int MAX_NUMBER = 1000000;
		int max = 0, step, maxStep = 0;
		long temp;
		long start,stop;
		start = System.currentTimeMillis();
		for(int i = 1; i <= MAX_NUMBER; i++) {
			temp = i;
			step = 0;
			while( temp > 1) {
				++step;
				if ((temp % 2) == 0) 
					temp = temp/2;
				else
					temp = 3*temp+1;
				
				if(step > maxStep ) {
					max = i;
					maxStep = step;
				}
			}
		}
		stop = System.currentTimeMillis();
		String returnMessage = "Liczba to: "+max+ " ilość kroków " + maxStep + " wynik znaleziony w " + (stop - start) + " mils"; ; 
		System.out.println(returnMessage);

	}
}

Program wielowątkowy u mnie wykonuje się w ok. 3400 ms, a jednowątkowy 260 ms.

3

Na poczatek dzialajacy kod:

 
import java.util.concurrent.*;
import java.util.concurrent.locks.LockSupport;

public class Collatz2 {

    public static final int cpus = Runtime.getRuntime().availableProcessors() - 1;
    public static final int MAX = 10_000_000;
    private static final int BIN = MAX / cpus;

    public static void main(String[] args) throws InterruptedException {
        new ComputationThread(1, 50_000, new CountDownLatch(0)).run();
        LockSupport.parkNanos(1_000_000_000L);
        
        testSingleThread();
        testParallel();
    }

    private static void testSingleThread() {
        final ComputationThread task = new ComputationThread(1, MAX, new CountDownLatch(0));
        final long start = System.nanoTime();
        task.run();
        final long duration = (System.nanoTime() - start) / 1_000_000;
        final Result result = task.result;
        System.out.printf("1 threads:\t", cpus);
        System.out.printf("Duration: %s, number: %s, steps: %s\n", duration, result.number, result.steps);
    }

    private static void testParallel() throws InterruptedException {
        final CountDownLatch latch = new CountDownLatch(1);
        int lower = 0, upper = BIN;
        final ComputationThread[] threads = new ComputationThread[cpus];
        for (int i = 0; i < cpus; i++, lower = i * BIN, upper = (i+1) * BIN)
            (threads[i] = new ComputationThread(lower, upper, latch)).start();
        latch.countDown();
        final long start = System.nanoTime();
        for (final ComputationThread thread : threads) thread.join();
        final long duration = (System.nanoTime() - start) / 1_000_000;
        Result maxResult = new Result();
        for (final ComputationThread thread : threads) if (maxResult.steps < thread.result.steps) maxResult = thread.result;
        System.out.printf("%s threads:\t", cpus);
        System.out.printf("Duration: %s, number: %s, steps: %s\n", duration, maxResult.number, maxResult.steps);
    }


    static class Result { public int number, steps; }

    static class ComputationThread extends Thread {
        final int lower, upper; final CountDownLatch latch;
        final Result result = new Result();

        ComputationThread(final int lower, final int upper, final CountDownLatch latch) {
            this.lower = lower; this.upper = upper; this.latch = latch;
        }

        @Override
        public void run() {
            try { latch.await(); } catch (InterruptedException e) { e.printStackTrace(); }
            int max = 0, step, maxStep = 0; long temp;
            for (int i = lower; i <= upper; i++) {
                temp = i; step = 0;
                while(temp > 1) {
                    if ((temp & 1) == 0) temp >>= 1;
                    else temp = 3 * temp + 1;
                    if (++step > maxStep ) { max = i; maxStep = step;}
                }
            }
            result.number = max; result.steps = maxStep;
        }
    }

}

Na moim laptopie:
kernel: linux 3.2.0-61-generic amd64,
cpu: 4 x Intel(R) Core(TM) i7-3632QM CPU @ 2.20GHz (HT) = 8 watkow
java: Java HotSpot(TM) 64-Bit Server VM (build 24.45-b08, mixed mode)
Wyniki sa nastepujace:

1 threads: Duration: 3097, number: 8400511, steps: 685
7 threads: Duration: 878, number: 8400511, steps: 685

A teraz analiza kodu...

  1. Nie masz zadnej kontroli nad iloscia watkow utworzonych w ramach CachedThreadPool. Nie jestes w stanie zagwarantowac, ze algorytm zadziala wspolbieznie w ten sam sposob za kazdym razem.
  2. Tworzysz i submitujesz tylko 1 instancje callable. W zwiazku z tym twoja wspolbiezna wersja algorytmu jest tak na prawde 1-watkowa.
  3. Nie rozgrzewasz JVMa przed testem. Moja rozgrzewka tez nie jest idealna, ale przynajmniej gorace sciezki zostana skompilowane zanim uruchomiony zostanie wlasciwy test (-XX:+PrintCompilation).
  4. Twoj kod jest troche przekombinowany. Ja zmiescilem sie w 72 liniach wliczajac w to warmup, a widac, ze niespecjalnie zalezalo mi na estetyce, prostocie i czytelnosci.
  5. Do pomiaru czasu, ktory uplynal uzywaj nanoTime. Wartosci zwracane przez System.currentTimeMillis() zaleza o stosowanego przez system clock_source. Poniewaz wartosci te moga zostac poddane korektom (ntp albo ptp), funkcja nie jest monotoniczna. Obecnie na wspolczesnych procesorach mozna bezpiecznie uzywac nanoTime() w aplikacjach wielowatkowych ze wzgledu na constant_tsc.
  6. Jesli chcesz bawic sie w intensywne obliczeniowo algorytmy to uzywaj operatorow logicznych tam, gdzie to mozliwe. Zwlaszcza dzielenie jest kosztowne z punktu widzenia procesora, bo zapobiega pipeline'owaniu instrukcji i flushuje wszystko w ALU. Dla porownania wyniki z dzieleniem i modulo (Twoja wersja algorytmu):

1 threads: Duration: 4538, number: 8400511, steps: 685
7 threads: Duration: 1020, number: 8400511, steps: 685

Pozdrawiam
Wojtek

0

Czyli jednym słowem nie ma co się bawić w ExecutorService FutureTask etc. Coz wykladowca przedstawiał to zagadnienie jakby to było super rozwiązanie.
A czemu użyłeś 1 procesora mniej niż jest dostępne ?

0
mefmund napisał(a):

Czyli jednym słowem nie ma co się bawić w ExecutorService FutureTask etc. Coz wykladowca przedstawiał to zagadnienie jakby to było super rozwiązanie.
A czemu użyłeś 1 procesora mniej niż jest dostępne ?

Executor framework to wyjatkowo przydatne narzedzie w programowaniu wspolbieznym poniewaz uwalnia Cie o zarzadzania watkami i pozwala Ci skupic sie na zadaniach. Zdecydowanie polecam blizsze zapoznanie sie.
W moim przykladzie nie uzylem executora, poniewaz chcialem miec calkowita kontrole nad tym kiedy watki sa uruchamiane, co robia i kiedy sie zatrzymuja.
Co do ilosci wykorzystanych core'ow, wolalem zostawic 1 wolny, zeby drastycznie ograniczyc prawdopodobienstwo sytuacji w ktorej watki robocze skoncza prace, a watek glowny bedzie w tym momencie wywlaszczony przez scheduler i nie dokona ostatecznego pomiaru czasu dosc precyzyjnie.

0

Dołączę się. Mam pytanie bo nie rozumiem jak to wszystko działa.

Mam 2 requesty restowe, które chcę wywołać w puli wątków, żeby pobrać dane jednocześnie z dwóch miejsc i złączyć w jedno.
Stworzyłem w metodzie newcachedthreadpool, submit na 2 callablach, otrzymuję 2 futury. Niby wszystko cacy. Na koncu gdzieś to się blokuje get() i jest zwracany wynik.

Niby wszystko działa ale jednak nie działa. Gdy zaloguję się na innego użytkownika, często nie jest zwracany żaden wynik.
Podglądam co się dzieje w VisualVM by zrozumieć o co chodzi
newcachedthreadpool ma 60 sekund życia i dopóki te wątki żyją i mają status 'park' to nie jest zwracany żaden nowy wynik. Jak już sobie umrą to są chyba spawnowana nowa pula i ściąga wynik.

Nie rozumiem co się dzieje. Nie wiem czy gdzieś trzeba zrobić invoke all? Dla jednego usera co się loguje działa to prawidłowo. Wątki są reużywalne itp.

Jak to powinno być skonfigurowane.

a newFixedThreadPool trzeba ponoć zawsze zrobić shutdown, ale to jest bez sensu zaraz po wykonaniu zadania, bo potrzeba by był reużywalny. To gdzie to należy ubić?

Z góry dzięki za poomoc.

1 użytkowników online, w tym zalogowanych: 0, gości: 1