Zajímavosti z C++: Optimalizace iterování přes standardní kontejnery

Dneska se podíváme na to, jak lze různými způsoby iterovat přes standardní kontejnery a jak si stojí tyto způsoby ve vzájemném porovnání z hlediska rychlosti. Mrkneme se i na to, co s tím dokáže udělat překladač při zapnutí optimalizací.

O co půjde?

Každý z vás má jistě svůj oblíbený způsob, jak iterovat přes standardní kontejnery. V tomto příspěvku bych chtěl ukázat, jaký může mít vliv použitého způsobu na rychlost programu a co s tím dokáže udělat překladač při zapnutých optimalizacích. Jelikož je standardních kontejnerů celá řada, zaměřím se pouze na std::vector<>, který je zřejmě nejpoužívanější. Všechny testy proběhly na systému s 64b Arch Linux, kernel 3.8.7, Intel Core i5 i5-661 3330 MHz, 16 GB RAM. Použitá verze gcc je 4.8.0 a libstdc++5 je ve verzi 3.3.6-4. Použité parametry při překladu jsou -std=c++11 -pedantic. Všechny testy proběhly pětkrát za sebou a jejich čas byl zprůměrován.

Jakými způsoby iterovat přes std::vector<>?

Mějme následující vektor, který inicializujeme velkým počtem nul (abychom měli přes co iterovat a zmenšili statistické nepřesnosti):

vector<int> v(500000000, 0);

První způsob iterace je asi nejběžněji používaný a všichni jej znáte:

// (1)
for (vector<int>::iterator i = v.begin(); i != v.end(); i++) {
    *i = 5;
}

Pro jednoduchost jediné, co budu při iterování dělat, je umístění čísla 5 do všech prvků vektoru (ano, toto by rozhodně šlo udělat hned při konstrukci, ale o to nejde). Když program přeložíme výše zmíněným gcc s -O0 (bez optimalizací), tak ona iterace trvá 9.39 sekund. Zatím není s čím srovnat, takže těžko říct, zda je to moc, či málo. Vstupní vektor je dost velký, takže možná je to akorát.

Jak by to šlo urychlit? První věc je, že místo i++ použijeme ++i:

// (2)
for (vector<int>::iterator i = v.begin(); i != v.end(); ++i) {
    *i = 5;
}

Po přeložení s -O0 a spuštění dostaneme čas 7.61 sekund. Jak to? Důvodem je, že i++ musí udělat to, že si uloží kopii aktuálního iterátoru, provede inkrementaci, a vrátí uložený iterátor. Prefixová verze ++i provede inkrementaci a vrátí inkrementovaný iterátor, takže není potřeba vytvářet kopii.

Šlo by s tím udělat něco víc? Ano, šlo. Místo toho, abychom neustále volali v.end(), tak si jeho výsledek uložíme do proměnné:

// (3)
for (vector<int>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
    *i = 5;
}

Po přeložení s -O0 a spuštění se dostaneme na čas 4.52 sekund, což je méně než polovina původního času. Přitom jsme kód nijak neznečitelnili -- tento způsob iterace je často používaný idiom iterace přes kontejnery v C++.

Jelikož se jedná o std::vector<>, který umožňuje náhodný přístup, pojďme ještě zkusit, co se stane, když místo iterátorů použijeme indexy:

// (4)
for (vector<int>::size_type i = 0, e = v.size(); i < e; ++i) {
    v[i] = 5;
}

Dostaneme se na čas 2.99 sekund. Může za to skutečnost, že nyní není třeba vytvářet a aktualizovat žádné iterátory, pouze jeden int. Už to ale není tak obecné, takže tento přístup si typicky neužijete u jiných kontejnerů.

Když už jsme u C++, tak od C++11 máme možnost použít tzv. foreach verzi for cyklu. Zkusme to, co to udělá s časem:

// (5)
for (int &i : v) {
    i = 5;
}

Tato iterace trvá 4.78 sekund, což je nepatrně pomalejší, než verze (3). Je ale přehlednější.

Jsou zde i další způsoby, jak iterovat. Jeden je s použitím BOOST_FOREACH, další s použitím funkcí ze standardní knihovny, jako je std::for_each>. Ty jsem z porovnání vynechal. Kdo by měl zájem, tak si to může vyzkoušet.

Co s tím udělají optimalizace překladače?

Jak jsme mohli vidět, tak vhodným iterováním lze ušetřit až dvě třetiny času. V předchozí části jsme ale překládali bez optimalizací (-O0). Pojďme se podívat, co s tím udělají optimalizace překladače. Vyzkoušel jsem různé úrovně optimalizací a výsledky shrnul do následující tabulky:

gcc

Co je nejzajímavější a možná až šokující, tak je to, že jakmile povolíme překladači optimalizace, tak je naprosto jedno, který ze způsobů použijeme (minimálně teda v našem příkladu) -- výsledek je prakticky totožný. Nicméně, pokud už budete manuálně iterovat přes kontejner, doporučuji v C++98 použít způsob (3) či od C++11 způsob (5). Je to přehledné a pokud nemáte povoleny optimalizace (typicky při vývoji a překladu s ladicími informacemi), tak nebudete svůj program zbytečně zpomalovat.

Bylo by zajímavé vyzkoušet i jiné kontejnery ze standardní knihovny a zjistit, zda se s nimi dokáže překladač při povolených optimalizacích taky tak dobře poprat, jako u vektoru.

A co na to clang?

Kromě gcc jsem vyzkoušel i clang, konkrétně v aktuální verzi 3.2. Výsledky jsou uvedeny v následující tabulce:

clang

Vidíme, že clang je prakticky jednou tak pomalý jako gcc. Co je dále zajímavé, tak je to, že drastické urychlení se u clangu dosáhlo až při použití -O2. Ono zpomalení oproti gcc si vysvětluji tím, že clang není ještě tak promakaný co se týče překladu C++. Pokud víte o korektnějším důvodu, určitě se zmiňte do komentáře, zajímalo by mě to.