Sito Eratostenesa współbieżnie.

0

Cześć,

Chciałem porównać czasy obliczania sita Eratostenesa dla różnej liczby wątków. Napisałem następujący program, ale nie działa tak jak trzeba.

import java.util.HashMap;

public class Sieve implements Runnable{
	private HashMap<Integer,Boolean> array = new HashMap<Integer,Boolean>();
	private int counter = 1;
	private int x;
	public void run(){
	    while(counter < x-1){
	        do{
	            counter++;
	        }
	        while( array.get(counter));
	        int tmp = counter;
	        for(int i = tmp; i < array.size(); i+=tmp){
	            if( i!= tmp)
	                array.put(i,true);
	        }
	        try{
	        Thread.sleep(0L, 1);
	        }
	        catch (Exception e){}
	    }
	}

	public void setArray(int x){
	    this.x = x;
	    for(int i = 2; i < x; i++)
	        array.put(i, false);
	}
	public void printArray(){

	    for(int i = 2; i < array.size();i++){
	        if( !array.get(i))
	        System.out.println(i);

	    }
	}
} 

Klasa główna

import java.util.Date;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Main {
	public static void main(String[] args) throws InterruptedException{
		Sieve task = new Sieve();
		task.setArray(50000);
		Long beg = new Date().getTime();
		ExecutorService exec = Executors.newCachedThreadPool();
		for(int i = 0; i < 1;i++){
			exec.execute(task);
		}
		exec.shutdown();
		Long sleep = 300L;
		Thread.sleep(sleep);
		task.printArray();
		System.out.println("Time is "+(new Date().getTime()-beg-sleep));
	}
}

Problem polega na tym, że wraz ze wzrostem liczby wątków czasy wykonania nie zmniejszają się. Czasami wręcz zwiększają się... Czym może to być spowodowane?
Dodatkowo zauważyłem, że spory czas po zakończeniu obliczeń wątek DestroyJavaVM bardzo długo "pracuje". Czyżby to Garbage Collector sprzątał po HashMapie?

0

Ja chyba czegoś nie rozumiem. Przecież w u ciebie w tym kodzie odpalasz zwykłe seryjne sito, tylko że robisz to wiele razy. Ergo nie dziwota że działa wolniej -> procesor musi dzielić czas pomiędzy wątki. Spowolnienie zapewne jest liniowe i takie też być powinno...

0

Dodałem

System.out.print(tmp+" id="+Thread.currentThread().getId()+"\n");

do metody run()
Wyniki prezentują się następująco

2 id=8
3 id=9
5 id=10
7 id=8
11 id=11
13 id=10
17 id=9
19 id=8
23 id=11
29 id=10
31 id=9
37 id=8
41 id=11
43 id=10
47 id=9
53 id=8
59 id=9
61 id=8
67 id=11
71 id=10
73 id=9
79 id=8
83 id=11
89 id=10
97 id=9
Time is 5

Skoro kolejne liczby są "wykreślane" przez kolejne wątki, to dlaczego te wątki nie działają współbieżnie?

0

Dopiero teraz zobaczyłem co ty robisz. Słyszał kiedy o takich rzeczach jak synchronizacja albo race condition? To doczyta. Jakby to chciaż była ConcurrentHashMap...
Poza tym ile masz rdzeni procesora? Jak odpalisz ten kod to ile rdzeni zabiera JVM?

0

Słyszał i czytał, ale widocznie za mało, bo nie bardzo wiem jak to tutaj zastosować. Jeżeli dam dodam parametr synchronized do metody run, to nie będzie wtedy współbieżności. Bez bicia przyznam, że nie wiem jak inaczej mógłbym to usprawnić. Początkowo, program usuwał elementy z HashMapy( żeby nie sprawdzać 6 dwa razy itp), ale nie wiedziałem jak rozwiązać problem synchronizacji.
Rdzenie mam 4, ale nie wiem jak sprawdzić ile z nich jest wykorzystywanych przez JVM( JVisualVM ma takie możliwości?)

0

No ewidentnie za mało skoro "synchronizujesz" to sobie przez sleep() (którego być tu nie powinno!). Albo użyj ConcurrentHashMap albo synchronizuj samą operację na mapie tam gdzie ją wykonujesz, tzn

synchronized(array){
  operacja_na_mapie
}

A tego sleepa wywal. Powinno działać lepiej...

0

Synchronizacja synchronizacją, a tu się spory błąd wkradł i tak sobie czekał i czekał. Tym błędem było złe liczenie czasu. Zamiast liczyć czas, wykonywania wątków to mój program liczył czas wypisywania wyników.
Aby realnie mierzyć czas wykonywania programu dodałem do klasy Sieve zmienną threads. Którą później inkrementuję i dekrementuję w odpowiednich miejscach:

 public void run(){
    threads++;
    while(counter < x-1){
    ...
    }
    threads--;
}

W klasie Main dodałem coś takiego.

        Long time = 0L;
        while(true){
            if(task.threads == 0){
                time = new Date().getTime()-beg;
                break;
            }
            else 
                Thread.sleep(10);
           }

        task.printArray();
        System.out.println("Time is "+time);

Czyli sprawdzam w pętli czy wątki poboczne się zakończyły( a przynajmniej ja to tak rozumiem). Następnie wypisuję zawartość mapy i czas. Niestety nie działa to tak jak chciałem. Ostatnim poleceniem w metodzie run jest threads--; a mimo to wątek wydaje się liczyć dłużej. Czym może to być spowodowane?
Wyniki dla powyższego kodu i dla kodu po sleepie:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Time is 5



Po sleepie
2
3
5
7
11
13
17
19
0

Napisałem od początku metodę run. W ogólnym odczuciu program działa wolniej, ale przynajmniej współbieżnie. Niestety dla dużych zakresów liczb( 20 000). Wyniki są błędne, jakieś sugestie czemu?

public void run() {
		synchronized(this){
			threads++;
		}
		List<Integer> list = new ArrayList<Integer>();
		synchronized (list) {
			while (counter < Math.sqrt(x)){
				// 
				list.add(counter++);
				try {
					Thread.sleep(0,1);
				} catch (InterruptedException e) {}
			}
		}
		Collections.sort(list);
		for (Integer it : list) {
			int n = it.intValue();
			for (int i = n; i < x; i += n) {
				if (array.get(i) && i == n)
					break;
				if( i > n)
					array.put(i, true);
			}
		}
		synchronized(this){
			threads--;
		}
	}
0

Bo wykonujesz operacje na kolekcji poza sekcją krytyczną? o_O Robisz "sort" na liście poza blokiem synchronizacji i jak to niby ma działać? W ogóle zresztą modyfikujesz tam tą tablicę co jest jakimś WTFem. Nie lecą ci czasem ConcurrentModificationException? ;]

0
Shalom napisał(a):

W ogóle zresztą modyfikujesz tam tą tablicę co jest jakimś WTFem. Nie lecą ci czasem ConcurrentModificationException? ;]

Nie leci. Dlaczego WTF?

Ogólnie mój pomysł był następujący:
W pierwszej pętli while w każdym wątku wrzucam do listy kolejne liczby z podanego zakresu( np 2-200).
Po każdym addzie robię Thread.sleepa(* Thread.yield*() nie zmienia mi wątków1) aby kolejne liczby były dodawane do list kolejnych wątków.
czyli:

Ze sleepem Z yieldem
2 T-1 2 T-1
3 T-2 3 T-1
4 T-3 4 T-1
5 T-1 5 T-1
6 T-2 6 T-1
etc
Później w pętli każdy wątek sprawdza swoją listę liczb( co wykonuje współbieżnie) i zaznacza liczby złożone.

Problemem jest fakt, że korzystanie ze sleepa znacząco spowalnia program. Niekorzystanie ze sleepa nie skraca czasu przy zwiększaniu liczby wątków.
Ze sleepem:
2-2000, 1 watek, czas: 2242
2-2000, 4 wątki, czas:589
Z yieldem
2-200000, 1 watek, czas: 496
2-200000, 4 wątki, czas: 513

1 Czy może to wynikać z używania* CachedThreadPool*?

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