djbsort, knihovna pro rychlé řazení polí celých čísel využívající AVX2

Daniel J. Bernstein, často jenom djb, matematik, kryptolog a programátor, autor programů qmail nebo djbdns, představil djbsort, softwarovou knihovnu pro rychlé řazení polí celých čísel. Knihovna využívá rozšíření instrukční sady x86 AVX2 [Hacker News].

11.7.2018 12:22 | Ladislav Hagara | Zajímavý software

Komentáře

[cronin]

Nikde nevidím kľúčovú informáciu: toto používate teraz, takúto množinu to zotriedi za čas T1 a potrebuje to M1 pamäte, ale djbsort tú istú množinu na tom istom hardvéri zotriedi za čas T2 a potrebuje na to M2 pamäte. Nevedieť kto je DJB, tak poviem, že je to marketingový žvást, novinárska kačica alebo jednoducho hoax.

[Joe Joe]

Na stranke je zalozka speed. https://sorting.cr.yp.to/speed.html A tam je, že Intel's Integrated Performance Primitives library is reported to take about 32 cycles/byte. djbsort sorts an array of 1024 signed 32-bit integers in L1 cache in 2.5 cycles/byte.

Ale 1048576 už potrebuje cca 15 cyklov.

V špeciálnom prípade je až 10* rýchlejší v bežnom to bude pár percent.

Podstatné je asi to že rôzne rozhádzané polia triedi na konkréton HW takmer presne rovnako dlho, čo môže mať pri crypto problémoch zmysel pre obranu pred side-channel útokmi.

[Tom.š Ze.le.in]

Zajímavé, i když pro mne lehce matoucí. Jaký má smysl metrika cycles/byte řazení při 32bitových čísel? To je něco standardního? (předpokládám, že mi něco uniká - je tahle metrika nezávislá na délce slova? nebo je byte v původním významu odlišném od oktetu a znamená 32bitů? - ale to nesedí tabulka).

A vejde se pořád 1M 32bitů do L1 cache? Myslel jsem, že bývaly menší, ale co já vím.