Accès concurrent avec un contains rapide

Version imprimable

Bonjour,

J'ai une liste d'attente ConcurrentLinkedQueue<UrlX> d'URL (plus précisément ce sont des UrlX, un objet que j'ai créé avec une propriété urlString (string)).
J'ai 10 threads qui prennent les urls une à une (ils supprime l'url qu'ils prennent) et de temps en temps ces threads rajoutent des urls

L'ennui est que pour le pas avoir de heap space error j'ai une fonction qui regarde si l'url n'est pas déjà dans la file d'attente avant de l'ajouter :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 private boolean urlQueueContain(String urlString,int depth) { Iterator<UrlX> it=this.urlQueue.iterator(); UrlX url; while(it.hasNext()) { url=it.next(); if(url.urlString.equals(urlString)) { if(url.depth>depth) { this.urlQueue.remove(url); return false; } return true; } } return false; }
Et cette fonction prend beaucoup de temps à s'exécuter. Avant j'utilisais un ArrayList qui était beaucoup plus rapide mais à l'époque il n'y avait pas d'accès concurrent
Comment puis je résoudre cela ?

21/10/2014, 17h41
Pill_S

Déjà, la boucle à base d'itérateur c'est vraiment old school... "for each" c'est bcp plus joli (mais ça va pas améliorer tes perfs).

Si ton objet UrlX est immuable (son état ne change pas après instanciation) et que equals et hashcode sont correctement implémentés, alors la manière la plus rapide de déterminer si la queue contient un élément, est de passer par un hashset (en plus de ta queue) qui permet (théoriquement) un accès en temps constant (O(1)).

En fonction de ton cas d'utilisation, le surcoût lié au maintien de la cohérence entre les 2 structures de données sera contrebalancé par la rapidité du contains. 'fin bref à tester.

Attention cependant: comme tout ce qui est basé sur hashcode, si le contenu de l'objet peut changer après instantiation, alors tout s'effondre...

PS: j'espère que tu as des "synchronized" quelque part dans le code, parce que sinon les perfs ne seront vraiment pas ton plus gros problème...
21/10/2014, 18h33
thelvin

Ben l'idée d'un ConcurrentLinkedQueue c'est de pas avoir besoin de synchronized, sinon on utiliserait juste une LinkedList, logique.

Mais du coup pour tester si l'objet était pas déjà là, s'pas évident. Il y aurait moyen de faire ça en utilisant aussi une ConcurrentHashMap (dont on ne se sert que des clés, on associe chaque objet à lui-même,) l'idée étant d'ajouter l'UrlX à la map mais seulement si elle y est pas déjà, et si l'ajout a marché, l'ajouter aussi dans la queue.
En inverse, quand on enlève une UrlX de la queue, on l'enlève de la Map juste après.
21/10/2014, 19h39
Ceubex

Merci, j'utilise le ConcurrentHashMap avec l'url en clé en faisant des urlQueue.containsKey(urlString) dessus
ça marche très bien
21/10/2014, 19h53
thelvin

Bah non ça marche pas en concurrentiel -_-°.

Même si tu vérifies qu'à un moment m de ton exécution, l'url n'était pas dans la queue, ça veut pas dire pour autant qu'elle n'y est pas venue au moment m+1. Ça n'a aucun sens d'utiliser une ConcurrentHashMap si c'est juste pour appeler containsKey().
21/10/2014, 20h08
Ceubex

ben c pas juste pour ça
je fais aussi des put, des remove et des iterations sur cette liste.
containsKey je l'utilise pour voir si j'ai déjà l'objet UrlX
21/10/2014, 22h31
thelvin

Ya forcément une raison pour laquelle tu regardes si l'objet UrlX est dedans (cette raison c'est pour décider si oui ou non tu l'ajoutes)
Et donc pour cette raison c'est important que l'information "est-ce qu'il est dedans ou pas" soit toujours vraie au moment où tu réalises cette raison.

Si tu fais containsKey(), y a aucune raison que le résultat obtenu soit toujours vrai au moment où tu appliques ce pour quoi tu as vérifié. L'UrlX, qui était pas encore dedans, peut très bien être arrivée entre-temps.

containsKey() c'est pas intéressant dans une ConcurrentMap, il suffit d'une Map normale pour faire ça. Si tu prends la peine de faire une ConcurrentHashMap, c'est uniquement dans le but de ne pas utiliser containsKey() et similaire.
21/10/2014, 23h28
Ceubex

Non mais le soucis avec une map normal c'est que c'est pas fait pour de l'accès concurrent. Si je le lis en même temps que j'écris mon programme s'arrête. Donc je peux pas utiliser ça.
Je suis d'accord avec toi, il est possible dans de rare cas que l'insertion faite après le contains se fasse alors que ça existe mais si c'est le cas ça efface le précédent car la clé est la même (l'url)
Pour moi c'est un désagrément mineur pour plein d'avantages
21/10/2014, 23h48
tchize_
LA question,vu que ça écrase, c'est pourquoi tu t'emmerde alors à vérifier que c'est pas déjà présent.

En général, que l'on soit en synchronizée ou pas, faire ceci:
Code:

1 2 if (!map.containsKey(objet)) map.put(object,object)
ça n'a pas de sens ;)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
url="http://google.com";
object.url=url;
object.truc=50;
map.put(url,object)
 
 
.....
 
url="http://google.com";
object.url=url;
object.truc=160;
if (!map.containsKey(url)) map.put(url,object)

22/10/2014, 00h44
tchize_
N'oublie pas que tu es dans un contexte de concurrence, donc pour reprendre ton exemple:

put 50 puis put 160 est aussi probable que put 160 puis put 50, donc les deux opérations sont interchangeable, donc ça ne change rien à ton algorithme de ne pas faire le check. Et si vraiment c'est indispensable, alors fais le comme ça, c'est plus cohérent:
Code:

1 2 3 4 5 synchronized(map){ if (!map.containsKey(url)) map.put(url,object); }
22/10/2014, 09h33
Pill_S
Citation:

Envoyé par thelvin

Ben l'idée d'un ConcurrentLinkedQueue c'est de pas avoir besoin de synchronized, sinon on utiliserait juste une LinkedList, logique.
Citation:
Envoyé par tchize_

Code:

1 2 3 4 5 synchronized(map){ if (!map.containsKey(url)) map.put(url,object); }
C'est à ce genre de synchronized que je pensais (séquence de manipulations)...
22/10/2014, 09h57
thelvin

Oui n'importe qui penserait à ce genre de synchronisation. Mais dans ce cas, à quoi ça sert d'aller chercher les collections concurrentes ?

Si on veut profiter des optimisations concurrentes, c'est map.putIfAbsent(url, object); bien sûr -_-°.

Maintenant si finalement c'est pas utile de vérifier si la donnée était déjà là, ben ça ira encore plus vite de pas vérifier, c'est sûr.

Citation:

Envoyé par Ceubex

Non mais le soucis avec une map normal c'est que c'est pas fait pour de l'accès concurrent. Si je le lis en même temps que j'écris mon programme s'arrête. Donc je peux pas utiliser ça.
Je suis d'accord avec toi, il est possible dans de rare cas que l'insertion faite après le contains se fasse alors que ça existe mais si c'est le cas ça efface le précédent car la clé est la même (l'url)
Pour moi c'est un désagrément mineur pour plein d'avantages

Ok je vois ce que tu veux dire. Mais à partir du moment où tu as pris la peine de prendre une ConcurrentHashMap de toute façon, et qu'apparemment tu n'utilises plus que cette map toute seule et donc la manipulation des données est toute simple...
Ça rime à quoi de faire autre chose que ce qui était voulu ? Tu cherchais à ajouter l'élément s'il était pas déjà là, ben, fais ça, c'est quoi l'intérêt de faire autre chose ?