Pętla wykonywana równolegle–część III

W ostatnich wpisach, pokazałem dwa różne podejścia wykonywania pętli równolegle. Każda z nich wciąż ma wady, głównie związane z sytuacją gdzie część logiki blokuje wątki.

W tym poście, pokażę bardziej dynamiczne podejście. Żaden z wątków nie będzie miał z góry przydzielonych elementów na których musi pracować. Zacznijmy po prostu od kodu:

private static void For(Action<int> iteration, int startIndex, int endIndex, int threadsNumber)
{
  const int chunkSize = 4;
  int current = startIndex;
  var countdownEvent = new CountdownEvent(threadsNumber);

  for (int i = 0; i < threadsNumber; i++)
  {
      Task.Factory.StartNew(delegate(object threadIndexState)
      {
          int j;
          while ((j = (Interlocked.Add(ref current, chunkSize) - chunkSize)) < endIndex)
          {
              for (int k = 0; k < chunkSize && j + k < endIndex; k++)
              {
                  iteration(j + k);
              }
          }
          countdownEvent.Signal();
      }, i);
  }
  countdownEvent.Wait();
}

Wciąż mamy zmienną chunkSize, ponieważ optymalniej jest operować na porcjach danych.

W pętli while, zwiększamy indeks current. Każdy wątek, który chce coś wykonać, zwiększa current, tak że kolejny będzie wykonywał już inną porcję danych – nie ma potrzeby synchronizowania porcji, która jest przetwarzana. Raz zaalokowana porcja danych do danego wątku, nie może potem zostać wykonana przez inny wątek.

Warto zauważyć, że im mniejsze porcje danych, tym więcej należy wywołać Interlocked na zmiennej current, co jest sekcją krytyczną i spowalnia aplikację.  Liczba wątków użytych w algorytmie nie jest już tak kluczowym elementem, ponieważ kod jest skalowalny.

Powyższe rozwiązanie nadaje się do użycia wyłącznie w scenariuszu, gdzie z góry znamy rozmiar tablicy. Co jeśli do czynienia mamy np.  z IEnumerable? Nie mamy tam do dyspozycji dostępu przez indeks. Nie da się uzyskać takiej samej wydajności jak w przypadku tablic. Jednym z prostszych rozwiązań jest buforowanie elementów. Czyli jak wątek T1 chce wykonać jakiś kod, to najpierw czyta tą porcję danych z Enumerable i przechowuję ją potem w zwykłej tablicy. Oczywiście wiąże się to z dodatkową sekcją krytyczną oraz blokadą.