Dove posso trovare il servizio di implementazione più veloce al mondo?

Question

Sto cercando un'implementazione atof() estremamente veloce su IA32 ottimizzata per la locale US-en, ASCII e notazione non scientifica.Il CRT multithread di Windows fallisce miseramente qui mentre controlla le modifiche locali ad ogni chiamata a isdigit().Il nostro meglio attuale deriva dal meglio dell'implementazione atof di perl + tcl e supera atof di msvcrt.dll di un ordine di grandezza.Vorrei fare meglio, ma sono a corto di idee.Le istruzioni x86 relative a BCD sembravano promettenti, ma non sono riuscito a farle superare le prestazioni del codice C perl/tcl.Qualche SO'er può trovare un collegamento al meglio in circolazione?Sono benvenute anche soluzioni non basate su assembly x86.

Chiarimenti basati sulle risposte iniziali:

Imprecisioni di ~2 ulp vanno bene per questa applicazione.
I numeri da convertire arriveranno in messaggi ascii sulla rete in piccoli lotti e la nostra applicazione dovrà convertirli con la minor latenza possibile.

Answer 1

Qual è il tuo requisito di precisione?Se ne hai veramente bisogno "corretto" (ottiene sempre il valore in virgola mobile più vicino al decimale specificato), sarà probabilmente difficile battere le versioni della libreria standard (a parte rimuovere il supporto locale, cosa che hai già fatto), poiché ciò richiede l'esecuzione di operazioni aritmetiche di precisione arbitraria.Se sei disposto a tollerare uno o due errori (e più di quello per i subnormali), il tipo di approccio proposto da Cruzer può funzionare e potrebbe essere più veloce, ma sicuramente non produrrà un output <0,5ulp.Farai una migliore precisione nel calcolare separatamente le parti intere e frazionarie e calcolare la frazione alla fine (ad es.per 12345.6789, calcolalo come 12345 + 6789 / 10000.0, anziché 6*.1 + 7*.01 + 8*.001 + 9*0.0001) poiché 0.1 è una frazione binaria irrazionale e l'errore si accumulerà rapidamente mentre calcoli 0.1^ N.Ciò ti consente anche di eseguire la maggior parte dei calcoli con numeri interi anziché in virgola mobile.

Le istruzioni BCD non sono state implementate nell'hardware dal 286 (IIRC) e al giorno d'oggi sono semplicemente microcodificate.È improbabile che siano particolarmente performanti.

Answer 2

Questa implementazione che ho appena finito di codificare viene eseguita due volte più velocemente di "atof" integrato sul mio desktop.Converte 1024*1024*39 input numerici in 2 secondi, rispetto a 4 secondi con lo gnu 'atof' standard del mio sistema.(Incluso il tempo di installazione, l'acquisizione di memoria e tutto il resto).

AGGIORNAMENTO:Mi dispiace, devo revocare la mia richiesta due volte più velocemente.È più veloce se l'oggetto che stai convertendo è già in una stringa, ma se gli passi valori stringa codificati, è più o meno lo stesso di atof.Tuttavia lo lascerò qui, poiché forse con qualche modifica al file ragel e alla macchina a stati, potresti essere in grado di generare codice più veloce per scopi specifici.

https://github.com/matiu2/yajp

I file interessanti per te sono:

https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp

https://github.com/matiu2/yajp/blob/master/number.hpp

Inoltre potresti essere interessato alla macchina a stati che esegue la conversione:

Answer 3

Ho implementato qualcosa che potresti trovare utile.In confronto ad atof è circa 5 volte più veloce e se usato con __forceinline circa x10 più veloce.Un'altra cosa bella è che sembra avere esattamente la stessa aritmetica dell'implementazione crt.Ovviamente ha anche alcuni contro:

• supporta solo il float a precisione singola,
• e non esegue la scansione di valori speciali come #INF, ecc...

__forceinline bool float_scan(const wchar_t* wcs, float* val)
{
int hdr=0;
while (wcs[hdr]==L' ')
    hdr++;

int cur=hdr;

bool negative=false;
bool has_sign=false;

if (wcs[cur]==L'+' || wcs[cur]==L'-')
{
    if (wcs[cur]==L'-')
        negative=true;
    has_sign=true;
    cur++;
}
else
    has_sign=false;

int quot_digs=0;
int frac_digs=0;

bool full=false;

wchar_t period=0;
int binexp=0;
int decexp=0;
unsigned long value=0;

while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
{
    if (!full)
    {
        if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
        {
            full=true;
            decexp++;
        }
        else
            value=value*10+wcs[cur]-L'0';
    }
    else
        decexp++;

    quot_digs++;
    cur++;
}

if (wcs[cur]==L'.' || wcs[cur]==L',')
{
    period=wcs[cur];
    cur++;

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (!full)
        {
            if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
                full=true;
            else
            {
                decexp--;
                value=value*10+wcs[cur]-L'0';
            }
        }

        frac_digs++;
        cur++;
    }
}

if (!quot_digs && !frac_digs)
    return false;

wchar_t exp_char=0;

int decexp2=0; // explicit exponent
bool exp_negative=false;
bool has_expsign=false;
int exp_digs=0;

// even if value is 0, we still need to eat exponent chars
if (wcs[cur]==L'e' || wcs[cur]==L'E')
{
    exp_char=wcs[cur];
    cur++;

    if (wcs[cur]==L'+' || wcs[cur]==L'-')
    {
        has_expsign=true;
        if (wcs[cur]=='-')
            exp_negative=true;
        cur++;
    }

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (decexp2>=0x19999999)
            return false;
        decexp2=10*decexp2+wcs[cur]-L'0';
        exp_digs++;
        cur++;
    }

    if (exp_negative)
        decexp-=decexp2;
    else
        decexp+=decexp2;
}

// end of wcs scan, cur contains value's tail

if (value)
{
    while (value<=0x19999999)
    {
        decexp--;
        value=value*10;
    }

    if (decexp)
    {
        // ensure 1bit space for mul by something lower than 2.0
        if (value&0x80000000)
        {
            value>>=1;
            binexp++;
        }

        if (decexp>308 || decexp<-307)
            return false;

        // convert exp from 10 to 2 (using FPU)
        int E;
        double v=pow(10.0,decexp);
        double m=frexp(v,&E);
        m=2.0*m;
        E--;
        value=(unsigned long)floor(value*m);

        binexp+=E;
    }

    binexp+=23; // rebase exponent to 23bits of mantisa


    // so the value is: +/- VALUE * pow(2,BINEXP);
    // (normalize manthisa to 24bits, update exponent)
    while (value&0xFE000000)
    {
        value>>=1;
        binexp++;
    }
    if (value&0x01000000)
    {
        if (value&1)
            value++;
        value>>=1;
        binexp++;
        if (value&0x01000000)
        {
            value>>=1;
            binexp++;
        }
    }

    while (!(value&0x00800000))
    {
        value<<=1;
        binexp--;
    }

    if (binexp<-127)
    {
        // underflow
        value=0;
        binexp=-127;
    }
    else
    if (binexp>128)
        return false;

    //exclude "implicit 1"
    value&=0x007FFFFF;

    // encode exponent
    unsigned long exponent=(binexp+127)<<23;
    value |= exponent;
}

// encode sign
unsigned long sign=negative<<31;
value |= sign;

if (val)
{
    *(unsigned long*)val=value;
}

return true;
}

Answer 4

Mi sembra che tu voglia costruire (a mano) ciò che equivale a una macchina a stati in cui ogni stato gestisce l'ennesima cifra di input o le cifre dell'esponente;questa macchina statale avrebbe la forma di un albero (senza anelli!).L'obiettivo è eseguire l'aritmetica degli interi ove possibile e (ovviamente) ricordare implicitamente le variabili di stato ("meno iniziale", "punto decimale nella posizione 3") negli stati, per evitare assegnazioni, memorizzazioni e successivi recuperi/test di tali valori .Implementa la macchina a stati con semplici vecchie istruzioni "if" solo sui caratteri di input (in modo che il tuo albero diventi un insieme di if nidificati).Accessi in linea ai caratteri del buffer;a cui non vuoi una chiamata di funzione getchar per rallentarti.

Gli zeri iniziali possono essere semplicemente soppressi;potresti aver bisogno di un ciclo qui per gestire sequenze zero iniziali ridicolmente lunghe.La prima cifra diversa da zero può essere raccolta senza azzerare un accumulatore o moltiplicare per dieci.Le prime 4-9 cifre diverse da zero (per interi a 16 o 32 bit) possono essere raccolte con moltiplicazioni di numeri interi per il valore costante dieci (trasformato dalla maggior parte dei compilatori in pochi spostamenti e addizioni).[Esagerato:le cifre zero non richiedono alcun lavoro finché non viene trovata una cifra diversa da zero e quindi è richiesta una moltiplicazione 10 ^ N per N zeri sequenziali;puoi collegare tutto questo alla macchina statale].Le cifre successive al primo 4-9 possono essere raccolte utilizzando moltiplicazioni a 32 o 64 bit a seconda della dimensione della parola della macchina.Poiché non ti interessa la precisione, puoi semplicemente ignorare le cifre dopo aver raccolto 32 o 64 bit;Immagino che tu possa effettivamente fermarti quando hai un numero fisso di cifre diverse da zero in base a ciò che la tua applicazione fa effettivamente con questi numeri.Un punto decimale trovato nella stringa di cifre provoca semplicemente un ramo nell'albero della macchina a stati.Quel ramo conosce la posizione implicita del punto e quindi in seguito come scalare in modo appropriato con una potenza di dieci.Con uno sforzo, potresti essere in grado di combinare alcuni sottoalberi della macchina a stati se non ti piace la dimensione di questo codice.

[Esagerato:mantenere le parti intere e frazionarie come numeri interi (piccoli) separati.Ciò richiederà un'ulteriore operazione in virgola mobile alla fine per combinare le parti intere e frazionarie, probabilmente non ne vale la pena].

[Esagerato:raccogli 2 caratteri per coppie di cifre in un valore a 16 bit, cerca il valore a 16 bit.Ciò evita una moltiplicazione dei registri in commercio per l'accesso alla memoria, probabilmente non un vantaggio sulle macchine moderne].

Quando incontri "E", raccogli l'esponente come un numero intero come sopra;cercare accuratamente le potenze precalcolate/ridimensionate di dieci in una tabella di moltiplicatori precalcolati (reciproci se il segno "-" è presente nell'esponente) e moltiplicare la mantissa raccolta.(non eseguire mai una divisione float).Poiché ciascuna routine di raccolta degli esponenti si trova in un ramo (foglia) diverso dell'albero, deve adattarsi alla posizione apparente o effettiva del punto decimale compensando l'indice della potenza di dieci.

[Esagerato:puoi evitare il costo di ptr++ se sai che i caratteri del numero sono memorizzati linearmente in un buffer e non oltrepassano il limite del buffer.Nello stato k-esimo lungo un ramo di un albero, puoi accedere al carattere k-esimo come *(start+k).Un buon compilatore può solitamente nascondere "...+k" in un offset indicizzato nella modalità di indirizzamento.]

Fatto bene, questo schema esegue all'incirca una economica moltiplicazione-aggiunta per cifra diversa da zero, una conversione in virgola mobile della mantissa e una moltiplicazione mobile per ridimensionare il risultato in base all'esponente e alla posizione del punto decimale.

Non ho implementato quanto sopra.Ne ho implementato versioni con loop, sono piuttosto veloci.

Answer 5

Ricordo che avevamo un'applicazione Winforms che funzionava così lentamente durante l'analisi di alcuni file di scambio dati, e tutti pensavamo che fosse il server DB a perdere colpi, ma il nostro capo intelligente in realtà ha scoperto che il collo di bottiglia era nella chiamata che stava convertendo le stringhe analizzate in decimali!

Il modo più semplice è eseguire un ciclo per ogni cifra (carattere) nella stringa, mantenere un totale parziale, moltiplicare il totale per 10, quindi aggiungere il valore della cifra successiva.Continua a farlo finché non raggiungi la fine della stringa o incontri un punto.Se incontri un punto, separa la parte intera del numero dalla parte frazionaria, quindi ottieni un moltiplicatore che si divide per 10 per ogni cifra.Continua ad aggiungerli man mano che procedi.

Esempio:123.456

in esecuzione totale in esecuzione = 0, aggiungi 1 (ora è 1) in esecuzione totale = 1 * 10 = 10, aggiungi 2 (ora è 12) in esecuzione totale = 12 * 10 = 120, aggiungi 3 (ora è 123) riscontrato un punto, preparati per moltiplicatore di parte frazionaria = 0,1, moltiplicare per 4, ottenere 0,4, aggiungere al totale in esecuzione, produce 123,4 moltiplicatore = 0,1 / 10 = 0,01, moltiplica per 5, ottieni 0,05, aggiungi in esecuzione totale, produce 123,45 multipilatore = 0,01 / 10 = 0,001, Moltiplica per 6, ottieni 0,006, aggiungi al totale in esecuzione, fa 123,456

Naturalmente, testare la correttezza di un numero così come i numeri negativi renderà il tutto più complicato.Ma se puoi "supporre" che l'input sia corretto, puoi rendere il codice molto più semplice e veloce.

Answer 6

Hai considerato di far sì che la GPU faccia questo lavoro?Se riesci a caricare le stringhe nella memoria della GPU e farle elaborare tutte, potresti trovare un buon algoritmo che funzionerà molto più velocemente del tuo processore.

In alternativa, fallo in un FPGA: ci sono schede PCI-E FPGA che puoi utilizzare per creare coprocessori arbitrari.Usa DMA per puntare l'FPGA sulla parte di memoria contenente l'array di stringhe che desideri convertire e lascialo sfrecciare attraverso di esse lasciando dietro di sé i valori convertiti.

Hai dato un'occhiata a un processore quad core?Il vero collo di bottiglia nella maggior parte di questi casi è comunque l'accesso alla memoria...

-Adamo