문자열을 정수로 변환하는 데 CPU주기가 얼마나 걸립니까?

Question

이것은 문자열의 길이에 따라 다르므로 가장 쉬운 경우, 최악의 경우 및 중간의 3 가지 경우를 생각해 보겠습니다. 모두 32 비트 부호없는 정수입니다. 값은 0, 4294967295 및 67295 (절반 길이 문자열)입니다.

i7 Nehalem과 같이 최신 CPU에서 작동한다고 가정 해 보겠습니다.

이 작업이 구체적인 숫자와 함께 CPU 집약적 인 방법을 보여 드리고 싶습니다. 알고리즘은 일반적으로 하나의 반복이 이전 반복의 결과를 필요로하는 작은 루프이므로 코드는 상위 수퍼 CPU 최적화를 이용하지 않습니다.

최신 CPU에서이 작업을 수행하기 위해 유선 명령이 있습니까?

편집 : 나 자신에게 대답하려고 시도하고 검색을 수행했습니다. this answer

;parameters esi is a pointer to the string, ecx the length of the string 
string_to_int:  ; 
xor ebx,ebx   ; clear ebx     > 1,1 
.next_digit: 
movzx eax,byte[esi] ;        > 1,1 
inc esi    ;        > 1,1 
sub al,'0'   ; convert from ASCII to number > 1,1 
imul ebx,10   ;        > 1,3 
add ebx,eax   ; ebx = ebx*10 + eax   > 1,1 
loop .next_digit  ; while (--ecx)    > 6 
mov eax,ebx   ;        > 1,1 
ret 

처음이자 마지막 명령에서 Agner Fog's 'Instruction Tables' 및 코드를 사용하여

한 번 실행됩니다. 다른 대기 시간과 실행의 합은 반복 당 18입니다. 따라서 질문의 대답은 4 + 18 * string.length 여야합니다.

• "0"= 22 사이클
• "4294967295"= 184 사이클
• "67,295"= 94 사이클

생각보다 훨씬 작다. 이것은 변환 전용이며 NIC 버퍼에서 RAM으로, RAM에서 CPU 캐시로 복사 ...

올바른 일을 계산합니까? 이 말이 맞는지 저에게 말할 수있는 미세 최적화 전문가가 있습니까? (Mystical maybe?;))

Answer 1

문자열을 정수 값으로 변환해야하는 알고리즘은 일반적으로 받아 들여지는 알고리즘 (32 비트)입니다. 그러나 정수 값을 문자열로 변환하는 알고리즘이 여러 개 있습니다 (명령어 세트, 마이크로 아키텍처, 캐시 크기 등은 말할 필요도 없음). 당신이 모든 것을 제한하더라도, 그 질문에 대한 단 하나의 대답은 없습니다.

비록 조기 최적화의 경우 일 수 있다고 생각합니다. 내가 올바르게 이해한다면 비 - 바이너리 프로토콜에 의해 추가로 발생하는 오버 헤드가 걱정된다. 바이너리 프로토콜은 일반적으로 성능을 높이기 위해 극단적 인 조치입니다. 대기 시간을 제한하고 처리량을 늘리지 않는 것이 일반적입니다.

바이너리 프로토콜 (압축 특성, 사용 편의성, 디버그 용이성 등)을 사용하여 포기해야하는 텍스트 프로토콜에는 많은 이점이 있습니다. 또한 모든 CPU 구조가 리틀 엔디안 (특히 네트워크 바이트 순서는 빅 엔디 언) 인 것은 아니라는 점을 고려해야합니다. 최적화하기 전에 프로토콜에 병목 현상이 있는지 확인하십시오.

Answer 2

XML 파일의 내용을 해석하면 많은 양의 CPU 사이클을 사용합니다. 큰 서버는 구문 분석에 CPU 초 이상이 소요됩니다. 큰 XML 파일을 값의 데이터베이스로 유지하면 평균적으로 데이터를 찾는 것이 데이터를이 또는 해당 숫자 형식으로 변환하는 것보다 수백만 시간 이상 걸립니다.

Ergo (가능하면) 파일을 벡터, 매트릭스 또는 쉽게 색인을 생성 할 수있는 이진 값의 다른 구조로 일회 변환합니다.인덱싱이 불가능한 경우 벡터에서 데이터를 찾는 것만으로 XML 파일에서 동일한 작업을 수행하는 것보다 훨씬 빠릅니다. 어쨌든 일회성 변환에서도 XML 파일에서 데이터를 찾는 일은 발견 한 후에 변환하는 것보다 훨씬 큽니다.

귀하의 질문에 대해서는 루프 당 15 사이클을 10 번 (더 가깝게) 추측했을 것입니다. 나는 루프 [cond] 명령어가 펜티엄이 도입되었을 때 유용하지 않게되었을 수있는 초기 프로세서 세대에서부터 이월되었다는 것을 읽었다. gcc의 어셈블리 출력은 거의 사용되지 않음을 확인합니다. 그것은 이해할 수있는대로 명령을 쉽게 재 순서화하지 ​​않고 명령이 실행될 때 사용할 수없는 상태 플래그를 테스트하여 프로세서 스톨을 초래할 수 있습니다. 그 결과가 (예상되는) 점차적으로 예측 가능해야합니다.