Последовательная реализация Java в 4 раза быстрее, чем параллельная реализация

Question

Я создал очень простой сценарий, где я узнал действительно странное поведение, которое я не могу понять.

По следующей ссылке я создал последовательную реализацию: http://ideone.com/B8JYeA В принципе существует несколько больших массивов с фиксированным размером. Алгоритм выполняет итерацию через них и изменяет значение.

for(int i = 0; i < numberOfCells; i++) { 
    h0[i] = h0[i] + 1; 
    h1[i] = h1[i] + 1; 
    h2[i] = h2[i] + 1; 
    h3[i] = h3[i] + 1; 
    h4[i] = h4[i] + 1; 
} 

Если я запускаю его на своей рабочей станции, это занимает около 5 секунд.

Я реализовал то же самое в параллельной версии. И 8 потоков запускают его одновременно. Код должен быть потокобезопасным, и между потоками нет зависимости.

Но все же код работает около 4 раза медленнее, на моей рабочей станции: http://ideone.com/yfwVmr

final int numberOfThreads = Runtime.getRuntime().availableProcessors(); 

ExecutorService exec = Executors.newFixedThreadPool(numberOfThreads); 

for(int thread = 0; thread < numberOfThreads; thread++) { 
    final int threadId = thread; 
    exec.submit(new Runnable() { 
     @Override 
     public void run() { 
      for(int i = threadId; i < numberOfCells; i += numberOfThreads) { 
       h0[i] = h0[i] + 1; 
       h1[i] = h1[i] + 1; 
       h2[i] = h2[i] + 1; 
       h3[i] = h3[i] + 1; 
       h4[i] = h4[i] + 1; 
      } 
     } 
    }); 
} 

exec.shutdown(); 

Кто-нибудь есть идея, почему это происходит?

Редактировать: Эта проблема отличается от других, потому что причина, по-видимому, является проблемой кэширования. Как я могу решить эту проблему кэширования?

Answer 1

Самые большие накладные расходы - это время, затрачиваемое на запуск и остановку потоков. Если я уменьшу размер массива до 10 с 10000, потребуется примерно столько же времени.

Если вы сохраняете пул потоков и разделяете работу для каждого потока для записи в локальный набор данных, это на 4 раза быстрее на моей машине с 6 ядрами.

import java.util.ArrayList; 
import java.util.List; 
import java.util.concurrent.*; 


public class ParallelImplementationOptimised { 
    static final int numberOfThreads = Runtime.getRuntime().availableProcessors(); 
    final ExecutorService exec = Executors.newFixedThreadPool(numberOfThreads); 

    private int numberOfCells; 

    public ParallelImplementationOptimised(int numberOfCells) { 
     this.numberOfCells = numberOfCells; 
    } 

    public void update() throws ExecutionException, InterruptedException { 

     List<Future<?>> futures = new ArrayList<>(); 
     for(int thread = 0; thread < numberOfThreads; thread++) { 
      final int threadId = thread; 
      futures.add(exec.submit(new Runnable() { 
       @Override 
       public void run() { 
        int num = numberOfCells/numberOfThreads; 
        double[] h0 = new double[num], 
          h1 = new double[num], 
          h2 = new double[num], 
          h3 = new double[num], 
          h4 = new double[num], 
          h5 = new double[num], 
          h6 = new double[num], 
          h7 = new double[num], 
          h8 = new double[num], 
          h9 = new double[num]; 
        for (int i = 0; i < num; i++) { 
         h0[i] = h0[i] + 1; 
         h1[i] = h1[i] + 1; 
         h2[i] = h2[i] + 1; 
         h3[i] = h3[i] + 1; 
         h4[i] = h4[i] + 1; 
         h5[i] = h5[i] + 1; 
         h6[i] = h6[i] + 1; 
         h7[i] = h7[i] + 1; 
         h8[i] = h8[i] + 1; 
         h9[i] = h9[i] + 1; 
        } 
       } 
      })); 
     } 
     for (Future<?> future : futures) { 
      future.get(); 
     } 
    } 

    public static void main(String[] args) throws ExecutionException, InterruptedException { 

     ParallelImplementationOptimised si = new ParallelImplementationOptimised(10); 

     long start = System.currentTimeMillis(); 

     for (int i = 0; i < 10000; i++) { 
      if(i % 1000 == 0) { 
       System.out.println(i); 
      } 
      si.update(); 
     } 

     long stop = System.currentTimeMillis(); 
     System.out.println("Time: " + (stop - start)); 
     si.exec.shutdown(); 
    } 

} 

SequentialImplementation 3.3 sec. ParallelImplementationOptimised 0,8 сек.

---

Вы, кажется, записываете одни и те же данные в одну и ту же строку кеша. Это означает, что данные должны проходить через пропуски кеша L3, которая занимает 20 раз дольше, чем доступ к кэшу L1. Я предлагаю вам попробовать полностью отдельные структуры данных, размер которых не менее 128 байт, чтобы быть уверенным, что вы не касаетесь одной и той же строки кэша.

Примечание: даже если вы намереваетесь переписать всю строку кэша, процессоры x64 сначала будут извлекать предыдущие значения строки кэша.

Другой вопрос может быть

Почему не это 20x медленнее?

Ядро процессора, который захватил строку кэша может иметь две темы работы с Hyper-Threading (т.е. два потока могут получить доступ к данным на местном уровне), и что процессор может идти вокруг петли несколько раз, прежде чем она теряет кэш линии к другому ядру ЦП, который требует этого. Это означает, что штраф в 20 раз не на каждом доступе или на каждом цикле, но достаточно часто, чтобы получить более медленный результат.

Answer 2

Не совсем ответ, но: во-первых, я бы попытаться сохранить локальность доступа к данным, где это возможно:

final int numberOfCellsPerThread = numberOfCells/numberOfThreads; 

public void run() { 
    final int start = threadId * numberOfCellsPerThread; 
    final int end = start + numberOfCellsPerThread; 
    for(int i = start; i < end; i++) { 
     h0[i] = h0[i] + 1; 
     h1[i] = h1[i] + 1; 
     h2[i] = h2[i] + 1; 
     h3[i] = h3[i] + 1; 
     h4[i] = h4[i] + 1; 
    } 
} 

Для более подробного объяснения о том, почему вопросы местонахождение смотрите, например Why does cache locality matter for array performance? или http://en.wikipedia.org/wiki/Locality_of_reference.

В основном это касается использования данных, которые уже находятся в кеше, где это возможно. Поскольку кеш ограничен по размеру, если a[i] уже находится в кеше, например. из-за предыдущей операции чтения вероятность того, что a[i+1] также находится в кеше, довольно высока. По крайней мере, выше, чем у a[i+100].

Кроме того, последовательные считывания из памяти могут быть оптимизированы в пакетами аппаратными средствами и проще всего предсказать путем предварительной выборки логики.