DAVIDOWITCH: Kdyz se podivas na ten stackoverflow, tak je tam super odpoved, kde ten clovek mj. pise ze Intel Compiler 11 dokaze dokonce prohodit ty dve smycky 8)

XCHAOS: Muzes to nejak rozvest?
Pripadne po mne hodit ASM vypisem, protoze si nemyslim ze by compiler mel bejt schopnej nahradit ten skok maskovanim, coz je asi jediny jak stahne ty 2 casy tak blizko k sobe (pokud si teda nezkousel tu moji modifikaci)

REDGUY: jako ano, už jsem asi objevil, že jsem ve slepé uličce, s touto úvahou :-)

myslel jsem, že třeba sečtení 33+33 by trvalo stejně jako sečtení 33+0 nebo 0+33. ale sečtení 8+8 by bylo rychlejší :-) (tedy někde by byl nějaký pomocný bitcounter, kolik z aktuálních bitů na sběrnici je "dirty" a musí se s nimi počítat v následující instrukci

ale nemám to ničím podložené, tohle je na mě moc lowlevel :-) je to jen moje divoká spekulace "jak bych vymýšlel CPU"...

DAVIDOWITCH: to už mi taky došlo


DAVIDOWITCH: jiný -O switch compileru

REDGUY:
http://en.wikipedia.org/wiki/Carry-lookahead_adder (je logN misto N)
http://en.wikipedia.org/wiki/Carry_bypass_adder
Carry-select adder - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Carry-select_adder

Ale priznam, musel sem zkonzultovat spoluzaka, protoze uz to je 5 let co sem se to ucil, 4 roky od posledniho pouziti.

DAVIDOWITCH: Neznam terminus technicus, ale takovou tu uplne obycejnou. I kdyz nepochybuju ze zaimavy budou i ty chytrejsi 8)
Zkusim najit kde jsem o tom cetl...

REDGUY: Myslis Carry-lookahead, nebo nejakou z tech chytrejsich, nebo obecne proste tyhle bordely?

REDGUY: A btw, navrh hw scitacek co pracujou v konstatnim case, aniz bys musel nejak postupne v nekolika krocich propagovat carry zleva doprava je docela zajimavej a elegantni. Doporucuju si o tom neco najit,

XCHAOS: sčítání čísel obsahujíích různý počet nastavených bitů prostě trvá různě dlouho - ale kdeze. Delka scitani integeru je konstantni, na poslednich intelech trva tusim dokonce efektivne 0.5 taktu. Navic ty cisla co scitas jsou stejna, jen v jinem poradi. A konecne tuhle teorii lze snadno vyvratit tak, ze si to vyzkousis scitanim jinejch cisel.

nebo trváte na compile-time optimalizacích - netrvame, protoze compile-time optimalizace s tim nemaji nic spolecneho (*) a nikdo tady nic takoveho nerikal. Naopak, tohle je nasledkem v podstate run-time optimalizace, ktera probiha primo v procesoru. Podrobne vysvetleni i s obrazkama: http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

(*) tedy, c-t-o s tim maji spolecneho to, ze maji vliv na to jak vyrazny je ten efekt a pokud mas fakt hodne chytrej prekladac, dokazou ho eliminovat. Ale na ten rozdil v casech vliv nemaji.

XCHAOS: Cim se lisej tyhle dva behy?

XCHAOS: scitani cisel obsahujicich ruzny pocet bitu trva uplne stejne, jeden takt.

xchaos@tartarus:~$ ./test WTF
Sum: 403504454559365000
Time: 0.444335
xchaos@tartarus:~$ ./test
Sum: 403504454559365000
Time: 2.32974

....a tohle je nejlepší:

xchaos@tartarus:~$ ./test WTF
Sum: 403504454559365000
Time: 0.658788
xchaos@tartarus:~$ ./test
Sum: 403504454559365000
Time: 0.687157

ok, přiznávám se - dostali jste mě :-)

(jen podotýkám, že můj mini-toolkit zahnrnuje i dávkový soubor "bake", který se má používat místo "make" a Makefile - a že budu používat při volání gcc ty optimalizace, který mě nejlíp dopadnou s mými typy zasmyčkování, která chystám... ale to je offtopic, tohle byl hezký vtípek, uznávám ...)

xchaos@tartarus:~$ gcc -O1 test.c -otest
xchaos@tartarus:~$ ./test WTF
Sum: 403504454559365000
Time: 0.43624
xchaos@tartarus:~$ ./test
Sum: 403504454559365000
Time: 2.3264

huh


xchaos@tartarus:~$ gcc -O0 test.c -otest
xchaos@tartarus:~$ ./test
Sum: 403504454559365000
Time: 3.60948
xchaos@tartarus:~$ ./test
Sum: 403504454559365000
Time: 4.5604
xchaos@tartarus:~$

dobře... tohle už vypadá jako signál mimozemské civilizace "WTF" (zachycen po velkém úspěchu předchozího signálu "WOW")

xchaos@tartarus:~$ ./test WTF
Sum: 403504454559365000
Time: 1.53202
xchaos@tartarus:~$ ./test
Sum: 403504454559365000
Time: 3.59716

můj návrh interpretace: sčítání čísel obsahujíích různý počet nastavených bitů prostě trvá různě dlouho - prostě CPU nějak ví, kolik je max. platných bitů v registru a pak i mikrokód sčítačící různý počet bitů trvá různě dlouho, to je celé.... prostě se mi to jeví, že asm instrukce ADD už není "atomická" (či jak to nazvat) - prostě už na soudobých architekturách netrvá vždy stejný počet taktů CPU (resp. možná trvá na úrovni jednoho vlákna, ale ten čas se může využívat např. pro NEVÍM způsobem NEVÍM JAK)

je možné, že je to tímhle? (testováno zatím jen na 64bit platformě), nebo trváte na compile-time optimalizacích?

REDGUY: ok :-)

DAVIDOWITCH: myslím, že vidět v hlavním cíli mých pokusů "mikrooptimalizace" je trochu nepochopení mojí motivace k tomu, o co se snažím...

REDGUY: dvě setinky sekundy. hmm, zajímavý.

xchaos@tartarus:~$ ./test
Sum: 403504454559365000
Time: 3.50986
xchaos@tartarus:~$ ./test wtf
Sum: 403504454559365000
Time: 3.52524

REDGUY: mě to přijde jako zajímavý zadání... nevím proč se do mě musíš obouvat i v případě, že to je zajímavý téma který nijak nesouvisí s mýma ujetýma nápadama.

až budu mít chvilku, vyzkouším to.

DAVIDOWITCH: To maskovani funguje jak? Na pristi instrukci, pristi store, dokud ho nevypnu, nebo jinak?

REDGUY: Jako, je husty jak mi tohle vubec nedoslo, protoze ted programuju pro GPU a tam se takovyhle maly tela resej maskovanim.
tj. if by jen nastavil predikat jestli zapsat vysledek nebo ne, a tudiz skok by vubec neprobehl (to samy bych delal v SIMD)

DAVIDOWITCH: Rekl bych ze jo. Navic stejnej efekt je udajne videt i v Jave.

(ne, necekal sem to, myslel sem ze to bude opacne)

REDGUY: Tyjo, ze by se tohle CELY dalo svyst na branch prediction?

ANT_39: dík, to jsem možná teď napodruhé přehlédl, už jsem to ale měl nastudovaný... řetězící alokátor get_str() a formátující alokátor get_strf() u mě každopádně budou hlavní stringové nástroje (začal jsem diplomaticky používat označení "můj toolkit", protože cokoliv jiného působí jako rudý hadr :-)

(jo a připomínám, že rozhodně nečekám reputaci, dokud to nereleasnu...)