Algoritmická účinnost - Algorithmic efficiency
Ve výpočetní technice je algoritmická účinnost vlastností algoritmu, který souvisí s množstvím výpočetních zdrojů použitých algoritmem. Algoritmus musí být analyzován, aby se určilo jeho využití zdrojů, a účinnost algoritmu lze měřit na základě využití různých zdrojů. Algoritmickou účinnost lze považovat za analogickou s produktivní produktivitou opakujícího se nebo kontinuálního procesu.
Pro maximální efektivitu chceme minimalizovat využití zdrojů. Různé zdroje, jako je časová a prostorová složitost, však nelze přímo porovnávat, takže který ze dvou algoritmů je považován za účinnější, často závisí na tom, které měřítko účinnosti je považováno za nejdůležitější.
Například třídění bublin a timsort jsou oba algoritmy pro třídění seznamu položek od nejmenšího po největší. Třídění podle bublin třídí seznam v čase úměrném počtu prvků na druhou ( viz Big O notace ), ale vyžaduje pouze malé množství extra paměti, která je konstantní vzhledem k délce seznamu ( ). Timsort seřadí seznam podle lineárního času (úměrný množství a jeho logaritmu) podle délky seznamu ( ), ale v délce seznamu ( ) má lineární požadavek na prostor . Pokud musí být velké seznamy pro danou aplikaci tříděny vysokou rychlostí, je timsort lepší volbou; Pokud je však důležitější minimalizovat paměťovou stopu třídění, je lepší volbou bublinové třídění.
Pozadí
Důležitost účinnosti s ohledem na čas zdůraznila Ada Lovelace v roce 1843, když se vztahovala na mechanický analytický stroj Charlese Babbage :
„Téměř v každém výpočtu je možná široká škála uspořádání pro posloupnost procesů a jejich výběr musí být ovlivněn různými hledisky pro účely výpočetního motoru. Jedním z hlavních cílů je zvolit takové uspořádání, které bude mít tendenci se redukovat na minimální doba nutná k dokončení výpočtu "
Časné elektronické počítače byly vážně omezeny jak rychlostí operací, tak množstvím dostupné paměti. V některých případech bylo zjištěno, že došlo k časoprostorovému kompromisu , kdy bylo možné úkol zvládnout buď pomocí rychlého algoritmu, který používal poměrně hodně pracovní paměti, nebo pomocí pomalejšího algoritmu, který používal velmi málo pracovní paměti . Inženýrským kompromisem bylo poté použít nejrychlejší algoritmus, který by se vešel do dostupné paměti.
Moderní počítače jsou výrazně rychlejší než starší počítače a mají k dispozici mnohem větší množství paměti ( gigabajty místo kilobajtů ). Donald Knuth nicméně zdůraznil, že efektivita je stále důležitým hlediskem:
„V zavedených technických oborech se 12% zlepšení, snadno dosažitelné, nikdy nepovažuje za marginální a věřím, že stejný názor by měl převládat i v softwarovém inženýrství“
Přehled
Algoritmus je považován za efektivní, pokud jeho spotřeba zdrojů, známá také jako výpočetní náklady, je na nebo pod určitou přijatelnou úrovní. Zhruba řečeno, „přijatelné“ znamená: bude to běžet v rozumném množství času nebo prostoru na dostupném počítači, obvykle jako funkce velikosti vstupu. Od 50. let 20. století počítače zaznamenaly dramatický nárůst jak dostupného výpočetního výkonu, tak dostupného množství paměti, takže současná přijatelná úroveň by byla nepřijatelná i před 10 lety. Díky přibližně dvojnásobnému zdvojnásobení výkonu počítače každé 2 roky mohly být úkoly, které jsou na moderních smartphonech a vestavěných systémech přijatelně efektivní, pro průmyslové servery před 10 lety nepřijatelně neúčinné .
Výrobci počítačů často vydávají nové modely, často s vyšším výkonem . Náklady na software mohou být poměrně vysoké, takže v některých případech může být nejjednodušší a nejlevnější způsob, jak dosáhnout vyššího výkonu, koupit si rychlejší počítač, pokud je kompatibilní se stávajícím počítačem.
Existuje mnoho způsobů, jak lze měřit prostředky používané algoritmem: dvě nejběžnější měřítka jsou rychlost a využití paměti; další opatření by mohla zahrnovat přenosovou rychlost, dočasné využití disku, dlouhodobé využití disku, spotřebu energie, celkové náklady na vlastnictví , dobu odezvy na vnější podněty atd. Mnoho z těchto opatření závisí na velikosti vstupu do algoritmu, tj. množství zpracovávaných údajů. Mohou také záviset na způsobu, jakým jsou data uspořádána; například některé algoritmy řazení fungují špatně u dat, která jsou již tříděna nebo která jsou tříděna v opačném pořadí.
V praxi existují další faktory, které mohou ovlivnit účinnost algoritmu, například požadavky na přesnost a / nebo spolehlivost. Jak je podrobně popsáno níže, způsob implementace algoritmu může mít také významný vliv na skutečnou účinnost, ačkoli mnoho aspektů se týká problémů s optimalizací .
Teoretická analýza
V teoretické analýze algoritmů je běžnou praxí odhadnout jejich složitost v asymptotickém smyslu. Nejčastěji se používá notace popsat spotřebu zdrojů nebo „složitost“ je Donald Knuth je velký O notace , což představuje složitost algoritmu v závislosti na velikosti vstupu . Big O notace je asymptotická míra složitosti funkce, kde zhruba znamená, že časová náročnost algoritmu je úměrná , přičemž vynechává výrazy nižšího řádu, které přispívají méně než k růstu funkce, jak roste libovolně velká . Tento odhad může být zavádějící, když je malý, ale je obecně dostatečně přesný, když je velký, protože notace je asymptotická. Například třídění bublin může být rychlejší než sloučení, když má být tříděno pouze několik položek; je však pravděpodobné, že buď implementace splní požadavky na výkon malého seznamu. Programátoři se obvykle zajímají o algoritmy, které se efektivně rozšiřují na velké vstupní velikosti, a pro seznamy délky, které se vyskytují ve většině datově náročných programů, se upřednostňuje sloučení řazení před bublinovým.
Některé příklady notace Big O aplikované na asymptotickou časovou složitost algoritmů zahrnují:
Zápis | název | Příklady |
---|---|---|
konstantní | Hledání mediánu z seřazeného seznamu měření; Použití vyhledávací tabulky s konstantní velikostí ; Použití vhodné hashovací funkce k vyhledání položky. | |
logaritmický | Nalezení položky v seřazeném poli s binárním prohledáváním nebo vyváženým vyhledávacím stromem , stejně jako se všemi operacemi v binomické haldě . | |
lineární | Nalezení položky v netříděném seznamu nebo v nesprávně tvarovaném stromu (nejhorší případ) nebo v netříděném poli; Přidání dvou n -bitových celých čísel pomocí zvlnění . | |
lineární , loglineární nebo kvazilineární | Provádění rychlé Fourierovy transformace ; heapsort , quicksort ( nejlepší a průměrný případ ) nebo sloučení | |
kvadratický | Vynásobení dvou n -místných čísel jednoduchým algoritmem ; třídění podle bublin (nejhorší případ nebo naivní implementace), řazení podle prostředí , quicksort ( nejhorší případ ), řazení podle výběru nebo vložení | |
exponenciální | Nalezení optimálního (ne přibližné řešení) k problému obchodního cestujícího pomocí dynamické programování ; určení, zda jsou dva logické příkazy ekvivalentní pomocí vyhledávání hrubou silou |
Benchmarking: měření výkonu
U nových verzí softwaru nebo za účelem srovnání s konkurenčními systémy se někdy používají měřítka , která pomáhají s měřením relativního výkonu algoritmů. Pokud je například vytvořen nový třídicí algoritmus , může být porovnán s jeho předchůdci, aby bylo zajištěno, že je přinejmenším efektivní jako dříve se známými daty, s přihlédnutím k funkčním vylepšením. Referenční hodnoty mohou zákazníci použít při porovnávání různých produktů od alternativních dodavatelů k odhadu, který produkt bude nejlépe vyhovovat jejich konkrétním požadavkům z hlediska funkčnosti a výkonu. Například ve světě sálových počítačů některé proprietární třídicí produkty od nezávislých softwarových společností, jako je Syncsort, soutěží o rychlost s produkty od hlavních dodavatelů, jako je IBM .
Některá měřítka poskytují příležitosti pro vypracování analýzy porovnávající relativní rychlost různých kompilovaných a interpretovaných jazyků, například The Computer Language Benchmarks Game porovnává výkon implementací typických programovacích problémů v několika programovacích jazycích.
Dokonce i vytváření referenčních hodnot „ udělej si sám “ může demonstrovat relativní výkon různých programovacích jazyků pomocí různých kritérií specifikovaných uživatelem. To je docela jednoduché, jak ukazuje příklad „Shrnutí devíti jazykových výkonů“ od Christophera W. Cowell-Shaha.
Obavy z provádění
Problémy s implementací mohou mít také vliv na efektivitu, jako je volba programovacího jazyka nebo způsob, jakým je algoritmus ve skutečnosti kódován, nebo volba kompilátoru pro konkrétní jazyk, nebo použité možnosti kompilace , nebo dokonce provozní používaný systém . V mnoha případech může být jazyk implementovaný tlumočníkem mnohem pomalejší než jazyk implementovaný kompilátorem. Podívejte se na články o kompilaci just-in-time a interpretovaných jazycích .
Existují další faktory, které mohou ovlivnit problémy s časem nebo prostorem, ale které mohou být mimo kontrolu programátora; mezi ně patří zarovnání dat , datový granularity , vyrovnávací lokalitu , koherence cache , odvoz odpadu , na úrovni instrukcí paralelismus , multi-threading (buď v hardware nebo softwarové úrovni), simultánní multitasking a podprogram volání.
Některé procesory mají možnosti pro vektorové zpracování , které umožňují jediné instrukci pracovat na více operandech ; pro programátora nebo kompilátor může nebo nemusí být snadné tyto funkce použít. Algoritmy určené pro sekvenční zpracování může být nutné zcela přepracovat, aby bylo možné využívat paralelní zpracování , nebo je lze snadno překonfigurovat. Vzhledem k tomu, že na konci roku 2010 nabývá na významu paralelní a distribuovaná výpočetní technika , investuje se více investic do efektivních rozhraní API na vysoké úrovni pro paralelní a distribuované výpočetní systémy, jako jsou CUDA , TensorFlow , Hadoop , OpenMP a MPI .
Dalším problémem, který může nastat při programování, je to, že procesory kompatibilní se stejnou sadou instrukcí (například x86-64 nebo ARM ) mohou implementovat instrukci různými způsoby, takže instrukce, které jsou u některých modelů relativně rychlé, mohou být u jiných modelů relativně pomalé. . To často představuje výzvy pro optimalizaci překladačů , které musí mít velké množství znalostí o konkrétním CPU a dalším hardwaru dostupném v cíli kompilace, aby co nejlépe optimalizovaly výkon programu. V extrémním případě může být kompilátor vynucen emulovat pokyny, které nejsou podporovány na cílové platformě kompilace, nutit jej ke generování kódu nebo propojení externího volání knihovny za účelem vytvoření výsledku, který je na této platformě jinak nekompatibilní, i když je nativně podporován a efektivnější v hardwaru na jiných platformách. To je často případ vestavěných systémů, pokud jde o aritmetiku s plovoucí desetinnou čárkou , kde malým a nízkoenergetickým mikrokontrolérům často chybí hardwarová podpora pro aritmetiku s plovoucí desetinnou čárkou, a proto k výpočtu výpočtů s plovoucí desetinnou čárkou vyžadují výpočetně nákladné softwarové rutiny.
Míry využití zdrojů
Míry jsou obvykle vyjádřeny jako funkce velikosti vstupu .
Dvě nejběžnější opatření jsou:
- Čas : jak dlouho trvá dokončení algoritmu?
- Prostor : kolik pracovní paměti (obvykle RAM) potřebuje algoritmus? To má dva aspekty: množství paměti potřebné pro kód (využití pomocného prostoru) a množství paměti potřebné pro data, na kterých kód pracuje (využití vnitřního prostoru).
U počítačů, jejichž energii dodává baterie (např. Notebooky a smartphony ), nebo pro velmi dlouhé / velké výpočty (např. Superpočítače ), jsou další zajímavá opatření:
- Přímá spotřeba energie : energie potřebná přímo k provozu počítače.
- Nepřímá spotřeba energie : energie potřebná k chlazení, osvětlení atd.
Od roku 2018 roste spotřeba energie jako důležitá metrika pro výpočetní úlohy všech typů a ve všech měřítcích, od vestavěných zařízení typu internet věcí, přes zařízení na čipu po serverové farmy . Tento trend se často označuje jako zelený výpočet .
V některých případech mohou být relevantní i méně běžná opatření výpočetní účinnosti:
- Velikost přenosu : Šířka pásma může být omezujícím faktorem. Pomocí datové komprese lze snížit množství přenášených dat. Zobrazení obrázku nebo obrázku (např. Loga Google ) může vést k přenosu desítek tisíc bajtů (v tomto případě 48 kB) ve srovnání s přenosem šesti bajtů pro text „Google“. To je důležité pro výpočetní úlohy vázané na I / O.
- Externí prostor : místo potřebné na disku nebo jiném externím paměťovém zařízení; to může být pro dočasné úložiště, zatímco se algoritmus provádí, nebo to může být dlouhodobé úložiště, které je třeba převést pro budoucí potřebu.
- Doba odezvy ( latence ): toto je zvláště důležité v aplikaci v reálném čase, když musí počítačový systém rychle reagovat na nějakou externí událost .
- Celkové náklady na vlastnictví : zejména pokud je počítač vyhrazen jednomu konkrétnímu algoritmu.
Čas
Teorie
Analyzujte algoritmus, obvykle pomocí analýzy časové složitosti, abyste získali odhad doby chodu jako funkci velikosti vstupních dat. Výsledek je obvykle vyjádřen pomocí Big O notace . To je užitečné pro porovnání algoritmů, zvláště když se má zpracovat velké množství dat. Pokud je množství dat malé, jsou zapotřebí podrobnější odhady k porovnání výkonu algoritmu, i když to bude pravděpodobně méně důležité. Algoritmy, které zahrnují paralelní zpracování, může být obtížnější analyzovat .
Praxe
Použijte měřítko k načasování použití algoritmu. Mnoho programovacích jazyků má k dispozici funkci, která zajišťuje využití času CPU . U dlouhotrvajících algoritmů by mohl být zajímavý také uplynulý čas. Výsledky by obecně měly být zprůměrovány několika testy.
Run-based profiling může být velmi citlivý na hardwarovou konfiguraci a možnost dalších programů nebo úkolů běžících současně v prostředí s více procesy a s více programy .
Tento druh testu také silně závisí na výběru konkrétního programovacího jazyka, kompilátoru a možností kompilátoru, takže porovnávané algoritmy musí být implementovány za stejných podmínek.
Prostor
Tato část se zabývá využitím paměťových prostředků ( registry , mezipaměť , RAM , virtuální paměť , sekundární paměť ) během provádění algoritmu. Pokud jde o časovou analýzu uvedenou výše, analyzujte algoritmus, obvykle pomocí analýzy složitosti prostoru k získání odhadu run-time paměti potřebné jako funkce jako velikost vstupních dat. Výsledek je obvykle vyjádřen pomocí Big O notace .
Je třeba zvážit až čtyři aspekty využití paměti:
- Množství paměti potřebné k uložení kódu algoritmu.
- Množství paměti potřebné pro vstupní data .
- Množství paměti potřebné pro všechna výstupní data .
- Některé algoritmy, například třídění, často mění uspořádání vstupních dat a nepotřebují žádný další prostor pro výstupní data. Tato vlastnost se nazývá „ na místě provozu“.
- Množství paměti potřebné jako pracovní prostor během výpočtu.
- To zahrnuje lokální proměnné a všechny stack prostor potřebný podle rutiny se nazývají při výpočtu; tento prostor zásobníku může být významný pro algoritmy, které používají rekurzivní techniky.
Starší elektronické počítače a starší domácí počítače měly relativně malé množství pracovní paměti. Například automatická kalkulačka Electronic Delay Storage Automatic Calculator (EDSAC) z roku 1949 měla maximální pracovní paměť 1024 17bitových slov, zatímco model Sinclair ZX80 z roku 1980 přišel původně s 1024 8bitovými bajty pracovní paměti. Na konci 2010 je pro osobní počítače typické mít 4 až 32 GB RAM, což je nárůst o více než 300 milionůkrát větší paměť.
Ukládání do mezipaměti a hierarchie paměti
Současné počítače mohou mít relativně velké množství paměti (možná gigabajty), takže nutnost vtesnat algoritmus do omezeného množství paměti je mnohem menší problém, než tomu bylo dříve. Přítomnost čtyř různých kategorií paměti však může být významná:
- Registry procesoru , nejrychlejší z technologií počítačové paměti s nejmenším množstvím úložného prostoru. Většina přímých výpočtů na moderních počítačích probíhá u zdrojových a cílových operandů v registrech, než je v případě potřeby aktualizována do mezipaměti, hlavní paměti a virtuální paměti. Na jádře procesoru jsou obvykle řádově stovky bajtů nebo méně dostupnosti registrů, ačkoli soubor registru může obsahovat více fyzických registrů než architektonické registry definované v architektuře sady instrukcí.
- Mezipaměť je druhá nejrychlejší a druhá nejmenší paměť dostupná v hierarchii paměti. Mezipaměti jsou přítomny v procesorech, GPU, jednotkách pevného disku a externích periferních zařízeních a jsou obvykle implementovány ve statické paměti RAM . Mezipaměti paměti jsou víceúrovňové ; nižší úrovně jsou větší, pomalejší a obvykle sdílené mezi jádry procesorů ve vícejádrových procesorech . Aby bylo možné zpracovat operandy v mezipaměti, musí procesorová jednotka načíst data z mezipaměti, provést operaci v registrech a zapsat data zpět do mezipaměti. Funguje při rychlostech srovnatelných (přibližně 2–10krát pomalejší) s aritmetickou logickou jednotkou CPU nebo GPU nebo jednotkou s plovoucí desetinnou čárkou, pokud je v mezipaměti L1 . Je to asi 10krát pomalejší, pokud existuje mezipaměť L1 a musí být načtena z mezipaměti L2 a zapsána do mezipaměti L2 , a dalších 10krát pomalejší, pokud chybí mezipaměť L2 a musí být načtena z mezipaměti L3 , pokud současnost, dárek.
- Hlavní fyzická paměť je nejčastěji implementována v dynamické paměti RAM (DRAM). Hlavní paměť je mnohem větší (obvykle gigabajty ve srovnání s ≈ 8 megabajty ) než mezipaměť procesoru L3, čekací doba pro čtení a zápis je obvykle 10–100krát pomalejší. Od roku 2018 je RAM stále více implementována na čipu procesorů, jako CPU nebo GPU paměť .
- Virtuální paměť je nejčastěji implementována z hlediska sekundárního úložiště , jako je pevný disk , a je rozšířením hierarchie paměti, která má mnohem větší úložný prostor, ale mnohem větší latenci, obvykle asi 1000krát pomalejší než mezipaměť pro hodnotu v paměti RAM . Zatímco původně byla motivována k vytvoření dojmu, že je k dispozici větší množství paměti, než bylo skutečně k dispozici, virtuální paměť je v současném použití důležitější pro svůj časoprostorový kompromis a umožnění využití virtuálních strojů . Chybějící mezipaměti z hlavní paměti se nazývají chyby stránky a v programech jim hrozí velké výkonnostní tresty.
Algoritmus, jehož paměťové potřeby se vejdou do mezipaměti, bude mnohem rychlejší než algoritmus, který se vejde do hlavní paměti, což bude zase mnohem rychlejší než algoritmus, který se musí uchýlit k virtuální paměti. Z tohoto důvodu jsou zásady nahrazení mezipaměti pro vysoce výkonné výpočty nesmírně důležité, stejně jako programování a vyrovnání dat založené na mezipaměti . Aby se problém ještě více komplikoval, některé systémy mají až tři úrovně mezipaměti s různou efektivní rychlostí. Různé systémy budou mít různé množství těchto různých typů paměti, takže účinek potřeb paměti algoritmu se může u jednotlivých systémů velmi lišit.
V raných dobách elektronického výpočtu, pokud by se algoritmus a jeho data nevejde do hlavní paměti, pak by algoritmus nemohl být použit. V dnešní době se zdá, že využití virtuální paměti poskytuje mnoho paměti, ale za cenu výkonu. Pokud se algoritmus a jeho data vejdou do mezipaměti, lze dosáhnout velmi vysoké rychlosti; v tomto případě také minimalizace prostoru pomůže minimalizovat čas. Tomu se říká princip lokality a lze jej rozdělit na referenční lokalitu , prostorovou lokalitu a dočasnou lokalitu . Algoritmus, který se úplně nevejde do mezipaměti, ale který vykazuje referenční lokalitu, může fungovat poměrně dobře.
Kritika současného stavu programování
- David May FRS je britský počítačový vědec a v současné době profesorem a informatiky na University of Bristol a zakladatel a CTO ve XMOS Semiconductor , věří jeden z problémů je, že existuje závislost na Moorův zákon řešit neefektivnost. Postoupil jako „alternativa“ k Moorovu zákonu ( Mayův zákon ), který zní následovně:
Účinnost softwaru se každých 18 měsíců snižuje na polovinu, což kompenzuje Mooreův zákon
- May dále uvádí:
V všudypřítomných systémech může polovina provedených pokynů zdvojnásobit výdrž baterie a velké datové sady přinášejí velké příležitosti pro lepší software a algoritmy: Snížení počtu operací z N x N na N x log (N) má dramatický efekt, když je N velké ... pro N = 30 miliard je tato změna stejně dobrá jako 50 let technologických vylepšení.
- Autor softwaru Adam N. Rosenburg ve svém blogu „ Selhání digitálního počítače “ popsal současný stav programování jako blížící se „horizontu softwarových událostí“ (narážce na fiktivní „ horizont událostí obuvi “ popsaný Douglasem Adamsem v jeho Stopařův průvodce po Galaxii ). Odhaduje, že od 80. let došlo ke ztrátě 70 dB faktoru produktivity neboli „99,99999% jeho schopnosti dodávat zboží“ - „Když Arthur C. Clarke porovnal realitu výpočtu v roce 2001 s počítačem HAL 9000 v jeho kniha 2001: Vesmírná odysea poukázal na to, jak úžasně malé a výkonné počítače byly, ale jak zklamáním se stalo programování v počítači “.
Soutěže o nejlepší algoritmy
Následující soutěže vyzývají k zadání nejlepších algoritmů na základě libovolných kritérií, o nichž rozhodnou rozhodčí:
Viz také
- Analýza algoritmů - jak určit zdroje potřebné pro algoritmus
- Aritmetické kódování - forma entropického kódování s proměnnou délkou pro efektivní kompresi dat
- Asociativní pole - datová struktura, kterou lze zefektivnit pomocí stromů Patricia nebo polí Judy
- Benchmark - metoda pro měření srovnávacích časů provádění v definovaných případech
- Nejlepší, nejhorší a průměrný případ - úvahy pro odhad doby provádění ve třech scénářích
- Algoritmus binárního vyhledávání - jednoduchá a efektivní technika prohledávání seřazených polí
- Tabulka větví - technika snižování délky cesty instrukcí, velikosti strojového kódu (a často i paměti)
- Srovnání paradigmat programování - aspekty výkonu specifické pro parametry
- Optimalizace kompilátoru - optimalizace odvozená z kompilátoru
- Výpočetní složitost matematických operací
- Teorie výpočetní složitosti
- Výkon počítače - metriky hardwaru počítače
- Komprese dat - snížení šířky pásma přenosu a úložiště disku
- Databázový index - datová struktura, která zvyšuje rychlost operací načítání dat v databázové tabulce
- Entropické kódování - efektivní kódování dat s využitím frekvence výskytu řetězců jako kritéria pro náhradu
- Sběr odpadu - automatické uvolnění paměti po použití
- Zelené počítače - krok k implementaci „zelenějších“ technologií, které spotřebovávají méně zdrojů
- Huffmanův algoritmus - algoritmus pro efektivní kódování dat
- Zlepšení výkonu spravovaného kódu - knihovna Microsoft MSDN
- Lokalita reference - pro zamezení zpoždění ukládání do mezipaměti způsobeného přístupem do jiné než místní paměti
- Optimalizace smyčky
- Správa paměti
- Optimalizace (informatika)
- Analýza výkonu - metody měření skutečného výkonu algoritmu za běhu
- Výpočet v reálném čase - další příklady časově důležitých aplikací
- Analýza běhu - odhad očekávané doby běhu a škálovatelnost algoritmu
- Simultánní multithreading
- Algoritmus řazení § Porovnání algoritmů
- Spekulativní provedení nebo provedení Eager
- Větev predikce
- Supervlákno
- Kód se závitem - podobně jako tabulka virtuálních metod nebo tabulka větví
- Virtuální tabulka metod - oborová tabulka s dynamicky přiřazenými ukazateli pro odeslání