Wiele wątków Java daje bardzo mały przyrost wydajności

Question

Chciałem nauczyć się programowania równoległego do przyspieszania algorytmów i wybrałem Javę.
Napisałem dwie funkcje do sumowania liczb całkowitych long w tablicy - jedna prosta iteracja poprzez tablicę, druga - dzielenie tablicy na części i sumowanie części w oddzielnych wątkach.

Spodziewałem się, że będzie to logiczne z grubsza 2x przyspieszenie za pomocą dwóch wątków. Jednak to, co mam, przyspiesza o 24%. Co więcej, używając więcej wątków, nie otrzymuję żadnej poprawy (może mniej niż 1%) przez dwa wątki. Wiem, że powinno być tworzenie/łączenie wątków, ale myślę, że to nie powinno być tak duże.

Czy możesz wyjaśnić, czego mi brakuje lub gdzie jest błąd w kodzie? Oto Kod:

import java.util.concurrent.ThreadLocalRandom; 


public class ParallelTest { 


public static long sum1 (long[] num, int a, int b) { 
    long r = 0; 
    while (a < b) { 
     r += num[a]; 
     ++a; 
    } 
    return r; 
} 

public static class SumThread extends Thread { 
    private long num[]; 
    private long r; 
    private int a, b; 

    public SumThread (long[] num, int a, int b) { 
     super(); 
     this.num = num; 
     this.a = a; 
     this.b = b; 
    } 

    @Override 
    public void run() { 
     r = ParallelTest.sum1(num, a, b); 
    } 

    public long getSum() { 
     return r; 
    } 
} 


public static long sum2 (long[] num, int a, int b, int threadCnt) throws InterruptedException { 
    SumThread[] th = new SumThread[threadCnt]; 
    int i = 0, c = (b - a + threadCnt - 1)/threadCnt; 

    for (;;) { 
     int a2 = a + c; 
     if (a2 > b) { 
      a2 = b; 
     } 
     th[i] = new SumThread(num, a, a2); 
     th[i].start(); 
     if (a2 == b) { 
      break; 
     } 
     a = a2; 
     ++i; 
    } 

    for (i = 0; i < threadCnt; ++i) { 
     th[i].join(); 
    } 
    long r = 0; 
    for (i = 0; i < threadCnt; ++i) { 
     r += th[i].getSum(); 
    } 
    return r; 
} 

public static void main(String[] args) throws InterruptedException { 
    final int N = 230000000; 
    long[] num = new long[N]; 

    for (int i = 0; i < N; ++i) { 
     num[i] = ThreadLocalRandom.current().nextLong(1, 9999); 
    } 

    // System.out.println(Runtime.getRuntime().availableProcessors()); 

    long timestamp = System.nanoTime(); 
    System.out.println(sum1(num, 0, num.length)); 
    System.out.println(System.nanoTime() - timestamp); 

    for (int n = 2; n <= 4; ++n) { 
     timestamp = System.nanoTime(); 
     System.out.println(sum2(num, 0, num.length, n)); 
     System.out.println(System.nanoTime() - timestamp); 
    } 


} 
} 

Edycja: mieć i7 z 4 rdzeni (8) nici. wyjściowa podana za pomocą kodu:

1149914787860 
175689196 
1149914787860 
149224086 
1149914787860 
147709988 
1149914787860 
138243999 

Answer 1

Program jest prawdopodobnie głównym przepustowość pamięci ograniczona zaledwie dwóch wątków, jak to mała pętla, która pobiera dane prawie tak szybko jak baran może dostarczyć danych do procesora.

Answer 2

mogę myśleć o ilość powodów, dlaczego nie może uzyskać jak najwięcej przyspieszenie jak oczekujesz.

1. Koszty ogólne tworzenia wątków są znaczne. Wątek start() jest kosztowną operacją, która wymaga wielu układów w celu przydzielenia stosu wątku i jego "strefy czerwonej", a następnie utworzenia natywnego wątku.

2. Nici N nie zaczną się w tym samym czasie. Oznacza to, że czas zakończenia równoległej części obliczeń będzie w przybliżeniu końcem ostatniego wątku - czasu rozpoczęcia po raz pierwszy. To będzie dłuższe niż czas, w którym jeden wątek wykonuje swoją część pracy. (N-1 razy czas tworzenia nici ...)

3. N wątki (zasadniczo) wykonują skan szeregowy N rozłącznych sekcji tablicy. To wymaga dużej przepustowości pamięci, a sposób, w jaki skanujesz, oznacza, że ​​pamięci podręczne będą nieskuteczne. Dlatego istnieje duża szansa, że ​​wydajność jest ograniczona szybkością i przepustowością głównego sprzętu pamięci twojego systemu.