Zabawa klockami - przyśpieszamy budowę wieży Hanoi

Wieża  Hanoi jest  algorytmem bardzo krótkim i zwięzłym o wykładniczo rosnącej złożoności, wraz z liczbą krążków.

Implementacja w języku PL/SQL jest bardzo prosta..

CREATE OR REPLACE PROCEDURE Pdb_HanoiTower

( vn_Level NUMBER, vn_From NUMBER, vn_To NUMBER,

vn_Helper NUMBER) IS

 BEGIN

  IF vn_Level > 0 THEN

   Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);

    Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);

  END IF;

  END;

Do  testowania wydajności procedury wykorzystajmy poniższy blok:

DECLARE

 vn_Start NUMBER;

BEGIN

 vn_Start := dbms_utility.get_time;

 PdB_HanoiTower(25,1,3,2);

 DBMS_OUTPUT.PUT_LINE( round( (dbms_utility.get_time- vn_start)/100, 2 ) || ' seconds...' );

END;

Blok wykonał się w 16,38 s (średnia z kilku pomiarów).

Spróbujmy przyśpieszyć… Zauważmy, że do przekazywania parametrów wykorzystywany jest typ number, który zapewnia bardzo duży zmiennoprzecinkowy zakres liczbowy, a w naszym przypadku wystarczy zakres  typu SIMPLE_INTEGER – jest to odpowiednik czterobajtowego typu signed  int  z języka C bez sprawdzenia przepełniania  ( dla zwiększenia wydajności).. Unikniemy także niepotrzebnych konwersji między typami numerycznymi zmiennopozycyjnymi i całkowitymi..

CREATE OR REPLACE PROCEDURE Pdb_HanoiTower

( vn_Level SIMPLE_INTEGER, vn_From SIMPLE_INTEGER, vn_To SIMPLE_INTEGER,

vn_Helper SIMPLE_INTEGER) IS

 BEGIN

  IF vn_Level > 0 THEN

    Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);

    Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);

  END IF;

  END;

Blok testowy dla procedury w powyższej postaci wykonał się w 15.08 s (czas uśredniony).

Przyśpieszajmy dalej..  Ponieważ w trakcie działania procedury wywoływane są  dwie procedury z czterema parametrami, zastosujmy mechanizm inline znany z języka C++ - zamiast wskaźnika do funkcji, wstawiane jest rozwinięcie funkcji..

CREATE OR REPLACE PROCEDURE Pdb_HanoiTower

( vn_Level SIMPLE_INTEGER, vn_From SIMPLE_INTEGER, vn_To SIMPLE_INTEGER,

vn_Helper SIMPLE_INTEGER) IS

 BEGIN

  IF vn_Level > 0 THEN

    PRAGMA INLINE (Pdb_HanoiTower, 'YES');

    Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);

    PRAGMA INLINE (Pdb_HanoiTower, 'YES');

    Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);

  END IF;

  END;

Blok testowy wykonał się w 8.66 s – to prawie dwukrotne przyśpieszenie..

Domyślnie funkcjonalności PL/SQL kompilowane są do kodu pośredniego wykonywanego na maszynie wirtualnej.. Oracle 11g oferuje kompilaję do kodu natywnego dla danego systemu operacyjnego.. Wykorzystajmy to

ALTER PROCEDURE PdB_HanoiTower COMPILE PLSQL_CODE_TYPE = NATIVE

Czas wykonania zmniejszył się  do 3.83 s. – przyrost ponad czterokrotny..

Usuńmy teraz  wskazówki do rozwinięcia funkcji inline (dodawanie ich jest mocno uciążliwe), zachęćmy  kompilator do samodzielnego rozwinięcia i innych sztuczek optymalizacyjnych( parametr kompilacji PLSQL_OPTIMIZE_LEVEL = 3).

Kod wraca do czytelnej postaci:

CREATE OR REPLACE PROCEDURE Pdb_HanoiTower

( vn_Level SIMPLE_INTEGER, vn_From SIMPLE_INTEGER, vn_To SIMPLE_INTEGER,

vn_Helper SIMPLE_INTEGER) IS

 BEGIN

  IF vn_Level > 0 THEN

    Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);

    Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);

  END IF;

  END;

Po kompilacji

ALTER PROCEDURE PdB_HanoiTower COMPILE PLSQL_CODE_TYPE = NATIVE  PLSQL_OPTIMIZE_LEVEL = 3

Czas  wykonania zmniejszył  się do 3.43..

Warto było?? Uważam, że tak!

Uwagi:

·         Powyższy przykład dotyczy Oracle 11g

·         Po sprawdzeniu na platformach  Windows 64 i HP Unix 64 otrzymałem dość zbliżone przyrosty, wstawiłem z pierwszego środowiska

·         Optymalizacja powyższa przeznaczona jest  raczej dla algorytmów obliczeniowych lub operujących ma łańcuchach, w mniejszym stopniu opierających się na częstych operacjach  bazodanowych