[sort of clickbait] FreeBSD can now boot in 25 milliseconds

https://www-theregister-com.cdn.ampproject.org/c/s/www.theregister.com/…

( bucko | 2023. 08. 31., cs – 10:46 )

Replacing a sort algorithm in the FreeBSD kernel has improved its boot speed by a factor of 100 or more…

Nem azt mondom, hogy szánalmas. Ilyeneket ifjú titán koromban szoktam jól megheurékázni. ;)

Valahol itt kezdődik a szoftver vs. bitvadászat határvonala és vitája. Vajon miért volt idáig - ezek szerint - egy gagyi sort algoritmus a kernelben?

Ezen tegnap én is elgondolkodtam, és arra jutottam, hogy valószínűleg kódmemória spórolási célzattal került be az eredeti algoritmus, azaz fontosabb volt ezt a rendezést kevés utasítással megcsinálni, mint kevés idő alatt. Ráadásul ha jól olvastam a peccset, akkor elég sokáig csak néhány elemnek a rendezését végezték ezzel, és csak az utóbbi időben (ez persze lehet akár 20 év is, nem néztem utána) nőtt meg a rendezendő elemek darabszáma annyira, hogy már érzékelhető különbség van egy buta és egy intelligensebb rendező algoritmus futási ideje között. Ráadásul azt is emlegeti, hogy az új algoritmus olyan lehetőségeket is lehetővé tesz (valami kernel modullal betölthető nemtudommi), ami az eredetivel nem ment (vagy csak nagyon drágán?).

tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Csak annyi rémlik (és tévedhetek), hogy a sort általában kernel híváskén és kernel szolgáltatásként is implementált. Régen főként általános qsort() volt elérhető, későbbiekben láttam heapsort() megvalósítást is.

Bár kernelt nem igazán írtam, de sort-ot annál többet használtam. Egész pontosan nem kevés energiát fordítottam arra, hogy a feladataimnak optimális sort módszert megtaláljam. Nekem az jött ki, hogy bármiyen feladatra a legkisebb kódot és a leggyorsabb működést a heapsort adja. Rosszabb esetben az adatokat kell egy kicsit alakítani, de a néhány utasítás veszteség bőven megtérül a gyorsabb működés miatt. Különösen akkor, ha a heapsort() nem teljesen általános. Sőt, AIX->RISC esetén az "úgy sem tudod mit csinálsz" tiltás ellenére a register direktíva is jelentős gyorsulást hozott. Az algoritmus választásánál mindig meg kell vizsgálni a rendezendő adatokat mennyiség és minőség szempontjából. Ebben az esetben a leggyorsabb algoritmust kell alkalmazni bármilyen adatra és - mint írtam - legfeljebb az adatot igazítani az algoritmushoz. Az algoritmus a gyakorlatban nagyon jól működött ~10M adatra, de néhány ezer adatnál >50x gyorsabb működést eredményezett. Amin, ugye, nem tűnik túl lényegesenek, de minden apróság számíthat. Ez nem lóverseny, mégis, ha egy utasítással több fut a kelleténél, akkor akár egy egész diszk fordulatot veszthetsz, aminek igen gyors lassulás lehet a vége. ;)

Azért szószátyárkodtam ennyit, mert - ahogyan írod - láttam már néhány "úgy is kevés az adat, nem kell ezen okoskodni, jó az úgy" gondolatmenet végeredményét. Úgy látszik, végigmentek azon a folyamaton, amin annak idején én is. ;)