多線程只有.4秒快一點？

Question

所以我的編程類，我們必須做到以下幾點：

• 填充整數數組500萬個範圍的整數0-9。
• 然後找到每個數字（0-9）出現的次數並顯示。

我們必須測量計算單線程和多線程出現的時間。目前，我的單線程平均爲9.3ms，而在我的8核心cpu上爲8.9ms多線程和8線程，這是爲什麼呢？

當前爲多線程，我有一個數組填充數字，並計算每個線程的上下界來計算出現次數。這裏是我目前的嘗試：

public void createThreads(int divisionSize) throws InterruptedException { 

    threads = new Thread[threadCount]; 

    for(int i = 0; i < threads.length; i++) { 

     final int lower = (i*divisionSize); 
     final int upper = lower + divisionSize - 1; 

     threads[i] = new Thread(new Runnable() { 

      long start, end; 
      @Override 
      public void run() { 


       start = System.nanoTime(); 

       for(int i = lower; i <= upper; i++) { 
        occurences[numbers[i]]++; 
       } 

       end = System.nanoTime(); 

       milliseconds += (end-start)/1000000.0; 
      } 

     }); 

     threads[i].start(); 
     threads[i].join(); 
    } 

} 

任何人都可以說一些光？乾杯。

Answer 1

你基本上是在按順序完成所有的工作，因爲你創建的每個線程都立即join它。

將主構建循環外的threads[i].join()移動到它自己的循環中。當你在它的時候，你可能還應該啓動循環之外的所有線程，因爲在創建新線程時啓動它們並不是一個好主意，因爲創建線程需要時間。即使在這裏最快的解決方法是使用一個線程，但你可以清楚地看到，偶數線程做它更快，因爲我使用i5其中有2個內核，但通過超線程和4一樣

class ThreadTester { 

    private final int threadCount; 
    private final int numberCount; 
    int[] numbers = new int[5_000_000]; 
    AtomicIntegerArray occurences; 
    Thread[] threads; 
    AtomicLong milliseconds = new AtomicLong(); 

    public ThreadTester(int threadCount, int numberCount) { 
     this.threadCount = threadCount; 
     this.numberCount = numberCount; 
     occurences = new AtomicIntegerArray(numberCount); 
     threads = new Thread[threadCount]; 
     Random r = new Random(); 
     for (int i = 0; i < numbers.length; i++) { 
      numbers[i] = r.nextInt(numberCount); 
     } 
    } 

    public void createThreads() throws InterruptedException { 

     final int divisionSize = numbers.length/threadCount; 
     for (int i = 0; i < threads.length; i++) { 

      final int lower = (i * divisionSize); 
      final int upper = lower + divisionSize - 1; 

      threads[i] = new Thread(new Runnable() { 

       @Override 
       public void run() { 

        long start = System.nanoTime(); 

        for (int i = lower; i <= upper; i++) { 
         occurences.addAndGet(numbers[i], 1); 
        } 

        long end = System.nanoTime(); 

        milliseconds.addAndGet(end - start); 
       } 

      }); 

     } 

    } 

    private void startThreads() { 
     for (Thread thread : threads) { 
      thread.start(); 
     } 
    } 

    private void finishThreads() throws InterruptedException { 
     for (Thread thread : threads) { 
      thread.join(); 
     } 
    } 

    public long test() throws InterruptedException { 
     createThreads(); 
     startThreads(); 
     finishThreads(); 
     return milliseconds.get(); 
    } 
} 

public void test() throws InterruptedException { 
    for (int threads = 1; threads < 50; threads++) { 
     ThreadTester tester = new ThreadTester(threads, 10); 
     System.out.println("Threads=" + threads + " ns=" + tester.test()); 
    } 
} 

注意。

但有趣的是 - 如建議通過@biziclop - 通過occurrences通過給每個線程提供自己的`發生數組我們獲得了更多的預期結果刪除線程之間的所有爭：

Answer 2

連接方法允許一個線程等待另一個線程的完成，因此第二個線程只有在第一個線程完成後纔會啓動。

在您啓動所有主題後加入每個線程。

public void createThreads(int divisionSize) throws InterruptedException { 

     threads = new Thread[threadCount]; 

     for(int i = 0; i < threads.length; i++) { 

      final int lower = (i*divisionSize); 
      final int upper = lower + divisionSize - 1; 

      threads[i] = new Thread(new Runnable() { 

       long start, end; 
       @Override 
       public void run() { 


        start = System.nanoTime(); 

        for(int i = lower; i <= upper; i++) { 
         occurences[numbers[i]]++; 
        } 

        end = System.nanoTime(); 

        milliseconds += (end-start)/1000000.0; 
       } 

      }); 

      threads[i].start(); 

     } 

     for(int i = 0; i < threads.length; i++) { 
      threads[i].join(); 
     } 

    } 

也有似乎是在OCCURENCES在代碼中的競爭條件[編號[I] ++ 所以，最有可能，如果你更新的代碼，並使用多線程的輸出將是不正確的。你應該使用一個AtomicIntegerArray：https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicIntegerArray.html

Answer 3

其他答案都探討了你的代碼的直接問題，我會給你一個不同的角度：一個是關於多線程設計的一般。

並行計算加速計算的想法取決於假設您打破問題的小比特確實可以並行運行，彼此獨立。

乍一看，你的問題就是這樣，將輸入範圍分成8個相等部分，啓動8個線程，然後關閉它們。

有一個捕獲雖然：

occurences[numbers[i]]++; 

的occurences陣列是由所有線程共享的資源，因此必須控制訪問，以確保正確性：或者通過顯式同步（這是慢）或有點像AtomicIntegerArray。但是Atomic*類只有在訪問它們很少有爭議時才真的很快。而在你的情況下，訪問會受到很多爭議，因爲你的內部循環所做的大部分工作是增加出現次數。

那麼你能做什麼？

該問題部分地由以下事實occurences是這樣的小結構（只有10個元素的陣列，而不管輸入大小）引起的，線程將連續地嘗試更新相同的元件。但是你可以把它變成你的優勢：讓所有的線程保持他們自己的單獨計數，當他們完成時，把他們的結果加起來。這會在流程結束時增加一個小的，不斷的開銷，但會使計算真正並行。

Answer 4

使用ExecutorService與Callable和invoke all tasks然後您可以安全地聚合它們。還可以使用TimeUnit的經過時間的操作（睡眠，加盟，等待，皈依，...）

開始用他的輸入/輸出定義任務：

class Task implements Callable<Task> { 

    // input 
    int[] source; 
    int sliceStart; 
    int sliceEnd; 

    // output 
    int[] occurences = new int[10]; 
    String runner; 
    long elapsed = 0; 

    Task(int[] source, int sliceStart, int sliceEnd) { 
    this.source  = source; 
    this.sliceStart = sliceStart; 
    this.sliceEnd = sliceEnd; 
    } 

    @Override 
    public Task call() { 
    runner = Thread.currentThread().getName(); 
    long start = System.nanoTime(); 
    try { 
     compute(); 
    } finally { 
     elapsed = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - start); 
    } 
    return this; 
    } 

    void compute() { 
    for (int i = sliceStart; i < sliceEnd; i++) { 
     occurences[source[i]]++; 
    } 
    } 
} 

然後我們定義一些變量來管理參數：

// Parametters 
int size  = 5_000_000; 
int parallel = Runtime.getRuntime().availableProcessors(); 
int slices = parallel; 

然後生成隨機輸入：

// Generated source 
int[] source = new int[size]; 
ThreadLocalRandom random = ThreadLocalRandom.current(); 
for (int i = 0; i < source.length; i++) source[i] = random.nextInt(10); 

開始計時總計算和準備工作：

long start = System.nanoTime(); 
// Prepare tasks 
List<Task> tasks = new ArrayList<>(slices); 
int sliceSize = source.length/slices; 
for (int sliceStart = 0; sliceStart < source.length;) { 
    int sliceEnd = Math.min(sliceStart + sliceSize, source.length); 
    Task task = new Task(source, sliceStart, sliceEnd); 
    tasks.add(task); 
    sliceStart = sliceEnd; 
} 

執行線程上配置的所有任務（不要忘記關機了！）：

// Execute tasks 
ExecutorService executor = Executors.newFixedThreadPool(parallel); 
try { 
    executor.invokeAll(tasks); 
} finally { 
    executor.shutdown(); 
} 

然後任務已經完成，只是彙總數據：

// Collect data 
int[] occurences = new int[10]; 
for (Task task : tasks) { 
    for (int i = 0; i < occurences.length; i++) { 
    occurences[i] += task.occurences[i]; 
    } 
} 

終於可以輸出計算結果：

// Display result 
long elapsed = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - start); 
System.out.printf("Computation done in %tT.%<tL%n", calendar(elapsed)); 
System.out.printf("Results: %s%n", Arrays.toString(occurences)); 

您還可以輸出部分計算：

// Print debug output 
int idxSize = (String.valueOf(size).length() * 4)/3; 
String template = "Slice[%," + idxSize + "d-%," + idxSize + "d] computed in %tT.%<tL by %s: %s%n"; 
for (Task task : tasks) { 
    System.out.printf(template, task.sliceStart, task.sliceEnd, calendar(task.elapsed), task.runner, Arrays.toString(task.occurences)); 
} 

其中給我的工作站上：

Computation done in 00:00:00.024 
Results: [500159, 500875, 500617, 499785, 500017, 500777, 498394, 498614, 499498, 501264] 
Slice[  0-1 250 000] computed in 00:00:00.013 by pool-1-thread-1: [125339, 125580, 125338, 124888, 124751, 124608, 124463, 124351, 125023, 125659] 
Slice[1 250 000-2 500 000] computed in 00:00:00.014 by pool-1-thread-2: [124766, 125423, 125111, 124756, 125201, 125695, 124266, 124405, 125083, 125294] 
Slice[2 500 000-3 750 000] computed in 00:00:00.013 by pool-1-thread-3: [124903, 124756, 124934, 125640, 124954, 125452, 124556, 124816, 124737, 125252] 
Slice[3 750 000-5 000 000] computed in 00:00:00.014 by pool-1-thread-4: [125151, 125116, 125234, 124501, 125111, 125022, 125109, 125042, 124655, 125059] 

小竅門經過米利斯轉換成一個秒錶日曆：

static final TimeZone UTC= TimeZone.getTimeZone("UTC"); 
public static Calendar calendar(long millis) { 
    Calendar calendar = Calendar.getInstance(UTC); 
    calendar.setTimeInMillis(millis); 
    return calendar; 
}