¿Dónde puedo encontrar la implementación atof más rápida del mundo?

Question

Estoy buscando una implementación extremadamente rápida de atof() en IA32 optimizada para US-en locale, ASCII y notación no científica. El CRT multiproceso de windows se cae aquí miserablemente, ya que comprueba los cambios locales en cada llamada a isdigit(). Nuestro mejor rendimiento se deriva de lo mejor de la implementación de atof de perl + tcl, y supera al atof de msvcrt.dll en un orden de magnitud. Quiero hacerlo mejor, pero estoy sin ideas. Las instrucciones x86 relacionadas con BCD parecían prometedoras, pero no pude lograr que superaran al código perl/tcl C. ¿Alguno de los SOs puede encontrar un enlace al mejor que hay? Las soluciones basadas en el ensamblaje no x86 también son bienvenidas.

Aclaraciones sobre la base de las respuestas iniciales:

Las imprecisiones de ~ 2 ULP están muy bien para esta aplicación.
Los números que se convertirán llegarán en mensajes ASCII a través de la red en pequeños lotes y nuestra aplicación necesita convertirlos en la latencia más baja posible.

Answer 1

¿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 biblioteca estándar (que no sea eliminar el soporte de configuración regional, que ya ha hecho), ya que esto requiere hacer aritmética de precisión arbitraria. Si está dispuesto a tolerar un ulp o dos de error (y más que eso para los subnormales), el tipo de enfoque propuesto por cruzer puede funcionar y puede ser más rápido, pero definitivamente no producirá < de salida de 0.5ulp. Hará mejor en precisión para calcular el entero y las fracciones por separado, y calcular la fracción al final (por ejemplo, para 12345.6789, calcúlelo 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^n. Esto también le permite hacer la mayoría de los cálculos con enteros en lugar de flotantes.

Las instrucciones BCD no se han implementado en hardware desde (IIRC) el 286, y ahora simplemente están microcodificadas. Es poco probable que sean particularmente de alto rendimiento.

Answer 2

Recuerdo que teníamos una aplicación Winforms que funcionaba tan lentamente al analizar algunos archivos de intercambio de datos, y todos pensamos que era el servidor db, pero nuestro jefe inteligente descubrió que el cuello de botella estaba en la llamada que estaba convirtiendo ¡las cadenas analizadas en decimales!

Lo más simple es hacer un bucle para cada dígito (carácter) en la cadena, mantener un total acumulado, multiplicar el total por 10 y luego agregar el valor del siguiente dígito. Sigue haciendo esto hasta que llegues al final de la cuerda o te encuentres con un punto. Si encuentra un punto, separe la parte entera del número de la parte fraccionaria, luego tenga un multiplicador que se divida por 10 para cada dígito. Sigan sumando sobre la marcha.

Ejemplo: 123.456

total acumulado = 0, se añade 1 (ahora es 1) total acumulado = 1 * 10 = 10, añadir 2 (ahora es 12) corriendo Total = 12 * 10 = 120, agregar 3 (ahora es 123) encontrado un punto, prepararse para la parte fraccional multiplicador = 0.1, multiplicar por 4, obtener 0.4, agregar al total acumulado, hace 123.4 multiplicador = 0.1/10 = 0.01, multiplicar por 5, obtener 0.05 , sumar al total acumulado, hace 123.45 multiplicador = 0.01/10 = 0.001, multiplicar por 6, obtener 0.006, agregar al total acumulado, hace 123.456

Por supuesto, las pruebas de la corrección de un número, así como los números negativos lo harán más complicado. Pero si puede "asumir" que la entrada es correcta, puede hacer que el código sea mucho más simple y rápido.

Answer 3

¿Has considerado considerar hacer que la GPU haga este trabajo? Si puede cargar las cadenas en la memoria de la GPU y que las procese todas, es posible que encuentre un buen algoritmo que funcionará significativamente más rápido que su procesador.

O bien, hazlo en un FPGA: hay placas FPGA PCI-E que puedes usar para hacer coprocesadores arbitrarios. Use DMA para apuntar el FPGA a la parte de la memoria que contiene el conjunto de cadenas que desea convertir y dejar que se mueva a través de ellas dejando los valores convertidos atrás.

¿Has mirado un procesador de cuatro núcleos? El verdadero cuello de botella en la mayoría de estos casos es acceso a la memoria de todos modos ...

-Adam

Answer 4

he implementado algo que puede ser ú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 que tiene algunas desventajas también:

• sólo es compatible con flotador de precisión simple,
• y no escanea todos los valores especiales 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; 
} 

Answer 5

Esta implementación que acabo de terminar de ejecutar se ejecuta dos veces más rápido que el 'atof' incorporado en mi escritorio. Convierte 1024 * 1024 * 39 entradas de números en 2 segundos, en comparación con 4 segundos con el gnu 'atof' estándar de mi sistema. (Incluyendo el tiempo de configuración y obtención de memoria y todo eso).

ACTUALIZACIÓN: Lo siento, tengo que revocar mi reclamo dos veces más rápido. Es más rápido si lo que está convirtiendo ya está en una cadena, pero si lo pasa con literales de cadena codificados, es casi lo mismo que atof. Sin embargo, voy a dejarlo aquí, ya que posiblemente con algunos ajustes del archivo ragel y la máquina de estados, es posible que pueda generar código más rápido para fines 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 usted puede estar interesado en la máquina de estado que realiza la conversión:

Answer 6

Me parece que desea compilar (a mano) lo que equivale a una máquina de estado donde cada estado maneja el enésimo dígito de entrada o los dígitos de exponente; esta máquina de estado tendría la forma de un árbol (¡sin bucles!). El objetivo es hacer aritmética de enteros siempre que sea posible, y (obviamente) recordar las variables de estado ("menos", "punto decimal en la posición 3") en los estados implícitamente, para evitar asignaciones, almacenamientos y posteriores recuperaciones/pruebas de tales valores . Implemente la máquina de estado con simples declaraciones "si" simples en los caracteres de entrada solamente (para que su árbol llegue a ser un conjunto de if anidados). Accesos en línea a los caracteres del buffer; no desea una llamada de función al getchar para reducir la velocidad.

Los ceros a la izquierda pueden simplemente suprimirse; es posible que necesites un bucle aquí para manejar ridículamente largas secuencias cero iniciales. El primer dígito distinto de cero se puede recopilar sin poner a cero un acumulador o multiplicar por diez. Los primeros 4-9 dígitos distintos de cero (para enteros de 16 o 32 bits) se pueden recopilar con multiplicaciones enteras por valor constante de diez (convertido por la mayoría de los compiladores en unos pocos cambios y agrega). [En la parte superior: cero dígitos no requieren ningún trabajo hasta que se encuentre un dígito distinto de cero y luego se requiere una multiplicación de 10^N para N ceros secuenciales; puedes conectar todo esto en la máquina de estados]. Los dígitos que siguen a los primeros 4-9 se pueden recopilar utilizando multiplicaciones de 32 o 64 bits, dependiendo del tamaño de la palabra de su máquina. Como no le importa la precisión, simplemente puede ignorar los dígitos después de reunir el valor de 32 o 64 bits; Supongo que realmente puede detenerse cuando tiene un número fijo de dígitos distintos de cero basado en lo que su aplicación realmente hace con estos números. Un punto decimal encontrado en la cadena de dígitos simplemente causa 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, cómo escalar de forma adecuada con una potencia de diez. Con esfuerzo, puede combinar algunos subárboles de máquina de estado si no le gusta el tamaño de este código.

[Arriba: conserve el entero y las partes fraccionarias como enteros separados (pequeños). Esto requerirá una operación de punto flotante adicional al final para combinar las partes de entero y de fracción, probablemente no valga la pena].

[Arriba: 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 en los registros en el comercio por un acceso a la memoria, probablemente no sea una ganancia en las máquinas modernas].

Al encontrar "E", recoge el exponente como un entero como el anterior; buscar con precisión los poderes precalculados/escalados de diez en una tabla de multiplicador precalculado (recíprocos si el signo "-" está presente en el exponente) y multiplicar la mantisa recopilada. (nunca hagas una división flotante). Dado que cada rutina de recolección de exponente está en una rama (árbol) diferente del árbol, tiene que ajustarse para la ubicación aparente o real del punto decimal al compensar el índice de potencia de diez.

[Arriba: puede 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 kth a lo largo de una rama de árbol, puede acceder al carácter kth como *(start+k). Un buen compilador generalmente puede ocultar el "... + k" en un desplazamiento indexado en el modo de direccionamiento.]

Hecho a la derecha, este esquema hace aproximadamente un multiplicador barato por dígito distinto de cero, uno fundido a flotador 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. Implementé versiones con bucles, son bastante rápidos.