Java 8 diffuse les performances série et parallèle

Question

Sur ma machine, le programme ci-dessous imprime :

OptionalLong[134043]
 PARALLEL took 127869 ms
OptionalLong[134043]
 SERIAL took 60594 ms

Je ne comprends pas pourquoi l’exécution du programme en série est plus rapide que son exécution en parallèle.J'ai donné les deux programmes -Xms2g -Xmx2g sur un 8gb boîte relativement silencieuse.Quelqu'un peut-il clarifier ce qui se passe ?

import java.util.stream.LongStream;
import java.util.stream.LongStream.Builder;

public class Problem47 {

    public static void main(String[] args) {

        final long startTime = System.currentTimeMillis();
        System.out.println(LongStream.iterate(1, n -> n + 1).parallel().limit(1000000).filter(n -> fourConsecutives(n)).findFirst());
        final long endTime = System.currentTimeMillis();
        System.out.println(" PARALLEL took " +(endTime - startTime) + " ms");

        final long startTime2 = System.currentTimeMillis();
        System.out.println(LongStream.iterate(1, n -> n + 1).limit(1000000).filter(n -> fourConsecutives(n)).findFirst());
        final long endTime2 = System.currentTimeMillis();
        System.out.println(" SERIAL took " +(endTime2 - startTime2) + " ms");
    }

    static boolean fourConsecutives(final long n) {
        return distinctPrimeFactors(n).count() == 4 &&
                distinctPrimeFactors(n + 1).count() == 4 &&
                distinctPrimeFactors(n + 2).count() == 4 &&
                distinctPrimeFactors(n + 3).count() == 4;
    }

    static LongStream distinctPrimeFactors(long number) {
        final Builder builder = LongStream.builder();
        final long limit = number / 2;
        long n = number;
        for (long i = 2; i <= limit; i++) {
            while (n % i == 0) {
                builder.accept(i);
                n /= i;
            }
        }
        return builder.build().distinct();
    }

}

Answer 1

Bien que Brian Goetz ait raison à propos de votre configuration, par ex.que tu devrais utiliser .range(1, 1000000) plutôt que .iterate(1, n -> n + 1).limit(1000000) et que votre méthode de benchmark est très simpliste, je tiens à souligner le point important :

même après avoir résolu ces problèmes, même en utilisant une horloge murale et le TaskManager, vous pouvez voir qu'il y a quelque chose qui ne va pas.Sur ma machine, l'opération prend environ une demi-minute et vous pouvez voir que le parallélisme tombe à un seul cœur après environ deux secondes.Même si un outil de référence spécialisé pouvait produire des résultats différents, cela n’aurait pas d’importance à moins que vous souhaitiez exécuter votre application finale au sein d’un outil de référence à tout moment…

Nous pourrions maintenant essayer de nous moquer davantage de votre configuration ou vous dire que vous devriez apprendre des choses spéciales sur le framework Fork/Join comme le les implémenteurs l'ont fait sur la liste de discussion.

Ou nous essayons une implémentation alternative :

ExecutorService es=Executors.newFixedThreadPool(
                       Runtime.getRuntime().availableProcessors());
AtomicLong found=new AtomicLong(Long.MAX_VALUE);
LongStream.range(1, 1000000).filter(n -> found.get()==Long.MAX_VALUE)
    .forEach(n -> es.submit(()->{
        if(found.get()>n && fourConsecutives(n)) for(;;) {
            long x=found.get();
            if(x<n || found.compareAndSet(x, n)) break;
        }
    }));
es.shutdown();
try { es.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS); }
catch (InterruptedException ex) {throw new AssertionError(ex); }
long result=found.get();
System.out.println(result==Long.MAX_VALUE? "not found": result);

Sur ma machine, il fait ce que j'attendrais d'une exécution parallèle en ne prenant qu'un peu plus de ⟨sequential time⟩/⟨number of cpu cores⟩.Sans rien changer à votre fourConsecutives mise en œuvre.

L'essentiel est que, au moins lorsque le traitement d'un seul élément prend beaucoup de temps, le Stream la mise en œuvre (ou le framework Fork/Join sous-jacent) a des problèmes car déjà discuté dans cette question connexe.Si vous souhaitez un parallélisme fiable, je vous recommande d'utiliser des logiciels éprouvés et testés. ExecutorServices.Comme vous pouvez le voir dans mon exemple, cela ne signifie pas abandonner les fonctionnalités de Java 8, elles s'intègrent bien.Seul le parallélisme automatisé introduit avec Stream.parallel doit être utilisé avec précaution (compte tenu de la mise en œuvre actuelle).

Answer 2

Nous pouvons faciliter l’exécution en parallèle, mais nous ne pouvons pas nécessairement faciliter le parallélisme.

Le coupable dans votre code est la combinaison limite+parallèle.L'implémentation de limit() est triviale pour les flux séquentiels, mais assez coûteuse pour les flux parallèles.En effet, la définition de l'opération limite est liée à l'ordre de rencontre du flux.Les flux avec limit() sont souvent plus lents en parallèle qu'en séquentiel, à moins que le calcul effectué par élément ne soit très élevé.

Votre choix de source de flux limite également le parallélisme.En utilisant iterate(0, n->n+1) vous donne les entiers positifs, mais iterate est fondamentalement séquentiel ;vous ne pouvez pas calculer le nième élément tant que vous n'avez pas calculé le (n-1)ième élément.Ainsi, lorsque nous essayons de diviser ce flux, nous finissons par le diviser (d'abord, reste).Essayez d'utiliser range(0,k) plutôt;cela se divise beaucoup plus joliment, en se divisant proprement en deux avec un accès aléatoire.