c++ Où puis-je trouver la mise en œuvre la plus rapide au monde?



performance assembly (4)

Avez-vous envisagé de faire faire ce travail par le GPU? Si vous pouvez charger les chaînes dans la mémoire GPU et les faire traiter toutes, vous pouvez trouver un bon algorithme qui fonctionnera beaucoup plus vite que votre processeur.

Alternativement, le faire dans un FPGA - Il existe des cartes FPGA PCI-E que vous pouvez utiliser pour faire des coprocesseurs arbitraires. Utilisez DMA pour pointer le FPGA sur la partie de la mémoire contenant le tableau de chaînes que vous voulez convertir et laissez-le passer à travers eux en laissant les valeurs converties derrière.

Avez-vous regardé un processeur quad core? Le véritable goulot d'étranglement dans la plupart de ces cas est l'accès à la mémoire de toute façon ...

-Adam

https://ffff65535.com

Je suis à la recherche d'une implémentation atof () extrêmement rapide sur IA32, optimisée pour les paramètres régionaux US-en, ASCII et non-scientifiques. Le CRT Windows multithread tombe ici misérablement car il vérifie les changements de paramètres régionaux à chaque appel à isdigit (). Notre meilleur actuel est dérivé du meilleur de la mise en œuvre de perl + tcl, et surpasse l'atof de msvcrt.dll d'un ordre de grandeur. Je veux faire mieux, mais je suis à court d'idées. Les instructions x86 liées au BCD semblaient prometteuses, mais je ne pouvais pas l'obtenir pour surpasser le code C de perl / tcl. Est-ce que n'importe qui peut trouver un lien vers le meilleur? Les solutions basées sur l'assemblage non x86 sont également les bienvenues.

Clarifications basées sur les réponses initiales:

Les inexactitudes de ~ 2 ulp sont bien pour cette application.
Les nombres à convertir arriveront dans des messages ascii sur le réseau en petits lots et notre application doit les convertir dans le temps de latence le plus bas possible.


Je me souviens que nous avions une application Winforms qui fonctionnait si lentement en analysant certains fichiers d'échange de données, et nous pensions tous que c'était le serveur db qui battait, mais notre boss intelligent a découvert que le goulot d'étranglement était dans l'appel qui convertissait les chaînes analysées en décimales!

Le plus simple est de faire une boucle pour chaque chiffre (caractère) dans la chaîne, de garder un total cumulé, de multiplier le total par 10 puis d'ajouter la valeur du chiffre suivant. Continuez à faire cela jusqu'à ce que vous atteigniez la fin de la chaîne ou que vous rencontriez un point. Si vous rencontrez un point, séparez la partie entière de la partie fractionnaire, puis ayez un multiplicateur qui se divise par 10 pour chaque chiffre. Continuez à les additionner comme vous allez.

Exemple: 123.456

total cumulé = 0, ajouter 1 (maintenant c'est 1) total cumulé = 1 * 10 = 10, ajouter 2 (maintenant 12) total cumulé = 12 * 10 = 120, ajouter 3 (maintenant c'est 123) rencontré un point, préparer pour multiplicateur de partie fractionnaire = 0.1, multiplier par 4, obtenir 0.4, ajouter au total cumulé, fait 123.4 multiplicateur = 0.1 / 10 = 0.01, multiplier par 5, obtenir 0.05, ajouter au total cumulé, fait 123.45 multipilote = 0.01 / 10 = 0.001, multiplier par 6, obtenir 0,006, ajouter au total cumulatif, fait 123,456

Bien sûr, tester l'exactitude d'un nombre ainsi que les nombres négatifs le rendra plus compliqué. Mais si vous pouvez "supposer" que l'entrée est correcte, vous pouvez rendre le code beaucoup plus simple et plus rapide.


J'ai implémenté quelque chose que vous pourriez trouver utile. En comparaison avec atof c'est environ x5 plus rapide et si utilisé avec __forceinline environ x10 plus vite. Une autre bonne chose est que cela semble avoir exactement le même arithmétique que l'implémentation crt. Bien sûr, il a aussi quelques inconvénients:

  • il ne supporte que le flotteur à simple précision,
  • et ne scanne aucune valeur spéciale comme #INF, etc ...
__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;
}

Cette implémentation que je viens de terminer le codage est deux fois plus rapide que celle intégrée à 'atof' sur mon bureau. Il convertit les entrées numériques 1024 * 1024 * 39 en 2 secondes, comparé à 4 secondes avec le standard gnu 'atof' de mon système. (Y compris le temps d'installation et d'obtenir de la mémoire et tout ça).

MISE À JOUR: Désolé, je dois révoquer ma demande deux fois plus vite. C'est plus rapide si la chose que vous convertissez est déjà dans une chaîne, mais si vous passez des littéraux de chaîne codés en dur, c'est à peu près la même chose que atof. Cependant, je vais le laisser ici, comme éventuellement avec quelques ajustements du fichier ragel et de la machine d'état, vous pourriez être en mesure de générer du code plus rapide à des fins spécifiques.

https://github.com/matiu2/yajp

Les fichiers intéressants pour vous sont:

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

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

Vous pouvez également être intéressé par la machine d'état qui fait la conversion:





floating-point