세계에서 가장 빠른 atof 구현을 어디에서 찾을 수 있습니까?
https://stackoverflow.com/questions/98586
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
저는 US-en 로케일, ASCII 및 비과학적 표기법에 최적화된 IA32에서 매우 빠른 atof() 구현을 찾고 있습니다.Windows 다중 스레드 CRT는 isdigit()에 대한 모든 호출에서 로케일 변경 사항을 확인하기 때문에 여기서 비참하게 무너집니다.현재 최고 수준은 Perl + tcl의 atof 구현 중 최고 수준에서 파생되었으며 msvcrt.dll의 atof보다 몇 배나 뛰어납니다.더 잘하고 싶지만 아이디어가 부족합니다.BCD 관련 x86 지침은 유망해 보였지만 Perl/tcl C 코드보다 성능이 뛰어나도록 만들 수는 없었습니다.SO'ers 중 최고에 대한 링크를 찾을 수 있습니까?x86 어셈블리 기반이 아닌 솔루션도 환영합니다.
초기 답변을 기반으로 한 설명:
이 응용 프로그램에서는 ~2ulp의 부정확성도 괜찮습니다.
변환할 숫자는 네트워크를 통해 작은 배치로 ASCII 메시지로 도착하며 애플리케이션은 가능한 가장 낮은 대기 시간으로 이를 변환해야 합니다.
해결책
귀하의 정확성 요구 사항은 무엇입니까?정말로 "올바른" 것이 필요한 경우(항상 지정된 소수점에 가장 가까운 부동 소수점 값을 가져옴) 표준 라이브러리 버전을 이기기 어려울 것입니다(이미 수행한 로케일 지원을 제거하는 것 제외). 이를 위해서는 임의의 정밀 연산이 필요합니다.한 두 개의 오류(그리고 비정규 오류의 경우 그 이상)를 기꺼이 용납할 수 있다면 cruzer가 제안한 접근 방식이 작동할 수 있고 더 빠를 수도 있지만 확실히 0.5ulp 미만의 출력을 생성하지는 않습니다.정수 부분과 분수 부분을 별도로 계산하고 마지막 부분에서 분수를 계산하면 정확성 측면에서 더 나은 결과를 얻을 수 있습니다(예:12345.6789의 경우 6*.1 + 7*.01 + 8*.001 + 9*0.0001이 아닌 12345 + 6789 / 10000.0으로 계산합니다. 0.1은 비합리적인 이진 분수이고 0.1^을 계산하면 오류가 빠르게 누적됩니다. N.또한 부동 소수점 대신 정수를 사용하여 대부분의 수학을 수행할 수 있습니다.
BCD 명령어는 (IIRC) 286 이후 하드웨어로 구현되지 않았으며 현재는 단순히 마이크로코드되어 있습니다.특히 고성능이 아닐 가능성이 높습니다.
다른 팁
방금 코딩을 마친 이 구현은 데스크탑에 내장된 'atof'보다 두 배 빠르게 실행됩니다.1024*1024*39 숫자 입력을 2초 만에 변환하는데, 이는 내 시스템의 표준 gnu 'atof'에 비해 4초가 걸립니다.(설정 시간과 메모리 확보 등 모든 것을 포함합니다)
업데이트:죄송합니다. 두 배 빠른 청구를 취소해야 합니다.변환하려는 항목이 이미 문자열에 있으면 더 빠르지만 하드 코딩된 문자열 리터럴을 전달하는 경우 atof와 거의 같습니다.그러나 여기서는 그대로 두겠습니다. ragel 파일과 상태 머신을 약간 조정하면 특정 목적을 위한 더 빠른 코드를 생성할 수 있을 것입니다.
https://github.com/matiu2/yajp
흥미로운 파일은 다음과 같습니다.
https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp
https://github.com/matiu2/yajp/blob/master/number.hpp
또한 변환을 수행하는 상태 시스템에 관심이 있을 수도 있습니다.
유용하다고 생각되는 것을 구현했습니다.atof와 비교하면 약 x5 더 빠르며 다음과 함께 사용하면 __forceinline 약 10배 더 빠릅니다.또 다른 좋은 점은 crt 구현과 정확히 동일한 산술을 사용한다는 것입니다.물론 몇 가지 단점도 있습니다.
- 단정도 부동소수점만 지원합니다.
- #INF 등과 같은 특수 값은 스캔하지 않습니다.
__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;
}
각 상태가 N번째 입력 숫자 또는 지수 숫자를 처리하는 상태 머신에 해당하는 것을 (손으로) 구축하려는 것 같습니다.이 상태 머신은 나무 모양입니다(루프가 없습니다!).목표는 가능할 때마다 정수 산술을 수행하고 (분명히) 상태의 상태 변수("선행 빼기", "3 위치의 소수점")를 암시적으로 기억하여 이러한 값의 할당, 저장 및 나중에 가져오기/테스트를 방지하는 것입니다. .입력 문자에만 기존의 일반 "if" 문을 사용하여 상태 시스템을 구현합니다(따라서 트리는 중첩된 ifs 집합이 됩니다).버퍼 문자에 대한 인라인 액세스;당신은 함수 호출을 원하지 않습니다 getchar 당신의 속도를 늦추기 위해.
앞에 오는 0은 간단히 억제할 수 있습니다.엄청나게 긴 선행 0 시퀀스를 처리하려면 여기에 루프가 필요할 수 있습니다.0이 아닌 첫 번째 숫자는 누산기를 0으로 설정하거나 10을 곱하지 않고도 수집할 수 있습니다.0이 아닌 처음 4-9자리 숫자(16비트 또는 32비트 정수의 경우)는 정수에 상수 값 10을 곱하여 수집할 수 있습니다(대부분의 컴파일러에서는 몇 번의 시프트 및 덧셈으로 변환됨).[맨 위:0의 숫자는 0이 아닌 숫자가 발견될 때까지 어떤 작업도 필요하지 않으며 N개의 연속 0에 대해 10^N을 곱해야 합니다.이 모든 것을 상태 머신에 연결할 수 있습니다.]처음 4-9 다음의 숫자는 컴퓨터의 워드 크기에 따라 32비트 또는 64비트 곱셈을 사용하여 수집될 수 있습니다.정확성에는 관심이 없으므로 32비트 또는 64비트 상당의 숫자를 수집한 후에는 간단히 숫자를 무시할 수 있습니다.응용 프로그램이 실제로 이 숫자로 수행하는 작업을 기반으로 고정된 숫자의 0이 아닌 숫자가 있는 경우 실제로 중지할 수 있다고 생각합니다.숫자 문자열에서 발견된 소수점은 단순히 상태 기계 트리에서 분기를 발생시킵니다.해당 분기는 점의 암시적 위치를 알고 있으므로 나중에 적절하게 10의 거듭제곱으로 크기를 조정하는 방법을 알고 있습니다.이 코드의 크기가 마음에 들지 않으면 노력을 기울여 일부 상태 기계 하위 트리를 결합할 수 있습니다.
[맨 위:정수 부분과 소수 부분을 별도의 (작은) 정수로 유지하십시오.정수와 분수 부분을 결합하기 위해 마지막에 추가 부동 소수점 연산이 필요하지만 아마도 가치가 없을 것입니다.]
[맨 위:숫자 쌍의 2개 문자를 16비트 값으로 수집하고 16비트 값을 검색합니다.이는 메모리 액세스를 위한 레지스터의 곱셈을 방지합니다. 아마도 최신 시스템에서는 승리하지 못할 것입니다.]
"E"를 만나면 위와 같이 지수를 정수로 수집합니다.미리 계산된 승수(지수에 "-" 기호가 있는 경우 역수) 테이블에서 정확하게 미리 계산된/스케일링된 10의 거듭제곱을 찾아 수집된 가수를 곱합니다.(부동 분할을 수행하지 마십시오).각 지수 수집 루틴은 트리의 다른 분기(리프)에 있으므로 10 지수의 거듭제곱을 상쇄하여 소수점의 겉보기 또는 실제 위치를 조정해야 합니다.
[맨 위:비용을 피할 수 있습니다 ptr++ 숫자의 문자가 버퍼에 선형으로 저장되고 버퍼 경계를 넘지 않는다는 것을 알고 있는 경우.나무 가지를 따라 k번째 상태에서는 다음과 같이 k번째 문자에 액세스할 수 있습니다. *(start+k).좋은 컴파일러는 일반적으로 주소 지정 모드의 인덱스 오프셋에서 "...+k"를 숨길 수 있습니다.]
제대로 수행되면 이 체계는 대략 0이 아닌 숫자당 하나의 값싼 곱셈 덧셈, 가수의 부동 소수점 캐스팅, 지수 및 소수점 위치에 따라 결과의 크기를 조정하는 부동 곱셈을 한 번 수행합니다.
위의 사항을 구현하지 않았습니다.루프를 사용하여 버전을 구현했는데 꽤 빠릅니다.
일부 데이터 교환 파일을 구문 분석하는 동안 너무 느리게 수행되는 Winforms 애플리케이션이 있었던 것을 기억합니다. 우리 모두는 그것이 DB 서버 스래싱이라고 생각했지만, 우리의 똑똑한 상사는 실제로 구문 분석된 문자열을 다음으로 변환하는 호출에 병목 현상이 있음을 발견했습니다. 소수!
가장 간단한 방법은 문자열의 각 숫자(문자)를 반복하고 누적 합계를 유지한 다음 합계에 10을 곱하고 다음 숫자의 값을 더하는 것입니다.문자열 끝에 도달하거나 점이 나타날 때까지 이 작업을 계속하세요.점이 나타나면 정수 부분과 분수 부분을 분리한 다음 각 자릿수를 10으로 나누는 승수를 사용하세요.진행하면서 계속 추가하세요.
예:123.456
총 = 0, 1을 추가하고 (현재 1) 총계 = 1 * 10 = 10, 추가 2 (현재 12 세) 런닝 총 = 12 * 10 = 120, 추가 3 (현재 123), 도트를 만나고 준비합니다. 분수 부품 승수 = 0.1, 4를 곱하고, 0.4를 얻고, 런닝 총계를 추가하고, 123.4 곱셈기 = 0.1 / 10 = 0.01, 5를 곱하고, 0.05를 얻고, 달리기 총에 추가하고, 123.45 곱셈기 = 0.01 / 10 = 0.001을 만듭니다. 6을 곱하고, 0.006을 얻고, 총액을 추가하고, 123.456을 만듭니다.
물론 숫자의 정확성과 음수를 테스트하면 문제가 더 복잡해집니다.그러나 입력이 정확하다고 "가정"할 수 있다면 코드를 훨씬 더 간단하고 빠르게 만들 수 있습니다.
GPU가 이 작업을 수행하도록 고려한 적이 있습니까?문자열을 GPU 메모리에 로드하고 이를 모두 처리하게 하면 프로세서보다 훨씬 빠르게 실행되는 좋은 알고리즘을 찾을 수 있습니다.
또는 FPGA에서 수행하십시오. 임의의 보조 프로세서를 만드는 데 사용할 수 있는 FPGA PCI-E 보드가 있습니다.DMA를 사용하여 변환하려는 문자열 배열이 포함된 메모리 부분에 FPGA를 지정하고 변환된 값을 남겨두고 이를 통과하도록 합니다.
쿼드 코어 프로세서를 보셨나요?대부분의 경우 실제 병목 현상은 어쨌든 메모리 액세스입니다.
-아담
