Forum Programmation.c Comment effectuer une tache le plus rapidement possible ? threads / fork() ... ?

Posté par  .
Étiquettes :
0
9
sept.
2012

Bonjour,
en fait j'ai pri un petit exemple : *calculer la somme des nombres premiers en dessous de 2 millions.*

Et J'aimerais effectuer cette tâche le plus rapidement possible, quelque soit les ressources ou la mémoire consommée.
(Enfait, j'ai un même code, et ce que je veux c'est le paralléliser).

Les Threads :

J'ai fait un test dans un langage appelé Scala (proche du java), où j'utilise des threads.
Cependant le résultat n'est pas très concluant : le mieux que j'arrive à faire c'est de passer de 1.1sec à 0.7.
Pour cela : je fais un (ou plus) thread pour la somme des nombres de 1 à 1m puis un autre pour ceux de 1'000'001 à 2m (par exemple).

Les Processus (fork) :

Un ami m'a orienté vers l'utilisation de fork, en me disant qu'avec les threads, la capacité du processus principale est répartie entre les threads d'où la faible optimisation optenue.
Sur google j'ai lu que les threads pouvait ne pas forcément être un bonne idée car il y a copie de tout le contexte d'execution qui prend du temps.

Clone ?

Une variante de fork ?

Autre ?

Dans ce cas, ne peut on pas dire au système que notre processus peut utiliser toutes les ressources et utiliser les threads ? (Solution sans doute un peu naïve et fantasque ?)

Est-ce vrai ? Qu'en est-il et comment faire au mieux ?
Merci.

  • # algorithme

    Posté par  . Évalué à 2. Dernière modification le 09 septembre 2012 à 12:12.

    Des threads me semblent plus appropriés que des processus pour ce genre ce calcul.

    Cela dit, je vois a priori 3 choses qui peuvent faire vraiment faire augmenter la capacité de calcul :
    - créer autant de threads que ton CPU sait en gérer nativement.
    - améliorer l'algorithme de calcul.
    - tourner en 64 bits.

  • # Plutôt les threads...

    Posté par  . Évalué à 1.

    Je ne suis pas convaincu par la version de ton ami. Un fork est une opération relativement coûteuse, et le nombre de ressources que tu pourras utiliser dans les deux cas dépend du scheduler. La communication entre les processus a également un coût non négligeable.

    L'intérêt d'avoir un programme fonctionnant dans plusieurs processus est principalement de le répartir sur plusieurs machines (avec MPI par exemple).

    Dans ton cas, c'est excessif. Je pense qu'une implémentation threadée est le mieux, reste à voir comment tu divises le travail.

    Finalement, une optimisation relativement efficace est d'utiliser les instructions SSE/AVX. À voir selon ton algo précis.

  • # Mauvais exemple...

    Posté par  . Évalué à 2.

    Les threads seront moins coûteux. Sur un système Linux threads et processus sont tous deux des tâches, mais les threads ont beaucoup plus en commun (notamment l'espace d'addressage).

    Pour ton exercise, ni threads ni processus ! Une implémentation naïve, sans aucun parrallélisme prend 3 ms sur mon ordinateur portable.

    • [^] # Re: Mauvais exemple...

      Posté par  . Évalué à 3.

      Sur un système Linux threads et processus sont tous deux des tâches, mais les threads ont beaucoup plus en commun (notamment l'espace d'addressage).

      Il faut voir la JVM utilisé, il me semble que certaines implémentation n'utilise pas les threads Linux, du coup, une application avec plusieurs threads dans la JVM n'aura qu'une seule tâche dans le noyau et la perte en changement de contexte sera grande pour un avantage nul.

      « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

      • [^] # Re: Mauvais exemple...

        Posté par  . Évalué à 2.

        Toutes les JVM dont j'ai jamais entendu parler (et j'aime le sujet) utilisent des threads sous Linux depuis de nombreuses années.

      • [^] # Re: Mauvais exemple...

        Posté par  (Mastodon) . Évalué à 2.

        Il faut voir la JVM utilisé, il me semble que certaines implémentation n'utilise pas les threads Linux,

        Ce dont tu parles, ça s'appelle les Green threads, et ça n'est plus utilisé depuis Java 1.2.

        • [^] # Re: Mauvais exemple...

          Posté par  . Évalué à 4.

          Ah merci. Effectivement mes infos dataient un tout petit peu. Suite au commentaire de Pierre, j'ai cherché un peu pour voir mais je n'avais rien trouvé.

          « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

    • [^] # Re: Mauvais exemple...

      Posté par  . Évalué à 1.

      Bon, l'implémentation native prend en fait toujours moins de 2 millisecondes maintenant que je ne fais plus le boulet (code corrigé et compilation avec -O3 ; lien mis à jour).

      Vu que tu sembles axé JVM, j'ai fait une version en Java pour comparer l'effort.

      L'avantage est qu'elle gère des nombres considérablement plus grands (utilisation d'un BitSet et de BigInteger). Après, évidemment, on perd en perf…

      % java -cp target/classes PrimeSum 2000000 
max:2000000, count:148933, sum:142913828922, time:0.043000

% java -cp target/classes PrimeSum 100000000
max:100000000, count:5761455, sum:279209790387276, time:1.965000

      Je suppose qu'on a trouvé mieux que le crible d'Ératosthène en 22 siècles, mais c'était un exercise rigolo.

    • [^] # Re: Mauvais exemple...

      Posté par  . Évalué à 2.

      il y'aurait moyen d'optimiser ;)
      tous les nombres premiers sont impairs sauf deux
      (bon aussi tous les nombre premier sont impairs sauf un)

      tu peux donc allègrement utiliser des i+=2 bon faut pas se planter et bien commencer sur des impaires et pas rater le début, mais c'est une optimisation qui n'est pas négligeable.

      Il ne faut pas décorner les boeufs avant d'avoir semé le vent

      • [^] # Re: Mauvais exemple...

        Posté par  (site web personnel) . Évalué à 1.

        On peut aussi sauter les multiples de 5. Ça donne, à partir de n = 5 : n+2 (7), n+2 (9), n+2 (11), n+2 (13), n+4 (17).
        Et il suffit de s'arrêter à sqrt(n_max).

        • [^] # Re: Mauvais exemple...

          Posté par  . Évalué à 1.

          Oui, je m'arrête déjà à sqrt(n). Le reste des optimisations complique pas mal le code.

          • [^] # Re: Mauvais exemple...

            Posté par  . Évalué à 1.

            "les multiples de deux ne sont pas premiers"
            "les multiples de cinq ne sont pas premiers"
            "les multiples de trois ne sont pas premiers"
            …

            Ça revient à utiliser le crible d’Ératosthène pour optimiser le crible d’Ératosthène. Autant écrire tout les premiers en dur dans le code.

            Please do not feed the trolls

  • # Merci beaucoup !

    Posté par  . Évalué à 1.

    Hum, ok, merci beaucoup pour vos indications sur les threads et les processus.

    Et merci aussi à Pierre pour son code !
    Je vais ré-écrire mon code scala en C et voir ce que ça donne.
    Ensuite j'essaierais avec un nombre plus grand et je testerais les threads.

    Merci ;D !

    • [^] # Re: Merci beaucoup !

      Posté par  (site web personnel) . Évalué à 2.

      Sachant que tu veux calculer la somme, tu veux faire suffisamment de calculs dans un seul thread, sinon, après chaque nouveau nombre confirmé premier, tu vas vouloir faire un accès concurrent en lecture/écriture sur une variable partagée (ta somme), et donc perdre plein de temps.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.