Bitové operace ve vyšších jazycích

[Mirek]

Zavisi pripad od pripadu. Treba vediet, kde je zrada a podla toho sa zariadit.

No výborně, začínáme se dostávat k jádru věci. Záleží to na kontextu. Nejde slepě používat násobení nebo umocňování místo bitových operací. O tom je celý tento thread, někteří to ale bohužel ještě nepochopili.

Tenhle thread byl původně o Pythonu a tam je to úplně jedno. Můžeš posunovat a umocňovat kolik ti výkon počítače dovolí.

Opravdu je to thread o Pythonu? Já myslel, že je o otázce, kterou na blíže nespecifikovaném pohovoru na blíže nespecifikovanou pozici dostal člověk, který programuje např. V Pythonu...

[Reklama]

[franto]

tvl vy jste fakt volove. ale ze totalni. vlakno o bitovych operacich se natahne na 20 stranek. ty blaho, to je mozny jenom na rootu, kam si chodej lidi honit triko.

[PetrM]

A ke zpracování signálů na jednom řádku - mezi zpracování signálů se dá započítat třeba FIR filtr 1. řádu u ADC na potlačení šumu.

Třeba derivační článek x_n+1 = 7/8*x_n + 1/8*a se napíše v C v přerušení 12b ADC takto:

Kód: [Vybrat]


volatile uint16_t x = 0;

void ADC_ISR(void) {
  x = ((x << 3) - x + ADC_VALUE) >> 3;
}

Třeba u ARMu s barrel shifterem je to velice efektivní metoda. Jenom vědět, jak na to bez násobení a floatů.

Python nedělám, ale pokud by chtěl stejně filtrovat data, tak princip bude pořád stejný. A taky se to asi vejde na jednu lajnu...

v Pythonu na běžném procesoru je IMHO

Kód: [Vybrat]

x = (x*7 + ADC_VALUE)//8

stejně rychlé a je to přesnější přepis toho vzorce. Snáz se to čte.

A to, že je to stejně rychlý, jsi vzal kde? Na (8x-x) potřebuješ jeden shift o tři bity (u ARMu barrel shifter) a jeden rozdíl. To jsou dvě instrukce a stačí ti dva registry CPU. Pro násobení sedmi potřebuješ 3x shift o 1b a 3x součet a pravděpodobně si to vezme i jeden registr procesoru navíc. Takže samotná operace, pokud to kompilátor nepřevede na 8x-x, je 3x pomalejší. A pokud to vezme jako obecný násobení 16x16->32 bez HW násobičky, tak je to dokonce 16x pomalejší. Ve zpracování v časově kritickým přerušení nebo na větším objemu dat je to sakra poznat.

Kolega jednou dělal něco v C# na x86_64 a použil knihovní funkce. Přechrchlání dat za cca 2,5 minuty.
Vyhodil knihovní funkce, použil vnitřek (s floatama) přímo. Stáhl to na 80s.
Přešel na integer, byl na 20s.
Po úpravě konstant tak, aby to byly mocniny dvojky nebo maximálně dvě jedničky v konstantě (kompilátor mohl používat shifty) se dostal na 3,5s.

[Ivan Nový]

Java přece jen není tak univerzální, jak by si mnozí přáli. Některé záležitosti se v ní dělat nedají a jiné se v ní dělají blbě.

Pre lopaty a javamana mame v jave typ BigInteger.

Poněkud nepraktické, když Python, Lisp a hromada dalších jazyků s tím pracuje nativně. Podobně bychom dopadli třeba i s komplexními čísly, racionálními čísly, případně s finančními částkami.

Ale to je správná filosofie Javy, aby v ní nešlo dělat vše, ale jen to, co jazykem povolené typy umožňují. Aby nešlo používat << k aritmetickým operacím, aby se neoptimalizovalo na rychlost. Filosofií Javy je přenositelnost a podobné triky tu přenositelnost znemožňují, protože na každém procesoru je to trochu jinak. Optimalizovat na rychlost u Javy se má VM a ne aplikace.

Maximálně můžete použít k optimalizaci na úrovni bytekódu například pomocí tohoto frameworku https://github.com/Sable/soot .

[Ivan Nový]

Nebo k optimalizaci výkonu se v Javě dá použít přímo instrukce VM, viz například zde http://www.beyondjava.net/blog/quick-guide-writing-byte-code-asm/

[Reklama]

[Tuxik]

To se nám to tu pěkně zaflejmilo
Otázka do do davu:
Potřebuje účetní umět spočítat 2+5?
Odpověď:
Nepotřebuje, má kalkulačku.
Otázka:
Zaměstnáte účetní, o které víte, že neumí jednoduché sčítání?
Odpověď si doplňte.

[Ivan Nový]

A ke zpracování signálů na jednom řádku - mezi zpracování signálů se dá započítat třeba FIR filtr 1. řádu u ADC na potlačení šumu.

Třeba derivační článek x_n+1 = 7/8*x_n + 1/8*a se napíše v C v přerušení 12b ADC takto:

Kód: [Vybrat]


volatile uint16_t x = 0;

void ADC_ISR(void) {
  x = ((x << 3) - x + ADC_VALUE) >> 3;
}

Třeba u ARMu s barrel shifterem je to velice efektivní metoda. Jenom vědět, jak na to bez násobení a floatů.

Python nedělám, ale pokud by chtěl stejně filtrovat data, tak princip bude pořád stejný. A taky se to asi vejde na jednu lajnu...

v Pythonu na běžném procesoru je IMHO

Kód: [Vybrat]

x = (x*7 + ADC_VALUE)//8

stejně rychlé a je to přesnější přepis toho vzorce. Snáz se to čte.

A to, že je to stejně rychlý, jsi vzal kde? Na (8x-x) potřebuješ jeden shift o tři bity (u ARMu barrel shifter) a jeden rozdíl. To jsou dvě instrukce a stačí ti dva registry CPU. Pro násobení sedmi potřebuješ 3x shift o 1b a 3x součet a pravděpodobně si to vezme i jeden registr procesoru navíc. Takže samotná operace, pokud to kompilátor nepřevede na 8x-x, je 3x pomalejší. A pokud to vezme jako obecný násobení 16x16->32 bez HW násobičky, tak je to dokonce 16x pomalejší. Ve zpracování v časově kritickým přerušení nebo na větším objemu dat je to sakra poznat.

Kolega jednou dělal něco v C# na x86_64 a použil knihovní funkce. Přechrchlání dat za cca 2,5 minuty.
Vyhodil knihovní funkce, použil vnitřek (s floatama) přímo. Stáhl to na 80s.
Přešel na integer, byl na 20s.
Po úpravě konstant tak, aby to byly mocniny dvojky nebo maximálně dvě jedničky v konstantě (kompilátor mohl používat shifty) se dostal na 3,5s.

Zřejmě i v Pythonu v tom bude nějaký rozdíl, viz příklad

Kód: [Vybrat]


import dis

def shift(a):
x = a << 4

def mul(a):
x = a * 4

print(dis.dis(shift))
print(dis.dis(mul))

a výsledek

Kód: [Vybrat]

4           0 LOAD_FAST                0 (a)
              3 LOAD_CONST               1 (4)
              6 BINARY_LSHIFT
              7 STORE_FAST               1 (x)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE
None
  7           0 LOAD_FAST                0 (a)
              3 LOAD_CONST               1 (4.1)
              6 BINARY_LSHIFT
              7 STORE_FAST               1 (x)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE
None
 10           0 LOAD_FAST                0 (a)
              3 LOAD_CONST               1 (4)
              6 BINARY_MULTIPLY
              7 STORE_FAST               1 (x)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE
None


[gamer]

Samozřejmě pokud umocňuješ a posouváš celým číslem. Pro reálný exponent to nemá smysl porovnávat.

Takže podle tebe je tohle ekvivalentní? V klidu by jsi vyměnil foo za bar?

Kód: [Vybrat]

def foo(x):
    return x << 2
def bar(x):
    return x * 4


[grg]

tvl vy jste fakt volove. ale ze totalni. vlakno o bitovych operacich se natahne na 20 stranek. ty blaho, to je mozny jenom na rootu, kam si chodej lidi honit triko.

No a čo, nikto ťa nenúti to čítať. Pre mňa sú takéto diskusie vždy dobrým zdrojom zábavy a prokrastinácie v práci.

[balki]

Java přece jen není tak univerzální, jak by si mnozí přáli. Některé záležitosti se v ní dělat nedají a jiné se v ní dělají blbě.

Pre lopaty a javamana mame v jave typ BigInteger.

Poněkud nepraktické, když Python, Lisp a hromada dalších jazyků s tím pracuje nativně. Podobně bychom dopadli třeba i s komplexními čísly, racionálními čísly, případně s finančními částkami.

Java pracuje default s 32bit signed integermi. Komu sa nelubi, ten nech si zatrubi. Je to prakticke aj neprakticke. Zalezi od ulohy. Ked prijde sef a spyta sa "kolko pamati to zaberie" a ja mu poviem - "huh neviem" moc nadseny z toho nebyva.

Nikdo ti nebrání používat numpy.

Ale to je externa, kniznica, toje nepr...   , nechajme to tak

[tisnik]

Navic 63 je int a u toho je konstanta pro posun nejdrive maskovana 0x1f, tedy napriklad 1<<64 == 1>>64 == 1

Při shiftu longu (64-bit) je konstanta pro posun maskována 0x3F.

Presne tak, ja jen, ze v te ukazce to nebylo uplne jasne - u shiftu zalezi na typu LEVEHO operandu, takze 1L<<x versus 1<<x  ale uz ne na typu operandu druheho  1<<10L == 1<<10

Skutecne na okraj - i s timto se lze na pohovoru setkat, nema smysl mit testik, kde to da kazdej po svem prvnim Hello World na 100%, proto jsou tam speky pro ty lepsi a jeste lepsi, i kdyz v praxi se s tim skutecne malokdo setka.

[tisnik]

(omlouvam se, ze pouzivam hexadecimalni cisla, to je asi dneska taky uz prezitek?

Nic se neděje. Mám po ruce kalkulačku.

Navic 63 je int a u toho je konstanta pro posun nejdrive maskovana 0x1f, tedy napriklad 1<<64 == 1>>64 == 1

Takže posun o 31 je to stejné  co posun o 63?

Pokud se posunuje int a ne long, tak ano, zde konkretne s vysledkem 1<<31 == 1<<63 == Integer.MIN_VALUE (protoze dvojkovy doplnek, ale to uz taky asi neni zapotrebi dneska znat

Naproti tomu zdanlive to stejne s longy vypada jinak 1L<<31 != 1L<<63, tam dostanes Integer.MIN_VALUE a ve druhem pripade Long.MIN_VALUE.

Btw by me fakt zajimalo, jestli se toto jeste na SS/VS uci, tj. dvojkovy doplnek, proc funguje, jak funguje atd. My to pocitali na papire, byla to docela sranda a navic v podstate dobre znamky za "nic".

[v]

protoze dvojkovy doplnek, ale to uz taky asi neni zapotrebi dneska znat

tak samozřejmě, na to jsou dneska optimalizované frameworky, zalez kam geologicky patříš dinosaure

[franto]

kokoti uz tady nespamujte. delejte neco uzitecnyho. co kdyby jsme zalozili vlastni forum, ktere by bylo na urovni?

[Ivan Nový]

protoze dvojkovy doplnek, ale to uz taky asi neni zapotrebi dneska znat

tak samozřejmě, na to jsou dneska optimalizované frameworky, zalez kam geologicky patříš dinosaure

Dnes je trendy pure, pure css (bez js), pure javascript (bez jquery), ...