Perché la query PLINQ di ASOrder è più veloce della mia non ordinata

Question

Ho scritto un codice di esempio di base per familiarizzare con PLINQ.

Mi sono imbattuto in qualcosa di strano. Non so se si tratta di un errore nel mio codice o di un errore nella mia comprensione di PLINQ.

La documentazione MSDN afferma che l'aggiunta di AsOrdered() manterrà l'ordine della chiamata al costo possibile delle prestazioni.

Ho scritto alcuni test unitari e ho notato l'effetto sull'ordine sul set di risultati come indicato nella documentazione. Ma ho visto l'effetto inverso sulle prestazioni.

Ecco sia il mio metodo:

public IEnumerable<int> ParallelCalculatePrimesUpTo(int maxValue) 
{ 
    return from number in Enumerable.Range(1, maxValue).AsParallel() 
      where IsPrime(number) 
      select number; 
} 

public IEnumerable<int> OrderedParallelCalculatePrimesUpTo(int maxValue) 
{ 
    return from number in Enumerable.Range(1, maxValue).AsParallel().AsOrdered() 
      where IsPrime(number) 
      select number; 
} 

E i miei punti di riferimento molto semplici

[TestMethod] 
    public void SimplisticBenchmark6() 
    { 
     var primeNumberCalculator = new PrimeNumberCalculator(); 

     var startTime = DateTime.Now; 

     primeNumberCalculator.ParallelCalculatePrimesUpTo(10000000).ToList(); 

     var totalTime = DateTime.Now - startTime; 

     Console.WriteLine(totalTime); 
    } 

    [TestMethod] 
    public void SimplisticBenchmark7() 
    { 
     var primeNumberCalculator = new PrimeNumberCalculator(); 

     var startTime = DateTime.Now; 

     primeNumberCalculator.OrderedParallelCalculatePrimesUpTo(10000000).ToList(); 

     var totalTime = DateTime.Now - startTime; 

     Console.WriteLine(totalTime); 
    } 

Non importa quante volte ho eseguito questo test, la versione ordinata batte quella ordinata. Presto circa 4 secondi più veloce per quello ordinato sul mio computer quad core. Sto ottenendo circa 18 secondi per quello ordinato e 22 secondi per quello non ordinato. Ho eseguito i test decine di volte nel corso di due giorni (con riavvii tra quei giorni).

Se abbasso il numero da 10.000.000 a 6.000.000, le differenze sono ancora lì ma meno evidenti e se lo riduco a 3 000 000, è all'incirca la stessa velocità.

Ho provato a eseguire i test in entrambi gli ordini e i risultati sono gli stessi.

Ecco il metodo isPrime che viene chiamato nella query PLINQ:

// uses inneficient trial division algorithm 
private bool IsPrime(int number) 
{ 
    if (number == 1) 
     return false; 

    for (int divisor = 2; divisor <= Math.Sqrt(number); divisor++) 
    { 
     if (number % divisor == 0) 
      return false; 
    } 

    return true; 
} 

Cosa spiega questo?

Answer 1

Puoi dirci qual è l'utilizzo della CPU attraverso i 4 diversi core? È possibile che AsOrdered() imponga più chiamate sequenziali sullo stesso core. Con una localizzazione migliorata, la memorizzazione nella cache a livello di silicio e la previsione dei rami potrebbero funzionare a tuo favore.

Un'altra possibilità è l'ottimizzazione del framework .NET per il caso di numeri interi monotonamente incrementali (int.Range) quando si utilizza la proiezione AsOrdered(). Non sono sicuro di come funzionerebbe, ma è possibile.

Un test interessante per il confronto sarebbe quello di generare una terza serie di numeri, in ordine casuale (ovviamente, bisognerebbe randomizzarli prima del tempo e poi lavorare su tre array). Quindi vedi se questo ha qualcosa a che fare con questo?

Answer 2

Esegui sempre i test nello stesso ordine?

Ho ricreato i risultati sulla mia macchina e ho scoperto che, non importa, i risultati "ordinati" erano più veloci. Ho usato un codice leggermente modificato per il benchmarking:

static void Main(string[] args) 
{ 
    const int size = 9000000; 
    BenchIt("Parallel", ParallelCalculatePrimesUpTo, size); 
    BenchIt("Ordered ", OrderedParallelCalculatePrimesUpTo, size); 
    Console.ReadKey(); 
} 

public static void BenchIt(string desc, Func<int, IEnumerable<int>> myFunc, int size) 
{ 
    var sw = new Stopwatch();    
    sw.Restart(); 
    myFunc.Invoke(size).ToList(); 
    sw.Stop(); 
    Console.WriteLine("{0} {1}",desc, sw.Elapsed); 
} 

I miei risultati hanno mostrato, inizialmente, che avevi ragione. Il metodo ordinato era più veloce. Tuttavia, se avessi SWAPPED l'ordine delle chiamate, ho scoperto che il metodo non ordinato era più veloce. In altre parole, qualunque sia andato secondo era più veloce. Presumibilmente, a causa della gestione del pool di thread che sta facendo la libreria parallela attività.

Ma - le differenze tra i due sulla mia macchina erano molto piccole. Nulla vicino alla quantità di differenza che hai visto.

Come è il tuo hardware?

PLINQ fa qualche ipotesi su come eseguire il più veloce. Non so se questo ti aiuterà direttamente in questo caso; ma potresti voler impostare un punto di interruzione nel mezzo di IsPrime e fermarti dopo alcune centinaia di iterazioni ed esaminare la finestra del thread.

Quanti thread hai quando esegui ParallelCalculatedPrimesUpTo versetto OrderedParallelCalculatePrimesUpTo? Sto raggiungendo qui; ma è possibile che stia decidendo su diversi valori sulla tua macchina che crea i tempi inattesi che stai vedendo. Sulla mia macchina - ottengo otto thread, ogni volta - ma i miei tempi sono quasi identici - qualunque sia il primo nome è più lento a causa della creazione di quei thread. Ma non ti è garantito un numero particolare di thread (puoi impostare il massimo, ma non puoi forzarli a essere usati).