[NÁVOD] Branchless programming

[ffredyk 164]

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

[Fakerko_ 187]

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ě! 😄 

[ffredyk 164]

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ší

[ffredyk 164]

Zajímavé je, že jakmile jsem se o tomto tématu dozvěděl a následně napsal tento topic, tak mi utkvělo v paměti to nutkání psát co nejméně podmínek, či strukturovat kód tak, aby spouštěl co nejméně podmínek :D

Přidám ještě jednu libůstku - věděli jste, že krátká verze inkrementace a dekrementace je rychlejší ve formátu ++i než i++ ?

• ++i totiž rovnou inkrementuje proměnnou
• i++ ji načte do bufferu, vrátí tam kde je potřeba ji přečíst a až poté ji inkrementuje a vrátí do paměti

EDIT: Nebo spíš tedy načte do bufferu, poté inkrementuje v paměti a vrátí buffer - aby to dávalo programově smysl :D

[Hip 189]

Hehe, já se snažím automaticky obejít podmínky. Používám hodně streamy a skoro žádný proměnný. Vše direct do fce. Jednou jsem řešil nějakej problém na stackoverflow bylo řešení, kde se řekněme string:

String mujString = "s";

hodil do array a pak se sním pracovalo, protože to údajně šetřilo malý procento paměti. Bohužel si nepamatuju co to bylo, ale fungovalo to. Takže "If it works, don't touch it"

[Bloodman 295]

On 16. 7. 2020 at 4:44, ffredyk said:

ale také zkrátili funkci ze 4 řádků na jeden

 

int getMin(int a, int b) => a < b ? a : b;

Som tu fci skratil na -1 radek.

Edited 4. Říjen, 2022 by Bloodman

[ffredyk 164]

před 1hodinou, Bloodman said:

 

int getMin(int a, int b) => a < b ? a : b;

Som tu fci skratil na -1 radek.

Ale máš tom if-else :P - cílem bylo zbavit se podmínek