Maximálně negativní

27. 1. 2017

Když už jsem v tom, tak bych po minulém článku, tu mohl zmínit dvě drobnosti, které se nesou v podobném duchu. Jedna je jakž takž užitečná a druhá je jen intelektuální kuriozita.

#1

Nějakou dobu jsem ve Scale při řazení podle intů používal konstrukci

xs.sortBy(i => -i)

jako zkratku pro

xs.sorted.reverse

To je pěkně kompaktní, potenciálně efektivnější (nevytváří se jedna dočasná kolekce) a hlavně je to špatně.

Koho napadne, co může být špatně na jednom jediném znaku?

Problém je v tom, že znaménkové inty mají o jednu negativní hodnotu víc než těch pozitivních. Proto platí, že

Int.MinValue == -Int.MinValue

math.abs(Int.MinValue) == Int.MinValue

Z toho plyne, že když řadím podle -i, Int.MinValue bude chybně zařazený na začátek. Naštěstí existuje jednoduché řešení, které má taky jen jeden znak:

xs.sortBy(i => ~i)

Kdyby rozdíl nebyl vidět, místo mínusu je tilda, místo číselné negace je bitová negace. Pro tu platí, že

~Int.MinValue == Int.MaxValue
~0 = -1
~1 = -2

a všechno je zase v pořádku.

#2

Nedávno jsem přemýšlel nad následujícím problémem: Je možné porovnat dva znaménkové inty a dostat výsledek jako jeden bit bez CMP a SETE x86 instrukcí?

S CMP a SETE instrukcemi je to brnkačka. CMP porovná dvě hodnoty a nastaví příznaky do stavového registru. SETE pak extrahuje bit označující výsledek rovnosti. Ale jde to i bez nich?

Překvapivě ano.

Rovnost a == b je možné zapsat jako

a >= b & a <= b

Když tohle platí, a a b si musí být rovny. Výraz je pochopitelně rovný tomuhle:

!(a<b) & !(a>b)

Jestliže a < b, tak platí, že b-a je negativní a má tedy nejvyšší bit nastavený na jedničku. Můžu tedy nerovnost přepsat jako

~((b-a) >>> 31) & ~((a-b) >>> 31)

protože všechny operace jsou bitově paralelní, můžu výraz zjednodušit na

(~(b-a) & ~(a-b)) >>> 31

a pak na to hodit De Morgana

~((b-a) | (a-b)) >>> 31

Pět operací, to není špatné.

Za pozornost stojí, že obě nerovnosti můžou přetéct a vrátit špatný bit. Nikdy se však nestane, že přeteče jenom jedna z nich a zkazí výsledek. Obě nerovnosti vždy přetékají v tandemu. Když jedna přeteče a zkazí výsledek, druhá přeteče taky a opraví ho.

Teď jen přijít na to, kde by se to dalo použít.

Co se týká rychlosti, nativní CMP+SETE je pochopitelně rychlejší.

Když už jsem v tom, měl bych zmínit pár paperů, které přišly s užitečnými bit twidlling hacky.

Prvním je Faster Population Counts using AVX2 Instructions, který překonává dřívější SSSE3 fast popcount. Chytrým využitím SIMD instrukcí a bitově paralelního kódu je možné napsat population count, který je 2x rychlejší než nativní popcnt instrukce.

Dalším je Fast Sorted-Set Intersection using SIMD Instructions, který ukazuje jak napsat rychlé sjednocování množin za pomocí nejCISCovatější ze všech x86 CISC instrukci PCMPESTRM (hodí se to např. pro Jaccardovu podobnost)

A nakonec pak Sorting improves word-aligned bitmap indexes, což je tour de force publikace o (komprimovaných) bitových indexech.

To je všechno, rozejděte se.

Dále k tématu:

Bit twiddling hacks