Onde posso encontrar o mais rápido atof implementação mundo?
https://stackoverflow.com/questions/98586
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou procurando uma implementação extremamente rápido atof () no IA32 otimizado para US-en locale, ASCII, e notação não científica. As janelas de vários segmentos CRT cai miseravelmente aqui como ele verifica se há alterações de localidade em cada chamada para isdigit (). Nossa melhor atual é derivado do melhor de perl + TCL do atof implementação, e supera msvcrt.dll de atof por uma ordem de magnitude. Eu quero fazer melhor, mas estou fora de ideias. As instruções x86 relacionados BCD parecia promissor, mas eu não poderia obtê-lo a superar o perl / tcl código C. Pode qualquer SO'ers desenterrar um link para o melhor lá fora? Não x86 soluções baseadas montagem também são bem vindos.
Os esclarecimentos com base em respostas iniciais:
imprecisões das ~ 2 ulp são muito bem para esta aplicação.
Os números a ser convertido chegará em mensagens ASCII através da rede em pequenos lotes e nossas necessidades de aplicação para convertê-los no menor latência possível.
Solução
Qual é a sua exigência de precisão? Se você realmente precisar dele "correta" (sempre recebe o valor de ponto flutuante mais próximo do decimal especificado), que provavelmente será difícil de bater as versões da biblioteca padrão (exceto a remoção de suporte local, o que você já fez), uma vez isto requer fazendo aritmética de precisão arbitrária. Se você está disposto a tolerar um ULP ou dois de erro (e mais do que isso para subnormais), o tipo de abordagem proposta pelo trabalho lata de cruzer e pode ser mais rápido, mas definitivamente não vai produzir
Outras dicas
Esta implementação Acabei de codificação é executado duas vezes mais rápido que o construído em 'atof' no meu desktop. Ele converte 1024 entradas * 1024 * 39 números em 2 segundos, em comparação 4 segundos com gnu padrão do meu sistema 'atof'. (Incluindo o tempo de configuração e obtenção de memória e tudo o que).
UPDATE: Desculpe eu tenho que revogar o meu duas vezes alegação rápido. É mais rápido se a coisa que você está convertendo já está em uma corda, mas se você estiver passando-strings literais codificados, é aproximadamente o mesmo que atof. No entanto, eu vou deixá-lo aqui, como possivelmente com alguns ajustes do arquivo ragel e máquina de estado, você pode ser capaz de gerar mais rápido do código para fins específicos.
https://github.com/matiu2/yajp
Os arquivos interessantes para você são:
https://github.com/matiu2/yajp/blob /master/tests/test_number.cpp
https://github.com/matiu2/yajp/blob/master /number.hpp
Além disso, você pode estar interessado na máquina do Estado que faz a conversão:
Eu tenho implementado algo que você pode achar útil.
Em comparação com atof é sobre x5 mais rápido e se usado com __forceinline sobre x10 mais rápido.
Outra coisa legal é que ele costuras para ter exatamente mesmo aritmética como a implementação CRT.
Claro que tem algumas desvantagens demasiado:
- que suporta apenas precisão simples float,
- e não digitalizar quaisquer valores especiais 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;
}
Parece-me que você quer construir (à mão) o que equivale a uma máquina de estados em que cada Estado lida com o dígito de entrada ou expoente dígitos Nth; esta máquina de estado seria a forma de uma árvore (sem loops!). O objetivo é fazer inteiro aritmética, sempre que possível, e (obviamente) para lembrar variáveis ??de estado ( "menos líder", "ponto decimal na posição 3") nos estados implicitamente, para evitar atribuições, lojas e mais tarde buscar / testes de tais valores . Implementar a máquina de estado com simples antigos "se" declarações sobre os caracteres de entrada única (assim sua árvore chega a ser um conjunto de ifs aninhados). Inline acessos para tamponar caracteres; você não quer uma função chamada para getchar para atrasá-lo.
Os zeros à esquerda pode ser simplesmente suprimida; você pode precisar de um loop aqui para lidar com ridiculamente longo levando as sequências de zero. O primeiro dígito não-zero pode ser recolhido sem truncatura um acumulador ou multiplicando por dez. Os primeiros 4-9 dígitos diferentes de zero (para 16 bits ou 32 bits inteiros) pode ser recolhido com multiplicações de número inteiro por dez valor constante (transformou pela maioria dos compiladores em alguns turnos e acrescenta). [Sobre a parte superior: dígitos de zero não requer qualquer trabalho até um dígito diferente de zero é encontrado e, em seguida, uma multiplicação 10 ^ N N para zeros sequencial é necessária; você pode conectar tudo isso em na máquina de estado]. Algarismos a seguir ao primeiro 4-9 podem ser recolhidos usando 32 ou 64 multiplica bits dependendo do tamanho da palavra da máquina. Desde que você não se preocupam com precisão, você pode simplesmente ignorar dígitos depois que você coletou 32 ou 64 bits pena; Eu acho que você pode realmente parar quando você tem um número fixo de dígitos diferentes de zero com base no que o seu aplicativo realmente faz com esses números. Um ponto decimal encontrado na seqüência de dígitos simplesmente faz com que um ramo na árvore de máquina de estado. Esse ramo sabe a localização implícita do ponto e, portanto, mais tarde, como escalar por uma potência de dez adequadamente. Com esforço, você pode ser capaz de combinar algumas máquinas estado sub-árvores, se você não gosta do tamanho deste código.
[Over the top: manter o número inteiro e partes fracionárias como (pequenos) números inteiros separados. Isso vai exigir uma operação adicional de ponto flutuante no final para combinar as peças fração inteira e, provavelmente, não vale a pena].
[Over the top: Recolher 2 personagens para pares de dígitos em um valor de 16 bits, procurar o valor de 16 bits. Isso evita uma multiplicação dos registos no comércio para um acesso à memória, provavelmente não uma vitória em máquinas modernas].
Ao encontrar "E", recolher o expoente como um número inteiro tal como acima; olhar para cima Precomputed precisão poderes / escala de dez em uma tabela de multiplicador precomputed (reciprocals se sinal "-" presente em expoente) e multiplicar o mantissa coletadas. (Nunca mais faça uma divisão float). Uma vez que cada rotina de coleta expoente está em um ramo diferente (folha) da árvore, tem que ajustar para a localização aparente ou real do ponto decimal por compensação do poder do índice dez.
[Over the top: você pode evitar o custo de ptr++ se você conhece os personagens para o número são armazenados de forma linear em um buffer e não cruzar a fronteira buffer. No estado k ao longo de um galho de árvore, você pode acessar o personagem do k como *(start+k). Um bom compilador pode costumam esconder o "... + k" em um índice compensado no modo de endereçamento.]
right Concluído, esse esquema faz aproximadamente um barato multiplicam-add per dígito diferente de zero, um elenco-to-float da mantissa, e um flutuante multiplicam para dimensionar o resultado por expoente e localização do ponto decimal.
Eu não implementaram o acima. Eu tenho implementado versões dele com loops, eles são muito rápidos.
Eu me lembro que tinha um aplicativo WinForms que realizou tão lentamente ao analisar alguns arquivos de intercâmbio de dados, e todos nós pensamos que era a surra servidor db, mas nosso chefe inteligente, na verdade, descobri que o gargalo foi na chamada que estava convertendo o cordas analisado em decimais!
O mais simples é fazer um loop para cada dígito (personagem) na cadeia, manter uma execução total, multiplicar o total por 10, em seguida, adicionar o valor do próximo dígito. Continue fazendo isso até chegar ao final da corda ou você encontrar um ponto. Se você encontrar um ponto, separar a parte inteira da parte fracionária, em seguida, ter um multiplicador que se divide por 10 para cada dígito. Continuar a adicionar-las como você vai.
Exemplo: 123,456
correndo Total = 0, adicione 1 (agora é 1) execução total = 1 * 10 = 10, adicione 2 (agora é 12) execução total = 12 * 10 = 120, adicionar 3 (agora é 123) encontrou um ponto, se preparar para parte fracionária multiplicador = 0,1, multiplicar por 4, 0,4 obter, adicionar ao total corrente, torna 123,4 multiplicador = 0,1 / 10 = 0,01, multiplicam por 5, obter 0,05, adicionar ao total corrente, faz 123.45 multipiler = 0,01 / 10 = 0,001, multiplique por 6, obter 0,006, adicione a execução total, faz 123.456
É claro, o teste para correção de um número, bem como os números negativos irá torná-lo mais complicado. Mas se você pode "assumir" que a entrada está correta, você pode tornar o código muito mais simples e mais rápido.
Você já pensou olhando para ter a GPU fazer este trabalho? Se você pode carregar as cordas na memória GPU e tê-lo processá-los tudo que você pode encontrar um bom algoritmo que será executado significativamente mais rápido do que o seu processador.
Como alternativa, fazê-lo em um FPGA - Há FPGA PCI-E placas que você pode usar para fazer co-processadores arbitrárias. Use DMA para apontar o FPGA na parte da memória que contém a matriz de strings que deseja converter e deixá-lo whiz através deles deixando os valores convertidos para trás.
Você olhou para um processador quad core? O verdadeiro gargalo na maioria destes casos é o acesso à memória de qualquer maneira ...
-Adam
