Co heurystycznie używa TPL, aby określić, kiedy używać wielu rdzeni?

Question

Wiemy, że TPL (więc PLINQ) nie pobiera wszystkich rdzeni, jeśli uważa, że ​​zadanie jest łatwe i wykonuje je na pojedynczym rdzeniu. Ale robi to nawet dla skomplikowanego zadania! Na przykład, oto kod z artykułu o równoległości Java:

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)); 
    } 
} 

i wyniki:

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 

widać, że wielowątkowe wersja wykonana ~ 19 razy szybciej niż pojedynczej nici (Core i7-4702MQ używane). Ale w C# w wersji

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); 
} 

kod ten jest najgorszy wydajność w porównaniu do wszystkich innych, co nie jest zaskakujące, ponieważ OC napowietrznych bez korzyści wydajności z wielowątkowości.

Pytanie brzmi: dlaczego standardowa biblioteka Java z wielowątymi bibliotekami jest tak mądra (any operation that takes 100us+ will be boosted, see referencehttp://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html), podczas gdy C# nie może zwiększyć operacji, która zajmuje 1500 ms na moim komputerze.

Lubię C# i nie naprawdę bardzo jak Java, to dlatego, że boli i chcę, aby dowiedzieć się, dlaczego jest to co to jest ...

Answer 1

Przy wykorzystaniu metody takiego Aggregate, PLinq wykona agregację sekwencyjnie, a więc w jednym wątku. Oczywiście mnożenie może być wykonane w dowolnej kolejności, ale PLinq nie może tego odgadnąć. Jeśli operacja była na przykład podziałem, zmiana kolejności realizacji zmieni wynik końcowy.

Jednym ze sposobów, aby powiedzieć PLinq kwerendy można parallelized, jest użycie innego Agregat przeciążenie, która wskazuje, jak wynika z wielu wątków mogą być łączone:

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

W tej wersji, z n = 100.000, to trwa około 9000 ms dla wersji sekwencyjnej i 4400 ms dla wersji równoległej. To prawie dwa razy szybciej, co jest zgodne z moim sprzętem (dwurdzeniowy procesor).

Możesz przeczytać ten artykuł Więcej informacji na temat pracy z PLinq agregacje: http://blogs.msdn.com/b/pfxteam/archive/2008/01/22/7211660.aspx