Równolegle.Nie w stosunku do zwykłych wątków

Question

Próbuję zrozumieć, dlaczego Parallel.For jest w stanie przewyższyć liczbę wątków w następującym scenariuszu: rozważ partię zadań, które mogą być przetwarzane równolegle. Podczas przetwarzania tych zadań można dodawać nowe prace, które również muszą zostać przetworzone. Rozwiązanie Parallel.For będzie wyglądać następująco:

var jobs = new List<Job> { firstJob }; 
int startIdx = 0, endIdx = jobs.Count; 
while (startIdx < endIdx) { 
    Parallel.For(startIdx, endIdx, i => WorkJob(jobs[i])); 
    startIdx = endIdx; endIdx = jobs.Count; 
} 

Oznacza to, że istnieje wiele razy, gdzie Parallel.For musi zsynchronizować. Rozważ algorytm algorytmu wykresu chleba pierwszy; liczba synchronizacji byłaby dość duża. Strata czasu, nie?

Trying to samo w podejściu staromodnym gwintowania:

var queue = new ConcurrentQueue<Job> { firstJob }; 
var threads = new List<Thread>(); 
var waitHandle = new AutoResetEvent(false); 
int numBusy = 0; 
for (int i = 0; i < maxThreads; i++) 
    threads.Add(new Thread(new ThreadStart(delegate { 
    while (!queue.IsEmpty || numBusy > 0) { 
     if (queue.IsEmpty) 
     // numbusy > 0 implies more data may arrive 
     waitHandle.WaitOne(); 

     Job job; 
     if (queue.TryDequeue(out job)) { 
     Interlocked.Increment(ref numBusy); 
     WorkJob(job); // WorkJob does a waitHandle.Set() when more work was found 
     Interlocked.Decrement(ref numBusy); 
     } 
    } 
    // others are possibly waiting for us to enable more work which won't happen 
    waitHandle.Set(); 
}))); 
threads.ForEach(t => t.Start()); 
threads.ForEach(t => t.Join()); 

Kod Parallel.For jest oczywiście znacznie czystsze, ale czego nie mogę pojąć, to jeszcze szybciej, jak dobrze! Czy harmonogram zadań jest tak dobry? Synchronizacja została wyeliminowana, nie ma zajętego czekania, ale podejście gwintowane jest konsekwentnie wolniejsze (dla mnie). Co się dzieje? Czy podejście gwintowania może być szybsze?

Edycja: dzięki za wszystkie odpowiedzi, chciałbym móc wybrać wiele. Wybrałem ten, który pokazuje rzeczywistą możliwą poprawę.

Answer 1

Dwie próbki kodu nie są takie same.

Urządzenie Parallel.ForEach() będzie używać ograniczonej liczby wątków i będzie je ponownie wykorzystywać. Druga próbka zaczyna już od początku, tworząc kilka wątków. To wymaga czasu.

Jaka jest wartość maxThreads? Bardzo krytyczny, w Parallel.ForEach() jest dynamiczny.

Czy harmonogram zadań jest tak dobry?

Jest całkiem niezła. TPL wykorzystuje kradzież do pracy i inne technologie adaptacyjne. Będzie ci ciężko zrobić coś lepszego.

Answer 2

Tworzysz kilka nowych wątków i Parallel.Dla używa Threadpool. Będziesz widział lepszą wydajność, jeśli korzystasz z wątku C#, ale naprawdę nie ma sensu tego robić.

Nie zawaham się przed wprowadzeniem własnego rozwiązania; jeśli istnieje przypadek rogu, w którym potrzebujesz dostosowania, użyj licencji TPL i dostosuj ..

Answer 3

Równoległy. Nie rozbija elementów na pojedyncze jednostki pracy. Rozkłada całą pracę (na początku) na podstawie liczby wątków, które zamierza wykorzystać i liczby iteracji, które mają zostać wykonane. Następnie każdy wątek synchronicznie przetwarza tę partię (prawdopodobnie za pomocą kradzieży pracy lub zapisywania dodatkowych elementów do bilansu obciążenia pod koniec). Dzięki temu podejściu wątki robocze praktycznie nigdy nie czekają na siebie nawzajem, podczas gdy twoje wątki ciągle czekają na siebie ze względu na ciężką synchronizację, którą używasz przed/po każdej iteracji.

Ponadto, ponieważ używa wątków puli wątków, wiele wątków, których potrzebuje, jest prawdopodobnie już stworzonych, co jest kolejną zaletą na jego korzyść.

Jeśli chodzi o synchronizację, cały punkt równoległy.Dla tego, że wszystkie iteracje mogą być wykonywane równolegle, więc prawie nie ma synchronizacji, która musi się odbyć (przynajmniej w ich kodzie).

To oczywiście kwestia liczby wątków. W wątku znajduje się wiele bardzo dobrych algorytmów i heurystyk, które pomagają określić, ile wątków potrzebuje w tym momencie w czasie, w oparciu o aktualny sprzęt, obciążenie z innych aplikacji itp. Możliwe, że używasz też wiele lub mało wątków.

Ponadto, ponieważ liczba posiadanych przedmiotów nie jest znana przed uruchomieniem, sugerowałbym użycie Parallel.ForEach zamiast kilku pętli Parallel.For. Jest po prostu zaprojektowany dla sytuacji, w której się znajdujesz, więc jej heurystyka będzie działać lepiej. (To także sprawia, że ​​kod jest jeszcze bardziej czysty.)

BlockingCollection<Job> queue = new BlockingCollection<Job>(); 

//add jobs to queue, possibly in another thread 
//call queue.CompleteAdding() when there are no more jobs to run 

Parallel.ForEach(queue.GetConsumingEnumerable(), 
    job => job.DoWork());