Come si fa memchr () lavorano sotto il cofano?

Question

Sfondo: Sto cercando di creare un'implementazione pura lingua D di funzionalità che è più o meno equivalente a di C memchr ma usa array e indici invece dei puntatori. La ragione è così che std.string lavorerà con la valutazione della funzione tempo di compilazione. Per quelli di voi ha familiarità w / D, le funzioni possono essere valutati al momento della compilazione, se vengono soddisfatte determinate restrizioni. Una limitazione è che non possono utilizzare i puntatori. Un altro è che essi non possono chiamare funzioni C o usare un linguaggio assembly inline. Avere la stringa di lavoro in biblioteca in fase di compilazione è utile per un certo codice tempo di compilazione generazione hack.

Domanda: Come funziona memchr lavoro sotto il cofano per eseguire velocemente come lo fa? Su Win32, tutto ciò che sono stato in grado di creare in D pura usando i loop semplici è almeno 2 più lento anche w / tecniche di ottimizzazione evidenti, come limiti invalidanti controllo, ciclo di svolgimento, ecc Quali tipi di trucchi, non banali, sono disponibili per qualcosa di semplice come trovare un carattere in una stringa?

Answer 1

Vorrei suggerire di dare un'occhiata a GNU libc s ' fonte. Come per la maggior parte funzioni, conterrà sia una versione generica ottimizzata C della funzione, e lingua assemblaggio ottimizzati per le architetture supportate possibile, sfruttando trucchi macchina specifici.

x86-64 versione SSE2 i risultati di pcmpeqb su una intera cache-linea di dati contemporaneamente (quattro 16B vettori), per ammortizzare l'overhead del precoce uscita pmovmskb / test / jcc.

gcc e clang sono attualmente in grado di auto-vettorizzazione loop con condizioni if() break precoce uscita, in modo da rendere ingenuo asm byte-at-a-tempo dalla realizzazione ovvia C.

Answer 2

Questa implementazione di memchr da newlib è un esempio di qualcuno ottimizzazione memchr: sta leggendo e test 4 byte alla volta (a parte memchr, altre funzioni della libreria sono newlib qui ).

Per inciso, la maggior parte del codice sorgente per il MSVC libreria di runtime è disponibile, come una parte facoltativa dell'installazione MSVC (così, si poteva guardare a quello).

Answer 3

Ecco di FreeBSD memchr ((con licenza BSD)) da memchr.c . in linea del browser il codice sorgente di FreeBSD è un buon riferimento per, esempi di codice BSD-licenza time-tested.

void *
memchr(s, c, n)
    const void *s;
    unsigned char c;
    size_t n;
{
    if (n != 0) {
        const unsigned char *p = s;

        do {
            if (*p++ == c)
                return ((void *)(p - 1));
        } while (--n != 0);
    }
    return (NULL);
}

Answer 4

memchr come memset e memcpy generalmente ridurre al relativamente piccola quantità di codice macchina. È improbabile che siano in grado di riprodurre questo tipo di velocità, senza inlining simile codice assembly . Una questione importante da considerare in un'implementazione è allineamento dei dati .

tecnica generica si può essere in grado di utilizzare è quello di inserire un Sentinel alla fine della stringa cercata, che garantisce che lo troverete. Esso consente di spostare il test per la fine della stringa dal all'interno del ciclo, a dopo il ciclo.

Answer 5

GNU libc sicuramente utilizza il assemblea versione di memchr () (su qualsiasi distro linux comune). Questo è il motivo per cui è così incredibile veloce.
Ad esempio, se contiamo righe nel file di 11GB (come " wc -l " lo fa) si impiegano circa 2.5 secondi con assemblea versione di memchr () da GNU libc. Ma se sostituiamo memchr) chiamata di montaggio (con ad esempio memchr () implementazione C da FreeBSD - la velocità diminuisce a come 30 secondi
questo. è uguale a sostituire memchr () con un semplice ciclo while che confronta un carattere dopo l'altro.