Która funkcja jest szybsza?

Artykuł ten ma za zadanie zebrać w jednym miejscu informacje o tym które rozwiązanie np. użyta funkcja czy procedura, pętle, tricki programistyczne jest szybsze. Czasami mamy do wyboru dwa lub trzy rozwiązania jakiegoś problemu, a na pierwszy rzut oka nie widać co jest szybsze i chciałoby się dowiedzieć z czego skorzystać jeżeli zależy nam na szybkości, bo np. dana pętla wykonywana jest 100 tyś. razy.

Każdy test proponuje wykonać 10 razy. Zanotować wynik najlepszy, najgorszy, a także obliczyć średnią arytmetyczną (suma wszystkich wyników div 10).
Testy takie należy wykonać na nieobciążonym komputerze, więc trzeba wyłączyć programy obciążające procesor maszyny. Jeśli tego nie zrobimy musimy się liczyć z tym że wyniki będą miały zawyżone czasy wykonania lub niektóre wyniki będą znacząco odbiegały od pozostałych. Zalecam też robić testy przy włączonej optymalizacji kodu i wyłączonych wszystkich informacjach dla debuggera (Menu Project->Option, zakładka Compiler, pole Debugging). Testy należy robić uruchamiając plik wykonywalny (nie F9).

Zachęcam do nanoszenia poprawek, swoich uwag, a także swoich wyników testów na własnym sprzęcie.
Może ktoś zaproponuje lepszy sposób testowania, wtedy mam nadzieje zaktualizujemy swoje wyniki.
Jeśli ktoś ma jakieś uwagi niech zaproponuje swoje rozwiązanie i krótko uzasadni.
Niemniej jednak jeśli zajmujesz się "filozofią programowania" (każdy polak na wszystkim się zna (sic!)) i zamierzasz się tylko rozwodzić nad każdym aspektem sprawy to napisz książkę i ją opublikuj.

Do testów będziemy potrzebować dwóch funkcji TimeStart i TimeEnd klasy TTimeCount. Pierwsza zaczyna odliczanie, a druga kończy i zwraca wynik w milisekundach.

type
  TTimeCount = class(TObject)
  private
    Freq, Start, Koniec : Int64;
  public
    function TimeStart: Boolean; virtual;
    function TimeEnd: DWord; virtual;
end;

implementation

function TTimeCount.TimeEnd: DWord;
begin
  QueryPerformanceCounter(Koniec);
  Result:= Round(((Koniec - Start) / Freq) * 1000);
end;

function TTimeCount.TimeStart: Boolean;
begin
  Result:= QueryPerformanceFrequency(Freq); //czy zegar jest dostępny na sprzęcie
  if Result then
    QueryPerformanceCounter(Start);
end;

MulDiv vs MyMulDiv vs (A * B) div C

Szybkie MulDiv

Na początek na celownik weźmiemy sobie funkcję MulDiv.
Jest to prosta funkcja zwracająca typ całkowitoliczbowy, wykonująca proste działanie typu (A * B) Div C.
Jak się zaraz okaże MulDiv wcale nie jest szybkie.

Procedura testująca #1

procedure TForm1.Button1Click(Sender: TObject);
var
  i, z, a, b, c: Cardinal;
  Czas: TTimeCount;
  g: Cardinal;
  Tab: array[0..9] of Cardinal;
  Best, Worst, Medium: Cardinal;
begin
  Memo.Clear;
  Czas:= TTimeCount.Create;
  z:= 100000000;
  Randomize;
  g:= 0; i:= 0;
  Best:= 100000; Worst:= 0; Medium:= 0;
  Application.ProcessMessages;
  repeat
    a:= Random(High(SmallInt));
    b:= RandomRange(1, High(Cardinal) div 1000);
    Czas.TimeStart;
    for c:= 1 to z do
    begin
       // tu będą testowane metody
    end;
    Tab[g]:= Czas.TimeEnd;
    Memo.Lines.Add('Wynik i: ' + IntToStr(i) + #9 +  ' Czas wykonania testu nr. ' + IntToStr(g + 1) + ': ' + IntToStr(Tab[g]) + ' ms');
    Inc(g);
    Application.ProcessMessages;
  until g = 10;
  FreeAndNil(Czas);
  //podliczamy wyniki
  for i:= 0 to High(Tab) do
  begin
    Medium:= Medium + Tab[i];
    if Tab[i] > Worst then
      Worst:= Tab[i];
    if Tab[i] < Best then
      Best:= Tab[i];
  end;
  Medium:= Medium div Length(Tab);
  Memo.Lines.Add('--- WYNIKI ---');
  Memo.Lines.Add('Najlepszy: ' + IntToStr(Best) + ' ms');
  Memo.Lines.Add('Najgorszy: ' + IntToStr(Worst) + ' ms');
  Memo.Lines.Add('Średni: ' + IntToStr(Medium) + ' ms');
end;

Metody które będziemy testować wyglądają tak:

1. i:= MulDiv(a, b, c)
2. i:= MyMulDiv(a, b, c)
   przy czym funkcja MyMulDiv wygląda tak:

function MyMulDiv(const A, B, C: Cardinal): Cardinal;
begin
  Result:= (A * B) div C;
end;

1. i:= a * b div c
2. Zaproponuj coś lepszego!

Wyniki dla wszystkich metod, przedstawiają się następująco:

Lp.	Autor	Metoda	Procesor	Częstotliwość procesora (GHz)	System operacyjny	Wersja Delphi	Wynik najlepszy	Wynik najgorszy	Średnia
1.	mgyver	I	Intel Core Solo	1,6	Windows XP SP3	7	1513	2325	2013
2.	mgyver	II	Intel Core Solo	1,6	Windows XP SP3	7	881	971	893
3.	mgyver	III	Intel Core Solo	1,6	Windows XP SP3	7	846	967	860

Jak widać ta procedura z metodą pierwszą wykonuje się średnio 2 sekundy na procesorze Intel Core Solo. Zaskakujący może się wydać fakt że zazwyczaj pierwszy wynik jest najgorszy. Można to wytłumaczyć lepszym wykorzystaniem cache procesora przy kolejnych obliczeniach. Funkcja ta zwraca dość różne czasy wykonania w przedziale od 1,5 sekundy do 2,3 sekundy, co ją deprymuje z obliczeń w których potrzeba niskich i w miarę stałych czasów wykonania.

W metodzie drugiej widać o wiele lepsze czasy - wszystkie poniżej 1 sekundy. I znów wynik najgorszy ustanowiony został w teście pierwszym co może potwierdzać że chodzi o cache procesora.

Za to w metodzie trzeciej mamy najlepsze czasy i ta prosta metoda jest preferowana jeśli zależy nam na szybkości operacji z użyciem MulDiv. Metoda druga ustępuje niewiele metodzie trzeciej, a być może można to wytłumaczyć tym że procek musi skakać do funkcji co też zabiera paręnaście taktów zegara procesora.

Procedura testująca #2

Ta procedura testująca opiera się na wykorzystaniu instrukcji procesora RDTSC (Read Time Stamp Counter). Instrukcja to powinna być dostępna praktycznie dla każdego procesora generacji .586 lub wyżej. Zaletą tej metody jest to że funkcja zwraca wynik w postaci wykonanych taktów zegara procesora.

Na początek potrzebujemy funkcje która będzie korzystała z instrukcji RDTSC.

function RDTSC: Int64;
  const
    D32 = $66;
  var
    TimeStamp: record
      case Byte of
        1: (Whole: Int64);
        2: (Lo, Hi: LongInt);
      end;
  begin
    asm
      rdtsc
    {$ifdef Cpu386}
      mov [TimeStamp.Lo], eax
      mov [TimeStamp.Hi], edx
    {$else}
      db D32
      mov word ptr TimeStamp.Lo, AX
      mov [TimeStamp.Hi], eax
      db D32
      mov word ptr TimeStamp.Hi, DX
      mov [TimeStamp.Hi], edx
    {$endif}
    end;
    Result := TimeStamp.Whole;
  end;

Po więcej informacji odsyłam do FAQ -Jak zmierzyć czas wykonywania operacji .

Procedura testująca #2 wygląda tak:

procedure TForm1.Button2Click(Sender: TObject);
const
  n = $FFFFFFF; //Liczba powtórzeń. Im większa tym lepsze porównanie
var
  c: Cardinal;
  czas1, czas2: Int64;
  i, z, a, b: Cardinal;
  Czas: TTimeCount;
  g: Cardinal;
  Tab: array[0..9] of Single;
  Best, Worst, Medium: Single;
begin
  Memo.Clear;
  z:= 100000000;
  Randomize;          
  g:= 0; i:= 0;
  Best:= 100000; Worst:= 0; Medium:= 0;
  repeat
    a:= Random(High(SmallInt));
    b:= RandomRange(1, High(Cardinal) div 1000);
    Application.ProcessMessages;
    czas1 := RDTSC;
    for c:= 1 to n do
    begin
       //tu będą testowane metody
    end;
    czas2:= RDTSC;
    czas2 := czas2 - czas1;
    Tab[g]:= czas2/n;
    Memo.Lines.Add('Wynik i: ' + IntToStr(i));
    Memo.Lines.Add(FormatFloat('Średnia liczba cykli potrzebnych na wykonanie operacji 0.00', (Tab[g])));
    Inc(g);
  until g = 10;
    //podliczamy wyniki
  for i:= 0 to High(Tab) do
  begin
    Medium:= Medium + Tab[i];
    if Tab[i] > Worst then
      Worst:= Tab[i];
    if Tab[i] < Best then
      Best:= Tab[i];
  end;
  Medium:= Medium / Length(Tab);
  Memo.Lines.Add('--- WYNIKI ---');
  Memo.Lines.Add(FormatFloat('Najlepszy: 0.00 cykli/operację', Best));
  Memo.Lines.Add(FormatFloat('Najgorszy: 0.00 cykli/operację', Worst));
  Memo.Lines.Add(FormatFloat('Średnio: 0.00 cykli/operację', Medium));
end;

Wyniki testów dla procedury testowej #2 wyglądają następująco:

Lp.	Autor	Metoda	Procesor	Częstotliwość procesora (GHz)	System operacyjny	Wersja Delphi	Wynik najlepszy	Wynik najgorszy	Średnia
1.	mgyver	I	Intel Core Solo	1,6	Windows XP SP3	7	24,49	37,36	33,17
2.	mgyver	II	Intel Core Solo	1,6	Windows XP SP3	7	14,76	15,53	14,87
3.	mgyver	III	Intel Core Solo	1,6	Windows XP SP3	7	13,73	14,29	13,82
*Wszystkie wyniki w cyklach/operację

Co z tego wynika? Takie same wnioski jak w poprzedniej procedurze testowej. Jak widać funkcja systemowa MulDiv potrzebuje dwukrotnie więcej cykli zegara procesora niż pozostałe funkcje.

Załącznik wraz z kodem źródłowym: MulDiv.zip

Co dalej?

Zaproponuj własne testy do jakiejś innej funkcji, opisz co i jak, przedstaw procedurę lub funkcję która będzie realizować testy, załóż tabelkę do porównań wyników i napisz co z tego wynika. Dodaj także załącznik aby inni mogli szybko i sprawnie przetestować twój wynalazek.
Nie zapomnij także uzupełnić znaczników meta, oraz o tym aby nazwy używane w artykule kojarzyły się z tym co prawdopodobnie chciałbyś aby wujek Google i ciocia Bing zindeksowały. Dlatego ja w artykule użyłem słowa szybkie MulDiv, co powinno sprawić że po jakimś czasie wyszukiwarki będą zwracały stronę jako wynik poszukiwań.
I przecież o to chodzi!