Parallélisme en python avec un dictionnaire

Le problème exposé dans ce sujet a été résolu.

Salut, voilà, j’ai un problème qui est très probablement assez simple en python, mais étant une quiche en programmation parallèle j’y ai passé déjà 2 jours de taff

En gros, je construis un dictionnaire qui me sert à représenter un plan 2D (je peux switcher éventuellement à un tableau 2 dimensions étant donné que j’utilise un dictionnaire juste pour pouvoir utiliser des tuples en indice pour stocker mes coordonnées (x,y))

Je passe plusieurs fois sur ce dictionnaire de 5000x5000 entrées (d’où le côté lent de l’exécution) pour faire différents traitements avec des données (en gros des simulations de physique en 2D, mais c’est juste à chaque fois des opérations super simples). j’ai décidé de paralléliser le tout avec le package multiprocessing natif de python en utilisant un ProcessPoolExecutor et en passant mon dictionnaire à mes processus qui s’exécutent en parallèle avec un dict de la classe Manager Sauf que je ne sais pas si ce sont les opérations de lecture, d’écriture ou les deux mais c’est terriblement long (plus même qu’avant parallélisation) et clairement pas viable J’suis sur que ça vient de ça parce que quand je fais les calculs mais que je n’utilise pas ce dictionnaire, juste un dictionnaire dans mon sous-processus (et donc que je n’ai pas accès dans mon main processus à ces résultats) mon programme s’exécute environ 4x plus vite que sans, mais dès que je réutilise le dict du Manager pour récupérer les résultats, on arrive quasiment à un programme 2x moins rapide, puis j’ai vu quelques personnes se plaindre de cette lenteur aussi ci et là

Du coup deux questions, déjà est-ce que si je passais aux listes de la classe Manager j’aurai des chances d’avoir un gain de performances ? (je vais aller vérifier ça de mon côté mais si quelqu’un le sait d’avance) et ensuite quels autres solutions j’aurais pour pouvoir garder cette structure de données qui est assez complexe (un couple (x,y) renvoie à un objet unique qui peut s’étendre ou non sur plusieurs coordonnées donc difficile de faire autrement qu’avec un dict ou une liste de ces objets
Je met pas d’extrait de code parce que je vois pas trop en quoi ça serait cohérent, grosso modo la 1ere partie ou je l’utilisais c’était pour initialiser mon dictionnaire, donc un double for et on fait un grid[y, x] = None, vraiment rien de complexe mais toutes les solutions que j’ai trouvé et qui semblaient donner quelque chose reposaient sur Manager

Merci d’avance!

+0 -0

Salut,

En effet, utiliser un dictionnaire comme ça entre plusieurs processus, ça demande de la synchronisation, donc ça peut ralentir considérablement l’exécution.

À quoi te sert un dictionnaire avec autant d’entrées et as-tu pensé à d’autres structures de données pour le remplacer ? (par exemple sharder la structure en plusieurs dictionnaires qui représenteraient des zones indépendantes)

Les processus ont-ils besoin d’y accéder en lecture ou uniquement en écriture ?

S’il ne s’agit que d’écriture, je pense que tu pourrais t’orienter vers une Queue. Ainsi les workers y écriraient simplement les changements qu’ils veulent effectuer, et un autre processus se chargerait d’agréger les données.

Salut,

Est-ce que tu pourrais nous donner un peu plus de contexte ? Si ça se trouve, en sachant ce que tu veux faire précisément, on pourrait bien mieux t’aider…

Par exemple, pour ma part, j’ai déjà dû faire des scripts de simulation physique en 2D, qui mettaient en jeu environ 100k particules (soit 10G interactions) et j’ai pu les paralléliser efficacement (avec multiprocessing également).

En tout cas, l’idée que tu évoques d’utiliser un tableau à 2 dimensions me semble meilleure que celle d’un dictionnaire (hors de tout contexte).

EDIT : j’avais pour cela utilisé Pool.starmap(), peut-être que ça conviendrait à ton usage ?

+1 -0

JE suis aussi d’avis qu’un tableau 2D sera mieux qu’un dictionnaire. Ou, encore mieux si tu peux, une simple liste.

Sauf s’il existe une structure conçue pour ça, et à ce que je sache il n’y en a pas de base en python, les tableaux 2D, qui ne sont autre que des listes de listes, sont en fait généralement assez peu efficaces en tant que tel. Mieux vaut une simple liste, d’autant plus que python est extrêmement efficace avec les listes.

Attention toutefois au fait qu’avec une liste, 5K x 5K donne 25M cases. Sachant qu’une référence à un objet python fait au moins 16 octets (si pas plus), ça signifie que tu occupes d’office 400 MO de mémoire. Ce n’est pas forcément très efficace, notamment si la majeure partie des cases sont vides.

En fait la structure que tu vas adopter dépend fortement des données manipulées, et particulièrement la fréquence et la répartition des cass vides.

Si plus de 50–60% des cases sont occupées, la simple liste sera presque à coup sûr le plus efficace. VAs-y sans hésiter, tant que tu as assez de mémoire pour tout stocker. Si tu n’arrives plus à tout stocker en mémoire, ça devient un autre problème bien plus compliqué, où rentre en jeu le disque dur.

A moins de 40–50%, il y a plusieurs structures intermédiaires que tu pourrais essayer:

  • Une liste selon le concept du tableau segmenté, en divisant la matrice en tranches horizontales ou verticales, p.ex. 250 x 5000 ou 5000 x 250.
  • Une liste découpant la matrice en sous-parties, p.ex. 100 x 100 ou 250 x 250
  • Le tableau 2D évoqué au début n’est en fait rien d’autre qu’un tableau segmenté de taille 5000 x 1. Si tu as régulièrement des lignes vides non consécutives, ça peut être intéressant malgré tout.

Avec ce genre de structure, tu gagnes en mémoire et donc éventuellement en vitesse à cause du cache, mais tu reperds en vitesse le coût d’une indirection supplémentaire.

Tout est une affaire de compromis, et le seul moyen de savoir ce qui va le mieux, c’est 1/connaître la nature typique des données, et 2/tester.

Ce qui est sûr, c’est que le dictionnaire est infiniment plus lent qu’une liste, une liste de listes, ou même avec une troisième dimension. Avec le dictionnaire, à chaque accès, tu construis un tuple, tu prends son hash, tu vas chercher la valeur, tu détruis le tuple. Ce n’est pas des opérations coûteuses, mais chaque temps mis bout à bout sur des grosses quantitées, ça finit par faire la différence.

+1 -0

Merci pour vos réponses !

En gros une case du dictionnaire contient simplement une référence à un objet qui représente une particule, ensuite je simule le déplacement d’un laser sur le plan pour simuler l’interaction entre les deux

du coup je fais un passage en écriture pour placer mes particules, et ensuite uniquement de la lecture, en découpant le passage du laser en ligne, puis en trouvant toutes les particules qui vont être touchées par le laser, et pour les Queue (on parle bien de celle fournies par multiprocessing?) elles étaient vraiment trop lentes pour ça

En effet j’étais vachement vague, en gros ce que je fais c’est ça:
La simulation calcule les coordonnées de chaque point par lequel passe le laser (en comptant la taille du spot du laser du coup)
Elle va chercher dans mon dictionnaire (ou autre du coup) les particules associées à ces points
Et finalement j’appelle une fonction sur cette particule pour calculer l’énergie qu’elle a reçue pour lui assigner un état

Du coup les calculs s’effectuent pas sur le tableau directement, c’est pour ça que j’ai pas trouvé comment utiliser map ou star_map dessus :/

Et pour répondre à Quentin, toutes les cases sont remplies par une référence, la seule optimisation à laquelle j’avais pensé c’était de générer et prendre en compte une particule uniquement si cette dernière est excitée par le laser, mais c’était une optimisation que je comptais faire à la fin, j’avais vraiment sous estimé le nombre de calculs / d’accès en lecture et écriture de structures de données qui allaient être faits c’est ma faute, mais j’vais essayer de suivre tes pistes

Donc j’vais commencer par suivre vos conseils et dégager ce dictionnaire, merci à vous

(Et oui clairement on aurait jamais du utiliser python mais on a plus le temps pour changer de techno la deadline étant dans un mois)

Et pour répondre à Quentin, toutes les cases sont remplies par une référence

Donc comme je disais, prends une simple liste, tant que tu peux l’avoir en entier en mémoire, c’est ce qui sera le plus rapide.

Pour gagner encore en vitesse, tu peux jouer sur la façon dont une coordonnée (x,y) correspond à une case i de la liste. Le truc le plus simple, c’est i = y*width + x, ça correspond à un tableau rempli ligne par ligne.

Mais suivant ta façon de lire et d’écrire, c’est peut-être mieux de faire colonne par colonne, ou en dalles carrées ou rectangulaires. L’idée est que les données que tu dois manipuler ensemble devraient aussi être proches en mémoire, pour aider le cache.

Si je comprends bien, tu aurais peut-être intérêt à organiser une répartition en dalles afin que le rayon laser traverse le moins de jointures possibles. Si les trajectoires sont aléatoires, donc, peut-être des dalles carrées comme compromis.

+1 -0

Il est complètement absurde d’utiliser des listes ou des dictionnaires en Python pour faire des tâches lourdes en calculs. Il faut utiliser des tableaux numpy. C’est la première chose à faire avant même de songer à paralléliser ou quoique ce soit d’autre. La structure de données n’est simplement pas la bonne.

Et même avant d’en arriver aux tableaux qui me semblent logique en soit, il est aussi important de profiler afin de vérifier quel est le goulot d’étranglement du programme exécuté.

Normalement si c’est bien fait, les fonctions sont suffisamment découpées pour qu’on puisse en distinguer les étapes problématiques. Sinon, avec une idée de la chose, on peut isoler cette idée dans une fonction afin de simuler et reproduire le problème.

Mais il est vrai qu’avant de se lancer dans son code, on réfléchi à la structure de données la plus adaptée…

Il est complètement absurde d’utiliser des listes ou des dictionnaires en Python pour faire des tâches lourdes en calculs. Il faut utiliser des tableaux numpy. C’est la première chose à faire avant même de songer à paralléliser ou quoique ce soit d’autre. La structure de données n’est simplement pas la bonne.

adri1

en effet, cependant on n’était pas sensés avoir autant de données c’est pour cela que pour des raisons pratique on avait décidé d’utiliser un dictionnaire pour pouvoir indicer avec des tuples

maintenant tout est avec numpy (j’étais d’ailleurs persuadé que numpy pouvait uniquement gérer les types de base je sais pas pourquoi) mais j’ai un autre problème qui va nécessiter son thread pour lui tout seul, merci pour vos conseils en tous cas!

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte