CPU Pipeline

Na początek kod:


   [TestClass]
   public class CPU_Pipelining_tests
   {
      const int DATALENGTH = 1024 * 1024 * 50;
      const int REPEATS = 3;

      Random random = new Random();

      [TestMethod]
      public void Check_sum_calculation_timings()
      {
         byte[] data = getRandomData();

         sumCalculationTimingRepeats(data, REPEATS);

         sortData(data);

         sumCalculationTimingRepeats(data, REPEATS);
      }

      private void sumCalculationTimingRepeats(byte[] data, int repeats)
      {
         for (int i = 0; i < repeats; i++)
            sumCalculationTiminig(data);
      }

      private UInt64 calculateSum(byte[] data)
      {
         UInt64 result = 0;

         foreach (byte dataItem in data)
         {
            if (dataItem >= 128)
               result += dataItem;
         }

         return result;
      }

      private byte[] getRandomData()
      {
         byte[] data = new byte[DATALENGTH];

         random.NextBytes(data);

         return data;
      }

      private void sortData(byte[] data)
      {
         Console.WriteLine("Sortuję dane");

         Array.Sort(data);
      }

      void sumCalculationTiminig(byte[] data)
      {
         Stopwatch stopwatch = new Stopwatch();

         stopwatch.Start();

         calculateSum(data);

         stopwatch.Stop();

         Console.WriteLine(
             "Elapsed: {0} ms", stopwatch.ElapsedMilliseconds);
      }
   }

Co robi test Check_sum_calculation_timings?

Alokuje sobie 50Mb pamięci, wypełnia ją losowymi danymi. I oblicza sumę wszystkich elementów większych równych 128. Czas jaki zajęła funkcja sumowania jest wypisywany do konsoli.

Ponieważ wywołanie tej samej funkcji z tymi samymi parametrami może trwać dłużej albo krócej. Sumowanie wywoływane jest trze razy.

Po czym obszar pamięci który wcześniej wypełniłem losowymi wartościami zostaje posortowany.

I ponownie trzy razy wywołuję funkcję sumującą.

Oto wynik:

Test Outcome:	Passed
Test Duration:	0:00:09,9473528

Result StandardOutput:	
Elapsed: 685 ms
Elapsed: 699 ms
Elapsed: 687 ms
Sortuję dane
Elapsed: 355 ms
Elapsed: 357 ms
Elapsed: 352 ms

Niespodzianka.
Obliczanie sumy danych posortowanych trwa prawie dwa razy krócej niż danych losowych.

Dlaczego?

Pies pogrzebany leży tutaj:

if (dataItem >= 128)
  result += dataItem;

Co ten kawałek robi? Jeśli wartość z bufora jest większa lub równa 128, to wtedy jest dodawana do zmiennej przechowującej sumę.
Zmienię ten kawałek na coś co robi to samo, ale bez instrukcji warunkowej, np na coś takiego:

int sub = (dataItem & 128) >> 7;
int mask = 0 - sub;
result += (UInt64)(mask & dataItem);

oto wynik:

Test Duration:	0:00:09,6991485

Result StandardOutput:	
Elapsed: 486 ms
Elapsed: 477 ms
Elapsed: 496 ms
Sortuję dane
Elapsed: 465 ms
Elapsed: 480 ms
Elapsed: 470 ms

Czasy są mniej więcej takie same.

Dlaczego tak się dzieje?
Otóż współczesne procesory to diabelnie skomplikowane urządzenia. Jedną z ich funkcji jest pipelining – równoległe wykonywanie pewnych bloków kodu. Problemem jednak są instrukcje skoku (jeśli podejrzymy kod maszynowy jaki wygenerował się po kompilacji naszego IFa, zobaczymy porównanie, i skok – w zależności jaki był wynik porównania). Robione jest ZAŁOŻENIE – procesor na podstawie pewnego algorytmu szacuje, czy ten skok się odbędzie, czy nie. Jeśli założenie okaże się prawdziwe – program nadal się wykonuje. Jeśli nie – cofane są wszelkie założone zmiany i blok wykonuje się ponownie, co jest oczywiście czasochłonne.

Wracając do naszego programu. Losowe dane powodują, że nijak nie można oszacować czy skok się odbędzie, czy nie. Mniej więcej połowa założeń okazuje się słuszna, druga połowa kończy się rollbackiem i ponownym wykonaniem bloku kodu.

Co innego w przypadku posortowanych danych. Wynik IFa, i skok staje się przewidywalny.

Jakie ma to zastosowanie praktycznie? Wg mnie niewielkie. Po prostu ciekawa ciekawostka.

Aplikacja raczej nie pracują na danych losowych. A podczas „zwykłej” prazy na danych które nie są losowe, oszacowanie czy jump się odbędzie, czy nie, sprawdza się w ok 90%.

Wg mnie czytelność programu jest ważniejsza niż pojedyncze procenty wydajności, jakie zyskamy na takiej optymalizacji. Instrkucja IF jest jasna na pierwszy rzut oka, czego niestety nie można powiedzieć o bez-ifowym bitowo-przesuwanym potworku jakim ją zastąpiłem.

Dyskuja na Stackoverflow:
http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: