recentemente è stata rilasciata una proposta per il kernel Linux, in cui si propone di includere una serie di patch con a implementazione ottimizzata della funzione memchr() utilizzato per cercare un carattere in un array.
La funzione memchr() esegue la scansione degli n byte iniziali dell'area di memoria a cui punta s per la prima istanza di c. Sia c che i byte nell'area di memoria puntata da s vengono interpretati come caratteri senza segno.
la proposta promette essere più veloce per individuare un carattere all'interno di un blocco di memoria. Nei test degli sviluppatori, la nuova implementazione può essere quasi quattro volte più veloce su ricerche di grandi dimensioni
A differenza della versione precedente, che utilizzava un confronto byte per byte, l'implementazione proposta è realizzata considerando il pieno utilizzo dei registri CPU a 64 bit e 32 bit. Al posto dei byte, il confronto viene eseguito utilizzando parole macchina, che consentono di confrontare almeno 4 byte alla volta.
Questa serie di patch ha ottimizzato "memchr()" e ha aggiunto una macro per
"memchr_inv()" in modo che entrambe le funzioni possano usarlo per generare una maschera di bit.L'implementazione originale di "memchr()" si basa sul confronto dei byte,
che non utilizza completamente il registro a 64 o 32 bit nella CPU. Implementiamo a
confronto per parole in modo che almeno 4 byte possano essere confrontati con lo stesso
tempo atmosferico. Il memchr() ottimizzato è quasi 4 volte più veloce dell'originale
per lunghe catene. Nel kernel Linux, troviamo che la lunghezza della stringa
cercato da "memchr()" è fino a 512 byte in drivers/misc/lkdtm/heap.c.
Durante la ricerca su stringhe di grandi dimensioni, la nuova versione si è rivelata circa 4 volte più veloce della vecchia (ad esempio, per stringhe di 1000 caratteri). Per le piccole catene, l'efficienza della nuova implementazione non è così significativa, ma è comunque superiore alla versione originale.
La cosa interessante della nuova proposta è il miglioramento per le grandi catene, che migliora notevolmente i tempi. Vale la pena ricordare che nel kernel Linux, la dimensione delle stringhe elaborate in memchr() raggiunge i 512 byte. Nei nostri test, le prestazioni migliorano per le stringhe da 512 byte, in una situazione in cui il carattere di ricerca è alla fine della stringa, è 20%.
Vale la pena ricordare che la versione originale di memchr() è implementata con la tecnica del confronto byte-wise, che non utilizza completamente i registri sulla CPU a 64 o 32 bit.
Usiamo il confronto di intere parole in modo che 8 caratteri possano essere confrontati contemporaneamente sulla CPU. Questo codice si basa sull'implementazione di David Light.
Creiamo due file per misurare le prestazioni del primo file che contiene in media 10 caratteri prima del carattere di destinazione. Il secondo file contiene almeno 1000 caratteri prima del personaggio bersaglio.
La nostra implementazione di "memchr()" è leggermente migliore al primo test e quasi 4 volte più veloce dell'originale attuazione nella seconda prova.
Test del kernel 5.18 con la nuova variante "memchr()" per architetture a 32 e 64 bit non ha rivelato alcun problema.
Cosa succede se p non è allineato a 8 byte (o 4 su target a 32 bit)? Non tutti i target supportano carichi non allineati (efficienti), giusto?
Penso che funzioni se p non è allineato a 8 o 4 byte. Diciamo che la stringa è di 10 byte. Il ciclo for qui cercherà i primi 8 byte. Se il carattere di destinazione è negli ultimi 2 byte, il secondo ciclo for lo troverà. Funziona così anche su macchine a 32 bit.
Guadagno complessivo delle prestazioni non ancora valutato dei sottosistemi del kernel quando si utilizza la variante ottimizzata "memchr()", né si è discusso se sovrascrivere l'implementazione (la chiamata alla funzione memchr() ricorre 129 volte nel codice del kernel, inclusi driver e file system).
Infine Se sei interessato a saperne di più, puoi controllare i dettagli Nel seguente collegamento.