funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Maximálně negativní

27. 1. 2017 — k47

Když už jsem v tom, tak bych po mi­nu­lém článku, tu mohl zmínit dvě drob­nosti, které se nesou v po­dob­ném duchu. Jedna je jakž takž uži­tečná a druhá je jen in­te­lek­tu­ální ku­ri­o­zita.

#1

Ně­ja­kou dobu jsem ve Scale při řazení podle intů po­u­ží­val kon­strukci

xs.sortBy(i => -i)

jako zkratku pro

xs.sorted.reverse

To je pěkně kom­paktní, po­ten­ci­álně efek­tiv­nější (ne­vy­tváří se jedna do­časná ko­lekce) a hlavně je to špatně.

Koho na­padne, co může být špatně na jednom je­di­ném znaku?

Pro­blém je v tom, že zna­mén­kové inty mají o jednu ne­ga­tivní hod­notu víc než těch po­zi­tiv­ní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­řa­zený na za­čá­tek. Na­štěstí exis­tuje jed­no­du­ché ř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

Ne­dávno jsem pře­mýš­lel nad ná­sle­du­jí­cím pro­blé­mem: Je možné po­rov­nat dva zna­mén­kové inty a dostat vý­sle­dek jako jeden bit bez CMP a SETE x86 in­strukcí?

S CMP a SETE in­struk­cemi je to brn­kačka. CMP po­rovná dvě hod­noty a na­staví pří­znaky do sta­vo­vého re­gis­tru. SETE pak ex­tra­huje bit ozna­ču­jící vý­sle­dek rov­nosti. Ale jde to i bez nich?

Pře­kva­pivě ano.

Rov­nost a == b je možné zapsat jako

a >= b & a <= b

Když tohle platí, ab si musí být rovny. Výraz je po­cho­pi­telně rovný to­muhle:

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

Jestliže a < b, tak platí, že b-a je ne­ga­tivní a má tedy nej­vyšší bit na­sta­vený na jed­ničku. Můžu tedy ne­rov­nost pře­psat jako

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

pro­tože všechny ope­race jsou bitově pa­ra­lelní, můžu výraz zjed­no­du­šit na

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

a pak na to hodit De Mor­gana

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

Pět ope­rací, to není špatné.

Za po­zor­nost stojí, že obě ne­rov­nosti můžou pře­téct a vrátit špatný bit. Nikdy se však ne­stane, že pře­teče jenom jedna z nich a zkazí vý­sle­dek. Obě ne­rov­nosti vždy pře­té­kají v tan­demu. Když jedna pře­teče a zkazí vý­sle­dek, druhá pře­teče taky a opraví ho.

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

Co se týká rych­losti, na­tivní CMP+SETE je po­cho­pi­telně rych­lejší.


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

Prvním je Faster Po­pu­lation Counts using AVX2 In­structi­ons, který pře­ko­nává dří­vější SSSE3 fast po­p­count. Chyt­rým vy­u­ži­tím SIMD in­strukcí a bitově pa­ra­lel­ního kódu je možné napsat po­pu­lation count, který je 2x rych­lejší než na­tivní popcnt in­strukce.

Dalším je Fast Sorted-Set In­ter­section using SIMD In­structi­ons, který uka­zuje jak napsat rychlé sjed­no­co­vání množin za pomocí nej­CIS­Co­va­tější ze všech x86 CISC in­strukci PCMPESTRM (hodí se to např. pro Jac­car­dovu po­dob­nost)

A na­ko­nec pak Sor­ting im­pro­ves word-aligned bitmap in­de­xes, což je tour de force pu­b­li­kace o (kom­pri­mo­va­ných) bi­to­vých in­de­xech.

To je všechno, ro­ze­jděte se.


Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články