¿Dónde puedo encontrar el método de implementación más rápido del mundo?
https://stackoverflow.com/questions/98586
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy buscando una implementación atof() extremadamente rápida en IA32 optimizada para la configuración regional de EE. UU., ASCII y notación no científica.El CRT multiproceso de Windows cae miserablemente aquí mientras busca cambios de configuración regional en cada llamada a isdigit().Nuestro mejor rendimiento actual se deriva de lo mejor de la implementación atof de perl + tcl y supera al atof de msvcrt.dll en un orden de magnitud.Quiero hacerlo mejor, pero no tengo ideas.Las instrucciones x86 relacionadas con BCD parecían prometedoras, pero no pude lograr que superaran el código C perl/tcl.¿Puede algún SO'ers encontrar un enlace a lo mejor que existe?También se aceptan soluciones que no estén basadas en ensamblaje x86.
Aclaraciones basadas en las respuestas iniciales:
Las imprecisiones de ~2 ulp están bien para esta aplicación.
Los números a convertir llegarán en mensajes ascii a través de la red en pequeños lotes y nuestra aplicación necesita convertirlos con la menor latencia posible.
Solución
¿Cuál es su requisito de precisión?Si realmente lo necesita "correcto" (siempre obtiene el valor de punto flotante más cercano al decimal especificado), probablemente será difícil superar las versiones de la biblioteca estándar (aparte de eliminar el soporte local, lo cual ya ha hecho), ya que esto requiere hacer aritmética de precisión arbitraria.Si está dispuesto a tolerar uno o dos ulp de error (y más que eso para subnormales), el tipo de enfoque propuesto por Cruzer puede funcionar y puede ser más rápido, pero definitivamente no producirá una salida <0.5ulp.Logrará una mayor precisión si calcula las partes enteras y fraccionarias por separado y calcula la fracción al final (p. ej.para 12345.6789, calculelo como 12345 + 6789 / 10000.0, en lugar de 6*.1 + 7*.01 + 8*.001 + 9*0.0001) ya que 0.1 es una fracción binaria irracional y el error se acumulará rápidamente a medida que calcule 0.1^ norte.Esto también le permite hacer la mayor parte de los cálculos con números enteros en lugar de flotantes.
Las instrucciones BCD no se han implementado en hardware desde (IIRC) el 286, y hoy en día simplemente están microcodificadas.Es poco probable que tengan un rendimiento particularmente alto.
Otros consejos
Esta implementación que acabo de terminar de codificar se ejecuta dos veces más rápido que el 'atof' integrado en mi escritorio.Convierte 1024*1024*39 entradas numéricas en 2 segundos, en comparación con 4 segundos con el gnu 'atof' estándar de mi sistema.(Incluido el tiempo de configuración y la obtención de memoria y todo eso).
ACTUALIZAR:Lo siento, tengo que revocar mi reclamo dos veces más rápido.Es más rápido si lo que estás convirtiendo ya está en una cadena, pero si le pasas literales de cadena codificados, es más o menos lo mismo que atof.Sin embargo, lo dejaré aquí, ya que posiblemente con algunos ajustes en el archivo ragel y la máquina de estado, puedas generar código más rápido para propósitos específicos.
https://github.com/matiu2/yajp
Los archivos interesantes para usted son:
https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp
https://github.com/matiu2/yajp/blob/master/number.hpp
También te puede interesar la máquina de estados que realiza la conversión:
He implementado algo que puede resultarle útil.En comparación con atof, es aproximadamente x5 más rápido y si se usa con __forceinline aproximadamente x10 más rápido.Otra cosa buena es que parece tener exactamente la misma aritmética que la implementación de CRT.Por supuesto, también tiene algunas desventajas:
- solo admite flotador de precisión simple,
- y no escanea ningún valor especial como #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;
}
Me parece que desea construir (a mano) lo que equivale a una máquina de estados donde cada estado maneja el enésimo dígito de entrada o los dígitos exponentes;esta máquina de estados tendría forma de árbol (¡sin bucles!).El objetivo es hacer aritmética de enteros siempre que sea posible y (obviamente) recordar las variables de estado ("menos inicial", "punto decimal en la posición 3") en los estados implícitamente, para evitar asignaciones, almacenamientos y posteriores búsquedas/pruebas de dichos valores. .Implemente la máquina de estados con declaraciones "if" antiguas y simples solo en los caracteres de entrada (para que su árbol se convierta en un conjunto de if anidados).Accesos en línea a caracteres del búfer;no quieres una llamada de función a getchar para frenarte.
Los ceros a la izquierda pueden simplemente suprimirse;es posible que necesite un bucle aquí para manejar secuencias de ceros iniciales ridículamente largas.El primer dígito distinto de cero se puede recolectar sin poner a cero un acumulador o multiplicar por diez.Los primeros 4 a 9 dígitos distintos de cero (para enteros de 16 o 32 bits) se pueden recopilar con multiplicaciones de números enteros por un valor constante de diez (convertido por la mayoría de los compiladores en algunos cambios y sumas).[Excesivo:los dígitos cero no requieren ningún trabajo hasta que se encuentre un dígito distinto de cero y luego se requiere multiplicar 10^N por N ceros secuenciales;puedes conectar todo esto a la máquina de estado].Los dígitos que siguen a los primeros 4 a 9 se pueden recopilar utilizando multiplicaciones de 32 o 64 bits dependiendo del tamaño de palabra de su máquina.Como no le importa la precisión, puede simplemente ignorar los dígitos después de haber recopilado 32 o 64 bits;Supongo que puedes detenerte cuando tengas un número fijo de dígitos distintos de cero en función de lo que tu aplicación realmente hace con estos números.Un punto decimal encontrado en la cadena de dígitos simplemente provoca una rama en el árbol de la máquina de estados.Esa rama conoce la ubicación implícita del punto y, por lo tanto, más adelante sabe cómo escalar adecuadamente en una potencia de diez.Con esfuerzo, es posible que pueda combinar algunos subárboles de máquinas de estado si no le gusta el tamaño de este código.
[Excesivo:mantenga las partes enteras y fraccionarias como números enteros separados (pequeños).Esto requerirá una operación de punto flotante adicional al final para combinar las partes enteras y fraccionarias, probablemente no valga la pena].
[Excesivo:recopile 2 caracteres para pares de dígitos en un valor de 16 bits, busque el valor de 16 bits.Esto evita una multiplicación de los registros a cambio de un acceso a la memoria, lo que probablemente no sea una ventaja en las máquinas modernas].
Al encontrar "E", recopile el exponente como un número entero como se indica arriba;busque potencias de diez precalculadas/escaladas con precisión en una tabla de multiplicadores precalculados (recíprocos si el signo "-" está presente en el exponente) y multiplique la mantisa recopilada.(Nunca hagas una división flotante).Dado que cada rutina de recopilación de exponentes se encuentra en una rama (hoja) diferente del árbol, tiene que ajustarse a la ubicación aparente o real del punto decimal compensando el índice de potencia de diez.
[Excesivo:puedes evitar el costo de ptr++ si sabe que los caracteres del número se almacenan linealmente en un búfer y no cruzan el límite del búfer.En el estado k a lo largo de la rama de un árbol, puede acceder al carácter k como *(start+k).Un buen compilador normalmente puede ocultar "...+k" en un desplazamiento indexado en el modo de direccionamiento.]
Bien hecho, este esquema realiza aproximadamente una multiplicación y suma económica por dígito distinto de cero, una conversión a flotación de la mantisa y una multiplicación flotante para escalar el resultado por exponente y ubicación del punto decimal.
No he implementado lo anterior.He implementado versiones con bucles, son bastante rápidos.
Recuerdo que teníamos una aplicación Winforms que funcionaba muy lentamente mientras analizaba algunos archivos de intercambio de datos, y todos pensamos que era el servidor de base de datos, pero nuestro inteligente jefe descubrió que el cuello de botella estaba en la llamada que convertía las cadenas analizadas en decimales!
La más sencilla es realizar un bucle para cada dígito (carácter) de la cadena, mantener un total acumulado, multiplicar el total por 10 y luego sumar el valor del siguiente dígito.Continúe haciendo esto hasta que llegue al final de la cadena o encuentre un punto.Si encuentra un punto, separe la parte del número entero de la parte fraccionaria y luego tenga un multiplicador que se divida por 10 para cada dígito.Continúe sumándolos a medida que avanza.
Ejemplo:123.456
en ejecución total = 0, agregue 1 (ahora es 1) en ejecución total = 1 * 10 = 10, agregue 2 (ahora es 12) en ejecución total = 12 * 10 = 120, agregue 3 (ahora es 123) encontrado un punto, prepararse para Multiplicador de piezas fraccionales = 0.1, multiplicar por 4, obtener 0.4, agregar al total en funcionamiento, produce 123.4 multiplicador = 0.1 / 10 = 0.01, multiplicar por 5, obtener 0.05, agregar al total de funcionamiento, produce 123.45 multiplicador = 0.01 / 10 = 0.001, Multiplicar por 6, obtener 0.006, agregar al total de funcionamiento, hace 123.456
Por supuesto, probar la exactitud de un número y los números negativos lo hará más complicado.Pero si puedes "asumir" que la entrada es correcta, puedes hacer que el código sea mucho más simple y rápido.
¿Has considerado la posibilidad de que la GPU haga este trabajo?Si puede cargar las cadenas en la memoria de la GPU y hacer que las procese todas, puede encontrar un buen algoritmo que se ejecutará significativamente más rápido que su procesador.
Alternativamente, hágalo en una FPGA: existen placas FPGA PCI-E que puede usar para crear coprocesadores arbitrarios.Utilice DMA para apuntar el FPGA a la parte de la memoria que contiene la matriz de cadenas que desea convertir y déjelo recorrerlas dejando atrás los valores convertidos.
¿Has mirado un procesador de cuatro núcleos?De todos modos, el verdadero cuello de botella en la mayoría de estos casos es el acceso a la memoria...
-Adán
