Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
ffredyk

[NÁVOD] Branchless programming

Recommended Posts

Admin

Nedávno jsem narazil na zajímavou problematiku, která se využívá při stavbě time-sensitive prostředí a šifrovacích algoritmů. Jde o tzv. branchless programming - tedy programování bez větví.

Toto téma je zajímavé hlavně pro ty z vás, jenž zaujme malá zajímavost o programování. V reálné praxi se tyto "triky" využívají jen pro šifrovací funkce a při programování grafických shaderů. Moderní kompilátory high-level jazyků jsou výbornými optimizéry - snaží se kompilovat co nejjednodušeji zchroupatelný kód pro procesory zvolené architektury. V praxi to znamená, že jsou schopny generický kód s podmínkami relativně dobře zhodnotit a podmínky rovnou přeložit jako jejich branchless verzi. Toto se ovšem týká jen jednodušších řešení, pro které branchless verze má nějaký smysl. 

Branchless programming není něco, co se musí, nebo mělo by se, striktně dodržovat - ba naopak, kompilátory ve většině případů dokáží nejlépe určit, zda-li je překládaný kód výkonnější v branchless verzi a rovnou jej tak přeloží. Při programování platí jednoduché pravidlo - programovat hlavně čitelně, optimalizovat až při potřebě rychlejšího výkonu. A před samotnou optimalizací (a případným branchless kodingem) zvážit, zda-li se zapsaný algoritmus nedá vyřešit efektivnějším způsobem.

Branch (větev, blok, sekce)

Kód se jakoukoliv podmínkou rozděluje a větví - každé této oddělené části, či bloku kódu se říká branch (neboli větev). 

if(something == 10)
{
  //Branch A
}
else
{
  //Branch B
}

Vzhledem ke způsobu funkci procesoru je každý branch zbytečná zátěž navíc - toto platí několikanásobně u GPU výpočtů, protože procesorová pipeline spouští několik instrukcí současně, tímto se mohou spouštět obě cesty podmínky zároveň a po vyhodnocení podmínky se všechny neplatné výpočty (branch, pro kterou není splněna podmínka) prostě zahodí. Aneb kompilátor vytvoří instrukce pro zhodnocení podmínky a v případě nepravdy "přeskočí" na jiný než následující řádek v kódu - toto je operace, která je pro procesor zbytečně vytěžující.

Branchless v praxi

Představme si následující funkci min() - která zjistí, které ze dvou předaných čísel je menší než druhé:

function min(int a, int b)
{
  if(a < b)
    return a; //Branch A
  else
    return b; //Branch B
}

A nyní její branchless verzi:

function min(int a, int b)
{
  return a*(a<b)+b*(b<=a);
}

Je trochu nečitelná, ale víceméně jednoduchá. Dle většiny programovacích jazyků, je tento zápis vyhodnocen například takto:

a = 4;
b = 6;

return (4*true) + (6*false) 
=
return (4*1) + (6*0)
=
return 4 + 0
=
return 4

Nejen, že jsme kompletně vynechali podmínku v kódu, ale také zkrátili funkci ze 4 řádků na jeden a celou operaci provedli jen matematickým výpočtem. 

Tato funkce je velmi jednoduchá operace, nicméně její branchless verze se na první pohled může zdát poměrně nečitelná - proto se překlad do těchto branchless funkcí nechává více-méně na kompilátorech, díky kterým můžeme psát čitelný kód a i přesto nám jej kompilátor přeloží v optimalizované verzi. S každou přibývající složitostí a komplexností je branchless kód nečitelnější a zamotanější. Například funkce pro přepis znaků řetězce na velká písmena:

function toUpper(string text)
{
  for(int i=0; i<text.length; i++)
  {
    text[i] -= 32 * (text[i] >= 97 && text[i] <= 122);
  }
  return text;
}

//97 = 'a'
//122 = 'z'
//32 = 'Z' - 'a' offset

Závěr

I přesto, že toto není návod, tak doufám, že jsem vám předal alespoň nějakou zajímavou informaci. Pokud se mi povedlo vás zaháčkovat a jste hladoví po dalších informacích, tak vám nabídnu další zdroje, ze kterých jsem čerpal při sepisování tohoto topicu. Branchless programming je zajímavá technika - zřídka kdy využitelná při běžné praxi, nicméně způsobů jak vyčarovat branchless verzi složitých funkcí, je nepřeberné kvantum.

Další zdroje:

https://stackoverflow.com/questions/6133322/what-does-a-branchless-if-in-c-look-like
https://hbfs.wordpress.com/2008/08/05/branchless-equivalents-of-simple-functions/
https://stackoverflow.com/questions/31897718/branchless-conditionals-on-integers-fast-but-can-they-be-made-faster
https://stackoverflow.com/questions/32107088/how-can-i-make-branchless-code

Sdílet tento příspěvek


Link to post
Share on other sites

Zajímavé, jen si říkám, že pokud se o to starají kompilery, tak proč se o to zbytečně zajímat, ale je fajn o tom vědět.

Nicméně k té radosti o zredukování řádků.. Oba způsoby jsou ve výsledku na jednom řádku, když to kompilátor pak minifikuje.
+ další řádky můžeš ušetřit tím, že budeš psát závorky na stejný řádek 😄 
 

function min(int a, int b) {
  return a*(a<b)+b*(b<=a);
}

– ejhle, o řádek méně! 😄 

Sdílet tento příspěvek


Link to post
Share on other sites
Admin
Author of the topic Odesláno před

V tomto právěže nejde o krácení řádků high-level kódu, nýbrž právě o zkrácení počtu instrukcí procesoru (assembler) a vyhnutí se instrukcím jenž přeskakují v kódu (jump), které jsou pro zpracování nejnáročnější :)

Sdílet tento příspěvek


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Zde můžete odpovědět na toto téma...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Obnovili jsme váš původní obsah (obsah napsaný před zavřením).   Smazat obnovený obsah

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...