Quale euristica utilizza TPL per determinare quando utilizzare più core

Question

Sappiamo che TPL (quindi PLINQ) non consuma tutti i core se ritiene che l'attività sia semplice e la esegue su single core. Ma lo fa anche per un compito complicato! Per esempio, ecco il codice articolo su Java parallelismo:

import org.openjdk.jmh.infra.Blackhole; 
import org.openjdk.jmh.annotations.*; 
import java.util.concurrent.TimeUnit; 
import java.util.stream.IntStream; 
import java.math.BigInteger; 

@Warmup(iterations=5) 
@Measurement(iterations=10) 
@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.MICROSECONDS) 
@State(Scope.Benchmark) 
@Fork(2) 
public class Factorial { 
    private static final BigInteger ONE = BigInteger.valueOf(1); 

    @Param({"10", "100", "1000", "10000", "50000"}) 
    private int n; 

    public static BigInteger naive(int n) { 
     BigInteger r = ONE; 
     for (int i = 2; i <= n; ++i) 
      r = r.multiply(BigInteger.valueOf(i)); 
     return r; 
    } 

    public static BigInteger streamed(int n) { 
     if(n < 2) return ONE; 
     return IntStream.rangeClosed(2, n).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get(); 
    } 

    public static BigInteger streamedParallel(int n) { 
     if(n < 2) return ONE; 
     return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get(); 
    } 

    public static BigInteger fourBlocks(int n) { 
     if(n < 2) return ONE; 
     BigInteger r1 = ONE, r2 = ONE, r3 = ONE, r4 = ONE; 
     int i; 
     for (i = n; i > 4; i -= 4) 
     { 
      r1 = r1.multiply(BigInteger.valueOf(i)); 
      r2 = r2.multiply(BigInteger.valueOf(i - 1)); 
      r3 = r3.multiply(BigInteger.valueOf(i - 2)); 
      r4 = r4.multiply(BigInteger.valueOf(i - 3)); 
     } 
     int mult = i == 4 ? 24 : i == 3 ? 6 : i == 2 ? 2 : 1; 
     return r1.multiply(r2).multiply(r3.multiply(r4)).multiply(BigInteger.valueOf(mult)); 
    } 

    public static BigInteger streamedShift(int n) { 
     if(n < 2) return ONE; 
     int p = 0, c = 0; 
     while ((n >> p) > 1) { 
      p++; 
      c += n >> p; 
     } 
     return IntStream.rangeClosed(2, n).map(i -> i >> Integer.numberOfTrailingZeros(i)) 
       .mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get().shiftLeft(c); 
    } 

    public static BigInteger streamedParallelShift(int n) { 
     if(n < 2) return ONE; 
     int p = 0, c = 0; 
     while ((n >> p) > 1) { 
      p++; 
      c += n >> p; 
     } 
     return IntStream.rangeClosed(2, n).parallel().map(i -> i >> Integer.numberOfTrailingZeros(i)) 
       .mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get().shiftLeft(c); 
    } 

    @Benchmark  
    public void testNaive(Blackhole bh) { 
     bh.consume(naive(n)); 
    } 

    @Benchmark  
    public void testStreamed(Blackhole bh) { 
     bh.consume(streamed(n)); 
    } 

    @Benchmark  
    public void testStreamedParallel(Blackhole bh) { 
     bh.consume(streamedParallel(n)); 
    } 

    @Benchmark  
    public void testFourBlocks(Blackhole bh) { 
     bh.consume(fourBlocks(n)); 
    } 

    @Benchmark  
    public void testStreamedShift(Blackhole bh) { 
     bh.consume(streamedShift(n)); 
    } 

    @Benchmark  
    public void testStreamedParallelShift(Blackhole bh) { 
     bh.consume(streamedParallelShift(n)); 
    } 
} 

e risultati:

Benchmark        (n) Mode Cnt  Score  Error Units 
Factorial.testFourBlocks    10 avgt 20  0.409 ±  0.027 us/op 
Factorial.testFourBlocks    100 avgt 20  4.752 ±  0.147 us/op 
Factorial.testFourBlocks    1000 avgt 20  113.801 ±  7.159 us/op 
Factorial.testFourBlocks    10000 avgt 20 10626.187 ± 54.785 us/op 
Factorial.testFourBlocks    50000 avgt 20 281522.808 ± 13619.674 us/op 
Factorial.testNaive      10 avgt 20  0.297 ±  0.002 us/op 
Factorial.testNaive     100 avgt 20  5.060 ±  0.036 us/op 
Factorial.testNaive     1000 avgt 20  277.902 ±  1.311 us/op 
Factorial.testNaive     10000 avgt 20 32471.921 ± 1092.640 us/op 
Factorial.testNaive     50000 avgt 20 970355.227 ± 64386.653 us/op 
Factorial.testStreamed     10 avgt 20  0.326 ±  0.002 us/op 
Factorial.testStreamed     100 avgt 20  5.393 ±  0.190 us/op 
Factorial.testStreamed    1000 avgt 20  265.550 ±  1.772 us/op 
Factorial.testStreamed    10000 avgt 20 29871.366 ± 234.457 us/op 
Factorial.testStreamed    50000 avgt 20 894549.237 ± 5453.425 us/op 
Factorial.testStreamedParallel   10 avgt 20  6.114 ±  0.500 us/op 
Factorial.testStreamedParallel   100 avgt 20  10.719 ±  0.786 us/op 
Factorial.testStreamedParallel  1000 avgt 20  72.225 ±  0.509 us/op 
Factorial.testStreamedParallel  10000 avgt 20 2811.977 ± 14.599 us/op 
Factorial.testStreamedParallel  50000 avgt 20 49501.716 ± 729.646 us/op 
Factorial.testStreamedParallelShift  10 avgt 20  6.684 ±  0.549 us/op 
Factorial.testStreamedParallelShift 100 avgt 20  11.176 ±  0.779 us/op 
Factorial.testStreamedParallelShift 1000 avgt 20  71.056 ±  3.918 us/op 
Factorial.testStreamedParallelShift 10000 avgt 20 2641.108 ± 142.571 us/op 
Factorial.testStreamedParallelShift 50000 avgt 20 46480.544 ± 405.648 us/op 
Factorial.testStreamedShift    10 avgt 20  0.402 ±  0.006 us/op 
Factorial.testStreamedShift   100 avgt 20  5.086 ±  0.039 us/op 
Factorial.testStreamedShift   1000 avgt 20  237.279 ±  1.566 us/op 
Factorial.testStreamedShift   10000 avgt 20 27572.709 ± 135.489 us/op 
Factorial.testStreamedShift   50000 avgt 20 874699.213 ± 53645.087 us/o 

si può vedere che la versione multithreaded eseguito ~ 19 volte più veloce rispetto unico filo (Core i7-4702MQ utilizzato). Ma in C# versione

static BigInteger Streamed(int n) 
{ 
    return n < 2 ? 1 : Enumerable.Range(2, n - 1).Aggregate(BigInteger.One, (acc, elm) => acc*elm); 
} 

static BigInteger StreamedParallel(int n) 
{ 
    return n < 2 ? 1 : Enumerable.Range(2, n - 1).AsParallel().Aggregate(BigInteger.One, (acc, elm) => acc * elm); 
} 

questo codice è peggiore performance a confronto a tutti gli altri, che non è sorprendente, perché di TPL in testa senza il beneficio delle prestazioni da multithreading.

Quindi la domanda è: perché la libreria multithread standard Java è così saggia (any operation that takes 100us+ will be boosted, see referencehttp://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html), mentre C# non può incrementare un'operazione che richiede 1500 ms sulla mia macchina.

mi piace C# e non è davvero molto simile a Java, è per questo che fa male e voglio imparare perché è quello che è ...

Answer 1

Quando si utilizza il metodo Aggregate come questo, PLINQ eseguirà l'aggregazione sequenzialmente, e quindi su un singolo thread. Ovviamente, la moltiplicazione potrebbe essere eseguita in qualsiasi ordine, ma PLinq non ha modo di indovinarlo. Ad esempio, se l'operazione era una divisione, la modifica dell'ordine di esecuzione avrebbe modificato il risultato finale.

Un modo per dire PLINQ la query può essere parallelized, è quello di utilizzare un altro overload Aggregate, che indica come i risultati di più thread possono essere uniti:

return n < 2 ? 1 : Enumerable.Range(2, n - 1).AsParallel().Aggregate(BigInteger.One, (acc, elm) => acc * elm, (i, j) => i * j, i => i); 

Con questa versione, con n = 100000, è richiede circa 9000 ms per la versione sequenziale e 4400 ms per la versione parallela. Questo è praticamente il doppio più veloce, che è coerente con il mio hardware (processore dual core).

È possibile leggere questo articolo per ulteriori informazioni su come lavorare con aggregazioni PLINQ: http://blogs.msdn.com/b/pfxteam/archive/2008/01/22/7211660.aspx