x86-64 어셈블리-3 또는 5의 배수 합계
저는 기본적인 x86 어셈블리를 배우려고해서 프로젝트 오일러 문제를 해결하기 시작했습니다. 나는 내 코드에 대한 비판을 기대하고 있었는데, 그것이 작업의 효율성이나 코드 자체의 가독성 / 스타일을 포함하기를 바란다. Linux 64 비트 용 Makefile을 제공하겠습니다.
코드의 목적은 3 또는 5로 나눌 수있는 [0, 1000)의 모든 숫자를 합산하는 것입니다.
코드는 make RUN=euler_1.
주의 :
나는 대부분의 컴파일러의 조합으로 알려진 숫자의 modulos를 교체 할 것을 알고 mov및 shr정수 부문을 피하기 위해. 예를 들어이 스레드를 참조하십시오 .
Makefile
.PHONY: clean
all: $(RUN).elf ./$^
%.elf: %.o
ld $^ -o $@ -lc -e main -dynamic-linker /lib64/ld-linux-x86-64.so.2
%.o: %.asm
nasm -f elf64 $^
clean:
rm -f *.o *.elf
euler_1.asm
extern printf
global main
section .data
fmt: db "%d", 0x0a, 0
section .text
;; main - Calculate the sum of all numbers between [0, 1000) that are divisible
;; by 3 or 5.
;; sum : R8
main:
; sum = 0
mov r8, 0
; for i in [0, 1000) {
mov rcx, 0
for0:
; if i % 3 == 0 or i % 5 == 0 {
; i % 3 == 0
mov rax, rcx
mov rdx, 0
mov r9, 3
div r9
test rdx, rdx
jne if01
; sum = sum + i
add r8, rcx
jmp if0
if01:
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne if0
; sum = sum + i
add r8, rcx
jmp if0
; }
if0:
inc rcx
cmp rcx, 1000
jl for0
; }
; printf("%d", sum)
lea rdi, [rel fmt]
mov rsi, r8
mov rax, 0
call printf
; sys_exit(0)
mov rdi, 0
mov rax, 60
syscall
답변
다음은 코드를 개선하는 데 도움이되는 몇 가지 사항입니다. 다른 리뷰는 좋은 점을 제시했지만 여기에서 다루지 않은 일부가 있습니다.
stdlib 사용 여부 결정
Makefile과 전화 printf모두 당신이 다음 사용하여 프로그램의 종료 괜찮 표준 C 라이브러리를 사용하지만, 있다는 것을 표시 syscall하지 않은합니다. 그 이유는 표준 C 스타트 업 main이 호출 되기 전에 설정 한 다음 main반환 후에 다시 해체하기 때문 입니다. 이 코드는 대신를 사용 syscall하여 프로그램을 종료 함으로써 분해를 건너 뛰고 있으며 이는 좋은 습관이 아닙니다. 두 가지 대안이 있습니다. C 라이브러리를 전혀 사용하지 않거나 (즉, 직접 인쇄 루틴을 작성 ) 분해가 실제로 발생하도록합니다.
xor eax, eax ; set exit code to 0 to indicate success
ret ; return to _libc_start_main which called our main
Linux에서 시작 및 해체가 작동하는 방법에 대한 자세한 내용은 이것을 읽으십시오 .
신중하게 레지스터 관리
전문 어셈블리 언어 프로그래머 (그리고 훌륭한 컴파일러)가하는 일 중 하나는 레지스터 사용을 관리하는 것입니다. 이 경우 합계의 궁극적 인 용도는 인쇄하는 것이며이를 인쇄하려면 rsi레지스터에 값이 필요합니다 . 그렇다면 누적 합계 rsi대신 사용 하지 않는 이유 r8는 무엇입니까?
레지스터를 효율적으로 제로화하는 방법 알아보기
분명히 우리가 mov r8, 0그것을 작성 하면 값 0을 r8레지스터 에로드하는 원하는 효과가 있고 다른 리뷰 노트처럼이를 수행하는 더 좋은 방법이 있지만 더 자세히 살펴 보겠습니다. 코드는 현재 다음을 수행합니다.
; sum = 0
mov r8, 0
; for i in [0, 1000) {
mov rcx, 0
작동하지만 목록 파일을보고 NASM이 다음과 같이 변환했는지 살펴 보겠습니다.
13 ; sum = 0
14 00000000 41B800000000 mov r8, 0
15 ; for i in [0, 1000) {
16 00000006 B900000000 mov rcx, 0
첫 번째 열은 목록 파일의 줄 번호이고 두 번째 열은 주소이고 세 번째 열은 인코딩 된 명령어입니다. 따라서 두 명령어가 11 바이트를 사용함을 알 수 있습니다. 우리는 더 잘할 수 있습니다! 다른 리뷰에서 xor지침을 올바르게 언급 했으므로 시도해 보겠습니다.
19 00000000 4D31C0 xor r8, r8
20 00000003 4831C9 xor rcx, rcx
6 바이트 만 더 좋습니다. 우리는 여전히 더 잘할 수 있습니다. 주석 중 하나가 올바르게 언급했듯이 64 비트 x86 시스템에서 레지스터 xor의 아래쪽 절반이 rXX되면 위쪽 절반도 지워집니다. 그래서 그렇게합시다 :
19 00000000 4D31C0 xor r8, r8
20 00000003 31C9 xor ecx, ecx
1 바이트를 절약했지만 e8레지스터 가 없습니다 . ecx그 값을 지우고 복사 하면 더 잘할 수 있습니까 r8?
14 00000000 31C9 xor ecx, ecx
20 00000002 4989C8 mov r8, rcx
아니요, 위의 조언을 따르지 않고 다음 rsi대신 사용할 수 없습니다 r8.
19 00000000 31C9 xor ecx, ecx
20 00000002 31F6 xor esi, esi
이제 우리는 4 바이트로 줄었고, mov rsi, r8이 두 가지만으로 10 바이트를 절약하기 위해 3 바이트를 더 절약 하는 명령이 더 이상 필요하지 않습니다 .
div가능한 경우 피하십시오
이 div명령어는 x86_64 아키텍처에서 가장 느린 명령어 중 하나이며 0으로 나누려고하면 예외가 발생할 수도 있습니다. 두 가지 이유 때문에 가능하다면 지시를 피하는 것이 좋습니다. 이 경우이를 방지하는 한 가지 방법은 매우 비슷해 보이며 fizzbuzz두 개의 카운터를 유지하는 것입니다. 하나는 5부터 카운트 다운하고 다른 하나는 3부터 카운트 다운합니다.
실용적인 경우 지역 레이블 사용
있음이 분명 main필요 파일 전역 심볼 수 있지만, for0및 if01(모두 가난한 이름은, 이미 언급 된)가 될 필요가 없습니다. NASM에서는 레이블 앞에 마침표를 붙이는 대신를 for0사용할 수 있도록 로컬 레이블 을 지정할 수 있습니다 .for0. 이렇게하면 충돌에 대해 걱정할 필요없이 다른 함수에서 레이블을 재사용 할 수 있다는 장점이 있습니다.
가능한 경우 무조건 점프하지 마십시오.
x86 프로세서는 다음에 실행될 명령어를 파악하기 위해 최선을 다합니다. 다단계 캐싱 및 분기 예측을 포함하여 모든 종류의 작업을 수행 할 수 있습니다. 소프트웨어를 더 빠르게 실행하기 위해 그렇게합니다. 가능한 경우 분기를 전혀 피하고 특히 무조건 점프를 피함으로써 도움을 줄 수 있습니다. 신중하게 생각하면 코드를 재구성하여이를 수행 할 수 있습니다. 다음은 원래 코드입니다.
test rdx, rdx
jne if01
; sum = sum + i
add rsi, rcx
jmp if0
if01:
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne if0
; sum = sum + i
add rsi, rcx
jmp if0
; }
if0:
inc rcx
cmp rcx, 1000
jl for0
다음과 같이 다시 작성할 수 있습니다.
test rdx, rdx
je .accumulate
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne .next
.accumulate:
; sum = sum + i
add rsi, rcx
; }
.next:
inc rcx
cmp rcx, 1000
jl .for0
if01그리고if0가장 위대한 이름이 아닙니다.다시로드하는 대신
r9두 개의 레지스터를 사용하십시오. 하자r9항상 3을 포함하고r10항상 5가 포함되어 있습니다.r8한 곳에서 증가합니다 .루프를 위쪽이 아닌 아래쪽 (1000에서 0)으로 실행하면 명령어 (
cmp)가 절약 됩니다.mov rdx, 07 바이트로 인코딩됩니다.xor rdx, rdx훨씬 짧습니다.
말한 모든 것, 고려하십시오
main:
mov r8, 0
mov r9, 3
mov r10, 5
; for i in (1000, 0]
mov rcx, 999
for0:
mov rax, rcx
xor rdx, rdx
div r9
test rdx, rdx
jeq accumulate
mov rax, rcx
xor rdx, rdx
div r10
test rdx, rdx
jne next
accumulate:
add r8, rcx
next:
dec rcx
jne for0
추신 :이 문제에 매우 간단한 산술적 해결책이 있다는 것을 알고 있기를 바랍니다.
구현 선택에 대한 몇 가지 간단한 참고 사항과 이에 접근하는 방법 :
div숫자가 1000까지만 올라갈 때 64 비트 피연산자 크기가 필요하지 않습니다 . 이는 div r32Ice Lake 이전의 Intel 보다 훨씬 느립니다 . 다른 코드 검토에서 자세한 내용을 설명 했습니다. NASM Win64 어셈블리에서 숫자가 소수인지 확인 .
(그리고 다른 지침은 일반적으로 test edx, edx코드 크기가 저장됩니다. 심지어 64 비트 숫자 및 64 비트와 함께 div, i % 5항상 32 비트에 맞는이 높은 32 페이지를 무시해 그래서 에서 32 비트 레지스터를 사용하여 / 지침의 장점을 x86-64 - x86-64 의 기본 피연산자 크기이며 기계 코드 접두사가 필요하지 않습니다. 효율성을 위해 해당 특정 명령어에 대해 실제로 64 비트 피연산자 크기가 필요하고 64까지 암시 적 0 확장이 필요한 경우가 아니면 사용하십시오. -비트는 필요한 작업을 수행하지 않습니다. 그러나 추가 명령을 사용하지 마십시오. 64 비트 피연산자 크기가 종종 필요합니다 (예 : 포인터 증가).
물론, 컴파일 타임 상수로 나누는 div것은 고정 소수점 곱셈 역수를 사용하는 대신 컴파일러가 완전히 피하는 느린 옵션입니다. 마찬가지로에서 왜 정수 나누기를 구현 이상한 번호로 GCC의 승산을 사용합니까? 그래서 또는 이 코드 검토 .
참조 - 당신이 카운터를 사용하는 경우 또한, 당신은 당신이 그들이 FizzBuzz처럼 3, 5 패턴을 처리하기 위해 공을 명중 (및 / 또는 줄이기) 때 3 또는 5로 재설정하는 모든에 분할하지 않아도되는 이 스택 오버플로 대답을 그런 기술에 대한 대규모 튜토리얼을 썼는데 여기서는 반복하지 않을 것입니다. FizzBuzz와 달리 3과 5의 배수 인 경우에도 한 번만 숫자를 세고 싶습니다.
15 씩 풀고 (패턴이 완전히 반복되도록) 다음과 같이 하드 코딩 할 수 있습니다.
.unroll15_loop:
; lets say ECX=60 for example
add eax, ecx ; += 60
lea eax, [rax + rcx + 3] ; += 63
lea eax, [rax + rcx + 5] ; += 65
lea eax, [rax + rcx + 6] ; += 66
...
add ecx, 15
cmp ecx, 1000-15
jbe .unroll15_loop
; handle the last not full group of 15 numbers
또는 몇 가지 수학을 적용하고 실제로 모든 숫자를 보는 대신 15 개 숫자 범위에서 3과 5의 배수의 합에 대해 닫힌 형식의 공식을 사용하고, 범위 의 시작 i * nmuls위치 i로 오프셋 nmuls하고 숫자입니다. 배수의.
예를 들어 [60, 75)범위에는 60, 63, 65, 66, 69, 70, 72가 있습니다. 15 개 숫자 중 8 개입니다. 그래서 그것은 [0, 15)같지만 + 8*60. 0..14 부분을 손으로 수행하거나 루프를 사용하여 결과를 기억하십시오. (프로젝트 오일러는 프로그래밍만큼이나 수학에 관한 것입니다. 얼마나 많은 수학을하고 싶은지 대 프로그램이 수행하기를 원하는 무차별 대입의 정도는 여러분에게 달려 있습니다.)
편리하게도 8은 x86 주소 지정 모드가 지원하는 스케일 팩터 중 하나입니다.
lea eax, [rax + rcx*8 + 0 + 3 + 5 + 6 + 9 + 10 + 12]
(3 + 5 + 6 + ...는 상수 표현식이므로 어셈블러가 어셈블시 [reg + reg*scale + disp8]주소 지정 모드를 생성하여이를 수행 할 수 있습니다 . 불행히도 3 개 구성 요소 LEA는 Intel CPU에서 3주기 대기 시간이 있으며 해당 루프는 전달 된 종속성은 루프의 병목 현상이므로 실제로는 별도의 add명령 을 사용하는 것이 더 효율적 입니다.)
물론 우리는 선형 적으로 증가하는 일련의 기본적 합이 감소했으며, 가우스의 공식을 (적용 할 수있는 n * (n+1) / 2단지의 정화 처리하는 데 전체 간격 범위 폐쇄 양식) n%15접근하는 숫자를 n. BTW, clang은 간단한 for 루프 sum += i;를 닫힌 형식으로 바꾸는 방법을 알고 있으며 2로 나누기 전에 일시적인 오버플로를 방지하도록 배열합니다 (오른쪽 시프트). Matt Godbolt의 CppCon2017은 “최근 내 컴파일러가 나를 위해 무엇을 했는가? Unbolting the Compiler 's Lid” 에서는이를 예로 사용합니다. 또한보십시오https://stackoverflow.com/questions/38552116/how-to-remove-noise-from-gcc-clang-assembly-output
적절한 경우 조건부 이동 지침 사용
@Edward의 답변 에서 토론을 확장하려면 조건부 이동 지침을 사용할 수 있다면 분기의 양을 더 줄여 프로세서에 도움이 될 것입니다.
나눗셈을 수행하는 대신 모듈로 3 및 모듈로 5 카운터를 유지하기 위해 제안과 결합하면 메인 루프 본문의 개요가 다음과 같이 보일 수 있습니다.
%define mod3_reg r8
%define mod5_reg r9
%define zero_reg r10
%define count_reg rcx
%define accum_reg rsi
%define addend_reg rdi
%define limit 1000
...
mainloop:
xor addend_reg, addend_reg
inc mod3_reg
cmp mod3_reg, 3
cmove addend_reg, count_reg
cmove mod3_reg, zero_reg
inc mod5_reg
cmp mod5_reg, 5
cmove addend_reg, count_reg
cmove mod5_reg, zero_reg
add accum_reg, addend_reg
inc count_reg
cmp count_reg, limit
jl mainloop
(카운터의 초기 값 0을 일치 mod3_reg시키려면 2와 mod5_reg4 로 초기화해야합니다. 반면에 1로 시작하도록 조정하면 둘 다 0으로 초기화 할 수 있습니다. 조금 더 간단합니다.)
또한 @PeterCordes의 일부 의견에 따르면 cmov루프에 충분한 추가 종속성 을 만드는 데 문제가 있어 실제로 가치가없는 것으로 판명 될 수 있습니다. 성능에 신경을 많이 썼다면 타겟 머신에서 벤치 마크를 실행하는 것이 중요합니다.