Ordinamento parallelo più lento di tipo seriale

Question

Stavo leggendo delle nuove funzionalità in Java 8 e uno di questi era il nuovo metodo Arrays.parallelSort(). Ho fatto alcuni test ordinando una serie di doppi e una di stringhe e per le stringhe il parallelSort era molto più lento.

Ecco il contenuto di un metodo di prova per archi:

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

Il risultato è stato:

Arrays.sort: totalTimeInMicro= 11993

Arrays.parallelSort: totalTimeInMicro= 89823

Ho provato anche questo codice su un altro computer e la il risultato è stato lo stesso (25608 vs 808660). Il computer su cui eseguo i test ha una CPU i5-2500. Hai idea del perché ottengo questo tipo di risultati?

Answer 1

Questo punto di riferimento non dice quasi nulla. Le cose più importanti per un microbenchmark sono

• Dare il JIT la possibilità di ottimizzare il codice eseguendo i test più volte
• Usa ingresso differente formati
• Stampa alcuni dei risultati, per evitare che il JIT da ottimizzando via l'intero chiama

ci sono alcuni altri punti da considerare - in realtà, molti più punti. Si consiglia di consultare How do I write a correct micro-benchmark in Java? per ulteriori informazioni.

Per informazioni veramente "profonde", è necessario utilizzare strumenti come Caliper o JMH. Ma anche con uno sforzo minimo, è possibile creare un microbenchmark che mostri un'indicazione approssimativa di come sarebbe la prestazione effettiva. Così uno dei semplici forme di un microbenchmark potrebbe essere la seguente:

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

} 

Questa è un'opzione possibile, considerando il trade-off tra lo sforzo di ottenere un punto di riferimento JMH installato e funzionante, e l'affidabilità dei i risultati. Questo test stamperà qualcosa come

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

che dimostrano che il parallelo sorta dovrebbe essere più veloce, almeno.