Thread et synchronisation d'une liste

Version imprimable

18/01/2010, 11h12
mikeOSX

Thread et synchronisation d'une liste
Bonjour a tous,

j'ai une petite question dont je n'ai pas reussi a trouver la reponse dans les faq ou le forum.

j'ai une liste (ArrayList) qui va etre modifiée par plusieurs Thread.

n Thread qui vont rajouter des elements a cette liste.
1 Thread qui va lire cette liste si elle n'est pas vide, traiter l'element puis le supprimer de la liste.

La partie ou les Thread rajoutent des elements doit etre synchronisée pour que 2 Thread n'ecrivent pas au meme endroit :
Code:

1 2 3 synchronized(maListe) { maListe.add(element); }
La question que je me pose est la suivante:
Est ce que le thread qui va lire, traiter puis supprimer l'element doit etre synchronisé aussi ?
Si oui lors de quelle partie ? (suppression, lecture ? )

merci :)

mike
18/01/2010, 11h18
tchize_

toutes les opérations doivent etre synchronisée sinon tu risque de lire des données incomplete de ton arraylist (exemple: le tableau a été agrandi mais la dernière donnée pas encore insérée -> tu récupère un null)

De préférence, si il est court, synchronize le bloc lecture et effacement.

Note que pour ce genre de boulot un BlockingQueue serait peut etre plus appropriée http://java.sun.com/j2se/1.5.0/docs/...kingQueue.html

Merci tchize de ta reponse.

J'ai regardé pour les BlockingQueue, mais apparemment, il faut lui donner une taille max, taille que je ne connais pas (s'il doit y avoir 50000 elements, ba il faut que ca puisse etre le cas :D )
dans ce cas, la LinkedBlockingQueue serait adapté, mais quand je fais des tests de perf (oui, on me demande aussi que ce soit super rapide -_-" ) la ArrayList que je synchronise est plus rapide que la LinkedBlockingQueue.

En repassant sur la ArrayList, faut il aussi que je synchronize quand je teste si elle est vide ou pas ?

en gros, le code du thread qui lit se resume a :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 while(isRunning) { while(! maListe.isEmpty() ) { Object obj; synchronized (maListe) { obj = maListe.get(0); maListe.remove(obj): } traitement(obj); } try { Thread.sleep(PERIOD); } catch (InterruptedException e) {isRunning = false; } }
mike

18/01/2010, 12h22
adiGuba

Salut,

Citation:

Envoyé par mikeOSX

dans ce cas, la LinkedBlockingQueue serait adapté, mais quand je fais des tests de perf (oui, on me demande aussi que ce soit super rapide -_-" ) la ArrayList que je synchronise est plus rapide que la LinkedBlockingQueue.

On pourrait voir le test et ses résultats ?

a++

Citation:
Envoyé par mikeOSX
Merci tchize de ta reponse.

J'ai regardé pour les BlockingQueue, mais apparemment, il faut lui donner une taille max, taille que je ne connais pas (s'il doit y avoir 50000 elements, ba il faut que ca puisse etre le cas :D )
dans ce cas, la LinkedBlockingQueue serait adapté, mais quand je fais des tests de perf (oui, on me demande aussi que ce soit super rapide -_-" ) la ArrayList que je synchronise est plus rapide que la LinkedBlockingQueue.

En repassant sur la ArrayList, faut il aussi que je synchronize quand je teste si elle est vide ou pas ?

en gros, le code du thread qui lit se resume a :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 while(isRunning) { while(! maListe.isEmpty() ) { Object obj; synchronized (maListe) { obj = maListe.get(0); maListe.remove(obj): } traitement(obj); } try { Thread.sleep(PERIOD); } catch (InterruptedException e) {isRunning = false; } }
mike
Là tu risques un gros problème :
- Tu fais un test sur maListe, parfait elle n'est pas vide.
- Un autre thread vide la liste.
- Tu essayes de récupérer le premier élément.

Maintenant, si tu es sûr que ta liste ne peut être vidée par d'autres threads, vu qu'il ne semble pas y avoir de cas "liste considérée comme vide, mais un autre thread a ajouté un élément entre temps", ça me semble convenable du point de vue de la synchronisation.

adiGuba :
Ce sont des tests de perf fait maison, il doit y avoir beaucoup mieux :lol:
et le plus rapide, c'est juste de quelques micro secondes, mais apparemment, ca compte enormement.

Pour le test :
2 Thread, qui vont appeler des trucs avant, puis la methode pour ajouter dans la liste, en gros qui vont faire la meme chose.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 private void a(....) { //quelques tests //une creation d'un object obj long begin = System.nanoTime(); addToList(obj); long end1 = System.nanoTime(); addToQueue(obj); long end2 = System.nanoTime(); System.out.println("addToList : " + (end1 - begin) ); System.out.println("addToQueue : " + (end2 - end1) ); } private addToList(Object obj) { synchronized(maListe) { maListe.add(obj); } } private addToQueue(Object obj) { synchronized(maListe) { maListe.add(obj); } }
en vrai, la methode a(...) est dans une autre classe que les 2 methodes add, mais pour simplifier, je les ai mise au meme endroit.

au debut, j'avais mis un nanoTime avant et apres l'appel a la methode a() qui faisait soit addToQueue, soit addToList, et j'avais en moyenne une durée de :
17500 ns (Thread1) et 20300 ns (Thread2) pour le addToList
21000 ns (Thread1) et 23400 ns (Thread2) pour le addToQueue

Pour la methode actuelle, juste calculer le temps d'execution entre addToList et addToQueue,
addToList : 1500 ns
addToQueue : 5000 ns
c'est une moyenne, car addToQueue varie de 4200 a 10000 ns alors que addToList varie de 1200 a 1800 ns

sachant qu'en meme temps, j'ai le code de mon precedent post qui lit les 2 listes pour traiter les elements.

En esperant que ca reponde a ta question :)

Rei Ichido :
Il n'y a qu'un seul thread qui lit et supprime les elements de la liste, les autres thread ne font qu'ajouter des elements.
La liste peut tres bien etre vide, dans ce cas, le thread ne passera jamais a l'interieur du while(! maListe.isEmpty() )
Il dormira un peu, puis recommencera.

mike

c'est pas comme ca qu'on mesure des perfs. Pour mesurer des perfs ils faut faire des appels pendant quelques minutes. Ensuite tu divise le temps par le nombre d'appels effectués, et tu as un mesure correcte des perfs.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ArrayBlockingQueue;
 
public class TestPerfs {
 
	private static ArrayBlockingQueue<Object> queue = new ArrayBlockingQueue<Object>(50000);
	private static List<Object> list = new ArrayList<Object>();
	private final static int MAX = 5000000;
	/**
         * @param args
         */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i=0; i<10; i++){
			Thread t1 = new Thread(){
 
				@Override
				public void run() {
					Object o = new Object();
					long l1 = System.currentTimeMillis();
					try {
						for (int i= 0; i< MAX; i++)
							queue.put(o);
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
					long l2 = System.currentTimeMillis();
					System.out.printf("Time per enqueue operation: %f ms\n",(((float)(l2-l1))/((float)MAX)));
				}			
			};
			Thread t2 = new Thread(){
 
				@Override
				public void run() {
					long l1 = System.currentTimeMillis();
					try {
						for (int i= 0; i< MAX; i++)
							queue.take();
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
					long l2 = System.currentTimeMillis();
					System.out.printf("Time per dequeue operation: %f ms\n",(((float)(l2-l1))/((float)MAX)));
				}			
			};
			t1.start();
			t2.start();
			try {
				t1.join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				t2.join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
 
 
			// TODO Auto-generated method stub
			t1 = new Thread(){
 
				@Override
				public void run() {
					Object o = new Object();
					long l1 = System.currentTimeMillis();
					for (int i= 0; i< MAX; i++)
						synchronized(list){
							list.add(o);
						}
					long l2 = System.currentTimeMillis();
					System.out.printf("Time per enqueue operation (list): %f ms\n",(((float)(l2-l1))/((float)MAX)));
				}			
			};
			t2 = new Thread(){
 
				@Override
				public void run() {
					long l1 = System.currentTimeMillis();
					for (int i= 0; i< MAX; i++)
						synchronized (list) {
							if (list.size()<1) 
								i--;
							else
								list.remove(list.size()-1);
						}
					long l2 = System.currentTimeMillis();
					System.out.printf("Time per dequeue operation (list): %f ms\n",(((float)(l2-l1))/((float)MAX)));
				}			
			};
			t1.start();
			t2.start();
			try {
				t1.join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				t2.join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
 
		}
	}
 
}

en sortie on a ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Time per enqueue operation: 0,000117 ms
Time per dequeue operation: 0,000117 ms
Time per enqueue operation (list): 0,000100 ms
Time per dequeue operation (list): 0,000112 ms
Time per enqueue operation: 0,000135 ms
Time per dequeue operation: 0,000134 ms
Time per enqueue operation (list): 0,000119 ms
Time per dequeue operation (list): 0,000116 ms
Time per enqueue operation: 0,000090 ms
Time per dequeue operation: 0,000090 ms
Time per enqueue operation (list): 0,000060 ms
Time per dequeue operation (list): 0,000063 ms
Time per enqueue operation: 0,000088 ms
Time per dequeue operation: 0,000088 ms
Time per enqueue operation (list): 0,000071 ms
Time per dequeue operation (list): 0,000077 ms
Time per enqueue operation: 0,000089 ms
Time per dequeue operation: 0,000089 ms
Time per enqueue operation (list): 0,000082 ms
Time per dequeue operation (list): 0,000090 ms
Time per enqueue operation: 0,000094 ms
Time per dequeue operation: 0,000093 ms
Time per enqueue operation (list): 0,000070 ms
Time per dequeue operation (list): 0,000082 ms
Time per enqueue operation: 0,000094 ms
Time per dequeue operation: 0,000094 ms
Time per enqueue operation (list): 0,000065 ms
Time per dequeue operation (list): 0,000073 ms
Time per enqueue operation: 0,000096 ms
Time per dequeue operation: 0,000095 ms
Time per enqueue operation (list): 0,000077 ms
Time per dequeue operation (list): 0,000087 ms
Time per enqueue operation: 0,000093 ms
Time per dequeue operation: 0,000093 ms
Time per enqueue operation (list): 0,000103 ms
Time per dequeue operation (list): 0,000105 ms
Time per enqueue operation: 0,000106 ms
Time per dequeue operation: 0,000106 ms
Time per enqueue operation (list): 0,000059 ms
Time per dequeue operation (list): 0,000072 ms

Tu notera que les perf sont instables, par moment la liste est plus lente, par moment la liste est plus rapide. En "global" elle est plus rapide. Tu notera que la différence de perfs est au maximum de 0.000050ms par élément. Ca signifie que pour économiser une seconde il faut mettre 20 millions d'éléments dans la liste! Est-ce que ca vaut le coup de se coincer avec le risque de s'emeler les pinceaux dans un synchronized ou vaut-il mieux utiliser la classe blocking queue déjà synchronizée?

Note : la linkedBlockingQueue est effectivement plus lente si tu la teste (suffit d'adapter le code). Là, on peut gagner 1s de temps de traitement sur le traitement de 5 millions d'éléments (+- 4 fois plus lente que la blockingqueue)

-> Eviter d'optimiser trop vite le code. La tu va viser l'arraylist pour économiser des perfs alors qu'il n'y a que des cacahuetes à économiser. Mieux vaut te concentrer sur les vrais point noirs de l'application et éviter des soucis avec la synchronisation en utilisant des classes déjà testées pour leur solidité.

18/01/2010, 14h30
adiGuba
Une remarque : tu n'as pas à synchroniser les BlockingQueue ;)

Sinon attention à ce genre de test qui peuvent être assez perturbé par plein d'élément externe. Il est plus juste de prendre des valeurs plus grande en multipliant le nombre d'appel et en calculant la moyenne de traitement.

Par contre tu risque d'avoir le résultat inverse sur la suppression du premier élément, qui est très couteux dans une ArrayList, mais très rapide sur une Linked***

Enfin si tu utilises les Queues, n'hésites pas à utiliser ses méthodes spécifiques (offer(), take()). Les boucles de traitements en seront simplifié :
Code:

1 2 3 4 while(isRunning) { traitement(queue.take()); }
a++
18/01/2010, 14h31
hibour

Citation:

Envoyé par tchize_

try {
t1.join();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
try {
t2.join();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

Pourquoi l'ajout de join, Ya aucun intérêt des thread? sans join on simulera un comportement plus proche de la réalité je pense!
18/01/2010, 14h45
tchize_

du tout, le join permet à mon thread principal (qui éxécute main) d'attendre que la mesure soit finie ;) Ca n'influence pas les threads de meesures (t1 et t2) qui tournent bien en // Le but est de comparer les méthodes, pas de les faire tourner en même temps. sinon on aura des mesures abhérrante ;)

En l'occurence ici, je fait un ajout / réception en // avec une technique, puis le meme avec l'autre classe, puis je recommence, etc. Mais les mesures sont bien indépendantes.

Et effectivement, dans mon test, la list se comporte comme une LIFO alors que la blockinqueue se comporte comme une FIFO! Si je fais passer la liste en FIFO

Code:

list.remove(0);

les performances s'effondrent quand le remplissage est plsu rapide que le vidage de la liste. A partir de 100.000 éléments, on arrive * 0.05ms par opération de remove. A partir de 500.000 éléments j'attends toujours la réponse, ca se casse la dent monstrueux...

Edit: 0.25ms par remove(0), soit 2 minute pour 500.000 élément. Je rappelle qu'à l'origine on parlait de gagner 1 seconde par tranche de 5 millions d'éléments.....
18/01/2010, 15h08
hibour

On aurai pu faire ton test sans thread. Car le t1 s'exécute toujours avant le t2..
Tu crée 2 thread pour rien à mon avis.
18/01/2010, 15h13
tchize_
t1 tourne en // avec t2
Code:

1 2 t1.start(); t2.start();
par contre t2 fini toujours après t1 vu que t2 traite les éléments de t1
18/01/2010, 15h17
mikeOSX

oui, c'est vrai, tu as raison tchize :P
Pour calculer le temps d'execution de a() sur 500 appels, j'avais fait comme tu dis, le resultat donné est bien la moyenne sur ces 500 appels.
Pour le code que j'ai donné, j'avais fait la moyenne de tete en fonction des resultats que je voyais :D
je viens de le refaire en calculant la vrai moyenne, et j'ai
arrayList : 1524 ns
LinkedBlockingQueue : 5224 ns
ArrayBlockingQueue : 3984 ns

Le probleme que je vois pour l'ArrayBlockingQueue, c'est qu'il faut mettre une taille max.
Si jamais mon thread qui depile plante, on ne va faire que de rajouter des elements, et au bout d'un moment, ca va etre plein, et bloquer indefiniment :S
Ou alors dans ce cas, faire un add ou lieu d'un put, il y a une difference entre les 2 ?
EDIT: il est preferable en fait de faire un offer :D ca ne bloque pas le processus si la liste est pleine

Sinon, je suis entierement d'accord qu'il faut mieux "perdre" 2 micro secondes (selon mes mesures ^^ ), et avoir une liste deja synchronisé, et plus solide.
18/01/2010, 16h00
tchize_

Citation:

Envoyé par mikeOSX

Si jamais mon thread qui depile plante, on ne va faire que de rajouter des elements, et au bout d'un moment, ca va etre plein, et bloquer indefiniment :S

Dans le cas d'un arraylist, on va l'engorger jusqu'à crash de la jvm, est-ce mieux? Si ton thread qui doit gérer la liste plante, t'as déjà un problème, autant en etre informé le plus vite possible....
18/01/2010, 16h58
mikeOSX

c'est pas faux, j'avais pas pensé au crash de la jvm :mrgreen:
de toute facon, j'ai capté les erreurs possible, et si le thread qui lit et traite les info plante, un autre est créé pour prendre sa place :P
donc normalement pas de risque de liste pleine.

merci a tous en tout cas pour ces reponses rapides :ccool:

mike