Wo kann ich die schnellste atof Implementierung der Welt finden?
https://stackoverflow.com/questions/98586
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich suche nach einem extrem schnellen atof () Implementierung auf IA32 optimiert für US-en locale, ASCII und nicht-wissenschaftliche Notation. Die Fenster multithreaded CRT fällt kläglich hier, wie es für locale Änderungen bei jedem Aufruf überprüft (), um isdigit. Unser derzeitiges am besten aus den besten perl + TCL atof Implementierung abgeleitet und übertrifft msvcrt.dll der atof durch eine Größenordnung. Ich will es besser zu machen, aber ich bin aus Ideen. Die BCD verwandten x86-Befehle schienen vielversprechend, aber ich konnte es nicht das Perl / tcl C-Code zu übertreffen erhalten. Kann kein SO'ers einen Link zu dem besten da draußen graben? Nicht x86-Assembler-basierte Lösungen sind ebenfalls willkommen.
Clarifications basierend auf erste Antworten:
Ungenauigkeiten von ~ 2 ULP sind für diese Anwendung gut.
Die Zahlen umgewandelt werden in ASCII-Nachrichten über das Netzwerk in kleinen Chargen kommen und unsere Anwendung muss sie in der niedrigsten Latenzzeit möglich umzusetzen.
Lösung
Was ist Ihre Genauigkeitsanforderung? Wenn Sie es wirklich brauchen „richtigen“ (immer bekommt die nächste Gleitkommawert auf das Dezimalsystem angegeben), wird es wahrscheinlich schwierig sein, die Standardbibliothek Versionen (außer Entfernen locale-Unterstützung, die Sie bereits getan haben) zu schlagen, da dies erfordert beliebige Genauigkeit arithmetische tun. Wenn Sie bereit sind, eine ULP oder zwei Fehler (und mehr als das für subnormals) zu tolerieren, die Art von Ansatz von cruzer vorgeschlagen arbeiten kann und schneller sein kann, aber es wird definitiv nicht produzieren <0.5ulp ausgegeben. Sie werden bessere Genauigkeit weise tun, um die Ganzzahl- und Bruchteilteile separat, zu berechnen und den Anteil am Ende (zB für 12345,6789 berechnen, berechnen sie als 12345 + 6789 / 10000.0, anstatt 6 * .1 + 7 * .01 + 8 * .001 + 9 * 0,0001), da 0,1 ist eine irrationale Binärbruch und Fehler schnell wie man 0,1 ^ n berechnet ansammeln. Dies können Sie auch tun, die meisten der Mathematik mit ganzen Zahlen anstelle von Schwimmern.
Die BCD-Anweisungen sind in der Hardware, da (IIRC) implementiert die 286 und sind einfach mikrocodierter heute nicht. Sie sind wahrscheinlich nicht besonders leistungsstark.
Andere Tipps
Diese Implementierung ich Codierung gerade fertig läuft doppelt so schnell wie die in ‚atof‘ auf meinem Desktop gebaut. Er wandelt 1024 * 1024 * 39 Anzahl Eingänge in 2 Sekunden, 4 Sekunden, verglichen mit meinem System Standard gnu 'atof'. (Einschließlich der Rüstzeit und immer Speicher und das alles).
UPDATE: Leider habe ich meine doppelt so schnell Anspruch zu widerrufen. Es ist schneller, wenn das, was Sie konvertieren sind bereits in einer Reihe, aber wenn Sie es hart codiert Stringliterale vorbei sind, es ist ungefähr das Gleiche wie atof. Ich werde es aber hier verlassen, da eventuell mit einigen Optimierungen der ragel Datei und Zustandsmaschine, können Sie in der Lage sein, schnellen Code für bestimmte Zwecke zu erzeugen.
https://github.com/matiu2/yajp
Die interessanten Dateien für Sie sind:
https://github.com/matiu2/yajp/blob /master/tests/test_number.cpp
https://github.com/matiu2/yajp/blob/master /number.hpp
Auch Sie können in der Zustandsmaschine interessiert sein, die die Konvertierung funktioniert:
Ich habe etwas umgesetzt Sie nützlich sein können.
Im Vergleich mit atof es geht um x5 schneller und wenn mit __forceinline über x10 schneller eingesetzt.
Eine andere nette Sache ist, dass es genau das gleiche Arithmetik wie crt Implementierung haben Nähte.
Natürlich hat es einige Nachteile auch:
- unterstützt nur mit einfacher Genauigkeit float,
- und scannen keine besonderen Werte wie #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;
}
Es scheint mir, Sie (von Hand) aufbauen wollen, was zu einer Zustandsmaschine beträgt, wobei jeder Zustand die n-ten Eingabeziffer oder Exponenten Ziffern behandelt; würde diese Zustandsmaschine wie ein Baum geformt sein (keine Schleifen!). Das Ziel ist Integer-Arithmetik, wo immer möglich zu tun, und (natürlich) Zustandsvariablen ( „leading minus“, „Komma an Position 3“) in den Staaten implizit, zu vermeiden Zuweisungen, speichert und später holen / Tests solcher Werte zu erinnern, . Implementieren Sie die Zustandsmaschine mit plain old „wenn“ Aussagen über die eingegebenen Zeichen nur (so Ihr Baum bekommt eine Reihe von verschachtelten ifs zu sein). Inline-Zugriffe Zeichen zu puffern; Sie nicht ein Funktionsaufruf möchten Sie getchar verlangsamen.
Führende Nullen kann einfach unterdrückt werden; Sie könnte eine Schleife hier brauchen lächerlich lange führende Null-Sequenzen zu behandeln. Die erste Ziffer ungleich Null kann ohne Nullstellen einen Akkumulator oder Multiplikation mit zehn gesammelt werden. Die ersten 4-9 Ziffern ungleich Null (für 16-Bit oder 32-Bit-Integer) mit ganzzahligen multipliziert mit konstantem Wert von zehn (gedreht von den meisten Compilern in wenigen Verschiebungen und Additionen) gesammelt werden. [Over the top: Nullstellen erfordern keine Arbeit, bis eine Ziffer ungleich Null gefunden wird, und dann eine Multiplikation 10 ^ N für N aufeinanderfolgende Nullen erforderlich ist; Sie können dies alles in der Zustandsmaschine verdrahten]. Ziffern nach den ersten 4-9 können auf der Wortgröße Ihrer Maschine mit 32 oder 64 Bit vervielfachen gesammelt werden, abhängig. Da Sie Genauigkeit nicht kümmern, können Sie einfach ignorieren Ziffern, nachdem Sie 32 oder 64 Bits gesammelt haben wert; Ich würde vermuten, dass Sie tatsächlich stoppen kann, wenn Sie einige feste Anzahl von Nicht-Null-Ziffern haben auf das, was Ihre Anwendung mit diesen Zahlen tatsächlich der Fall ist. Ein Komma in der Ziffernfolge gefunden einfach verursacht einen Zweig in der Zustandsmaschine Baum. Dieser Zweig kennt die implizite Position des Punktes und damit später, wie eine Zehnerpotenz in geeigneter Weise zu skalieren, indem. Mit Mühe, können Sie möglicherweise einige Zustandsmaschinen Teilbäume kombinieren, wenn Sie nicht über die Größe dieses Codes mögen.
[Over the top: Halten Sie die ganze Zahl und Bruchteile als separate (small) ganze Zahlen sind. Dies wird eine zusätzliche Gleitkommaoperation am Ende erfordert die ganzzahligen und Bruchteile zu kombinieren, wahrscheinlich nicht wert].
[Over the top: sammeln 2 Zeichen für Ziffernpaare in einen 16-Bit-Wert, Nachschlagen der 16-Bit-Wert. Dies vermeidet einen mehrfach in den Registern im Handel für einen Speicherzugriff, wahrscheinlich keinen Gewinn auf moderne Maschinen].
Auf der Begegnung „E“, sammelt die Exponenten als eine ganze Zahl wie oben; aufblicken genau vorberechneten / skaliert Zehnerpotenzen nach oben in einer Tabelle von vorberechneten Multiplikator (reziproken wenn „-“ Zeichen in Exponent) und multiplizieren Sie die gesammelten Mantisse. (Nicht tun immer einen Schwimmer divide). Da jede Exponent Sammelroutine in einem anderen Zweig (Blatt) des Baumes ist, hat es für die scheinbare oder tatsächliche Position des Dezimalpunktes einzustellen, indem die Leistung von zehn Indices ausgleicht.
[Over the top: Sie haben die Kosten der ptr++ vermeiden können, wenn Sie die Zeichen für die Nummer wissen linear in einem Puffer gespeichert und nicht kreuzen die Puffergrenze. In dem k-ten Zustand auf einem Ast, können Sie die die k-te Zeichen als *(start+k) zugreifen. Ein guter Compiler kann in der Regel verbirgt die „... + k“ in einem in dem Adressierungsmodus versetzt indexierte.]
Fertig Recht, diese Regelung macht etwa eine billig Multiply-Add pro Ziffer ungleich Null, ein Guss zu float des Mantisse, und ein mehrfach schwimmend das Ergebnis durch Exponenten und Lage des Dezimalpunkt zu skalieren.
Ich habe nicht die oben umgesetzt. Ich habe implementiert Versionen davon mit Loops, sie sind ziemlich schnell.
Ich erinnere mich, wir hatten eine WinForms-Anwendung, die so langsam durchgeführt, während einige Datenaustausch Dateien Parsen, und wir alle dachten, es der DB-Server Dreschen war, aber unser Smart-Chef tatsächlich, dass der Engpass in der Aufforderung war herausgefunden, dass die wurde Umwandlung geparste Zeichenfolgen in Dezimalzahlen!
Am einfachsten ist es für jede Stelle (Zeichen) in der Zeichenfolge Schleife, eine laufende Summe halten, multiplizieren Sie die Summe durch 10 dann den Wert der nächsten Ziffer hinzuzufügen. Halten Sie sich auf diese, bis Sie das Ende der Schnur erreichen oder treffen Sie auf einen Punkt. Wenn Sie einen Punkt treffen, trennen Sie die ganze Zahl teilweise aus dem Bruchteil, dann einen Multiplikator, der sich für jede Ziffer von 10 aufteilt. Halten Sie sich auf das Hinzufügen ihnen, wie Sie gehen.
Beispiel: 123.456
laufende Summe = 0, 1 hinzufügen (jetzt ist es 1) laufende Summe = 1 * 10 = 10, 2 hinzufügen (jetzt ist es 12) gesamt = 12 * 10 = 120, fügen 3 läuft (es ist jetzt 123) ein Punkt angetroffen wird, bereiten für Bruchteil Multiplikator = 0,1, multipliziere mit 4, 0,4 erhalten, fügen Sie insgesamt zu laufen, macht 123,4 Multiplikator = 0,1 / 10 = 0,01, multiplizieren mit 5, 0,05 erhalten, fügt insgesamt zu laufen, macht 123,45 multipiler = 0,01 / 10 = 0,001 multiplizieren um 6, 0,006 erhalten, fügen Sie insgesamt zu laufen, macht 123.456
Natürlich Tests für eine Richtigkeit der Zahl als auch negative Zahlen wird es komplizierter machen. Aber wenn man „davon ausgehen“, dass die Eingabe korrekt ist, können Sie den Code viel einfacher und schneller machen.
Haben Sie darüber nachgedacht Blick in die GPU, diese Arbeit zu tun haben? Wenn Sie die Saiten in GPU-Speicher geladen werden können und sie verarbeiten sie alle können Sie einen guten Algorithmus finden, die deutlich schneller als der Prozessor ausgeführt wird.
Alternativ tut es in einem FPGA - Es FPGA PCI-E-Boards, die Sie beliebig Coprozessoren machen verwenden können. Verwenden Sie DMA das FPGA auf dem Teil des Speichers zu Punkt mit dem Array von Strings, die Sie konvertieren möchten und lassen Sie es durch sie sausen hinter die gewandelten Werte zu verlassen.
Haben Sie sich ein Quad-Core-Prozessor? Der eigentliche Engpass in den meisten dieser Fälle ist Speicherzugriff sowieso ...
-Adam
