Параллельная сортировка медленнее, чем серийная сортировка

Question

Я читал о новых возможностях Java 8, и одним из них был новый метод Arrays.parallelSort(). Я сделал несколько тестов, сортируя массив двойников и один из строк, а для строк - параллельный сорт был намного медленнее.

Вот содержание метода испытаний для струнных:

final int size = 10000; 
    final String[] values1 = new String[size]; 
    final String[] values2 = new String[size]; 
    for (int i = 0; i < size; i++) { 
     values1[i] = Integer.toString(i); 
     values2[i] = values1[i]; 
    } 
    Collections.shuffle(Arrays.asList(values1)); 
    Collections.shuffle(Arrays.asList(values2)); 
    final Comparator<String> comparator = (o1, o2) -> o2.compareTo(o1); 

    long startTimeInNano = System.nanoTime(); 
    Arrays.sort(values1, comparator); 
    long endTimeInNano = System.nanoTime(); 
    System.out.println("Arrays.sort: totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000)); 

    //parallel sort with java 8 
    startTimeInNano = System.nanoTime(); 
    Arrays.parallelSort(values2,comparator); 
    endTimeInNano = System.nanoTime(); 
    System.out.println("Arrays.parallelSort: totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000)); 

Результат был:

Arrays.sort: totalTimeInMicro= 11993

Arrays.parallelSort: totalTimeInMicro= 89823

Я также попробовал этот код на другом компьютере а результат был таким же (25608 против 808660). Компьютер, на котором я запускаю тесты, имеет процессор i5-2500. У вас есть идея, почему я получаю такие результаты?

Answer 1

Этот тест почти ничего не говорит. Самые важные вещи для microbenchmark являются

• Дайте JIT возможность оптимизировать код, запустить тесты несколько раз
• Использование различных входных размеров
• Печать некоторые из результатов, чтобы предотвратить JIT от оптимизируя прочь весь называет

Есть еще несколько моментов, чтобы рассмотреть - на самом деле, многие больше очков. Для получения дополнительной информации обратитесь к How do I write a correct micro-benchmark in Java?.

Для действительно «глубокой» информации вы должны использовать такие инструменты, как Caliper или JMH. Но даже с небольшими усилиями можно создать микрообъект, который показывает приблизительную индикацию того, как будет производиться фактическая производительность. Так один из простейших форм microbenchmark может выглядеть следующим образом:

import java.util.Arrays; 
import java.util.Collections; 
import java.util.Comparator; 

public class ParallelSortSpeedTest 
{ 
    public static void main(String[] args) 
    { 
     for (int size=100000; size<=1000000; size+=100000) 
     { 
      final String[] values1 = new String[size]; 
      final String[] values2 = new String[size]; 
      for (int i = 0; i < size; i++) { 
       values1[i] = Integer.toString(i); 
       values2[i] = values1[i]; 
      } 
      Collections.shuffle(Arrays.asList(values1)); 
      Collections.shuffle(Arrays.asList(values2)); 
      final Comparator<String> comparator = (o1, o2) -> o2.compareTo(o1); 

      testSort(values1, comparator); 
      testParallelSort(values2, comparator); 
     } 
    } 

    private static void testSort(
     String array[], final Comparator<String> comparator) 
    { 
     long startTimeInNano = System.nanoTime(); 
     Arrays.sort(array, comparator); 
     long endTimeInNano = System.nanoTime(); 
     System.out.println("Arrays.sort  : totalTimeInMicro= " + 
      ((endTimeInNano - startTimeInNano)/1000)+", first "+array[0]); 
    } 

    private static void testParallelSort(
     String array[], final Comparator<String> comparator) 
    { 
     long startTimeInNano = System.nanoTime(); 
     Arrays.parallelSort(array, comparator); 
     long endTimeInNano = System.nanoTime(); 
     System.out.println("Arrays.parallelSort: totalTimeInMicro= " + 
      ((endTimeInNano - startTimeInNano)/1000)+", first "+array[0]); 
    } 

} 

Это разумный вариант, учитывая компромисс между усилиями получить тест JMH и работает, и надежность результаты. Этот тест будет печатать что-то вроде

... 
Arrays.sort  : totalTimeInMicro= 530669, first 999999 
Arrays.parallelSort: totalTimeInMicro= 158227, first 999999 

Показано, что параллельно рода должны быть быстрее, по крайней мере.