Hlavní navigace

Praktické použití nástroje Cython při překladu Pythonu do nativního kódu

Pavel Tišnovský

Dnes se seznámíme s dalšími vlastnostmi Cythonu, které nám umožní provádět různé optimalizace kódu. Ukážeme si výslednou podobu programu pro výpočet Mandelbrotovy množiny, jehož rychlost bude srovnatelná s céčkovou variantou.

Doba čtení: 28 minut

11. Pythonovské seznamy a céčková pole

12. Předchozí varianta benchmarku a oblasti, kde je možné provést optimalizace

13. Použití pole s barvovou paletou

14. Odstranění kontrol při dělení

15. Náhrada print za printf

16. Odstranění GIL

17. Finální podoba benchmarku, srovnání s variantou naprogramovanou v céčku

18. Výsledky všech benchmarků

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Praktické použití nástroje Cython při překladu Pythonu do nativního kódu

V dnešním článku, který poměrně úzce navazuje na článek porovnávající RPython s Cythonem, si ukážeme, jak se Cython používá prakticky. Připomeňme si, že tento nástroj slouží k převodu (takzvané transkompilaci/transpřekladu) zdrojových kódů napsaných v Pythonu (popř. nadmnožině tohoto jazyka) do zdrojového kódu určeného pro překlad standardními překladači céčka. Výsledkem může být buď dynamická knihovna plně využitelná v CPythonu (standardním interpretru jazyka Python) nebo spustitelná aplikace, kterou je možné dále používat popř. distribuovat (ovšem s některými omezeními popsanými dále). Cython sice přeloží i běžné zdrojové kódy Pythonu, ovšem jak uvidíme v dalších kapitolách, přináší to s sebou některá omezení – výsledný kód není příliš efektivní, a to ani z hlediska jeho velikosti ani z pohledu rychlosti. Pro zajištění lepší efektivity je zapotřebí zdrojové kódy upravit – a právě tato problematika je ústředním tématem dnešního článku.

Obrázek 1: Porovnání doby výpočtu Mandelbrotovy množiny RPythonem, Cythonem (bez i s type hinty) a variantou naprogramovanou přímo v ANSI C. Z tohoto grafu je dobře patrné, jak důležité je pro Cython mít k dispozici informace o typech proměnných, parametrů a návratových kódů funkcí.

Poznámka: ve skutečnosti dokážeme po přečtení tohoto článku dobu výpočtu Mandelbrotovy množiny (viz předchozí graf) ještě snížit a přiblížit se tak čistě céčkové implementaci!

2. Postupné úpravy jednoduché funkce pro součet dvou celých čísel

Základní koncepty, na kterých je založeno mnoho optimalizací prováděných Cythonem (pokud ovšem tomuto transpřekladači vhodným způsobem pomůžeme), je možné vysvětlit na funkci sloužící pro součet dvou celých čísel. Programovací jazyk Python většina programátorů používá mj. i kvůli jeho jednouše použitelnému typovému systému, takže funkci pro součet mohou bez větší námahy zapsat například takto:

def add_two_numbers(x, y):
    return x + y

Ve skutečnosti však samozřejmě tato funkce může provádět i mnoho dalších operací na základě konkrétních typů parametrů, které jsou funkci předávány. A právě zde leží základní problém, který musí řešit jak Cython, tak i již zmíněný RPython – aby byla tato funkce skutečně přeložena optimálně (v podstatě jen jedinou instrukcí add následovanou instrukcí ret), musíme dynamický typový systém Pythonu v tomto konkrétním případě omezit a stanovit jak typy parametrů, tak i návratový typ. Navíc, jak uvidíme dále, je možné v této funkci zcela vyloučit GIL (Global Interpreter Lock) a tak výslednou céčkovou funkci ještě zkrátit a zrychlit.

Postupně si tedy ukážeme vliv těchto dílčích kroků:

  1. Deklarace typů parametrů funkce
  2. Deklarace návratového typu
  3. Odstranění použití GIL (prolog a epilog ve funkci)

3. Soubor Makefile pro řízení překladu funkcí z Pythonu do nativního kódu

Před popisem jednotlivých (celkem šesti) variant funkce určené pro součet dvou čísel si ukažme, jakým způsobem vlastně budeme provádět překlad. Již víme, že celý překlad probíhá ve třech krocích:

  1. Transpřeklad zdrojového kódu napsaného v Pythonu do programovacího jazyka C
  2. Překlad kódu z jazyka C do tzv. objektového kódu (de facto strojový kód s relativními adresami)
  3. Slinkování objektového kódu s knihovnami a vytvoření spustitelné aplikace

Ze zdrojového kódu napsaného v Pythonu (či jeho nadstavbě) postupně vzniknou tři další soubory:

soubor.py → soubor.c → objektový_kód.o → nativní spustitelná aplikace

Celý řetězec zpracování bude řízen souborem Makefile, který vypadá následovně (jeho jednotlivé části budou popsány pod výpisem):

PYTHON=python3
COMPILER=gcc
LINKER=gcc
 
CFLAGS=-O9
 
INCLUDE_DIR:=$(shell $(PYTHON) -c "from distutils import sysconfig; print(sysconfig.get_python_inc())")
LIBRARY_DIR:=$(shell $(PYTHON) -c "from distutils import sysconfig; print(sysconfig.get_config_var('LIBDIR'))")
PYTHON_LIB:=$(shell $(PYTHON) -c "from distutils import sysconfig; print(sysconfig.get_config_var('LIBRARY')[3:-2])")
SYSLIBS:=$(shell $(PYTHON) -c "from distutils import sysconfig; print(sysconfig.get_config_var('SYSLIBS'))")
 
 
all:    add_numbers_1 \
        add_numbers_2 \
        add_numbers_3 \
        add_numbers_4 \
        add_numbers_5 \
        add_numbers_7
 
 
.PHONY: clean
 
# Výsledky překladu do C chceme ponechat i po doběhnutí Make
.PRECIOUS: %.c
 
clean:
        rm -f *.o \
        rm -f *.c \
        rm -f add_numbers_[1-5]
 
 
# Pravidlo pro slinkovani vsech objektovych souboru a vytvoreni
# vysledne spustitelne aplikace.
%:      %.o
        $(LINKER) -o $@ -L$(LIBRARY_DIR) -l$(PYTHON_LIB) $(SYSLIBS) $<
 
 
# Pravidlo pro preklad kazdeho zdrojoveho souboru v C do prislusneho
# objektoveho souboru.
%.o:    %.c
        $(COMPILER) $(CFLAGS) -I$(INCLUDE_DIR) -c $< -o $@
 
 
# Pravidlo pro preklad kazdeho zdrojoveho souboru v Pythonu nebo Cythonu
# do prislusneho souboru C
%.c:    %.py
        cython -a --embed $<
 
%.c:    %.pyx
        cython -a --embed $<

Některé části Makefile jsou snadno pochopitelné. Jedná se zejména o pravidla pro transpřeklad zdrojových kódů s koncovkou .py nebo .pyx do céčkových souborů s koncovkou .c. Přepínač –embed zajistí vygenerování kódu funkce main, přepínač -a pak vytvoření HTML souboru, jehož význam si ukážeme dále.

Podobně je zde deklarováno pravidlo pro překlad céčkových souborů .c do objektového kódu .o. Zde musíme použít informaci o tom, kde se nachází hlavičkové soubory Pythonu – důvod jsme si vysvětlili zde. Další pravidlo určuje slinkování .o do spustitelné aplikace, opět s přidáním všech důležitých informací (umístění systémových knihoven apod.)

Následující deklarace zajistí, že nástroj make nebude mazat soubory *.c, které vznikly aplikací implicitních pravidel. Pokud tuto deklaraci zakomentujete, smaže utilita make na závěr nejenom všechny objektové soubory, ale i transpřeložené zdrojové kódy v céčku, které sice již nebudou zapotřebí, ale my je budeme chtít později prozkoumat:

.PRECIOUS: %.c

4. Přímý překlad Pythonovské funkce bez přidání typových informací

Pokusme se nyní přeložit první variantu funkce pro součet dvou celých čísel. Zdrojový kód s deklarací této funkce i s příkladem jejího volání naleznete na adrese https://github.com/tisnik/cython-examples/blob/master/add_num­bers/add_numbers1.py:

def add_two_numbers(x, y):
    return x + y
 
 
z = add_two_numbers(123, 456)
print(z)

Výsledkem překladu bude spustitelný soubor „add_numbers1“, ovšem nás nyní budou zajímat další dva vytvořené soubory nazvané „add_numbers1.c“ a „add_numbers1.html“. První z těchto souborů obsahuje zdrojový kód v céčku, jehož překladem a slinkováním vznikla výsledná spustitelná aplikace, druhý soubor pak obsahuje zajímavé informace o tom, jakým způsobem Cython program přeložil a především pak, na kterých místech by bylo vhodné provést úpravy s určením datových typů atd. Obsah tohoto souboru vypadá takto:

Obrázek 2: Část HTML souboru „add_numbers1.html“ vytvořeného Cythonem. Žlutě označené řádky označují ty bloky kódu, o nichž Cython nemá typové informace a které musel přeložit dosti neefektivním způsobem simulujícím chování interpretru Pythonu.

Lepší však bude, když si celý soubor přímo otevřete v prohlížeči, protože umožňuje interaktivní rozbalování jednotlivých přeložených řádků (kliknutím na znak + umístěný v prvním sloupci, popř. na libovolný řádek se žlutým podsvícením).

5. Proč Cython používá PyObject * aneb problematika dynamického typového systému

Zdrojový (céčkový) kód vygenerovaný Cythonem je poměrně nečitelný (alespoň prozatím!), a to mj. i z toho důvodu, že oba dva parametry funkce add_two_numbers i její návratová hodnota jsou představovány ukazateli na struktury typu PyObject. Cython totiž nemá k dispozici žádné informace o tom, jakého typu parametry budou a tak musí předpokládat, že se funkce bude volat s celými čísly, čísly s plovoucí řádovou čárkou, seznamy, n-ticemi, řetězci či dokonce s instancemi tříd, které mají předefinovánu speciální metodu __add__ (jinými slovy se všemi typy, u kterých má smysl používat operátor +).

Ostatně se stačí podívat na následující demonstrační příklad, v němž je naše funkce volána s různými typy parametrů (z čehož mj. plyne i to, že její název je dosti zavádějící):

def add_two_numbers(x, y):
    return x + y
 
 
class Foo:
    def __init__(self, value):
        self._value = value
 
    def __add__(self, other):
        return Foo(self._value + other._value)
 
    def __str__(self):
        return "*" * self._value
 
 
def test_adding():
    f1 = Foo(1)
    f2 = Foo(2)
 
    print(add_two_numbers(123, 456))
    print(add_two_numbers("foo", "bar"))
    print(add_two_numbers([1,2,3], [4,5,6]))
    print(add_two_numbers((1,2,3), (4,5,6)))
    print(add_two_numbers(f1, f2))
 
 
test_adding()

Po spuštění příkladu dostaneme následující řádky, které ukazují, že se + skutečně dá použít s různými datovými typy:

579
foobar
[1, 2, 3, 4, 5, 6]
(1, 2, 3, 4, 5, 6)
***

Zkusme si příklad ještě dále upravit – podíváme se na bajtkód, který bude interpretován Pythonem (bajtkód se vytváří vždy, i když se nemusí ukládat na disk):

import dis
 
dis.dis(add_two_numbers)
dis.dis(test_adding)

Funkce add_two_numbers je přeložena do čtyř instrukcí, které ovšem neobsahují řádné informace o typech operandů (na rozdíl od bajtkódu JVM, kde existuje například instrukce IADD, FADD, DADD apod.):

  4           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 BINARY_ADD
              7 RETURN_VALUE

Příklad volání funkce s předáním dvou celočíselných parametrů. Toto je varianta bajtkódu pro Python 2, který obsahuje print jako příkaz a tudíž pro něj existuje i odpovídající instrukce v bajtkódu:

 22          24 LOAD_GLOBAL              1 (add_two_numbers)
             27 LOAD_CONST               3 (123)
             30 LOAD_CONST               4 (456)
             33 CALL_FUNCTION            2
             36 PRINT_ITEM
             37 PRINT_NEWLINE

Celý bajtkód pro Python 2 vypadá následovně (poznámky jsem dopsal ručně):

# tělo funkce add_two_numbers()
  4           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 BINARY_ADD
              7 RETURN_VALUE
 
# f1 = Foo(1)
 19           0 LOAD_GLOBAL              0 (Foo)
              3 LOAD_CONST               1 (1)
              6 CALL_FUNCTION            1
              9 STORE_FAST               0 (f1)
 
# f2 = Foo(2)
 20          12 LOAD_GLOBAL              0 (Foo)
             15 LOAD_CONST               2 (2)
             18 CALL_FUNCTION            1
             21 STORE_FAST               1 (f2)
 
# součet dvou celých čísel
 22          24 LOAD_GLOBAL              1 (add_two_numbers)
             27 LOAD_CONST               3 (123)
             30 LOAD_CONST               4 (456)
             33 CALL_FUNCTION            2
             36 PRINT_ITEM
             37 PRINT_NEWLINE
 
# spojení dvou řetězců
 23          38 LOAD_GLOBAL              1 (add_two_numbers)
             41 LOAD_CONST               5 ('foo')
             44 LOAD_CONST               6 ('bar')
             47 CALL_FUNCTION            2
             50 PRINT_ITEM
             51 PRINT_NEWLINE
 
# konstrukce dvou seznamů s jejich následným spojením
 24          52 LOAD_GLOBAL              1 (add_two_numbers)
             55 LOAD_CONST               1 (1)
             58 LOAD_CONST               2 (2)
             61 LOAD_CONST               7 (3)
             64 BUILD_LIST               3
             67 LOAD_CONST               8 (4)
             70 LOAD_CONST               9 (5)
             73 LOAD_CONST              10 (6)
             76 BUILD_LIST               3
             79 CALL_FUNCTION            2
             82 PRINT_ITEM
             83 PRINT_NEWLINE
 
# konstrukce dvou n-tic s jejich následným spojením
 25          84 LOAD_GLOBAL              1 (add_two_numbers)
             87 LOAD_CONST              11 ((1, 2, 3))
             90 LOAD_CONST              12 ((4, 5, 6))
             93 CALL_FUNCTION            2
             96 PRINT_ITEM
             97 PRINT_NEWLINE
 
# "spojení" dvou instancí třídy Foo
 26          98 LOAD_GLOBAL              1 (add_two_numbers)
            101 LOAD_FAST                0 (f1)
            104 LOAD_FAST                1 (f2)
            107 CALL_FUNCTION            2
            110 PRINT_ITEM
            111 PRINT_NEWLINE
 
# ukončení funkce main
            112 LOAD_CONST               0 (None)
            115 RETURN_VALUE

Příklad volání funkce s předáním dvou celočíselných parametrů. Toto je varianta bajtkódu pro Python 3, v němž je print běžnou funkcí:

 22          24 LOAD_GLOBAL              1 (print)
             27 LOAD_GLOBAL              2 (add_two_numbers)
             30 LOAD_CONST               3 (123)
             33 LOAD_CONST               4 (456)
             36 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
             39 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             42 POP_TOP

Opět si ukažme celý bajtkód pro Python 3 (poznámky jsem dopsal ručně):

# tělo funkce add_two_numbers()
  4           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 BINARY_ADD
              7 RETURN_VALUE
 
# f1 = Foo(1)
 19           0 LOAD_GLOBAL              0 (Foo)
              3 LOAD_CONST               1 (1)
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 STORE_FAST               0 (f1)
 
# f2 = Foo(2)
 20          12 LOAD_GLOBAL              0 (Foo)
             15 LOAD_CONST               2 (2)
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 STORE_FAST               1 (f2)
 
# součet dvou celých čísel
 22          24 LOAD_GLOBAL              1 (print)
             27 LOAD_GLOBAL              2 (add_two_numbers)
             30 LOAD_CONST               3 (123)
             33 LOAD_CONST               4 (456)
             36 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
             39 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             42 POP_TOP
 
# spojení dvou řetězců
 23          43 LOAD_GLOBAL              1 (print)
             46 LOAD_GLOBAL              2 (add_two_numbers)
             49 LOAD_CONST               5 ('foo')
             52 LOAD_CONST               6 ('bar')
             55 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
             58 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             61 POP_TOP
 
# konstrukce dvou seznamů s jejich následným spojením
 24          62 LOAD_GLOBAL              1 (print)
             65 LOAD_GLOBAL              2 (add_two_numbers)
             68 LOAD_CONST               1 (1)
             71 LOAD_CONST               2 (2)
             74 LOAD_CONST               7 (3)
             77 BUILD_LIST               3
             80 LOAD_CONST               8 (4)
             83 LOAD_CONST               9 (5)
             86 LOAD_CONST              10 (6)
             89 BUILD_LIST               3
             92 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
             95 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             98 POP_TOP
 
# konstrukce dvou n-tic s jejich následným spojením
 25          99 LOAD_GLOBAL              1 (print)
            102 LOAD_GLOBAL              2 (add_two_numbers)
            105 LOAD_CONST              11 ((1, 2, 3))
            108 LOAD_CONST              12 ((4, 5, 6))
            111 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
            114 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            117 POP_TOP
 
# "spojení" dvou instancí třídy Foo
 26         118 LOAD_GLOBAL              1 (print)
            121 LOAD_GLOBAL              2 (add_two_numbers)
            124 LOAD_FAST                0 (f1)
            127 LOAD_FAST                1 (f2)
            130 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
            133 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            136 POP_TOP
 
# ukončení funkce main
            137 LOAD_CONST               0 (None)
            140 RETURN_VALUE

6. Použití deklarace cdef namísto def

První úpravou našeho zdrojového kódu funkce add_two_numbers, která povede k menšímu a rychlejšímu strojovému (nativnímu) kódu, bude použití klíčového slova cdef namísto pythonovského def. Zdrojový kód uložíme do souboru s koncovkou .pyx namísto .py, a to především z toho důvodu, že se již nejedná o běžný kód zpracovatelný Pythonem (pro připomenutí: Cython používá nadmnožinu Pythonu zatímco RPython jeho podmnožinu). Žádné další úpravy kromě náhrady s/def/cdef prozatím nebudou provedeny:

cdef add_two_numbers(x, y):
    return x + y
 
 
z = add_two_numbers(123, 456)
print(z)

Vzhledem k tomu, že v Makefile voláme Cython s parametrem -a, vygeneruje se mj. i HTML stránka, na níž je patrné, jak byla naše funkce přeložena do céčka tentokrát. Celý kód je již citelně kratší, i když je stále velmi neefektivní: cython_add_numbers2.

Obrázek 3: Část HTML souboru „add_numbers2.html“ vytvořeného Cythonem. Žlutě označené řádky opět označují ty bloky kódu, o nichž Cython nemá typové informace a které musel přeložit dosti neefektivním způsobem simulujícím chování interpretru Pythonu.

Hlavička céčkové funkce vzniklé transpřekladem vypadá takto:

static PyObject *__pyx_f_13add_numbers_2_add_two_numbers(PyObject *__pyx_v_x, PyObject *__pyx_v_y) {}

Potenciálně neefektivní části kódu:

  1. __Pyx_RefNannyDeclarations a __Pyx_RefNannySetupContext() na začátku funkce
  2. __Pyx_RefNannyFinishContext() na konci funkce
  3. vlastní výpočet je ovšem implementován voláním další funkce PyNumber_Add(__pyx_v_x, __pyx_v_y)

7. Přidání informace o typech parametrů funkce pro součet celých čísel

První výraznější úpravou, kterou můžeme provést, je přidání informace o typech parametrů funkce. Zápis je v tomto případě naprosto stejný, jako v klasickém céčku, tj. používá se pořadí datový_typ jméno_parametru. V našem případě budeme vyžadovat, aby parametry byly typu celé číslo, tj. v céčku se jedná o základní typ pojmenovaný int. Změněná funkce bude vypadat následovně:

cdef add_two_numbers(int x, int y):
    return x + y
 
 
z = add_two_numbers(123, 456)
print(z)

Pokud se podíváme na vygenerovanou HTML stránku (cython_add_numbers3), popř. raději přímo na céčkový kód, uvidíme, že došlo k několika zásadním změnám. Zejména se pochopitelně změnila hlavička céčkové funkce vzniklé transpřekladem, která nyní vypadá následovně:

static PyObject *__pyx_f_13add_numbers_3_add_two_numbers(int __pyx_v_x, int __pyx_v_y) {

Obrázek 4: Část HTML souboru „add_numbers3.html“ vytvořeného Cythonem..

Dále se – pokud prozatím budeme ignorovat kód na začátku a konci funkce – celý výpočet pozměnil, protože se namísto volání PyNumber_Add již používá běžný součet. Ovšem následně se vypočtené celé číslo opět konvertuje na pythonovský objekt s využitím __Pyx_PyInt_From_int, protože jsme prozatím naschvál nespecifikovali návratový typ funkce:

  __pyx_t_1 = __Pyx_PyInt_From_int((__pyx_v_x + __pyx_v_y))

Úplný céčkový kód je tedy již nepatrně lepší, ovšem k optimálnosti má stále daleko:

static PyObject *__pyx_f_13add_numbers_3_add_two_numbers(int __pyx_v_x, int __pyx_v_y) {
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  PyObject *__pyx_t_1 = NULL;
  __Pyx_RefNannySetupContext("add_two_numbers", 0);
 
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_1 = __Pyx_PyInt_From_int((__pyx_v_x + __pyx_v_y)); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 2, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_t_1);
  __pyx_r = __pyx_t_1;
  __pyx_t_1 = 0;
  goto __pyx_L0;
 
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_1);
  __Pyx_AddTraceback("add_numbers_3.add_two_numbers", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = 0;
  __pyx_L0:;
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

8. Přidání informace o návratovém typu funkce pro součet celých čísel

Další úprava naší funkce se již přímo nabízí – musíme specifikovat typ návratové hodnoty. Pokud totiž tento typ není zadán, považuje Cython za nutné vracet PyObject *, aby byly výsledky kompatibilní s běžnými pythonovskými funkcemi a metodami. Specifikace návratové hodnoty se opět provádí stejným způsobem, jako v programovacím jazyku C, tj. zápisem příslušného typu před jméno funkce:

cdef int add_two_numbers(int x, int y):
    return x + y
 
 
z = add_two_numbers(123, 456)
print(z)

Při transpřekladu do céčka získáme i HTML stránku s podrobnějšími informacemi o tom, jak byl Cython úspěšný. Tato stránka nyní vypadá takto a z jejího obsahu je patrné, že jsme se již velmi přiblížili k takové deklaraci, kterou by použil céčkový programátor (až na prolog a epilog):

static int __pyx_f_13add_numbers_4_add_two_numbers(int __pyx_v_x, int __pyx_v_y) {
  int __pyx_r;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("add_two_numbers", 0);
 
  __pyx_r = (__pyx_v_x + __pyx_v_y);
  goto __pyx_L0;
 
  /* function exit code */
  __pyx_L0:;
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

Obrázek 5: Část HTML souboru „add_numbers4.html“ vytvořeného Cythonem. Zde již není žádná část těla funkce podbarvena, protože Cython má k dispozici všechny potřebné informace o použitých datových typech.

Poznámka: příkaz goto bude eliminován při překladu céčka do strojového kódu.

9. Zákaz volání funkcí souvisejících s GILem

Zbývá nám udělat ještě poslední krok, a to odstranit přípravu takzvaného kontextu na začátku těla funkce a naopak odstranění kontextu na jejím konci. Jedná se o tuto trojici řádků:

  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("add_two_numbers", 0);
  ...
  ...
  ...
  __Pyx_RefNannyFinishContext();

Zjednodušeně řečeno – kontext úzce souvisí s GIL (Global Interpreter Lock), který prozatím tvoří neoddělitelnou část klasického interpretru CPythonu (ovšem například v Jythonu ho nenajdeme, i když tento interpret má zase jiné problémy). GIL je zapotřebí nastavit tehdy, pokud naše (nyní vlastně céčková) funkce bude interně volat funkce naprogramované v Pythonu popř. funkce z jeho interní knihovny. To my ovšem nepotřebujeme – pouze sčítáme dvě celá čísla a vracíme výsledek součtu – takže můžeme práci s GILem zcela zakázat, a to použitím specifikace nogil. Finální podoba naší funkce bude vypadat následovně:

cdef int add_two_numbers(int x, int y) nogil:
    return x + y
 
 
z = add_two_numbers(123, 456)
print(z)

Pokud se podíváme na výsledek překladu, zjistíme, že až na již výše zmíněné goto získáme čistý a čitelný céčkový kód:

static int __pyx_f_13add_numbers_5_add_two_numbers(int __pyx_v_x, int __pyx_v_y) {
  int __pyx_r;
 
  __pyx_r = (__pyx_v_x + __pyx_v_y);
  goto __pyx_L0;
 
  /* function exit code */
  __pyx_L0:;
  return __pyx_r;
}

Podívat se můžete i na HTML stránku vygenerovanou při transpřekladu: cython_add_numbers5. Ta ovšem nyní nebude obsahovat příliš zajímavé informace, protože jsme postupně (ve třech krocích) v nadmnožině Pythonu vlastně naprogramovali ekvivalent céčkovské funkce.

Obrázek 6: Část HTML souboru „add_numbers5.html“ vytvořeného Cythonem. Zde již není žádná část těla funkce podbarvena, protože Cython má k dispozici všechny potřebné informace o použitých datových typech.

Poznámka: všechny tři kroky, které jsme provedli, jsou vlastně velmi jednoduché, ale současně jsou nezbytné pro to, aby Cython dokázal vygenerovat optimální kód.

10. Náhrada Pythonovské funkce print za funkci printf

Odstranění GILu z naší funkce bylo zcela korektní a nebude způsobovat žádné nepříjemnosti (pokud kratší a rychlejší kód nebudeme považovat za nepříjemnost). Ovšem zajímavé bude zjistit, co se stane ve chvíli, kdy se budeme snažit v takto upravené funkci volat jakýkoli Pythonovský kód (například print). Zkusme si tedy funkci upravit takovým způsobem, aby před provedením součtu vypsala hodnotu svého prvního parametru:

cdef int add_two_numbers(int x, int y) nogil:
    print(x)
    return x + y
 
 
z = add_two_numbers(123, 456)
print(z)

Při pokusu o transpřeklad s využitím Cythonu dojde k několika chybám:

$ cython -a --embed add_numbers_6.pyx
 
Error compiling Cython file:
------------------------------------------------------------
...
cdef int add_two_numbers(int x, int y) nogil:
    print(x)
   ^
------------------------------------------------------------
 
add_numbers_6.pyx:2:4: Python print statement not allowed without gil
 
Error compiling Cython file:
------------------------------------------------------------
...
cdef int add_two_numbers(int x, int y) nogil:
    print(x)
   ^
------------------------------------------------------------
 
add_numbers_6.pyx:2:4: Constructing Python tuple not allowed without gil
 
Error compiling Cython file:
------------------------------------------------------------
...
cdef int add_two_numbers(int x, int y) nogil:
    print(x)
         ^
------------------------------------------------------------
 
add_numbers_6.pyx:2:10: Converting to Python object not allowed without gil

Proč tomu tak je? Problém spočívá v tom, že se sice naše funkce bez GILu zdánlivě obejde, ovšem běžné Pythonovské funkce a operace z ní volané s ním počítají. Proto pokud použijeme nogil, budeme se muset v tomto bloku obejít bez podpory pythoních funkcí. V našem případě to nebude nic složitého – prostě použijeme funkci printf ze standardní céčkové knihovny (ta se stejně bude linkovat). Řešení může vypadat následovně (pozor na slovo cimport a ne import):

from libc.stdio cimport printf
 
 
cdef int add_two_numbers(int x, int y) nogil:
    printf("%i\n", x)
    return x + y
 
 
z = add_two_numbers(123, 456)
print(z)

Podívejme se na vygenerovaný céčkový kód, který sice působí trochu uměle (explicitní (void), generované názvy identifikátorů atd.), ale v podstatě stejně, jako ručně psaný kód. Ono zbytečné goto bude odstraněno optimalizujícím překladačem céčka:

static int __pyx_f_13add_numbers_7_add_two_numbers(int __pyx_v_x, int __pyx_v_y) {
  int __pyx_r;
 
  (void)(printf(((char const *)"%i\n"), __pyx_v_x));
 
  __pyx_r = (__pyx_v_x + __pyx_v_y);
  goto __pyx_L0;
 
  /* function exit code */
  __pyx_L0:;
  return __pyx_r;
}

11. Pythonovské seznamy a céčková pole

Seznamy a n-tice jsou sice v Pythonu základními a současně i velmi užitečnými složenými datovými typy, ovšem kvůli tomu, že jsou nehomogenní, se s nimi musí zacházet poměrně neefektivně. Navíc je neefektivní i samotné uložení těchto datových typů v operační paměti. Řešením je použití klasických céčkových polí s případným převodem seznamů na pole. To lze provést například vytvořením klasického céčkového pole s prvky zadaného typu:

cdef array.array byte_array = array.array('B')
cdef array.array int_array = array.array('i')
 
cdef array.array a = array.array('i', [1, 2, 3])

Důležité je specifikovat typ prvků pole:

Signatura Typ v C
b signed char
B unsigned char
u Py_UNICODE
h signed short
H unsigned short
i signed int
I unsigned int
l signed long
L unsigned long
q signed long long
Q unsigned long long
f float
d double

Ve skutečnosti není takto vytvořené pole přesnou obdobou céčkového pole, protože s ním můžeme provádět i operace, které spíše odpovídají dynamicky alokovanému poli:

// změna velikosti
int resize(array self, Py_ssize_t n)
 
// přidání nových prvků do pole (musí ovšem odpovídat jejich datový typ)
cdef inline int extend_buffer(array self, char* stuff, Py_ssize_t n)
 
// připojení obsahu druhého pole (opět musí odpovídat datový typ prvků)
cdef inline int extend(array self, array other)

Takto vytvořené pole lze do funkcí předat přes ukazatel (referencí) příslušného typu, tj. například:

cdef void test(char *byte_array) nogil:
    ...
    ...
    ...

12. Předchozí varianta benchmarku a oblasti, kde je možné provést optimalizace

Nyní již máme k dispozici všechny potřebné informace nutné pro úpravu našeho benchmarku pro výpočet Mandelbrotovy množiny. Naším cílem bude dosažení rychlosti srovnatelné s variantou naprogramovanou v čistém ANSI C. Jen pro připomenutí – předchozí varianta, s níž jsme končili minulý článek, vypadala následovně. Nejedná se o špatné řešení, ovšem již nyní je nutné říct, že ho můžeme vylepšit a cca dvojnásobně urychlit:

#!/usr/bin/env python
# vim: set fileencoding=utf-8
 
import palette_mandmap
from sys import argv, exit
 
 
cdef calc_mandelbrot(int width, int height, int maxiter, palette):
    cdef double zx
    cdef double zy
    cdef double zx2
    cdef double zy2
    cdef double cx
    cdef double cy
    cdef int r
    cdef int g
    cdef int b
    cdef int i
 
    print("P3")
    print("{w} {h}".format(w=width, h=height))
    print("255")
    cy = -1.5
 
    for y in range(0, height):
        cx = -2.0
        for x in range(0, width):
            zx = 0.0
            zy = 0.0
            i = 0
            while i < maxiter:
                zx2 = zx * zx
                zy2 = zy * zy
                if zx2 + zy2 > 4.0:
                    break
                zy = 2.0 * zx * zy + cy
                zx = zx2 - zy2 + cx
                i += 1
 
            r = palette[i][0]
            g = palette[i][1]
            b = palette[i][2]
            print("{r} {g} {b}".format(r=r, g=g, b=b))
            cx += 3.0/width
        cy += 3.0/height
 
 
if __name__ == "__main__":
    if len(argv) < 4:
        print("usage: python mandelbrot width height maxiter")
        exit(1)
 
    width = int(argv[1])
    height = int(argv[2])
    maxiter = int(argv[3])
    calc_mandelbrot(width, height, maxiter, palette_mandmap.palette)

13. Použití pole s barvovou paletou

Nyní budeme muset provést ve zdrojovém kódu benchmarku několik úprav. První úprava se týká přístupu k n-tici s barvovou paletou. Jedná se konkrétně o tento kód:

cdef calc_mandelbrot(int width, int height, int maxiter, palette):
    ...
    ...
    ...
            r = palette[i][0]
            g = palette[i][1]
            b = palette[i][2]

Problém spočívá v tom, že přístup k pythonovské n-tici nebo seznamu nebude nikdy optimální a bude se zbytečně provádět převod z PyObject * na číslo atd. atd. Tento kód se sice nevolá v nejvnitřnější smyčce, ale i tak může výpočet zdržovat – pro obrázek o rozlišení 1000×1000 pixelů se bude do seznamu nebo n-tice přistupovat 3 000 000×. Úprava spočívá v použití jednorozměrného pole:

cdef array.array palette = array.array('B')
 
for color in palette_mandmap.palette:
    for component in color:
        palette.append(component)

k jehož prvkům se bude přistupovat takto:

cdef unsigned char r
cdef unsigned char g
cdef unsigned char b
 
cdef int index
 
index = i * 3
r = palette[index]
g = palette[index+1]
b = palette[index+2]

Výsledkem bude kód minimálně srovnatelný s variantou naprogramovanou v ANSI C:

__pyx_v_index = (__pyx_v_i * 3);
__pyx_v_r = (__pyx_v_palette[__pyx_v_index]);
__pyx_v_g = (__pyx_v_palette[(__pyx_v_index + 1)]);
__pyx_v_b = (__pyx_v_palette[(__pyx_v_index + 2)]);

14. Odstranění kontrol při dělení

Jen krátce se zmiňme o tom, že Cython implicitně vkládá do céčkového kódu testy na dělení nulou. V našem konkrétním případě vypadají takto (kód jsem pro větší čitelnost upravil):

/*
 *         cy += 3.0/height
 */
 
      if (unlikely(__pyx_v_width == 0)) {
        PyErr_SetString(PyExc_ZeroDivisionError, "float division");
        __PYX_ERR(0, 56, __pyx_L1_error)
      }
      __pyx_v_cx = (__pyx_v_cx + (3.0 / __pyx_v_width));
    }
 
/*
 *         cy += 3.0/height
 */
    if (unlikely(__pyx_v_height == 0)) {
      PyErr_SetString(PyExc_ZeroDivisionError, "float division");
      __PYX_ERR(0, 57, __pyx_L1_error)
    }

Sice se nejedná o implementačně příliš složité operace, ale i tak je můžeme odstranit, a to velmi jednoduše úpravou hlavičky funkce, resp. přesněji přidáním anotace před hlavičku:

@cython.cdivision(True)
cdef void calc_mandelbrot(int width, int height, int maxiter, unsigned char *palette):
Poznámka: překlad podmínky do strojového kódu je sice jednoduchý, ovšem pokud by se měl takový test provádět ve vnitřní smyčce, představuje to pro mikroprocesor poměrně velký problém, který je částečně řešen prediktorem skoků. Samozřejmě je ovšem mnohem lepší se těchto testů zbavit a popř. je provést jen na začátku výpočtu (pokud to má pro daný algoritmus význam).

15. Náhrada print za printf

Další úprava je vyžádána tím, že budeme chtít z celé funkce pro výpočet Mandelbrotovy množiny odstranit GIL. Proto nahradíme veškeré volání funkce print za céčkovou funkci printf.

Původní kód:

    print("P3")
    print("{w} {h}".format(w=width, h=height))
    print("255")
    ...
    ...
    ...
            r = palette[i][0]
            g = palette[i][1]
            b = palette[i][2]
            print("{r} {g} {b}".format(r=r, g=g, b=b))
            ...
            ...
            ...

Nový kód:

    printf("P3\n%d %d\n255\n", width, height)
    ...
    ...
    ...
            r = palette[index]
            g = palette[index+1]
            b = palette[index+2]
            printf("%d %d %d\n", r, g, b)
            ...
            ...
            ...

Odměnou nám bude mnohem kratší a čitelnější výsledek.

16. Odstranění GIL

Tímto tématem jsme se již zabývali v deváté kapitole, takže jen krátce – volání jakýchkoli funkcí souvisejících s GILem můžeme odstranit, protože jsme mj. provedli náhradu print za printf. Změní se tedy hlavička funkce pro výpočet Mandelbrotovy množiny na finální podobu:

@cython.cdivision(True)
cdef void calc_mandelbrot(int width, int height, int maxiter, unsigned char *palette) nogil:

17. Finální podoba benchmarku, srovnání s variantou naprogramovanou v céčku

Nyní si již můžeme ukázat výslednou verzi benchmarku upraveného takovým způsobem, aby byl výsledkem jeho transpřekladu do céčka co nejlepší kód. Zda se nám to skutečně povedlo se dozvíme po spuštění benchmarku a porovnání výsledků s výsledky předchozími. V kódu jsou zvýrazněny všechny speciality Cythonu:

#!/usr/bin/env python
# vim: set fileencoding=utf-8
 
import palette_mandmap
from sys import argv, exit
import cython
from cpython cimport array
from libc.stdio cimport printf
 
 
@cython.cdivision(True)
cdef void calc_mandelbrot(int width, int height, int maxiter, unsigned char *palette) nogil:
    cdef double zx
    cdef double zy
    cdef double zx2
    cdef double zy2
    cdef double cx
    cdef double cy
    cdef unsigned char r
    cdef unsigned char g
    cdef unsigned char b
    cdef int i
    cdef int index
 
    printf("P3\n%d %d\n255\n", width, height)
    cy = -1.5
 
    for y in range(0, height):
        cx = -2.0
        for x in range(0, width):
            zx = 0.0
            zy = 0.0
            i = 0
            while i < maxiter:
                zx2 = zx * zx
                zy2 = zy * zy
                if zx2 + zy2 > 4.0:
                    break
                zy = 2.0 * zx * zy + cy
                zx = zx2 - zy2 + cx
                i += 1
 
            index = i * 3
            r = palette[index]
            g = palette[index+1]
            b = palette[index+2]
            printf("%d %d %d\n", r, g, b)
            cx += 3.0/width
        cy += 3.0/height
 
 
cdef array.array palette = array.array('B')
 
if __name__ == "__main__":
 
    if len(argv) < 4:
        print("usage: python mandelbrot width height maxiter")
        exit(1)
 
    for color in palette_mandmap.palette:
        for component in color:
            palette.append(component)
 
    width = int(argv[1])
    height = int(argv[2])
    maxiter = int(argv[3])
    calc_mandelbrot(width, height, maxiter, palette.data.as_uchars)

Jen pro porovnání – takto vypadá varianta benchmarku naprogramovaná v ANSI C:

#include <stdlib.h>
#include <stdio.h>
 
#include "palette_mandmap.h"
 
void calc_mandelbrot(unsigned int width, unsigned int height, unsigned int maxiter, unsigned char palette[][3])
{
    puts("P3");
    printf("%d %d\n", width, height);
    puts("255");
 
    double cy = -1.5;
    int y;
    for (y=0; y<height; y++) {
        double cx = -2.0;
        int x;
        for (x=0; x<width; x++) {
            double zx = 0.0;
            double zy = 0.0;
            unsigned int i = 0;
            while (i < maxiter) {
                double zx2 = zx * zx;
                double zy2 = zy * zy;
                if (zx2 + zy2 > 4.0) {
                    break;
                }
                zy = 2.0 * zx * zy + cy;
                zx = zx2 - zy2 + cx;
                i++;
            }
            unsigned char *color = palette[i];
            unsigned char r = *color++;
            unsigned char g = *color++;
            unsigned char b = *color;
            printf("%d %d %d\n", r, g, b);
            cx += 3.0/width;
        }
        cy += 3.0/height;
    }
}
 
 
int main(int argc, char **argv)
{
    if (argc < 4) {
        puts("usage: ./mandelbrot width height maxiter");
        return 1;
    }
    int width = atoi(argv[1]);
    int height = atoi(argv[2]);
    int maxiter = atoi(argv[3]);
    calc_mandelbrot(width, height, maxiter, palette);
    return 0;
}

18. Výsledky všech benchmarků

Výsledky prezentované v následující tabulce hovoří jasně – optimalizace vysvětlené v předchozích kapitolách mají velký význam pro rychlost výsledného kódu a navíc je možné dosáhnout (a to relativně snadno) rychlosti plně srovnatelné s ANSI C. Přitom je Cythoní kód kratší a většinou i čitelnější:

Rozlišení CPython 2 CPython 3 Jython RPython ANSI C Cython Cython (typy) Cython (optim)
16×16 0,01 0,03 2,25 0,00 0,00 0,03 0,03 0,02
24×24 0,01 0,03 1,87 0,00 0,00 0,02 0,02 0,02
32×32 0,02 0,03 1,95 0,00 0,00 0,03 0,02 0,02
48×48 0,03 0,04 2,14 0,00 0,00 0,03 0,02 0,02
64×64 0,05 0,06 2,02 0,00 0,00 0,04 0,03 0,02
96×96 0,09 0,10 2,17 0,01 0,00 0,06 0,03 0,02
128×128 0,16 0,16 2,52 0,02 0,00 0,10 0,04 0,02
192×192 0,34 0,34 2,73 0,05 0,01 0,20 0,05 0,03
256×256 0,57 0,59 2,79 0,07 0,02 0,34 0,08 0,03
384×384 1,27 1,34 3,93 0,16 0,04 0,74 0,16 0,06
512×512 2,26 2,34 5,48 0,29 0,07 1,32 0,27 0,09
768×768 5,08 5,52 9,41 0,65 0,16 2,89 0,60 0,18
1024×1024 9,32 9,69 13,70 1,17 0,29 5,17 1,03 0,32
1536×1536 24,48 21,99 28,50 2,61 0,67 11,63 2,28 0,69
2048×2048 36,27 36,70 54,22 4,62 1,19 21,39 4,15 1,21
3072×3072 84,82 83,41 104,16 10,53 2,68 46,42 10,14 2,74
4096×4096 150,31 152,21 203,18 18,64 4,75 88,67 16,42 4,80

Obrázek 7: Porovnání doby výpočtu Mandelbrotovy množiny všemi sedmi variantami: CPython 2, CPython 3, Jython, RPython, ANSI C, Cython bez type hintů, Cython s type hinty a plně optimalizovaný kód v Cythonu.

Obrázek 8: Porovnání doby výpočtu Mandelbrotovy množiny RPythonem, Cythonem (bez i s type hinty + plně optimalizovaná varianta) a verzí naprogramovanou přímo v ANSI C.

18. Repositář s demonstračními příklady

Všechny demonstrační příklady, které jsme si v dnešním článku ukázali, naleznete na adrese https://github.com/tisnik/cython-examples. Následují odkazy na jednotlivé příklady (pro jejich spuštění je nutné mít nainstalován Cython a jeho závislosti, především tedy překladač céčka a taktéž vývojové varianty knihoven pro Python včetně jejich hlavičkových souborů):

20. Odkazy na Internetu

  1. Cython (home page)
    http://cython.org/
  2. Cython (wiki)
    https://github.com/cython/cython/wiki
  3. Cython (Wikipedia)
    https://en.wikipedia.org/wiki/Cython
  4. Cython (GitHub)
    https://github.com/cython/cython
  5. Python Implementations: Compilers
    https://wiki.python.org/mo­in/PythonImplementations#Com­pilers
  6. EmbeddingCython
    https://github.com/cython/cyt­hon/wiki/EmbeddingCython
  7. The Basics of Cython
    http://docs.cython.org/en/la­test/src/tutorial/cython_tu­torial.html
  8. Overcoming Python's GIL with Cython
    https://lbolla.info/python-threads-cython-gil
  9. GlobalInterpreterLock
    https://wiki.python.org/mo­in/GlobalInterpreterLock
  10. The Magic of RPython
    https://refi64.com/posts/the-magic-of-rpython.html
  11. RPython: Frequently Asked Questions
    http://rpython.readthedoc­s.io/en/latest/faq.html
  12. RPython’s documentation
    http://rpython.readthedoc­s.io/en/latest/index.html
  13. RPython (Wikipedia)
    https://en.wikipedia.org/wi­ki/PyPy#RPython
  14. Getting Started with RPython
    http://rpython.readthedoc­s.io/en/latest/getting-started.html
  15. PyPy (home page)
    https://pypy.org/
  16. PyPy (dokumentace)
    http://doc.pypy.org/en/latest/
  17. Localized Type Inference of Atomic Types in Python (2005)
    http://citeseer.ist.psu.e­du/viewdoc/summary?doi=10­.1.1.90.3231
  18. Numba
    http://numba.pydata.org/
  19. Tutorial: Writing an Interpreter with PyPy, Part 1
    https://morepypy.blogspot­.com/2011/04/tutorial-writing-interpreter-with-pypy.html
  20. List of numerical analysis software
    https://en.wikipedia.org/wi­ki/List_of_numerical_analy­sis_software
  21. Pixie: lehký skriptovací jazyk s „kouzelnými“ schopnostmi
    https://www.root.cz/clanky/pixie-lehky-skriptovaci-jazyk-s-kouzelnymi-schopnostmi/
  22. Programovací jazyk Pixie: funkce ze základní knihovny a použití FFI
    https://www.root.cz/clanky/pro­gramovaci-jazyk-pixie-funkce-ze-zakladni-knihovny-a-pouziti-ffi/
  23. The future can be written in RPython now (článek z roku 2010)
    http://blog.christianpero­ne.com/2010/05/the-future-can-be-written-in-rpython-now/
  24. PyPy is the Future of Python (článek z roku 2010)
    https://alexgaynor.net/2010/ma­y/15/pypy-future-python/
  25. Portal:Python programming
    https://en.wikipedia.org/wi­ki/Portal:Python_programming
  26. RPython Frontend and C Wrapper Generator
    http://www.codeforge.com/ar­ticle/383293
  27. PyPy’s Approach to Virtual Machine Construction
    https://bitbucket.org/pypy/ex­tradoc/raw/tip/talk/dls2006/py­py-vm-construction.pdf
  28. Tutorial: Writing an Interpreter with PyPy, Part 1
    https://morepypy.blogspot­.com/2011/04/tutorial-writing-interpreter-with-pypy.html
  29. A simple interpreter from scratch in Python (part 1)
    http://www.jayconrod.com/posts/37/a-simple-interpreter-from-scratch-in-python-part-1
  30. Brainfuck Interpreter in Python
    https://helloacm.com/brainfuck-interpreter-in-python/
Našli jste v článku chybu?