Collatz 추측을 수작업으로 작성한 어셈블리보다 빠르게 테스트하기위한 C ++ 코드-왜?
나는 어셈블리와 C ++에서 Project Euler Q14에 대한이 두 가지 솔루션을 작성했습니다 . 그것들은 Collatz 추측 을 테스트하기위한 동일한 무차별 대입 접근 방식입니다 . 조립 솔루션은
nasm -felf64 p14.asm && gcc p14.o -o p14
C ++는 다음과 같이 컴파일되었습니다.
g++ p14.cpp -o p14
어셈블리, p14.asm
section .data
fmt db "%d", 10, 0
global main
extern printf
section .text
main:
mov rcx, 1000000
xor rdi, rdi ; max i
xor rsi, rsi ; i
l1:
dec rcx
xor r10, r10 ; count
mov rax, rcx
l2:
test rax, 1
jpe even
mov rbx, 3
mul rbx
inc rax
jmp c1
even:
mov rbx, 2
xor rdx, rdx
div rbx
c1:
inc r10
cmp rax, 1
jne l2
cmp rdi, r10
cmovl rdi, r10
cmovl rsi, rcx
cmp rcx, 2
jne l1
mov rdi, fmt
xor rax, rax
call printf
ret
C ++, p14.cpp
#include <iostream>
using namespace std;
int sequence(long n) {
int count = 1;
while (n != 1) {
if (n % 2 == 0)
n /= 2;
else
n = n*3 + 1;
++count;
}
return count;
}
int main() {
int max = 0, maxi;
for (int i = 999999; i > 0; --i) {
int s = sequence(i);
if (s > max) {
max = s;
maxi = i;
}
}
cout << maxi << endl;
}
속도와 모든 것을 향상시키기위한 컴파일러 최적화에 대해 알고 있지만 어셈블리 솔루션을 더 최적화하는 방법은 많지 않습니다.
C ++ 코드에는 모든 용어와 짝수 용어마다 모듈러스가 있습니다. 어셈블리는 짝수 용어 당 하나의 분할입니다.
그러나 어셈블리는 C ++ 솔루션보다 평균 1 초 더 오래 걸립니다. 왜 이런거야? 나는 주로 호기심에서 묻는다.
실행 시간
내 시스템 : 1.4GHz Intel Celeron 2955U (Haswell 마이크로 아키텍처)의 64 비트 Linux.
g++(최적화되지 않음) : 평균 1272msg++ -O3평균 578ms원래 asm (div) 평균 2650ms
Asm (shr)평균 679ms@johnfound asm , nasm 평균 501 ms로 조립 됨
@hidefromkgb asm 평균 200ms
@Veedrac C ++ 평균 81ms (, 305ms
-O3사용)-O0
64 비트 DIV 명령어가 2로 나누는 좋은 방법이라고 생각한다면 컴파일러의 asm 출력이 -O0(빠른 컴파일, 추가 최적화 없음, 메모리에 저장 / 다시로드 / 디버거가 변수를 수정할 수 있도록 모든 C 문 앞에).
효율적인 asm을 작성하는 방법을 배우려면 Agner Fog의 최적화 어셈블리 가이드 를 참조하십시오 . 또한 특정 CPU에 대한 특정 세부 정보에 대한 지침 테이블과 마이크로 아키텍처 가이드도 있습니다. 더 많은 perf 링크 는 x86 태그 위키를 참조하십시오 .
손으로 작성한 asm으로 컴파일러를이기는 것에 대한 더 일반적인 질문을 참조하십시오. 인라인 어셈블리 언어가 네이티브 C ++ 코드보다 느립니까? . TL : DR : 네가 잘못하면 예 (이 질문처럼).
특히 효율적으로 컴파일 할 수있는 C ++를 작성하려는 경우 일반적으로 컴파일러가 작업을 수행하도록하는 것이 좋습니다 . 또한 어셈블리가 컴파일 된 언어보다 빠릅니다. . 답변 중 하나는 다양한 C 컴파일러가 멋진 트릭으로 정말 간단한 함수를 최적화하는 방법을 보여주는 이 깔끔한 슬라이드에 대한 링크 입니다.
even:
mov rbx, 2
xor rdx, rdx
div rbx
Intel Haswell에서 div r6436 uops 이며 대기 시간은 32-96주기 이고 처리량은 21-74주기 당 1입니다. (RBX를 설정하고 RDX를 0으로 설정하는 데 2 개의 uop이 추가되지만 순서가 잘못된 실행은이를 조기에 실행할 수 있습니다.) DIV와 같은 높은 uop 카운트 명령어는 마이크로 코딩되어 프런트 엔드 병목 현상이 발생할 수도 있습니다. 이 경우 지연은 루프 전달 종속성 체인의 일부이기 때문에 가장 관련성이 높은 요소입니다.
shr rax, 1동일한 부호없는 분할을 수행합니다. 1uop, 1c 지연 시간 , 클록주기 당 2 개 실행 가능.
비교를 위해 32 비트 분할이 더 빠르지 만 교대에 비해 여전히 끔찍합니다. idiv r329 uops, 22-29c 지연 시간 및 Haswell에서 8-11c 처리량 당 하나입니다.
gcc의 -O0asm 출력 ( Godbolt 컴파일러 탐색기 ) 에서 볼 수 있듯이 시프트 명령어 만 사용합니다 . clang -O0은 64 비트 IDIV를 두 번 사용하더라도 생각대로 순진하게 컴파일됩니다. (최적화 할 때 컴파일러는 소스가 동일한 피연산자로 분할 및 모듈러스를 수행 할 때 IDIV의 출력을 모두 사용합니다 (IDIV를 전혀 사용하는 경우))
GCC에는 완전히 순진한 모드가 없습니다. 항상 GIMPLE을 통해 변환되므로 일부 "최적화"를 비활성화 할 수 없습니다 . 여기에는 상수로 나눗셈을 인식하고 시프트 (2의 거듭 제곱) 또는 고정 소수점 곱셈 역 (2의 제곱이 아님)을 사용하여 IDIV ( div_by_13위의 godbolt 링크 참조)를 방지 하는 것이 포함됩니다.
gcc -Os(크기 최적화)을 수행 불행히도, 심지어 역수 코드는 약간 크지 만 더 빠르지 경우, 비 파워의 -2- 부문을 사용 IDIV.
컴파일러 돕기
(이 경우 요약 : 사용 uint64_t n)
우선, 최적화 된 컴파일러 출력을 보는 것이 흥미 롭습니다. ( -O3). -O0속도는 기본적으로 무의미합니다.
asm 출력을보십시오 (Godbolt에서 또는 GCC / clang 어셈블리 출력에서 "노이즈"를 제거하는 방법? 참조 ). 컴파일러가 처음에 최적의 코드를 만들지 못하는 경우 : 컴파일러가 더 나은 코드를 만들도록 안내하는 방식으로 C / C ++ 소스를 작성하는 것이 일반적으로 가장 좋은 방법 입니다. asm을 알아야하고 무엇이 효율적인지 알아야하지만이 지식을 간접적으로 적용합니다. 컴파일러는 또한 좋은 아이디어 소스입니다. 때로는 clang이 멋진 일을 할 수 있으며 gcc를 손으로 잡고 똑같은 일을 할 수 있습니다. 이 답변 과 아래 @Veedrac의 코드에서 언 롤링되지 않은 루프 로 수행 한 작업을 참조하십시오 .)
이 접근 방식은 이식 가능하며 20 년 후에는 미래의 일부 컴파일러가 새로운 ISA 확장 또는 자동 벡터화를 사용하여 향후 하드웨어 (x86 여부에 관계없이)에서 효율적인 모든 것으로 컴파일 할 수 있습니다. 15 년 전의 손으로 쓴 x86-64 asm은 일반적으로 Skylake에 맞게 최적으로 조정되지 않았습니다. 예를 들어 비교 및 분기 매크로 융합은 당시에는 존재하지 않았습니다. 하나의 마이크로 아키텍처에 대해 수작업으로 제작 된 asm에 현재 최적 인 것은 현재 및 미래의 다른 CPU에 최적이 아닐 수 있습니다. @johnfound의 답변에 대한 의견은 이 코드에 큰 영향을 미치는 AMD Bulldozer와 Intel Haswell의 주요 차이점에 대해 설명합니다. 그러나 이론적으로, g++ -O3 -march=bdver3그리고 g++ -O3 -march=skylake옳은 일을 할 것입니다. (또는 -march=native.) 또는 -mtune=...다른 CPU가 지원하지 않을 수있는 명령을 사용하지 않고 조정합니다.
내 느낌은 현재 CPU에 적합한 asm으로 컴파일러를 안내하는 것이 향후 컴파일러에 문제가되지 않아야한다는 것입니다. 그들은 코드를 변환하는 방법을 찾는데 현재 컴파일러보다 낫고 미래의 CPU에서 작동하는 방법을 찾을 수 있기를 바랍니다. 그럼에도 불구하고 미래의 x86은 현재 x86에서 좋은 것에 대해 끔찍하지 않을 것이며, 미래의 컴파일러는 C 소스에서 데이터 이동과 같은 것을 구현하는 동안 asm 관련 함정을 피할 것입니다.
손으로 쓴 asm은 옵티 마이저를위한 블랙 박스이므로 인라인이 입력을 컴파일 시간 상수로 만들 때 상수 전파가 작동하지 않습니다. 다른 최적화도 영향을받습니다. asm을 사용하기 전에 https://gcc.gnu.org/wiki/DontUseInlineAsm 을 읽으십시오 . (그리고 MSVC 스타일의 인라인 asm을 피하십시오. 입력 / 출력은 오버 헤드를 추가하는 메모리를 거쳐야 합니다 .)
이 경우 : 당신 n은 서명 된 유형을 가지고 있으며 gcc는 올바른 반올림을 제공하는 SAR / SHR / ADD 시퀀스를 사용합니다. (음수 입력의 경우 IDIV 및 산술 시프트 "반올림"이 다릅니다. SAR insn set ref 수동 입력 참조 ). (gcc n가 음수 가 될 수 없다는 것을 증명하려고 시도했지만 실패한 경우 IDK . 서명 된 오버플로는 정의되지 않은 동작이므로 가능해야합니다.)
을 사용해야 uint64_t n하므로 SHR 만 가능합니다. 따라서 long32 비트 (예 : x86-64 Windows) 만 있는 시스템에 이식 할 수 있습니다 .
BTW, gcc의 최적화 된 asm 출력은 꽤 좋아 보입니다 (사용 unsigned long n) . 인라인 내부 루프 main()는 다음 을 수행합니다.
# from gcc5.4 -O3 plus my comments
# edx= count=1
# rax= uint64_t n
.L9: # do{
lea rcx, [rax+1+rax*2] # rcx = 3*n + 1
mov rdi, rax
shr rdi # rdi = n>>1;
test al, 1 # set flags based on n%2 (aka n&1)
mov rax, rcx
cmove rax, rdi # n= (n%2) ? 3*n+1 : n/2;
add edx, 1 # ++count;
cmp rax, 1
jne .L9 #}while(n!=1)
cmp/branch to update max and maxi, and then do the next n
내부 루프는 분기가 없으며 루프 전달 종속성 체인의 중요 경로는 다음과 같습니다.
- 3 성분 LEA (3 사이클)
- cmov (Haswell에서 2주기, Broadwell 이상에서 1c).
전체 : 반복 당 5주기, 지연 시간 병목 현상 . 비 순차적 실행은 이것과 병행하여 다른 모든 것을 처리합니다 (이론상 : 실제로 5c / iter에서 실행되는지 확인하기 위해 성능 카운터로 테스트하지 않았습니다).
의 FLAGS 입력 cmov(TEST에서 생성)은 RAX 입력 (LEA-> MOV에서)보다 생성 속도가 빠르기 때문에 중요한 경로에 있지 않습니다.
마찬가지로 CMOV의 RDI 입력을 생성하는 MOV-> SHR은 LEA보다 빠르기 때문에 중요 경로를 벗어납니다. IvyBridge 이상의 MOV는 지연 시간이 없습니다 (등록-이름 변경시 처리됨). (여전히 uop과 파이프 라인의 슬롯이 필요하므로 무료가 아니며 지연 시간이 0입니다). LEA dep 체인의 추가 MOV는 다른 CPU의 병목 현상의 일부입니다.
cmp / jne은 또한 중요 경로의 일부가 아닙니다. 제어 종속성은 중요 경로에 대한 데이터 종속성과 달리 분기 예측 + 예측 실행으로 처리되기 때문에 루프 전달되지 않습니다.
컴파일러를 이길
GCC는 여기서 꽤 잘했습니다. 누구도 부분 플래그 수정 명령에 대한 P4 및 그 거짓 종속성에 대해 신경 쓰지 않기 때문에 inc edx대신을add edx, 1 사용하여 하나의 코드 바이트를 절약 할 수 있습니다.
또한 모든 MOV 명령어를 저장할 수 있으며 TEST : SHR은 CF = 비트를 시프트 아웃하도록 설정하므로 / cmovc대신 사용할 수 있습니다 .testcmovz
### Hand-optimized version of what gcc does
.L9: #do{
lea rcx, [rax+1+rax*2] # rcx = 3*n + 1
shr rax, 1 # n>>=1; CF = n&1 = n%2
cmovc rax, rcx # n= (n&1) ? 3*n+1 : n/2;
inc edx # ++count;
cmp rax, 1
jne .L9 #}while(n!=1)
또 다른 영리한 트릭에 대해서는 @johnfound의 답변을 참조하십시오 : SHR의 플래그 결과를 분기하고 CMOV에 사용하여 CMP를 제거하십시오 .n이 1 (또는 0) 인 경우에만 0으로 시작하십시오. (재미있는 사실 : Nehalem 또는 이전 버전에서 count! = 1을 사용하는 SHR은 플래그 결과를 읽으면 중단을 일으 킵니다 . 이것이 그들이 단일 uop으로 만든 방법입니다.하지만, shift-by-1 특수 인코딩은 괜찮습니다.)
MOV를 피하는 것은 Haswell의 지연 시간에 전혀 도움이되지 않습니다 ( x86의 MOV가 정말로 "무료"일 수 있습니까? 왜 이것을 전혀 재현 할 수 없습니까? ). Intel pre-IvB와 같은 CPU 및 MOV가 제로 지연이 아닌 AMD Bulldozer 제품군에서 크게 도움 이됩니다. 컴파일러의 낭비되는 MOV 명령어는 중요 경로에 영향을줍니다. BD의 복잡한 LEA 및 CMOV는 모두 더 낮은 지연 시간 (각각 2c 및 1c)이므로 지연 시간의 더 큰 부분입니다. 또한 두 개의 정수 ALU 파이프 만 있기 때문에 처리량 병목 현상이 문제가됩니다. AMD CPU의 타이밍 결과가있는 @johnfound의 답변을 참조하십시오 .
Haswell에서도이 버전은 중요하지 않은 uop가 중요 경로에있는 하나에서 실행 포트를 훔쳐 실행 포트를 1주기 지연시키는 간헐적 인 지연을 방지함으로써 약간의 도움이 될 수 있습니다. (이를 리소스 충돌이라고합니다.) 또한 레지스터를 저장하므로 n인터리브 루프에서 병렬로 여러 값을 수행 할 때 도움이 될 수 있습니다 (아래 참조).
LEA의 지연 시간은 Intel SnB 제품군 CPU 의 주소 지정 모드에 따라 다릅니다 . 3 개 구성 요소의 경우 3c ( [base+idx+const], 두 개의 개별 추가가 필요함), 2 개 이하의 구성 요소 (하나의 추가)가있는 1c 만 있습니다. 일부 CPU (예 : Core2)는 단일주기에서 3 성분 LEA를 수행하지만 SnB 제품군은 그렇지 않습니다. 더 나쁜 것은 Intel SnB 제품군이 지연 시간을 표준화하므로 2c uops가 없습니다 . 그렇지 않으면 3 개 구성 요소 LEA가 Bulldozer와 같이 2c에 불과합니다. (3 구성 요소 LEA는 AMD에서도 느립니다.
따라서 lea rcx, [rax + rax*2]/ inc rcx는 lea rcx, [rax + rax*2 + 1]Haswell과 같은 Intel SnB 제품군 CPU에서 보다 빠른 2c 지연 시간 입니다. BD에서는 손익분기 점, Core2에서는 더 나쁩니다. 추가 uop 비용이 들지만 일반적으로 1c 대기 시간을 절약하는 데는 가치가 없지만 대기 시간은 여기서 주요 병목이며 Haswell은 추가 uop 처리량을 처리 할 수있는 충분한 파이프 라인을 가지고 있습니다.
gcc, icc 또는 clang (godbolt에서)은 항상 AND 또는 TEST를 사용하는 SHR의 CF 출력을 사용하지 않았습니다 . 어리석은 컴파일러. : P 그들은 복잡한 기계의 훌륭한 조각이지만 영리한 인간은 종종 소규모 문제에서 그들을 이길 수 있습니다. (물론 생각하는 데 수천에서 수백만 배 더 오래 걸립니다! 컴파일러는 모든 가능한 작업 방법을 검색하는 데 완전한 알고리즘을 사용하지 않습니다. 많은 인라인 코드를 최적화 할 때 너무 오래 걸리기 때문입니다. 그들은 또한 대상 마이크로 아키텍처에서 파이프 라인을 모델링하지 않습니다. 적어도 IACA 또는 기타 정적 분석 도구 와 동일한 세부 사항은 아닙니다 . 단지 몇 가지 휴리스틱을 사용합니다.)
간단한 루프 언 롤링은 도움이되지 않습니다 . 이 루프는 루프 오버 헤드 / 처리량이 아닌 루프 전달 종속성 체인의 지연 시간에 병목 현상이 발생합니다. 이는 CPU가 두 스레드의 명령을 인터리브 할 시간이 많기 때문에 하이퍼 스레딩 (또는 다른 종류의 SMT)에서 잘 수행된다는 것을 의미합니다. 이것은에서 루프를 병렬화하는 것을 의미 main하지만 각 스레드는 n값 범위를 확인 하고 결과적으로 정수 쌍을 생성 할 수 있기 때문에 괜찮습니다 .
단일 스레드 내에서 손으로 인터리빙하는 것도 가능할 수 있습니다 . 한 쌍의 숫자에 대한 시퀀스를 병렬로 계산할 수 있습니다. 각 숫자는 몇 개의 레지스터 만 사용하고 모두 동일한 max/를 업데이트 할 수 있기 때문 maxi입니다. 이것은 더 많은 명령어 수준의 병렬성을 생성 합니다.
트릭은 다른 시작 값 쌍을 얻기 전에 모든 n값에 도달 할 때까지 기다릴 것인지 또는 다른 시퀀스의 레지스터를 건드리지 않고 종료 조건에 도달 한 하나에 대해 새로운 시작점을 얻을 것인지 여부를 결정하는 것입니다. 아마도 각 체인이 유용한 데이터에서 작동하도록 유지하는 것이 가장 좋습니다. 그렇지 않으면 카운터를 조건부로 증가시켜야합니다.1n
아직 n도달 1하지 않은 벡터 요소에 대한 카운터를 조건부로 증가시키기 위해 SSE 압축 비교 항목으로 이것을 수행 할 수도 있습니다. 그런 다음 SIMD 조건부 증가 구현의 더 긴 대기 시간을 숨기려면 더 많은 n값 벡터를 공중 에 유지해야합니다 . 256b 벡터 (4x uint64_t) 에서만 가치가있을 수 있습니다 .
1"sticky"를 감지하는 가장 좋은 전략 은 카운터를 증가시키기 위해 추가하는 all-one의 벡터를 마스킹하는 것입니다. 따라서 1요소에서 a 를 본 후에 증분 벡터는 0을 가지며 + = 0은 작동하지 않습니다.
수동 벡터화에 대한 테스트되지 않은 아이디어
# starting with YMM0 = [ n_d, n_c, n_b, n_a ] (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1): increment vector
# ymm5 = all-zeros: count vector
.inner_loop:
vpaddq ymm1, ymm0, xmm0
vpaddq ymm1, ymm1, xmm0
vpaddq ymm1, ymm1, set1_epi64(1) # ymm1= 3*n + 1. Maybe could do this more efficiently?
vprllq ymm3, ymm0, 63 # shift bit 1 to the sign bit
vpsrlq ymm0, ymm0, 1 # n /= 2
# There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure. Probably worth it
vpblendvpd ymm0, ymm0, ymm1, ymm3 # variable blend controlled by the sign bit of each 64-bit element. I might have the source operands backwards, I always have to look this up.
# ymm0 = updated n in each element.
vpcmpeqq ymm1, ymm0, set1_epi64(1)
vpandn ymm4, ymm1, ymm4 # zero out elements of ymm4 where the compare was true
vpaddq ymm5, ymm5, ymm4 # count++ in elements where n has never been == 1
vptest ymm4, ymm4
jnz .inner_loop
# Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero
vextracti128 ymm0, ymm5, 1
vpmaxq .... crap this doesn't exist
# Actually just delay doing a horizontal max until the very very end. But you need some way to record max and maxi.
손으로 작성한 asm 대신 내장 함수를 사용하여이를 구현할 수 있으며 구현해야합니다.
알고리즘 / 구현 개선 :
보다 효율적인 asm으로 동일한 로직을 구현하는 것 외에도 로직을 단순화하거나 중복 작업을 피하는 방법을 찾으십시오. 예를 들어 시퀀스의 공통 엔딩을 감지하기 위해 메모합니다. 또는 더 나은 방법은 한 번에 8 개의 후행 비트를 확인하는 것입니다 (gnasher의 대답).
@EOF는 tzcnt(또는 bsf)을 사용하여 n/=2한 단계에서 여러 반복 을 수행 할 수 있음을 지적합니다 . SSE 또는 AVX 명령이이를 수행 할 수 없기 때문에 SIMD 벡터화보다 낫습니다. 그래도 n다른 정수 레지스터에서 병렬로 여러 스칼라를 수행하는 것과 여전히 호환됩니다 .
따라서 루프는 다음과 같습니다.
goto loop_entry; // C++ structured like the asm, for illustration only
do {
n = n*3 + 1;
loop_entry:
shift = _tzcnt_u64(n);
n >>= shift;
count += shift;
} while(n != 1);
이렇게하면 반복 횟수가 크게 줄어들 수 있지만 BMI2가없는 Intel SnB 제품군 CPU에서는 가변 카운트 시프트가 느립니다. 3 uops, 2c 지연. (count = 0은 플래그가 수정되지 않았 음을 의미하므로 FLAGS에 대한 입력 종속성이 있습니다.이를 데이터 종속성으로 처리하고 uop에 2 개의 입력 만있을 수 있기 때문에 여러 uop을 사용합니다 (어쨌든 사전 HSW / BDW)). 이것은 사람들이 x86의 미친 CISC 디자인에 대해 불평하는 종류입니다. ISA가 오늘날 처음부터 설계되었을 때보 다 x86 CPU를 느리게 만듭니다. (즉, 이것은 속도 / 전력 비용이 드는 "x86 세금"의 일부입니다.) SHRX / SHLX / SARX (BMI2)는 큰 승리입니다 (1 uop / 1c 대기 시간).
또한 tzcnt (Haswell 이상에서는 3c)를 중요 경로에 배치하므로 루프 전달 종속성 체인의 총 대기 시간이 크게 늘어납니다. 그러나 CMOV 또는 레지스터 보유 준비가 필요하지 않습니다 n>>1. @Veedrac의 답변은 여러 반복에 대해 tzcnt / shift를 연기함으로써이 모든 것을 극복하며 이는 매우 효과적입니다 (아래 참조).
BSF 또는 TZCNTn 는 그 시점에서 절대 0이 될 수 없기 때문에 안전하게 사용할 수 있습니다. TZCNT의 머신 코드는 BMI1을 지원하지 않는 CPU에서 BSF로 디코딩됩니다. (의미없는 접두사는 무시되므로 REP BSF는 BSF로 실행됩니다).
TZCNT는이를 지원하는 AMD CPU에서 BSF보다 훨씬 더 나은 성능을 제공하므로 REP BSF입력이 출력이 아닌 0 인 경우 ZF를 설정하는 데 신경 쓰지 않아도 를 사용하는 것이 좋습니다 . 사용할 때 어떤 컴파일러는 이렇게 __builtin_ctzll도 함께 -mno-bmi.
그들은 Intel CPU에서 똑같이 수행하므로 그게 중요한 경우 바이트를 저장하십시오. Intel (Skylake 이전)의 TZCNT는 BSF와 마찬가지로 쓰기 전용 출력 피연산자에 대한 거짓 의존성을 가지고있어 입력 = 0 인 BSF가 대상을 수정되지 않은 상태로 남겨 두는 문서화되지 않은 동작을 지원합니다. 따라서 Skylake에 대해서만 최적화하지 않는 한이 문제를 해결해야하므로 추가 REP 바이트에서 얻을 수있는 것이 없습니다. (인텔은 종종 x86 ISA 매뉴얼이 요구하는 것 이상으로 사용되어서는 안되는 것에 의존하거나 소급 적으로 허용되지 않는 널리 사용되는 코드를 깨뜨리는 것을 방지합니다. 예를 들어 Windows 9x는 TLB 항목에 대한 추측 성 프리 페치가 없다고 가정 합니다. 인텔이 TLB 관리 규칙을 업데이트하기 전에 코드가 작성되었을 때 .)
어쨌든 Haswell의 LZCNT / TZCNT는 POPCNT와 동일한 false dep을 가지고 있습니다 . 이 Q & A를 참조 하세요 . 이것이 @Veedrac의 코드에 대한 gcc의 asm 출력에서 dst = src를 사용하지 않을 때 TZCNT의 대상으로 사용할 레지스터에서 xor-zeroing 을 사용하여 dep 체인을 끊는 것을 볼 수 있는 이유입니다. TZCNT / LZCNT / POPCNT는 목적지를 정의되지 않거나 수정하지 않은 상태로 두지 않기 때문에 Intel CPU의 출력에 대한 이러한 잘못된 종속성은 순전히 성능 버그 / 제한 사항입니다. 아마도 동일한 실행 장치로 이동하는 다른 uop처럼 작동하도록 일부 트랜지스터 / 전력의 가치가있을 것입니다. 소프트웨어에서 볼 수있는 유일한 장점은 다른 마이크로 아키텍처 제한과의 상호 작용에 있습니다 . 즉, 인덱스 주소 지정 모드로 메모리 피연산자를 마이크로 퓨즈 할 수 있습니다 . Haswell에서는하지만 Intel이 LZCNT / TZCNT에 대한 잘못된 종속성을 제거한 Skylake에서는 인덱싱 된 주소 지정 모드를 "un-laminate"하는 반면 POPCNT는 모든 addr 모드를 마이크로 융합 할 수 있습니다.
다른 답변의 아이디어 / 코드 개선 :
@hidefromkgb의 대답 에는 3n + 1 후에 오른쪽 교대를 한 번 할 수 있다는 좋은 관찰이 있습니다. 단계 사이의 확인을 생략하는 것보다 더 효율적으로이를 계산할 수 있습니다. 그 대답의 asm 구현은 깨졌지만 (개수가 1 ROR rdi,2보다 큰 SHRD 후에 정의되지 않은 OF에 따라 다름) 느립니다. 보다 빠르며 SHRD rdi,rdi,2중요 경로에서 두 개의 CMOV 명령을 사용하는 것이 추가 테스트보다 느립니다. 병렬로 실행할 수 있습니다.
나는 깔끔한 / 개선 된 C (컴파일러가 더 나은 asm을 생성하도록 안내)를 넣고 테스트 + 더 빠른 asm (C 아래의 주석에서)을 Godbolt에 올려 놓았습니다 . @ hidefromkgb의 답변 링크를 참조하십시오 . (이 답변은 큰 Godbolt URL에서 30k 문자 제한에 도달했지만 shortlink 는 썩을 수 있으며 어쨌든 goo.gl에는 너무 길었습니다.)
또한 write()한 번에 하나의 문자를 쓰는 대신 문자열로 변환하여 하나 를 만들도록 출력 인쇄를 개선했습니다 . 이것은 perf stat ./collatz(성능 카운터를 기록하기 위해) 전체 프로그램 타이밍에 미치는 영향을 최소화 하고 중요하지 않은 asm의 일부를 난독 화했습니다.
@Veedrac의 코드
나는 우리가 알고있는 만큼 오른쪽 시프트를 하고 루프를 계속하기 위해 확인하면서 아주 작은 속도 향상을 얻었습니다 . limit = 1e8의 경우 7.5 초에서 Core2Duo (Merom)의 경우 7.275 초로, 언롤 계수는 16입니다.
코드 + Godbolt에 대한 주석 . 이 버전을 clang과 함께 사용하지 마십시오. 지연 루프로 어리석은 일을합니다. tmp 카운터를 사용하고 나중에 k추가하면 countclang이 수행하는 작업이 변경되지만 gcc 가 약간 손상됩니다.
의견 토론을 참조하십시오 : Veedrac의 코드는 우수한 BMI1 (즉,하지 셀러론 / 펜티엄)와 CPU에서
C ++ 컴파일러가 유능한 어셈블리 언어 프로그래머보다 더 최적의 코드를 생성 할 수 있다고 주장하는 것은 매우 나쁜 실수입니다. 특히이 경우. 인간은 항상 컴파일러가 할 수있는 것보다 더 나은 코드를 만들 수 있으며,이 특정 상황은이 주장을 잘 보여줍니다.
당신이 보는 타이밍 차이는 질문의 어셈블리 코드가 내부 루프에서 최적과는 거리가 멀기 때문입니다.
(아래 코드는 32 비트이지만 64 비트로 쉽게 변환 할 수 있습니다.)
예를 들어 시퀀스 함수는 5 개의 명령어로만 최적화 할 수 있습니다.
.seq:
inc esi ; counter
lea edx, [3*eax+1] ; edx = 3*n+1
shr eax, 1 ; eax = n/2
cmovc eax, edx ; if CF eax = edx
jnz .seq ; jmp if n<>1
전체 코드는 다음과 같습니다.
include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"
start:
InitializeAll
mov ecx, 999999
xor edi, edi ; max
xor ebx, ebx ; max i
.main_loop:
xor esi, esi
mov eax, ecx
.seq:
inc esi ; counter
lea edx, [3*eax+1] ; edx = 3*n+1
shr eax, 1 ; eax = n/2
cmovc eax, edx ; if CF eax = edx
jnz .seq ; jmp if n<>1
cmp edi, esi
cmovb edi, esi
cmovb ebx, ecx
dec ecx
jnz .main_loop
OutputValue "Max sequence: ", edi, 10, -1
OutputValue "Max index: ", ebx, 10, -1
FinalizeAll
stdcall TerminateAll, 0
이 코드를 컴파일하려면 FreshLib 가 필요합니다.
내 테스트 (1GHz AMD A4-1200 프로세서)에서 위 코드는 질문의 C ++ 코드보다 약 4 배 빠르며 (컴파일시 -O0: 430ms 대 1900ms) 두 배 이상 빠릅니다 (430 ms vs. 830 ms) C ++ 코드가 -O3.
두 프로그램의 출력은 동일합니다. i = 837799에서 최대 시퀀스 = 525입니다.
더 많은 성능을 위해 : 간단한 변경은 n = 3n + 1 이후 n이 짝수이므로 즉시 2로 나눌 수 있습니다. n은 1이 아니므로 테스트 할 필요가 없습니다. 따라서 몇 개의 if 문을 저장하고 다음과 같이 작성할 수 있습니다.
while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
n = (3*n + 1) / 2;
if (n % 2 == 0) {
do n /= 2; while (n % 2 == 0);
if (n == 1) break;
}
}
여기에 큰 승리가 있습니다. n의 가장 낮은 8 비트를 보면 2로 8 배로 나눌 때까지의 모든 단계는이 8 비트에 의해 완전히 결정됩니다. 예를 들어 마지막 8 비트가 0x01이면 이진수는 ???? 0000 0001 다음 단계는 다음과 같습니다.
3n+1 -> ???? 0000 0100
/ 2 -> ???? ?000 0010
/ 2 -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2 -> ???? ???0 0010
/ 2 -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2 -> ???? ???? ?010
/ 2 -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2 -> ???? ???? ???0
/ 2 -> ???? ???? ????
따라서 이러한 모든 단계를 예측할 수 있으며 256k + 1은 81k + 1로 대체됩니다. 모든 조합에 대해 유사한 일이 발생합니다. 따라서 큰 switch 문으로 루프를 만들 수 있습니다.
k = n / 256;
m = n % 256;
switch (m) {
case 0: n = 1 * k + 0; break;
case 1: n = 81 * k + 1; break;
case 2: n = 81 * k + 1; break;
...
case 155: n = 729 * k + 425; break;
...
}
n ≤ 128이 될 때까지 루프를 실행하십시오. 그 지점에서 n은 2로 8 개 미만의 분할로 1이 될 수 있고 한 번에 8 개 이상의 단계를 수행하면 처음으로 1에 도달하는 지점을 놓치게됩니다. 그런 다음 "정상"루프를 계속하거나 1에 도달하는 데 필요한 단계가 몇 개 더 있는지 알려주는 테이블을 준비하십시오.
추신. 나는 Peter Cordes의 제안이 그것을 더 빨리 만들 것이라고 강력하게 의심합니다. 하나를 제외하고 조건부 분기가 전혀 없으며 루프가 실제로 끝날 때를 제외하고는 올바르게 예측됩니다. 따라서 코드는 다음과 같습니다.
static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }
while (n > 128) {
size_t lastBits = n % 256;
n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}
실제로 n의 마지막 9, 10, 11, 12 비트를 한 번에 처리하는 것이 더 빠른지 여부를 측정합니다. 각 비트에 대해 테이블의 항목 수는 두 배가되고 테이블이 더 이상 L1 캐시에 맞지 않으면 속도가 느려집니다.
PPS. 연산 개수가 필요한 경우 : 각 반복에서 정확히 8 개를 2로 나누고 가변 개수의 (3n + 1) 연산을 수행하므로 연산을 계산하는 확실한 방법은 또 다른 배열이 될 것입니다. 그러나 우리는 실제로 단계 수를 계산할 수 있습니다 (루프의 반복 횟수에 따라).
문제를 약간 재정의 할 수 있습니다. 홀수이면 n을 (3n + 1) / 2로 바꾸고 짝수이면 n을 n / 2로 바꿉니다. 그런 다음 모든 반복은 정확히 8 단계를 수행하지만 부정 행위를 고려할 수 있습니다. :-) 따라서 r 연산이 n <-3n + 1이고 s 연산이 n <-n / 2라고 가정합니다. n <-3n + 1은 n <-3n * (1 + 1 / 3n)을 의미하기 때문에 결과는 정확히 n '= n * 3 ^ r / 2 ^ s가됩니다. 로그를 취하면 r = (s + log2 (n '/ n)) / log2 (3)를 찾습니다.
n ≤ 1,000,000까지 루프를 수행하고 시작점 n ≤ 1,000,000에서 몇 번의 반복이 필요한지 미리 계산 된 테이블이있는 경우, 위와 같이 r을 가장 가까운 정수로 반올림하여 계산하면 s가 실제로 크지 않는 한 올바른 결과를 얻을 수 있습니다.
다소 무관 한 메모 : 더 많은 성능 해킹!
[첫 번째«추론»이 마침내 @ShreevatsaR에 의해 반박되었습니다. 제거됨]
시퀀스를 순회 할 때 현재 요소의 2 개 이웃에서 가능한 경우 3 개만 얻을 수 있습니다
N(먼저 표시됨).- [홀수]
- [홀수] [짝수]
- [짝수] [짝수]
이 두 요소를 뛰어 넘는다는 것은 각각
(N >> 1) + N + 1,((N << 1) + N + 1) >> 1및 을 계산하는 것을 의미합니다N >> 2.두 경우 모두 (1)과 (2)에 대해 첫 번째 공식 인
(N >> 1) + N + 1.사례 (1)은 분명합니다. Case (2)는을 의미
(N & 1) == 1하므로 N이 2 비트 길이이고 해당 비트가ba최상위에서 최하위까지 라고 가정하면 (일반성을 잃지 않고)a = 1다음이 유지됩니다.(N << 1) + N + 1: (N >> 1) + N + 1: b10 b1 b1 b + 1 + 1 ---- --- bBb0 bBb어디서
B = !b. 첫 번째 결과를 오른쪽으로 이동하면 원하는 것을 정확하게 얻을 수 있습니다.QED :
(N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.입증 된대로 단일 삼항 연산을 사용하여 시퀀스 2 요소를 한 번에 순회 할 수 있습니다. 또 다른 2 배의 시간 단축.
결과 알고리즘은 다음과 같습니다.
uint64_t sequence(uint64_t size, uint64_t *path) {
uint64_t n, i, c, maxi = 0, maxc = 0;
for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
c = 2;
while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
c += 2;
if (n == 2)
c++;
if (c > maxc) {
maxi = i;
maxc = c;
}
}
*path = maxc;
return maxi;
}
int main() {
uint64_t maxi, maxc;
maxi = sequence(1000000, &maxc);
printf("%llu, %llu\n", maxi, maxc);
return 0;
}
n > 2시퀀스의 총 길이가 홀수이면 프로세스가 1이 아닌 2에서 멈출 수 있기 때문에 비교 합니다.
[편집하다:]
이것을 어셈블리로 번역합시다!
MOV RCX, 1000000;
DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;
@main:
XOR RSI, RSI;
LEA RDI, [RCX + 1];
@loop:
ADD RSI, 2;
LEA RDX, [RDI + RDI*2 + 2];
SHR RDX, 1;
SHRD RDI, RDI, 2; ror rdi,2 would do the same thing
CMOVL RDI, RDX; Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
CMOVS RDI, RDX;
CMP RDI, 2;
JA @loop;
LEA RDX, [RSI + 1];
CMOVE RSI, RDX;
CMP RAX, RSI;
CMOVB RAX, RSI;
CMOVB RBX, RCX;
SUB RCX, 2;
JA @main;
MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;
@itoa:
XOR RDX, RDX;
DIV RCX;
ADD RDX, '0';
PUSH RDX;
TEST RAX, RAX;
JNE @itoa;
PUSH RCX;
LEA RAX, [RBX + 1];
TEST RBX, RBX;
MOV RBX, RDI;
JNE @itoa;
POP RCX;
INC RDI;
MOV RDX, RDI;
@outp:
MOV RSI, RSP;
MOV RAX, RDI;
SYSCALL;
POP RAX;
TEST RAX, RAX;
JNE @outp;
LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;
다음 명령을 사용하여 컴파일하십시오.
nasm -f elf64 file.asm
ld -o file file.o
Godbolt에서 Peter Cordes 가 작성한 asm의 C 및 개선 / 버그 수정 버전을 참조하십시오 . (편집자 주 : 답변에 내 물건을 넣어서 죄송하지만 내 답변은 Godbolt 링크 + 텍스트에서 30k 문자 제한에 도달했습니다!)
C ++ 프로그램은 소스 코드에서 기계어 코드를 생성하는 동안 어셈블리 프로그램으로 변환됩니다. 어셈블리가 C ++보다 느리다고 말하는 것은 사실상 잘못된 것입니다. 또한 생성 된 이진 코드는 컴파일러마다 다릅니다. 따라서 스마트 C ++ 컴파일러 는 멍청한 어셈블러의 코드보다 더 최적화되고 효율적인 바이너리 코드를 생성 할 수 있습니다.
그러나 나는 당신의 프로파일 링 방법론에 특정한 결함이 있다고 생각합니다. 다음은 프로파일 링에 대한 일반적인 지침입니다.
- 시스템이 정상 / 유휴 상태인지 확인하십시오. 시작했거나 CPU를 많이 사용하는 (또는 네트워크를 통해 폴링) 실행중인 모든 프로세스 (애플리케이션)를 중지하십시오.
- 데이터 크기는 더 커야합니다.
- 테스트는 5-10 초 이상 실행되어야합니다.
- 하나의 샘플에만 의존하지 마십시오. 테스트를 N 번 수행합니다. 결과를 수집하고 결과의 평균 또는 중앙값을 계산합니다.
Collatz 문제의 경우 "꼬리"를 캐싱하여 성능을 크게 향상시킬 수 있습니다. 이것은 시간 / 메모리 트레이드 오프입니다. 참고 : 메모 화 ( https://en.wikipedia.org/wiki/Memoization ). 다른 시간 / 메모리 절충에 대한 동적 프로그래밍 솔루션을 살펴볼 수도 있습니다.
Python 구현 예 :
import sys
inner_loop = 0
def collatz_sequence(N, cache):
global inner_loop
l = [ ]
stop = False
n = N
tails = [ ]
while not stop:
inner_loop += 1
tmp = n
l.append(n)
if n <= 1:
stop = True
elif n in cache:
stop = True
elif n % 2:
n = 3*n + 1
else:
n = n // 2
tails.append((tmp, len(l)))
for key, offset in tails:
if not key in cache:
cache[key] = l[offset:]
return l
def gen_sequence(l, cache):
for elem in l:
yield elem
if elem in cache:
yield from gen_sequence(cache[elem], cache)
raise StopIteration
if __name__ == "__main__":
le_cache = {}
for n in range(1, 4711, 5):
l = collatz_sequence(n, le_cache)
print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))
print("inner_loop = {}".format(inner_loop))
댓글에서 :
그러나이 코드는 절대로 멈추지 않습니다 (정수 오버플로 때문에)!?! Yves Daoust
많은 숫자의 경우 오버플로 되지 않습니다 .
이 경우 것이다 오버 플로우 - 그 불운 초기 씨앗 하나를 들어, 오버 플로워 수는 매우 가능성이 다른 오버 플로우없이 한 방향으로 수렴됩니다.
여전히 이것은 흥미로운 질문을 제기합니다. 오버플로 순환 시드 번호가 있습니까?
간단한 최종 수렴 시리즈는 두 값의 거듭 제곱으로 시작합니다 (분명한가요?).
2 ^ 64는 알고리즘에 따라 정의되지 않은 무한 루프 인 0으로 오버플로되지만 (1로만 끝남) shr raxZF = 1 생성 으로 인해 가장 최적의 솔루션이 완료됩니다 .
2 ^ 64를 생산할 수 있습니까? 시작 숫자가 0x5555555555555555이면 홀수이고 다음 숫자는 3n + 1, 즉 0xFFFFFFFFFFFFFFFF + 1= 0입니다. 이론적으로는 정의되지 않은 알고리즘 상태이지만 johnfound의 최적화 된 답변은 ZF = 1에서 종료하여 복구됩니다. cmp rax,1베드로의 코르는 무한 루프를 종료한다 (QED 변이체 1 내지 정의 "사기꾼" 0수).
더 복잡한 숫자는 0어떻습니까? 솔직히, 내 수학 이론이 너무 흐릿해서 진지한 생각과 진지하게 대처하는 방법을 알 수 없습니다. 그러나 직관적으로 나는 시리즈가 모든 숫자에 대해 1로 수렴한다고 말할 것입니다 : 0 <숫자, 3n + 1 공식은 조만간 원래 숫자 (또는 중간)의 모든 비 -2 소인수를 2의 거듭 제곱으로 천천히 바꿉니다. . 따라서 원래 시리즈의 무한 루프에 대해 걱정할 필요가 없습니다. 오버플로만 우리를 방해 할 수 있습니다.
그래서 저는 몇 개의 숫자를 시트에 넣고 8 비트 잘린 숫자를 살펴 보았습니다.
거기에 넘쳐 세 값은 0: 227, 170그리고 85( 85로 직접 이동 0방향으로 진행하는 다른 두, 85).
그러나 순환 오버플로 시드를 생성하는 가치는 없습니다.
재미있게도 나는 8 비트 잘림으로 고통받는 첫 번째 숫자 인 확인을했고 이미 27영향을 받았습니다! 9232잘리지 않은 적절한 시리즈의 값 에 도달하고 (첫 번째 잘린 값은 32212 단계에 있음) 잘리지 않은 방식으로 2-255 개의 입력 숫자 중 하나에 도달 한 최대 값은 13120( 255자체를 위해 ) 최대 단계 수입니다. 수렴 대상 1은 약 128(+ -2, "1"이 계산되는지 확실하지 않음 등)입니다.
흥미롭게도 (나에게) 그 수가 9232다른 많은 소스 번호에 대해 최대 값입니다. 무엇이 그렇게 특별한가요? : -O 9232= 0x2410... 흠 .. 모르겠어요.
불행하게도, 난 왜 수렴하고이를 절단의 의미 무엇 않으며,이 시리즈의 깊은 이해를 얻을 수 없다 케이 비트 만과 cmp number,1종료 조건은 특정 입력 값으로 끝나는 무한 루프에 알고리즘을 넣어 확실히 가능 0한 후 잘림.
그러나 278 비트 경우에 넘쳐나 는 값 은 일종의 경고입니다. value에 도달하는 단계 수를 세면 1총 k 비트 정수 집합에서 대부분의 숫자에 대해 잘못된 결과를 얻을 수 있습니다. 8 비트 정수의 경우 256 개 중 146 개 숫자가 잘림에 의해 시리즈에 영향을 미쳤습니다 (일부는 여전히 실수로 올바른 단계 수에 도달 할 수 있으며 확인하기에는 너무 게으르다).
컴파일러에 의해 생성 된 코드를 게시하지 않았으므로 여기에 추측이 있습니다. 그러나 그것을 보지 않고도 다음과 같이 말할 수 있습니다.
test rax, 1
jpe even
... 분기를 잘못 예측할 확률이 50 %이며 비용이 많이 듭니다.
컴파일러는 거의 확실하게 두 가지 계산을 수행하고 (div / mod가 대기 시간이 길기 때문에 비용이 많이 들기 때문에 곱하기 더하기는 "무료") CMOV를 따릅니다. 물론 잘못 예측 될 확률은 0 %입니다.
어셈블리를 보지 않아도 가장 분명한 이유는 많은 프로세서가 매우 빠른 시프트 작업을 수행하므로 /= 2최적화되어 있기 때문입니다 >>=1. 그러나 프로세서에 시프트 연산이 없더라도 정수 나누기는 부동 소수점 나누기보다 빠릅니다.
편집 : 귀하의 마일리지는 위의 "정수 나누기가 부동 소수점 나누기보다 빠릅니다"문에 따라 달라질 수 있습니다. 아래 설명은 현대 프로세서가 정수 나누기보다 fp 나누기 최적화를 우선시했음을 보여줍니다. 그래서 만약 누군가가이 thread의 질문에 대해, 다음 컴파일러 최적화 묻는 속도 향상에 대한 가능성이 가장 높은 이유를 찾고 있었다 /=2으로 >>=1보기에 최적의 첫번째 장소가 될 것입니다.
온 관련이없는 참고 하면, n홀수, 표현은 n*3+1항상도있을 것입니다. 따라서 확인할 필요가 없습니다. 해당 분기를 다음으로 변경할 수 있습니다.
{
n = (n*3+1) >> 1;
count += 2;
}
따라서 전체 진술은 다음과 같습니다.
if (n & 1)
{
n = (n*3 + 1) >> 1;
count += 2;
}
else
{
n >>= 1;
++count;
}
이 작업에 특별히 지정되지 않은 일반적인 대답으로 : 대부분의 경우 높은 수준에서 개선하여 모든 프로그램의 속도를 크게 높일 수 있습니다. 데이터를 여러 번 계산하는 대신 한 번 계산하고 불필요한 작업을 완전히 피하고 캐시를 최선의 방법으로 사용하는 것과 같습니다. 이러한 것들은 높은 수준의 언어로하는 것이 훨씬 쉽습니다.
어셈블러 코드를 작성 하면 최적화 컴파일러가 수행하는 작업을 개선 할 수 있지만 어려운 작업입니다. 일단 완료되면 코드를 수정하기가 훨씬 더 어려워 알고리즘 개선 사항을 추가하기가 훨씬 더 어렵습니다. 프로세서에 고급 언어에서 사용할 수없는 기능이있는 경우가 있습니다. 인라인 어셈블리는 이러한 경우에 유용하며 여전히 고급 언어를 사용할 수 있도록합니다.
오일러 문제에서 대부분의 경우 무언가를 만들고, 느린 이유를 찾고, 더 나은 것을 만들고, 느린 이유를 찾는 등의 방식으로 성공합니다. 어셈블러를 사용하는 것은 매우 어렵습니다. 가능한 속도의 절반에서 더 나은 알고리즘은 일반적으로 최대 속도에서 더 나쁜 알고리즘을 이길 것이며 어셈블러에서 최대 속도를 얻는 것은 사소한 일이 아닙니다.
간단한 대답 :
MOV RBX, 3 및 MUL RBX를 수행하는 것은 비용이 많이 듭니다. RBX, RBX를 두 번 추가하십시오.
여기서 ADD 1은 아마도 INC보다 빠를 것입니다.
MOV 2 및 DIV는 매우 비쌉니다. 그냥 오른쪽으로 이동
64 비트 코드는 일반적으로 32 비트 코드보다 눈에 띄게 느리고 정렬 문제는 더 복잡합니다. 이와 같은 작은 프로그램을 사용하면 패키지를 압축해야하므로 32 비트 코드보다 빠를 가능성이있는 병렬 계산을 수행해야합니다.
C ++ 프로그램에 대한 어셈블리 목록을 생성하면 어셈블리와 어떻게 다른지 확인할 수 있습니다.
'programing tip' 카테고리의 다른 글
| % w (array)는 무엇을 의미합니까? (0) | 2020.09.29 |
|---|---|
| 경계 내에 맞게 TextView 텍스트 자동 크기 조정 (0) | 2020.09.29 |
| Mac에 Java 8을 설치하는 방법 (0) | 2020.09.29 |
| 표준 Python 독 스트링 형식은 무엇입니까? (0) | 2020.09.29 |
| Git에서 마지막 커밋을 해제하는 방법 (0) | 2020.09.29 |