Nedávno bol vydaný návrh pre linuxové jadro, do ktorého sa navrhuje zaradiť sadu náplastí s a optimalizovaná implementácia funkcie memchr(). používa sa na vyhľadávanie znaku v poli.
Funkcia memchr() prehľadá prvých n bajtov pamäťovej oblasti, na ktorú ukazuje s pre prvú inštanciu c. C aj bajty v oblasti pamäte, na ktorú ukazuje s, sa interpretujú ako znaky bez znamienka.
Návrh sľubuje byť rýchlejší na nájdenie znaku v bloku pamäte. V testoch vývojárov môže byť nová implementácia pri veľkých vyhľadávaniach takmer štyrikrát rýchlejšia
Na rozdiel od predchádzajúcej verzie, ktorá používala porovnávanie bajtov po bajtoch, navrhovaná implementácia je vytvorená s ohľadom na plné využitie 64-bitových a 32-bitových registrov CPU. Namiesto bajtov sa porovnanie vykonáva pomocou strojových slov, čo umožňuje porovnávať naraz aspoň 4 bajty.
Táto séria opráv optimalizovala "memchr()" a pridala makro pre
"memchr_inv()", aby ho obe funkcie mohli použiť na generovanie bitovej masky.Pôvodná implementácia "memchr()" je založená na porovnaní bajtov,
ktorý plne nevyužíva 64 alebo 32 bitový register v CPU. Realizujeme a
porovnanie slovami tak, aby bolo možné porovnať aspoň 4 bajty s tým istým
počasie. Optimalizovaná memchr() je takmer 4-krát rýchlejšia ako originál
pre dlhé reťaze. V Linux Kernel zistíme, že dĺžka reťazca
hľadaný pomocou "memchr()" je až 512 bajtov v ovládačoch/misc/lkdtm/heap.c.
Pri vyhľadávaní vo veľkých reťazcoch nová verzia sa ukázala byť asi 4-krát rýchlejšia ako stará (napríklad pre reťazce 1000 znakov). Pre malé reťazce nie je efektivita novej implementácie taká výrazná, no stále je vyššia ako pôvodná verzia.
Zaujímavosťou nového návrhu je zlepšenie pre veľké reťazce, ktoré značne zlepšuje časy. Stojí za zmienku, že v jadre Linuxu veľkosť reťazcov spracovaných v memchr() dosahuje 512 bajtov. V našich testoch je nárast výkonu pre 512-bajtové reťazce v situácii, keď sa hľadá znak je na konci reťazca, je to 20 %.
Za zmienku stojí, že pôvodná verzia memchr() je implementovaná technikou porovnania po bajtoch, ktorá plne nevyužíva registre na 64-bitovom alebo 32-bitovom CPU.
Používame porovnávanie celých slov, aby bolo možné na CPU porovnať súčasne 8 znakov. Tento kód je založený na implementácii Davida Lighta.
Vytvoríme dva súbory na meranie výkonu prvého súboru ktorý obsahuje v priemere 10 znakov pred cieľovým znakom. Druhý súbor obsahuje aspoň 1000 znakov pred cieľová postava.
Naša implementácia "memchr()" je mierne lepšie pri prvom teste a takmer 4-krát rýchlejšie ako originál implementácia v druhom teste.
Testovanie jadra 5.18 s novým variantom "memchr()" pre 32-bitové a 64-bitové architektúry neodhalili žiadne problémy.
Čo sa stane, ak p nie je zarovnané o 8 (alebo 4 na 32-bitových cieľoch) bajtov? Nie všetky ciele podporujú nezarovnané (efektívne) zaťaženia, však?
Myslím, že to funguje, ak p nie je zarovnané na 8 alebo 4 bajty. Povedzme, že reťazec má 10 bajtov. Cyklus for tu vyhľadá prvých 8 bajtov. Ak je cieľový znak v posledných 2 bajtoch, druhý cyklus for ho nájde. Funguje to takto aj na 32-bitových strojoch.
Celkový prírastok výkonu ešte nebol vyhodnotený subsystémov jadra pri použití optimalizovaného variantu "memchr()", ani sa nediskutovalo o tom, či sa má implementácia prepísať (volanie funkcie memchr() sa v kóde jadra vrátane ovládačov a súborových systémov vyskytuje 129-krát).
Konečne Ak máte záujem dozvedieť sa viac, môžete skontrolovať podrobnosti Na nasledujúcom odkaze.