Hlavní navigace

Skrytá úskalí vícenásobné dědičnosti v C++

7. 5. 2012 0:13 (aktualizováno) | Ondřej Novák

Upozorňuji dopředu, že nehodlám zde probírat to, co všichni programátoři v C++ určitě znají a co si mohou přečíst na milionech stránkách, které nabídne google. Myslím tím zejména ony problémy s diamantovým děděním a jak správně pracovat s virtuální dědičností. Při práci s generikou, kdy se hojně používají „prázdné třídy“ časem narazíme na další komplikaci, které i zkušeného programátora překvapí a možná mu trošku zkomplikují život. 

Prázdná třída

V generickém programování (to jsou takové ty programy, ve kterých se hojně vyskytuje klíčové slovo template) postupem času asi každý programátor nalezne zalíbení ve vytváření prázdných tříd. To jsou třídy, které obsahují deklarace, nebo definice metod, avšak neobsahují žádné proměnné, ani virtuální metody. Objekt takové třídy by ve skutečnosti neobsadil žádnou paměť, protože jeho instance vlastně nic neobsahuje. Velmi často používáme prázdné třídy k vytváření alokátorů nebo porovnávačů

class CmpItem {
public:
    bool operator()(const Item &a, const Item &b) const;
};
typedef std::set<Item, CmpItem> MujSet;

Kdo se s tím ještě nesetkal, toho překvapí, že dotaz na sizeof(CmpItem) vrátí hodnotu 1, ačkoliv třída je prázdná a neobsahuje jedinou proměnnou. Je to přitom záměr. Představte si, že by taková třída propadla zkrz parametr šablony do nějakého pole. Pokud by velikost třídy byla nastavena na nulu, všechny hodnoty v poli by měly stejnou adresu a pole by také mělo velikost 0 bajtů. Převod ukazatele na index pak nutně vede na dělení nulou. Tyto důvody a dalších N podobných komplikací (například, že dvě různé instance stejné třídy nesmějí sdílet stejnou adresu v paměti) vedly autory norem k pravidlu, že instance každé třídy musí alokovat vždy minimálně 1 bajt paměti. Stejně se například chová malloc(0) … alokuje 1 bajt a vrátí jeho adresu.

Prázdná třída a dědění

Pokud použijeme prázdnou třídu jako členskou proměnnou, zabere 1 bajt v rozvržení instance třídy. Pokud je taková proměnná umístěna mezi vícebajtové proměnné, které je třeba zarovnat na dělitelnou adresu, pak překladač za takovou proměnnou umístí povinný padding. Na 32bitové platformě to znamená, nikoliv 1 bajt, ale 4 bajty! Dost vyplýtvaného místa na prázdnou třídu nemyslíte?

Tomuto plýtvání lze zabránit tak, že namísto proměnné budeme prázdnou třídu dědit.

class A {};
class B {
    A a;
    int x;
};
 class C: public A {
   int x;
};

GCC vám řekne toto:

sizeof(A): 1
sizeof(B): 8
sizeof(C): 4

Račte si to vyzkoušet:  (codepad). Příklad krásně demonstruje to co jsem napsal. Proměnná a má skutečně velikost 1 a protože x musí být zarovnáno, je za proměnnou a doplněn padding. Instance třídy pak zabere 8 bajtů. Pokud však třídu A podědíme, zmenšíme velikost instance na poloviční velikost. Za třídu A si lze dosadit třídu dodanou šablonou, například výše uvedený příklad CmpItem, který může (ale nemusí) být deklarován prázdný (například při řazení indexů v databázi bude obsahovat odkaz na kontejner dat, jelikož index obsahuje pouze indexy … což jsou vlastně jen čísla, která bez odkazu na data nelze řadit).

Vícenásobná dědičnost.

Pokud máme možnost do šablony dodat jen jednu třídu, která může být (běžně) prázdná  (například CmpItem), lze to obejít děděním. Co když těch tříd máme víc? Můžeme použít vícenásobné dědění? Zdálo by se logické, že to bude fungovat obdobně.

Ve skutečnosti to je problém, protože to nezafunguje tak, jak bychom si představovali. Navíc se implementace liší podle platformy a překladače. K demonstraci jsem si připravil následující příklad:

#include <iostream>

class A1 {};

class A: public A1 {};

class B1 {};

class B: public A1, public B1 {};

class C1 {};

class C: public A1, public B1, public C1 {};

class D1 {};

class D: public A1, public B1, public C1, public D1 {};

class E1: public A1, public B1 {};

class E: public E1 {};

class F1: public A1, public B1 {};

class F: public E1, public F1 {};

class G1: public A {};

class G: public E1, public G1 {};

class H: public C, public D {};

class I: public H, public G {};

int main(int argc, char* argv[])
{
 std::cout << "sizeof(A): " << sizeof(A) << std::endl;
 std::cout << "sizeof(B): " << sizeof(B) << std::endl;
 std::cout << "sizeof(C): " << sizeof(C) << std::endl;
 std::cout << "sizeof(D): " << sizeof(D) << std::endl;
 std::cout << "sizeof(E): " << sizeof(E) << std::endl;
 std::cout << "sizeof(F): " << sizeof(F) << std::endl;
 std::cout << "sizeof(G): " << sizeof(G) << std::endl;
 std::cout << "sizeof(H): " << sizeof(H) << std::endl;
 std::cout << "sizeof(I): " << sizeof(I) << std::endl;
}

Výsledky, které vrací překladač od Microsoftu, Visual C++ 2008:

sizeof(A): 1
sizeof(B): 1
sizeof(C): 2
sizeof(D): 3
sizeof(E): 1
sizeof(F): 3
sizeof(G): 2
sizeof(H): 6
sizeof(I): 9

Jiná čísla vrací GCC

sizeof(A): 1
sizeof(B): 1
sizeof(C): 1
sizeof(D): 1
sizeof(E): 1
sizeof(F): 2
sizeof(G): 2
sizeof(H): 2
sizeof(I): 4

Rozebereme si nejprve výsledek od Microsoftu. Vzhledem k tomu, že jsem nikde nenašel oficiální popis, budu vycházet z mého pozorování. Podle všeho Visual C++ započítává každou další třídu, ze které se dědí, jako členskou proměnnou o jednom bajtě. To je krásně vidět na výsledcích pro třídy A – D. Zatímco třída A má velikost 1 „z povinnosti“, velikost třídy B je opravdu 1 bajt, protože pro dědění z B1 je tento bajt alokován. Přitom jde evidentně o zbytečnou operaci, protože obě podtřídy budou mít ukazatel stejné hodnoty. V případě třídy C je nutné započítat už dva bajty za dvě třídy navíc. Podobně je na tom třída D. Z další analýzy se zdá, že každá třída navíc navyšuje počet alokovaných adres pro prázdnou třídu. Aby jsme si udělali přehled, je nutné provést tranzitivní uzávěr celé hierarchie a označit si třídy, které jsou ve vícenásobné dědičnosti navíc. Rozepíšeme si třídu I:

I,H,G,C,D,E1,G1,A1,B1,C1,­A1,B1,C1,D1,A1,B1,A,A1

Tučně jsem označil třídy, které se nachází na druhém a dalším místě v deklaraci vícenásobné dědičnosti. Vidíte, že jich je devět, a z toho vyplývá devět alokovaných bajtů pro celou třídu I

Proč tohle Visual C++ dělá opravdu netuším. Ale podle mne se to možná vyjasní, pokud se podíváme na výsledek GCC. Podle mého názoru se Visual C++ snaží zabránit situaci, kdy některé třídy, které se v rozložené hierarchii opakují, by mohly sdílet stejnou adresu, přestože jde o různé instance… a jak víme, různé instance nesmějí mít stejnou adresu, viz první kapitola. Nicméně způsob, jakým se to řeší, není úplně nejšťastnější.

To GCC není vícenásobnou dědičností nijak rozhozeno a i pro třídu D vrací velikost 1. Teprve třída F, ve které se dvakrát vyskytují třídy A1 a B1 alokuje dvě adresy. Opět se podíváme na třídu I:

I,H,G,C,D,E1,G1,A1,B1,C1A1,B1,C1,D1,A1,B1,A,A1

Tady jsem podtrhl třídu A1, tučně označil třídu B1 a kurzívou třídu C1. Vidíte, že po rozbalení třídy I zde máme 4× třídu A1. Protože se nejedná o virtuální dědění, žádný diamant se zde nekoná, a třída A1 je zde zastoupena čtyřmi instancemi, kde každá instance by měla ležet na jiné adrese. Zajímavé je, že GCCčku není proti srsti, že stejnou adresu jako A1 bude pravděpodobně sdílet i B1. Jde vlastně o objekt A1,B1,C1, který dohromady může alokovat pouze jednu adresu. Jiný objekt A1, B1 okupuje druhou adresu, a tak dále. Rozložení podtříd do adres můžeme zobrazit třeba takto.

+0 I,G,G1,A,A1
+1 E1,A1,B1
+2 H,D,A1,B1,C1,D1
+3 C,A1,B1,C1

Neověřoval jsem to přesně, ale cílem je, aby se žádná třída neopakovala na jednom řádku. Samozřejmě, že celá problematika bude složitější v tom, že nestačí jen dodržet pravidlo nesdílení adresy pro stejné podtřídy, ale zároveň každá potřída musí fungovat samostatně, takže počet alokovaných adres může být i vyšší. Například, třída G alokuje 2 adresy, tedy musí alokovat offset 0 a offset 1. Třída H také alokuje 2 adresy, zbývají pro ně offset 2 a offset 3. Ostatní třídy alokují jednu adresu a tak se musí naskládat ke svým nadtřídám na každém řádku. Celé to pak tvoří třídu I, která začíná na offsetu 0 a zabírá 4 bajty.

Linuxovou verzi si můžete opět vyzkoušet na codepadu

Závěr

No na závěr bych napsal toto: Nepřehánět to s vícenásobnou dědičnosti. Pokud jsem si doposud šablony skládat přes vícenásobnou dědičnost do jedné souhrnné šablony, tak jsem si neuvědomoval tento problém a žil jsem v domění, že to překladač nějak dobře zoptimalizuje. Nedělo se tak. A tak se jednoho krásného dne stalo, že jsem objevil podivný padding u třídy ConstStrA, která by se dala zkráceně zapsat takto:

class ConstStrA {
public:
      const char *str;
      unsigned int length;
};

A ačkoliv z tohoto pohledu má mít třída pouhých 8 bajtů, ve skutečnosti má bajtů 16, protože není takto jednoduše deklarovaná, ale jedná se o kombinaci několik šablon (například lze změnit char za jiný typ, přes další šablonu se tam importuje rozhrani pro práci s řetězci). Výsledná třída má před první proměnnou 4 bajtový padding, a stejný padding se nachází na konci. To vše vytvořilo vícenásobné dědění prázdných tříd různě po cestě navěšených (a aby to nebylo všechno, při předávání instance třídy se všechny bajty, včetně nepoužívaného paddingu, poctivě kopírují na zásobník, Visual C++)

  • Pro představu složitosti, fragment třídy ConstStrA (ConstString<T>) jsem umístil na pasteBin: http://pastebin.com/i3gLRZrr. Už tady najdete důvod toho druhého zbytečného paddingu. A to nechtějte vidět, jak vypadá třída ArrayRef<> a kolik podtříd je v ní schováno.

Je hlavně podivné, jak vícenásobnou dědičnost řeší Microsoft Visual C++. Předpokládám, že v normě C++ není jasně definován layout tříd, které používají vícenásobnou dědičnost v souvislosti s prázdnými třídami. I z toho důvodu musí člověk být opatrný, pakliže chce prázdné třídy používat jako nástroj generického programování. Čas od času se mu může důsledek použitého návrhu šablony zásadně promítnout do výsledného kódu.