Où puis-je trouver l'application la plus rapide au monde?
https://stackoverflow.com/questions/98586
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je recherche une implémentation atof () extrêmement rapide sur IA32, optimisée pour la notation locale US-en, ASCII et non scientifique. Le tube cathodique multithread de Windows tombe ici misérablement, car il vérifie les changements de paramètres régionaux à chaque appel de isdigit (). Notre meilleur actuel est dérivé du meilleur de la mise en œuvre de perl + tcl, et surpasse celui de msvcrt.dll d'un ordre de grandeur. Je veux faire mieux, mais je suis à court d'idées. Les instructions x86 relatives à BCD semblaient prometteuses, mais je n’arrivais pas à obtenir de meilleures performances que le code C perl / tcl. Les SO 'peuvent-ils trouver un lien vers les meilleurs? Les solutions basées sur les assemblages non x86 sont également les bienvenues.
Clarifications basées sur les réponses initiales:
Les inexactitudes de ~ 2 ulp conviennent à cette application.
Les nombres à convertir arriveront dans des messages ASCII sur le réseau par petits lots et notre application doit les convertir dans le temps de latence le plus bas possible.
La solution
Quelle est votre exigence de précision? Si vous en avez vraiment besoin & "Corrigez &"; (obtient toujours la valeur en virgule flottante la plus proche de la décimale spécifiée), il sera probablement difficile de battre les versions de bibliothèque standard (autres que la suppression du support de paramètres régionaux, ce que vous avez déjà fait), car cela nécessite de faire de l'arithmétique à précision arbitraire. Si vous êtes prêt à tolérer un ou deux ulp d'erreur (et plus que cela pour les subnormals), l'approche proposée par cruzer peut fonctionner et peut être plus rapide, mais elle ne produira certainement pas & Lt; 0.5ulp output . Vous ferez mieux de calculer les parties entières et fractionnaires séparément, puis la fraction à la fin (par exemple, pour 12345.6789, calculez-la comme 12345 + 6789 / 10000.0, plutôt que 6 * .1 + 7 * .01 + 8 * .001 + 9 * 0.0001) puisque 0.1 est une fraction binaire irrationnelle et que l'erreur s'accumulera rapidement lors du calcul de 0.1 ^ n. Cela vous permet également de faire la plupart des calculs avec des entiers au lieu de floats.
Les instructions BCD n’ont pas été implémentées dans le matériel depuis (IIRC) 286 et sont simplement microcodées de nos jours. Ils ne seront probablement pas particulièrement performants.
Autres conseils
Cette implémentation que je viens de terminer de coder est deux fois plus rapide que le "atof" intégré sur mon bureau. Il convertit 1024 * 1024 * 39 entrées numériques en 2 secondes, comparé à 4 secondes avec le gnu standard 'atof' de mon système. (Y compris le temps d'installation et obtenir de la mémoire et tout ça).
MISE À JOUR: Désolé de devoir révoquer ma réclamation deux fois plus rapide. C'est plus rapide si ce que vous convertissez est déjà dans une chaîne, mais si vous lui 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, avec éventuellement quelques modifications du fichier ragel et de la machine à états, vous pourrez peut-être 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 à états qui effectue la conversion:
J'ai mis en place quelque chose qui pourrait vous être utile.
En comparaison avec atof, il est environ 5 fois plus rapide et avec __forceinline environ x10 plus rapidement.
Une autre bonne chose est qu'il semble avoir exactement la même arithmétique que la mise en œuvre de crt.
Bien sûr, il a aussi quelques inconvénients:
- il ne prend en charge que les flottants à simple précision,
- et ne scanne pas les valeurs spéciales telles que #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;
}
Il me semble que vous souhaitez créer (à la main) ce qui revient à une machine à états dans laquelle chaque état gère le Nième chiffre d'entrée ou le nombre d'exposants; cette machine d'état aurait la forme d'un arbre (pas de boucles!). Le but est de faire de l’arithmétique entière autant que possible et (évidemment) de se souvenir des variables d’état implique implicitement pour éviter les affectations, les magasins et les extractions / tests ultérieurs de telles valeurs. Implémentez la machine à états avec l'ancien & Quot; plain & Quot; instructions sur les caractères de saisie uniquement (votre arborescence devient alors un ensemble de if imbriqués). Accès en ligne aux caractères de la mémoire tampon; vous ne voulez pas qu'un appel de fonction à getchar vous ralentisse.
Les zéros non significatifs peuvent simplement être supprimés; vous aurez peut-être besoin d'une boucle ici pour gérer des séquences zéro extrêmement longues. Le premier chiffre différent de zéro peut être collecté sans remise à zéro d'un accumulateur ni multiplication par dix. Les 4 à 9 premiers chiffres non nuls (pour les entiers 16 bits ou 32 bits) peuvent être collectés avec des multiplications d’entiers par la valeur constante dix (convertis par la plupart des compilateurs en quelques décalages et ajouts). [Au-dessus: les chiffres zéro ne nécessitent aucun travail tant qu’un chiffre différent de zéro n’est trouvé et qu’il faut ensuite multiplier 10 ^ N pour N zéros séquentiels; vous pouvez câbler tout cela dans la machine d'état]. Les chiffres qui suivent les premiers 4 à 9 peuvent être collectés en multipliant par 32 ou 64 bits en fonction de la taille des mots de votre machine. Puisque vous ne vous souciez pas de la précision, vous pouvez simplement ignorer les chiffres une fois que vous avez collecté 32 ou 64 bits. J'imagine que vous pouvez réellement arrêter lorsque vous avez un nombre fixe de chiffres non nuls en fonction de ce que votre application fait réellement avec ces chiffres. Un point décimal trouvé dans la chaîne de chiffres provoque simplement une branche dans l'arborescence de la machine à états. Cette branche connaît l'emplacement implicite du point et par conséquent, plus tard, comment s'y prendre avec une puissance de dix. Si vous n’aimez pas la taille de ce code, vous pourrez peut-être combiner des sous-arbres de la machine à états.
[Over the top: conservez les parties entières et fractionnaires sous forme de nombres entiers séparés. Cela nécessitera une opération supplémentaire en virgule flottante à la fin pour combiner les entiers et les fractions, ce qui ne vaut probablement pas la peine].
[Sur le dessus: rassemblez 2 caractères pour les paires de chiffres en une valeur de 16 bits, recherchez la valeur de 16 bits. Cela évite une multiplication dans les registres du commerce pour un accès mémoire, probablement pas une victoire sur les machines modernes].
Si vous rencontrez & "E &", collectez l’exposant sous forme d’entier comme ci-dessus; Recherchez avec précision les puissances précalculées / mises à l'échelle de dix dans un tableau de multiplicateur précalculé (inverses si & "; - &"; signe présent dans l'exposant) et multipliez la mantisse collectée. (ne faites jamais de fracture flottante). Chaque routine de collecte des exposants se trouvant dans une branche différente (feuille) de l’arbre, elle doit être ajustée en fonction de l’emplacement apparent ou réel de la virgule décimale en compensant la puissance de dix index.
[Par dessus: vous pouvez éviter le coût de ptr++ si vous savez que les caractères du numéro sont stockés de manière linéaire dans une mémoire tampon et ne franchissent pas la limite de la mémoire tampon. Dans le kème état le long d’une branche d’arbre, vous pouvez accéder au k-caractère sous la forme *(start+k). Un bon compilateur peut généralement cacher le & Quot; ... + k & Quot; dans un décalage indexé en mode d'adressage.]
Fait bien, ce schéma fait approximativement un multiplier-pas cher par chiffre non nul, un transtypage en flottant de la mantisse et un multiplicateur flottant pour mettre à l'échelle le résultat par exposant et emplacement du point décimal.
Je n'ai pas mis en œuvre ce qui précède. J'en ai implémenté des versions avec des boucles, elles sont assez rapides.
Je me souviens que nous avions une application Winforms qui fonctionnait si lentement lors de l’analyse de certains fichiers d’échange de données. Nous pensions tous que c’était le serveur db qui volait, mais notre chef intelligent a en fait découvert que le goulot d’étranglement était dans l’appel qui convertissait le fichier. des chaînes analysées en décimales!
Le plus simple est de boucler pour chaque chiffre (caractère) de la chaîne, de conserver un total cumulé, de multiplier le total par 10, puis d’ajouter la valeur du chiffre suivant. Continuez ainsi jusqu'à ce que vous atteigniez la fin de la chaîne ou rencontriez un point. Si vous rencontrez un point, séparez la partie entière de la partie décimale, puis un multiplicateur se divisant par 10 pour chaque chiffre. Continuez à les additionner au fur et à mesure.
Exemple: 123.456
total cumulé = 0, ajoutez 1 (maintenant c'est 1) total cumulé = 1 * 10 = 10, ajoutez 2 (maintenant c'est 12) total cumulé = 12 * 10 = 120, ajoutez 3 (maintenant, c'est 123) rencontré un point, préparer la partie décimale multiplicateur = 0.1, multiplier par 4, obtenir 0.4, ajouter au total cumulé, rend 123.4 multiplicateur = 0.1 / 10 = 0.01, multiplier par 5, obtenir 0.05, ajouter au total cumulé, rend 123.45 multipiler = 0.01 / 10 = 0.001, multiplier par 6, obtenir 0.006, ajouter au total cumulé, rend 123.456
Bien sûr, le test de l'exactitude d'un nombre ainsi que des nombres négatifs compliquera les choses. Mais si vous pouvez & "Assumer &"; que la saisie est correcte, vous pouvez rendre le code beaucoup plus simple et plus rapide.
Avez-vous envisagé de demander au GPU de faire ce travail? Si vous pouvez charger les chaînes dans la mémoire du processeur graphique et les faire traiter toutes, vous pouvez trouver un bon algorithme qui s'exécutera bien plus rapidement que votre processeur.
Vous pouvez également le faire dans un FPGA - Il existe des cartes FPGA PCI-E que vous pouvez utiliser pour créer 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 filer à travers en laissant les valeurs converties derrière vous.
Avez-vous examiné un processeur quad core? Le véritable goulot d’étranglement dans la plupart des cas est quand même l’accès à la mémoire ...
-Adam
