2016-03-21 12 views
5

Stavo passando per i concetti di ordinamento parallelo introdotti in Java 8. Come da doc.Perché la granularità minima è definita come 8192 in Java8 per passare da Parallel Sort a Arrays.sort indipendentemente dal tipo di dati

Se la lunghezza della matrice specificato è inferiore al minimo granularità, allora è ordinato con il metodo Arrays.sort appropriato.

La specifica tuttavia non specifica questo limite minimo.
Quando ho guardato il codice in java.util.Arrays è stata definita come

private static final int MIN_ARRAY_SORT_GRAN = 1 << 13; 

cioè valori nella matrice

Secondo la spiegazione fornita here. Capisco perché il valore era hardcoded come 8192.

È stato progettato tenendo presente l'architettura della CPU corrente.
Con l'opzione -XX:+UseCompressedOops attivata per impostazione predefinita, qualsiasi sistema con meno di 32 GB di RAM utilizza puntatori a 32 bit (4 byte). Ora, con una dimensione L1 Cache di 32 KB per la porzione di dati, possiamo passare a 32 KB/4 byte = 8 KB di dati alla volta per la CPU per il calcolo. Questo è equivalente a 8192 byte di dati elaborati contemporaneamente.

Quindi per una funzione che sta lavorando sull'ordinamento di un array di byte parallelSort(byte[]) questo ha senso. È possibile mantenere il limite di ordinamento parallelo minimo come 8192 valori (ogni valore = 1 byte per l'array di byte).

ma se si considera public static void parallelSort(int[] a)

un numero intero variabile è di 4Byte (32-bit). Quindi idealmente degli 8192 byte, possiamo memorizzare 8192/4 = 2048 numeri nella cache della CPU in una sola volta. Così la granularità minima in questo caso è supponiamo di essere 2048.

Perché sono tutte le funzioni parallelSort in Java (che si tratti di byte [], int [], lungo [], ecc) utilizzando 8192 come predefinito min. numero di valori necessari per eseguire l'ordinamento parallelo?
Non dovrebbe variare in base ai tipi passati alla funzione parallelSort?

risposta

5

In primo luogo, sembra che tu abbia interpretato erroneamente la spiegazione collegata. La cache di dati L1 è 32Kb, quindi per int[] si adatta idealmente: 32768/4=8192 gli intep possono essere inseriti nella cache L1 mentre.

In secondo luogo, non penso che la spiegazione data sia corretta. Si concentra sui puntatori, quindi dice principalmente sull'ordinamento dell'array di oggetti, ma quando si confrontano i dati nell'array di oggetti, è sempre necessario dereferenziare questi puntatori che accedono ai dati reali. E nel caso che i tuoi oggetti abbiano campi non primitivi, dovrai dereferenziarli ulteriormente. Ad esempio, se si ordina una matrice di stringhe, è necessario accedere non solo alla matrice stessa, ma anche agli oggetti String e agli array char[] che sono memorizzati al loro interno. Tutto ciò richiederebbe molte linee di cache aggiuntive.

Non ho trovato alcuna spiegazione esplicita su questo particolare valore in review thread per questa modifica. Precedentemente era 256, quindi è stato modificato in 8192 come parte dell'aggiornamento JDK-8014076. Penso che abbia mostrato le migliori prestazioni su una ragionevole suite di test. Mantenere soglie separate per casi diversi aggiungerebbe più complessità. Probabilmente i test dimostrano che non sta pagando. Si noti che la soglia ideale è impossibile per gli array Object[] poiché la funzione di confronto è specificata dall'utente e potrebbe avere una complessità arbitraria. Per una funzione di confronto sufficientemente complessa è probabilmente ragionevole parallelizzare anche array molto piccoli.