abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 15:00 | Zajímavý software

Stop motion je technika animace, při níž je reálný objekt mezi jednotlivými snímky ručně upravován a posouván o malé úseky, tak aby po spojení vyvolala animace dojem spojitosti. Jaký software lze pro stop motion použít na Linuxu? Článek na OMG! Ubuntu! představuje Heron Animation. Ten bohužel podporuje pouze webové kamery. Podpora digitálních zrcadlovek je začleněna například v programu qStopMotion.

Ladislav Hagara | Komentářů: 0
včera 21:21 | Nová verze Ladislav Hagara | Komentářů: 0
včera 11:44 | Zajímavý projekt

Na Indiegogo byla spuštěna kampaň na podporu herní mini konzole a multimediálního centra RetroEngine Sigma od Doyodo. Předobjednat ji lze již od 49 dolarů. Požadovaná částka 20 000 dolarů byla překonána již 6 krát. Majitelé mini konzole si budou moci zahrát hry pro Atari VCS 2600, Sega Genesis nebo NES. Předinstalováno bude multimediální centrum Kodi.

Ladislav Hagara | Komentářů: 0
včera 00:10 | Nová verze

Byla vydána verze 4.7 redakčního systému WordPress. Kódové označením Vaughan bylo vybráno na počest americké jazzové zpěvačky Sarah "Sassy" Vaughan. Z novinek lze zmínit například novou výchozí šablonu Twenty Seventeen, náhledy pdf souborů nebo WordPress REST API.

Ladislav Hagara | Komentářů: 4
6.12. 12:00 | Zajímavý projekt

Projekt Termbox umožňuje vyzkoušet si linuxové distribuce Ubuntu, Debian, Fedora, CentOS a Arch Linux ve webovém prohlížeči. Řešení je postaveno na projektu HyperContainer. Podrobnosti v často kladených dotazech (FAQ). Zdrojové kódy jsou k dispozici na GitHubu [reddit].

Ladislav Hagara | Komentářů: 27
6.12. 11:00 | Bezpečnostní upozornění

Byly zveřejněny informace o bezpečnostní chybě CVE-2016-8655 v Linuxu zneužitelné k lokální eskalaci práv. Chyba se dostala do linuxového jádra v srpnu 2011. V upstreamu byla opravena minulý týden [Hacker News].

Ladislav Hagara | Komentářů: 2
5.12. 22:00 | Komunita

Přibližně před měsícem bylo oznámeno, že linuxová distribuce SUSE Linux Enterprise Server (SLES) běží nově také Raspberry Pi 3 (dokumentace). Obraz verze 12 SP2 pro Raspberry Pi 3 je ke stažení zdarma. Pro registrované jsou po dobu jednoho roku zdarma také aktualizace. Dnes bylo oznámeno, že pro Raspberry Pi 3 je k dispozici také nové openSUSE Leap 42.2 (zprávička). K dispozici je hned několik obrazů.

Ladislav Hagara | Komentářů: 6
5.12. 06:00 | Zajímavý software

OMG! Ubuntu! představuje emulátor terminálu Hyper (GitHub) postavený na webových technologiích (HTML, CSS a JavaScript). V diskusi k článku je zmíněn podobný emulátor terminálu Black Screen. Hyper i Black Screen používají framework Electron, stejně jako editor Atom nebo vývojové prostředí Visual Studio Code.

Ladislav Hagara | Komentářů: 50
5.12. 06:00 | Zajímavý článek

I letos vychází řada ajťáckých adventních kalendářů. QEMU Advent Calendar 2016 přináší každý den nový obraz disku pro QEMU. Programátoři se mohou potrápit při řešení úloh z kalendáře Advent of Code 2016. Kalendáře Perl Advent Calendar 2016 a Perl 6 Advent Calendar přinášejí každý den zajímavé informace o programovacím jazyce Perl. Stranou nezůstává ani programovací jazyk Go.

Ladislav Hagara | Komentářů: 10
3.12. 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 17
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 791 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Vzdálenost dvou reálných kladných čísel v C

Thunder.m avatar 23.1.2011 11:50 Thunder.m | skóre: 35 | blog: e17
Vzdálenost dvou reálných kladných čísel v C
Přečteno: 996×
Provádím různé optimalizace kódu, dostal jsem se do části která se provádí asi nejvícekrát ze všech a to výpočet absolutní hodnoty rozdílu dvou čísel.

V tuto chvíli používám pro data signed int (4B) ale rád bych použil pouze unsigned short (2B).

Už jsem dělal nějaké pokusy v rychlosti, jde o kritickou část kódu která se nedá jinak zoptimalizovat.

Jsou dvě možnosti, při zpracování dat:
  • data přetypovat na signed int a poté provést funkci abs(x - y)
  • použít podmínku
    if (x > y) {
    z = x - y
    } else {
    z = y - x
    }
    
  • Třetí metoda je již jen modifikací druhé a to vytvořit makro
    #define ABS_DIFF(X,Y) ((X > Y) ? (X - Y) : (Y - X))
    
Bohužel C zpracuje nejrychleji první metodu s přetypováním, ale i tak je rozdíl zpomalení docela výrazný (cca 30%) proti původnímu abs bez přetypování, nevíte jak se dá rychleji ideálně nativní funkcí spočítat rozdíl dvou reálných celočíselných čísel?

Řešení dotazu:


Odpovědi

Thunder.m avatar 23.1.2011 11:52 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Oprava, reálných kladných celých čísel :)
23.1.2011 13:55 chrono
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Je nejaký špeciálny dôvod, prečo potrebuješ práve 2 bajtový typ?
Thunder.m avatar 23.1.2011 13:56 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
No tak protože hodnoty nabívají hodnot od 0 - 50 000, chci menší datový typ, protože pokud mám data načtená v operační paměti a že jich je opravdu velké množství, zabírají zbytečně 2x tolik místa.
Thunder.m avatar 23.1.2011 13:57 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
nabývají :D
23.1.2011 14:11 chrono
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
V takom prípade (a aj vo veľa iných prípadoch) je potom najlepšie použiť priamo funkciu abs, pretože ju kompilátor optimalizuje (platí to minimálne pre gcc a llvm).

Predpokladám, že to ABS makro by sa dalo, minimálne pre gcc, urobiť tak, aby to generovalo lepší kód, ale je otázne, či to má zmysel a či to bude v priemere rýchlejšie ako tá abs funkcia.
23.1.2011 14:09 Pavel Löbl | skóre: 7 | blog: vadnej_pixel
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
V glibc to vypada neak tak:
/* Return the absolute value of I.  */
int
abs (int i)
{
  return i < 0 ? -i : i;
}
na tom mym srotu (i686) to pri pouziti makra a prelozeni s -O1 vychazi podobne jako volani abs, a mezi pouzitim short a int neni taktez temer rozdil.

Dost mozny, ze to brzdi ten short. Prace s typem, kterej nema velikost slova muze bejt asi drazsi.

23.1.2011 14:31 chrono
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Rýchlejšie bude niečo ako
int abs(int i)
{
    int t = i >> (32 - 1);
    return (i ^ t) - t;
}
(a presne to isté generuje gcc pre 32 bitový int)
Thunder.m avatar 23.1.2011 14:40 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
No a napadá tě podobná funkce pro rozdíl unsigned celých čísel? Bitové operace mi nikdy moc nešly :)
23.1.2011 15:10 chrono
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Nič lepšie ako tú tvoju prvú možnosť asi nevymyslíš. :) (pretože 16 bitov na to odpočítavanie stačiť nebude, takže aj tak nakoniec skončíš pri aspoň 32 bitovom type).

Možno by sa dali použiť MMX inštrukcie, ale je otázne, či by to bolo rýchlejšie.
23.1.2011 16:02 l4m4
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Nejspíš byly, protože operují na 4 argumentech současně a existuje přímo instrukce na abs vektoru 16bitových čísel se znaménkem, viz můj příspěvek níže.
23.1.2011 15:17 Sixkillers
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Tak tady je trochu upravena varianta.
unsigned short my_abs(int i)
{
    int t = i >> (sizeof(int) * CHAR_BIT - 1);

    /* patent free */
    return (i + t) ^ t;
    /*return (i ^ t) - t;*/
}
Jinak ta varianta s minusem je možná patentově chráněna (viz.) :)

Např.:
unsigned short x = 5;
unsigned short y = 20;
unsigned short z = my_abs(x - y);
Přetypování my_abs(x - y) typicky zabere jeden procesorový cyklus. Přetypování int na unsigned short je bez výkonové penalizace.

Josef Kufner avatar 23.1.2011 15:36 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
A co se tomu přetypování vyhnout třeba tím, že by se už na začátku počítalo se správným typem? Nevím co tam okolo máš, ale snad by to mohlo jít nějak přerovnat. Případně bych zkusil se té absolutní hodnoty zbavit (nějak jinak zaručit, že tam budou vždy jen kladná čísla nebo aby nevadilo, že bude záporné).
Hello world ! Segmentation fault (core dumped)
Thunder.m avatar 23.1.2011 15:43 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
To bohužel nejde, unsigned short má rozsah +-32 768, ale já potřebuju porovnávat čísla od 0 do 50 000.

Myslím že ani nejde posunout si nulu (předem data přesunout do spodní části), protože bych narazil na možné překročení limitu unsigned shortu, např abs(-15 000 - 32000) nelze.
Josef Kufner avatar 23.1.2011 15:56 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
A co nějak zaručit, že a bude vždy větší neź b, takže bys nemusel dělat abs(), ale jen bys odčítal.
Hello world ! Segmentation fault (core dumped)
23.1.2011 15:52 Sten
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Funkce abs dělá:
return i < 0 ? -i : i;
Všechny tři metody jsou ve výsledném kódu totožné.

Doporučuji nepoužívat short, operace s ním jsou dražší než s intem (resp. longem na 64bitech).
23.1.2011 16:00 l4m4
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Pokud ten program skutečně tráví nejvíc času výpočtem absolutních hodnot, asi to dělá uvnitř vnitřních smyček na spoustě argumentů, a v tom případě se podívej na pabsw (v gcc __builtin_ia32_pabsw), psubw a podobné.
Thunder.m avatar 23.1.2011 16:11 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Ano přesně tak, vnitřní smyčky probíhající cca 20x, tj. podobný kód
function soucet_abs_hodnot(unsigned short *input1, unsigned short *input2, unsigned int size) {
int z = 0, i;
for (i = 0; i < size; i++) z+= abs(input1[i] - input2[i]);
return z;
}
Takhle přesně vypadá funkce kterou chci zoptimalizovat.
23.1.2011 16:33 l4m4
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
V tom případě se použití vektorových instrukcí nejspíš vyplatí. Kromě ručního psaní assembleru znám dvě cesty. Jednak gcc builtiny, které provádějí konkrétní instrukce procesoru, takže jsou platformově závislé (tj. budeš potřebovat přinejmenším fallback pro ostatní architektury, případně i více implementací kritického kódu). Druhak knihovna ORC, která umožňuje napsat jakýsi pseudokód, který pak převede do konkrétních instrukcí sama (i run-time); vypadá nadějně, je ovšem zatím poměrně dost ve vývoji.
23.1.2011 19:04 dooku | skóre: 4
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Zkoušel jsem několik metod:
1> jednu zde jmenovanou - pomocí bitového posunu a nonekvivalence
2> nejjednodušší možnou porovnávající číslo s nulou pomocí podmíněného operátoru
3> abs() z math.h
4> mou metodu - zařadil jsem ji jen pro porovnání, nepočítal jsem s tím že by měla závratné výsledky:

int abs(int i) {
 if (i & 0x80000000) return -i; // hex hodnota se samozřejmě liší podle použitých číselných typů
 return i;
}


Každou metodou bylo porovnáno 4 000 000 000 čísel, tedy kousek pod limitem unsigned int. Nepřetypovával jsem, zajímal jsem se pouze o efektivnost algoritmů výpočtu absolutních hodnot. Výsledky jsou následující:
1> 21.65 sekund
2> 23.27 sekund
3> 15.44 sekund
4> 20.31 sekund

Měření jsem několikrát opakoval a výsledky se liší jen minimálně. Opět jsem se přesvědčil, že pokoušet se překonat optimalizované funkce je marné - je to stejné i v případě jiných matematických funkcí. Takže myslím, že pokud nechcete zabředávat do assembleru - což je sice zajímavé, avšak zdlouhavé a v mnoha případech nepraktické - nemá smysl zkoušet jiné algoritmy. Možná vektorové instrukce, ale to je docela kanón na vrabce. Lepší už to prostě nebude :)
Thunder.m avatar 24.1.2011 00:29 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Bohužel v tomhle máš opravdu pravdu a protože počítání absolutních hodnot program tráví 99% procesorového času je to bohužel hodně znat, takže mi asi nezbývá nic jiného, než data předávat jako float, nebo integer a použít interní abs funkci, než jakékoliv jiné metody.

Data ve formátu unsigned int
int sim = 0;
int i;
for (i = 1; i <= input2[0]; i++) sim+= abs((int) input1[i] - (int) input2[i]);
return sim;
real	0m16.898s
user	0m56.828s
#define MACRO_DIST(X,Y) ((X < Y) ? (Y - X) : (X - Y))
unsigned short sim = 0;

for (i = 1; i <= input2[0]; i++) sim += MACRO_DIST(input1[i],input2[i]);

return sim;
real	0m20.070s
user	1m18.761s
Data ve formátu float
float sim = 0;
int i;
for (i = 1; i <= input2[0]; i++) sim+= fabs(input1[i] - input2[i]);
return sim;
real	0m12.351s
user	0m33.758s
24.1.2011 00:41 l4m4
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Pokud tím program tráví 99% času, tak se možná na vektorové gcc builtiny podívej. Aritmetické operace na integerech i floatech lze provádět na blocích 4 hodnot. Při -O3 taky gcc zkouší vektorizovat sám, ale nevím, jak je v tom úspěšný.
24.1.2011 08:54 dustin | skóre: 60 | blog: dustin
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Nebo to napsat pod OpenCL nebo CUDA + GPU, tam by těch paralelních výpočtů mohlo běžet o řád víc:)
Thunder.m avatar 24.1.2011 10:34 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Pokud se to co píšeš týká jen paralelních výpočtů tak mám celý program psaný vícevláknově přes pthread, škálování s počtem CPU je téměř lineární, měl jsem možnost otestovat až 12 fyzických CPU. Otázka je jestli by pak takové úpravy přinesly ještě nárust výkonu.
stativ avatar 24.1.2011 11:52 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Určitě, protože pokud bys mohl pomocí SIMD počítat 4 hodnoty na každém procesoru, na 12 CPU by tě to paralelně počítalo 48 hodnot. A to je slušné zrychlení.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
stativ avatar 24.1.2011 11:55 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Pokud by ses rozhodl pro použití SSE, doporučuji mrknout na stránky Intel AVX. Dá se tam stáhnout „Intel Intrinsic Guide,“ což je nejlepší referenční příručka pro SSE co znám.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
Thunder.m avatar 24.1.2011 13:52 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Tak to zní skvěle, výpočty provádím na procesorech architektury Core, s podporou starších CPU se nepočítá. Pokusím se tedy o tom něco najít na internetu.
24.1.2011 12:30 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Neznám celý problém, ale než pthread může být na úrovni výpočtů efektivnější OpenMP a je možné automaticky použít tolik thredů, kolik je jader k dispozici, bez nějakého dalšího programovaní.
Pokud ovšem máte nárust výkonu lineární s násobkem jader, tak to asi nepomůže :)
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
24.1.2011 11:09 a
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Mozno by bolo dobre, keby Ste popisali nasledujuce veci:

- odkial pochadzaju vstupne data (premenne "input1" a "input2")

- ake (matematicke) vlastnosti maju vstupne data

- ako sa vstupne data vyvijaju v case
Thunder.m avatar 24.1.2011 13:51 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
input1 a input2 jsou indexy seřazeného pole, které mají hodnoty od 0 - 50000, jsou celočíselné a vždy kladné, za celý chod programu se nemění. Obš pole jsou až třetí dimenzí nadřazených polí, snad jsem to popsal dostatečně. Obě pole mají průměrnou velikost cca 200 ale mohou mít až velikost 25 000.
24.1.2011 13:57 a
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Ake IPC (min, max, avg) dosahuje ten loop, co pocita vzdialenost.
Thunder.m avatar 24.1.2011 14:27 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Aha, tak na takové úrovni ještě v C nejsem, nevím co tím myslíš, ale pokud myslíš kolik tím tráví času tak je to drtivá většina, co se týká dostupných různých polí input1 a input2 pak je to:

input1: 18000x200 input2: 5000x150x200

První je pole dvourozměrné, druhé je pole třírozměrné.

V rámci zásadních optimalizací už neporovnávám navzájem celé hodnoty, ale pouze vzdálenosti seřazených indexů a k tomu slouží ta funkce o které tu mluvíme, spočítá mi celkový rozdíl vzádlenosti mezi indexy polí.
Josef Kufner avatar 24.1.2011 17:57 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Ono tohle už není ani tak o C jako spíš o té matematice za tím. Třeba by se to dalo nějak upravit, že bys například rozlišil několik případů, ty vyřešil samostatně a efektivněji a nakonec dal výsledky dohromady. Nebo si někde přidal mezivýsledky a později ušetřil výpočty... Současný algoritmus zjevně narazil na hranice svých možností, takže pokud chceš víc, musíš to vzít odjinud.
Hello world ! Segmentation fault (core dumped)
24.1.2011 18:44 a
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Vzhladom na velkost dat, asi to nebude tak, ze cele data by sa generovali nanovo kazdu minutu. Z toho mi vyplyva, ze N-te spustenie programu dostane priblizne tie iste 'input1' a 'input2' ako (N+1) spustenie. Vznika otazka, kedze sa 'input1' a 'input2' prilis nemenia, naco je potrebne program spustat opakovane (nestaci iba raz spustit?).

Alebo to je tak, ze treba vykonat 18000*5000*150 iteracii, co by celkovo zabralo vela casu (den, tyzden)?
Thunder.m avatar 24.1.2011 18:54 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Ano v tuto chvíli je opravdu potřeba tolik iterací, na testovaném stroji Intel Core i7 2600K to zvládne za desítky vteřin.
24.1.2011 21:09 dustin | skóre: 60 | blog: dustin
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Už jsem to psal jednou, ale nebylo by to vážně zralé počítat na mnoha desítkách paralelních jednotek GPU?
25.1.2011 11:21 __dark__
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Příloha:
Ahoj, tady máš základní kód, který by ti mohl pomoct se odrazit dál. Implementace používá buď čisté C, kde si můžeš upravit MY_ABS makro (pokud to pomůže), pak SSE2, kde není instrukce abs, takže je nutné udělat pár instrukcí navíc, a SSSE3, kde se použije instrukce pabsd.

Neprováděl jsem nějaké velké testy, ale zdá se, že to počítá správně. Přeložit by to mělo být možné snad čímkoliv pro x86/amd64, zkoušel jsem jen MSVC.
Řešení 1× (Thunder.m (tazatel))
25.1.2011 11:39 __dark__
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Příloha:
Verze 2, trik s unsigned saturation je mnohem lepší, teoreticky lze vystačit s SSE2.
#include <stdio.h>
#include <math.h>

// Config.
#define USE_SSE2
#define USE_SSSE3

// SSE2.
#if defined(USE_SSE2)
#include <emmintrin.h>
#endif // USE_SSE2

// SSSE3.
#if defined(USE_SSSE3)
#include <tmmintrin.h>
#endif // USE_SSE3

#define ABS_C(_Value_) abs(_Value_)

int sum_abs_u16(
  const unsigned short* input1,
  const unsigned short* input2,
  size_t size)
{
  size_t i = size;
  int z = 0;

#if defined(USE_SSE2)
  if (i >= 20)
  {
    // Align.
    while ((intptr_t)input1 & (intptr_t)0xF)
    {
      z += ABS_C((int)input1[0] - (int)input2[0]);

      if (--i == 0) return z;
      input1++;
      input2++;
    }

    // Counter.
    __m128i cn = _mm_setzero_si128();
    __m128i zn = _mm_setzero_si128();

    // Large loop.
    while (i >= 16)
    {
      __m128i r0, r1;
      __m128i r2, r3;
      __m128i r4, r5;
      
      // Load input1, aligned.
      r0 = _mm_load_si128(reinterpret_cast<const __m128i*>(input1 + 0));
      r3 = _mm_load_si128(reinterpret_cast<const __m128i*>(input1 + 8));

      // Load input2, unaligned.
      r2 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(input2 + 0));
      r4 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(input2 + 8));

      // Get absolute values.
      r1 = _mm_subs_epu16(r2, r0);
      r0 = _mm_subs_epu16(r0, r2);

      r5 = _mm_subs_epu16(r3, r4);
      r4 = _mm_subs_epu16(r4, r3);

      r0 = _mm_add_epi16(r0, r1);
      r4 = _mm_add_epi16(r4, r5);

      // Unpack to 32-bit and sum.
      r1 = _mm_unpackhi_epi16(r0, zn);
      r5 = _mm_unpackhi_epi16(r4, zn);

      r0 = _mm_unpacklo_epi16(r0, zn);
      r4 = _mm_unpacklo_epi16(r4, zn);

      r0 = _mm_add_epi32(r0, r1);
      r4 = _mm_add_epi32(r4, r5);

      cn = _mm_add_epi32(cn, r0);
      cn = _mm_add_epi32(cn, r4);

      i -= 16;
      input1 += 16;
      input2 += 16;
    }

#if defined(USE_SSSE3)
    cn = _mm_hadd_epi32(cn, cn);
    cn = _mm_hadd_epi32(cn, cn);

    z += _mm_cvtsi128_si32(cn);
#else
    cn = _mm_add_epi32(cn, _mm_shuffle_epi32(cn, _MM_SHUFFLE(2, 3, 0, 1)));
    cn = _mm_add_epi32(cn, _mm_shuffle_epi32(cn, _MM_SHUFFLE(0, 1, 3, 2)));
    z += _mm_cvtsi128_si32(cn);
#endif
  }
#endif // USE_SSE2

  // Small loop.
  while (i > 0)
  {
    z += ABS_C((int)input1[0] - (int)input2[0]);

    i--;
    input1++;
    input2++;
  }

  return z;
}

int main(int argc, char* argv[])
{
  const unsigned short input1[40] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
  const unsigned short input2[40] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };

  int sum = sum_abs_u16(input1, input2, 40);
  printf("Sum=%d\n", sum);

  return 0;
}
Thunder.m avatar 25.1.2011 14:32 Thunder.m | skóre: 35 | blog: e17
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Tak tohle vypadá opravdu pěkně, s C sice umím, ale assembler jsem už dlouho nepoužíval a tak mi bude chvíli trvat pochopit jak to funguje, jakmile to implementuji poskytnu výsledky rychlosti.
25.1.2011 15:00 chochi | skóre: 29 | Praha
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Ono taky dost zalezi na prekladaci a jeho konfiguraci.
Podle popisku mas Core i7, ktere jiz podporuje SSSE3 (neplest si s SSE3), ktere jiz na funkci na absolutni fondnotu intu (pabsd).
Takze pokud se rekne gcc, ze muze pouzit SSSE3 (gcc -O3 -mssse3), tak vygeneruje jeste o kousek lepsi kod (protoze ma funkci abs).
Napr. tento kousek

  // Small loop.
  while (i > 0)
  {
    z += ABS_C((int)input1[0] - (int)input2[0]);
 
    i--;
    input1++;
    input2++;
  }
Prelozi nejak takhle:

	movl	8(%ebp), %ebx
	xorl	%edx, %edx
	xorl	%eax, %eax
	pxor	%xmm4, %xmm4
	pxor	%xmm5, %xmm5
	.p2align 4,,7
	.p2align 3
.L7:
	movdqu	(%ebx,%eax), %xmm2
	movdqu	(%edi,%eax), %xmm3
	movdqa	%xmm2, %xmm0
	movdqa	%xmm3, %xmm1
	punpcklwd	%xmm5, %xmm0
	punpcklwd	%xmm5, %xmm1
	addl	$1, %edx
	psubd	%xmm1, %xmm0
	punpckhwd	%xmm5, %xmm2
	pabsd	%xmm0, %xmm0
	punpckhwd	%xmm5, %xmm3
	paddd	%xmm4, %xmm0
	psubd	%xmm3, %xmm2
	addl	$16, %eax
	cmpl	%edx, %ecx
	pabsd	%xmm2, %xmm4
	paddd	%xmm0, %xmm4
	ja	.L7
+ nejaka ta omacko okolo.
Takze nekdy si prekladac poradi sam. To se asi nejlepe zjisti tak, ze si nechas prelozit kod do ASM a podivas se, zda to dostatecne optimalizoval.
25.1.2011 15:14 __dark__
Rozbalit Rozbalit vše Re: Vzdálenost dvou reálných kladných čísel v C
Jo, benchmark by byl super :)

V tom kódu je použitých jen pár triků. Pro portabilitu jsem zvolil makro USE_SSE2, které si definuješ, pokud bude cílová architektura mít SSE2. Je možné udělat i runtime check, ale to bych moc komplikoval.

Dále jsem využil toho, že neznaménková saturace US(A - B) dá buď kladný rozdíl těchto dvou hodnot nebo nulu (saturuje se, pokud je B větší než A), no takže abych získal absolutní hodnotu rodílu, použiju vlastně US(A - B) + US(B - A), výsledek není nikdy větší než 16-bitové číslo, takže využiju instrukci pro práci s 16bitovými páry hodnot. Na toto stačí pouhé SSE2 a je to podle mě asi to nejoptimálnější řešení (teda nenapadlo mě nic lepšího).

Dále tyto hodnoty převedu na 32bitové čísla (unpack), protože je potřebuju sčítat a 16bitová hodnota už není dostačující. Registr CN funguje jako paralelní akumulátor 4 hodnot, které se po vykonání hlavní smyčky sečtou a přičtou k výsledné proměnné Z.

Vychází mi to 22 instrukcí (+ instrukce na chod cyklu) pro akumulaci 16 hodnot. Problém bude spíš sběrnice než rychlost tohoto algoritmu. Pokud máš velké sady dat, které se nikdy nevlezou do cache, je možné udělat ještě další experimenty, ale ty můžou v neoptimálním případě vést i ke zpomalení.

(Na těch 22 instrukcí bych to napsal v asm, nevím zda to překladač zvládne stejně)

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.