Dlaczego moje zapytanie Aslinowane PLINQ jest szybsze niż moje nieuporządkowane?

Question

Napisałem kilka podstawowych przykładów kodu, aby zapoznać się z PLINQ.

Natrafiłem na coś dziwnego. Nie wiem, czy to błąd w moim kodzie, czy błąd w zrozumieniu PLINQ.

Dokumentacja MSDN stwierdza, że ​​dodanie AsOrdered() zachowa kolejność połączeń pod możliwymi kosztami wydajności.

Napisałem kilka testów jednostkowych i zauważyłem wpływ na zamówienie na zestaw wyników, jak podano w dokumentacji. Ale widziałem odwrotny wpływ na wydajność.

Oto zarówno moja metoda:

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

A moje bardzo proste benchmarki

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

Bez względu na to, jak często mogę uruchomić ten test, wersja nakazał bije się z nieuporządkowaną jeden. Dostaję około 4 sekundy szybciej dla zamówionego na moim czterordzeniowym komputerze. Dostaję około 18 sekund na zamówioną jedną i 22 sekundy na nieuporządkowaną. Przeprowadziłem testy dziesiątki razy w ciągu dwóch dni (z restartami między tymi dniami).

Jeśli obniżę liczbę od 10 000 000 do 6 000 000, różnice nadal występują, ale są mniej zauważalne, a jeśli obniżę je do 3 000 000, to będą mniej więcej takie same.

Próbowałem uruchomić testy w obu kolejności wykonania, a wyniki są takie same.

Oto metoda IsPrime że jest wywoływana w zapytaniu 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; 
} 

Co wyjaśnia to?

Answer 1

Czy możesz nam powiedzieć, jakie jest wykorzystanie procesora w 4 różnych rdzeniach? Możliwe, że AsOrdered() wymusza kolejne sekwencyjne wywołania na tym samym rdzeniu. Dzięki poprawionej lokalizacji buforowanie na poziomie krzemu i przewidywanie rozgałęzień może działać na Twoją korzyść.

Inną możliwością jest, że istnieje pewna optymalizacja w środowisku .NET dla przypadku monotonicznie rosnących liczb całkowitych (int.Range) podczas korzystania z projekcji AsOrdered(). Nie jestem pewien, jak to będzie działać, ale jest to możliwe.

Interesującym testem dla porównania byłoby wygenerowanie trzeciego zestawu liczb, w losowej kolejności (oczywiście, trzeba by je z góry dobrać losowo, a następnie wykonać trzy tablice). Więc sprawdź, czy to ma coś z tym wspólnego?

Answer 2

Czy zawsze przeprowadzasz testy w tym samym zamówieniu?

Odtworzyłem twoje wyniki na moim komputerze i odkryłem, że bez względu na to, wyniki "Zamówione" były szybsze. Użyłem nieznacznie zmodyfikowanego kodu do testu porównawczego:

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

Moje wyniki wskazują, że początkowo byłeś poprawny. Zamówiona metoda była szybsza. Jednakże, jeśli I SWAPPED kolejność połączeń, okazało się, że metoda niezłożona była szybsza. Innymi słowy, to, co nastąpiło po drugim, było szybsze. Prawdopodobnie z powodu zarządzania pulą wątków wykonywaną przez zadanie Parallel Library.

Ale - różnice między tymi dwoma na mojej maszynie były bardzo małe. Nigdzie prawie nie widać różnicy różnicy.

Jaki jest twój sprzęt?

PLINQ zgaduje, jak wykonać najszybszy. Nie wiem, czy w tym przypadku będzie to bezpośrednio pomocne; ale możesz chcieć ustawić punkt przerwania w środku IsPrime i zatrzymać się na nim po kilkuset iteracjach i zbadać okno wątku.

Ile wątków masz przy wykonywaniu ParallelCalculatedPrimesUpTo werset OrderedParallelCalculatePrimesUpTo? Sięgam tutaj; ale możliwe jest, że decyduje on o różnych wartościach na komputerze, co tworzy nieoczekiwane czasy, które widzisz. Na moim komputerze - za każdym razem otrzymuję osiem wątków - ale moje czasy są PRAWDOPODOBIE identyczne - to, co się nazywa, jest wolniejsze z powodu tworzenia tych wątków. Ale nie masz gwarancji określonej liczby wątków (możesz ustawić maksimum, ale nie możesz ich zmusić do użycia).