x86-64 어셈블리의 성능 최적화 - 정렬과 분기 예측

 

나는 현재 x86-64 어셈블리와 SSE-2 명령어를 사용하여 C99 표준 라이브러리 문자열 함수인 'strlen()' , 'memset()' 등의 고도로 최적화된 버전을 코딩 중입니다.

지금까지는 성능 측면에서 탁월한 결과를 얻었지만, 더 최적화하려고 시도할 때 가끔 이상한 동작을 보입니다.

예를 들어, 몇 가지 간단한 지시문을 추가하거나 제거하거나, 점프에 사용되는 로컬 레이블을 간단히 재구성하는 것만으로도 전체 성능이 크게 저하됩니다. 코드적인 측면에서는 아무런 이유가 없습니다.

내 추측은 코드 정렬에 문제가 있거나 잘못 예측된 분기들 때문에 문제가 있을 것이라고 생각합니다.

나는 같은 아키텍처(x86-64)를 가지더라도 다른 CPU들이 분기 예측에 대해 다른 알고리즘을 가지고 있다는 것을 알고 있습니다.

하지만 x86-64에서 고성능을 위해 개발할 때 코드 정렬과 분기 예측에 대한 일반적인 조언이 있을까요?

특히 점프 명령에 사용되는 모든 레이블이 DWORD에 맞춰 정렬되었는지 확인해야 할까요?

_func:

; ... Some code ...

test rax, rax

jz .label

; ... Some code ...

ret

.label:

; ... Some code ...

ret

이전 코드에서는 '.label:' 앞에 align 지시문을 사용해야 할까요?

align 4

.label:

만약 그렇다면, SSE-2를 사용할 때 DWORD에 맞추는 것이 충분한가요?

그리고 분기 예측에 대해서, CPU에 도움을 주기위해 점프 명령어에 사용되는 라벨을 어떻게 조직화하는 것이 선호되는 방법인가, 아니면 오늘날의 CPU는 분기가 몇 번 이루어지는지 런타임에서 카운트하여 자동으로 결정하는 만큼 충분히 똑똑한가요?

수정하다

여기에 구체적인 예제가 있습니다 - 여기에서는 SSE-2를 사용한 시작 부분입니다.

_strlen64_sse2:

mov rsi, rdi

and rdi, -16

pxor xmm0, xmm0

pcmpeqb xmm0, [ rdi ]

pmovmskb rdx, xmm0

; ...

 

1000자 문자열을 10,000,000번 실행하면 약 0.48초가 걸립니다. 이는 괜찮습니다.

하지만 NULL 문자열 입력에 대해 확인하지 않습니다. 그래서 당연히 간단한 확인을 추가하겠습니다.

_strlen64_sse2:

test rdi, rdi

jz .null

; ...

 

동일한 테스트는 지금 0.59초에 실행됩니다. 그러나 이 확인 이후에 코드를 정렬하면:

_strlen64_sse2:

test rdi, rdi

jz .null

align 8

; ...

 

오리지널 공연이 돌아왔습니다. 저는 아무런 변경이 없으므로 8을 사용하여 정렬하였습니다. 이것에 대해 설명하고, 코드 섹션을 정렬할 때와 정렬하지 않을 때에 대한 조언을 주실 수 있을까요?

EDIT 2

 

편집 2

물론, 각 분기 대상을 정렬하는 것만으로는 그렇게 간단하지 않습니다. 만약 나 혼자 해본다면, 주로 성능이 나빠질 것이고, 위와 같은 특정한 경우가 아닌 한요.

 

답변 1

 

정렬 최적화

1. '.p2align ' 대신에 'align' 을(를) 사용하세요.

그랜트는 3개의 매개변수를 사용하여 세밀한 제어를 제공합니다.

 

param1 - 어떤 경계에 맞추겠습니까?

param2 - 패딩을 무엇으로 채울지 정합니다 (0으로 채울지 아니면 'NOP' s로 채울지).

param3 - 지정된 바이트 수를 초과하는 경우 패딩을 정렬하지 마십시오.

 

2. 자주 사용하는 코드 블록의 시작을 캐시 라인 크기 경계에 맞춰 정렬하십시오.

 

이렇게 하면 전체 코드 블록을 하나의 캐시 라인에 위치시킬 확률이 증가합니다. L1 캐시로 로드된 후에는 명령어를 가져오기 위해 RAM에 액세스할 필요없이 완전히 실행할 수 있습니다. 이는 많은 반복 횟수를 가진 루프에 매우 유익합니다.

 

3. 3. 다중 바이트 'NOP' 를 사용하여 'reduce the time spent executing NOPs' 로 패딩을 만드세요.

/* nop */

static const char nop_1[] = { 0x90 };

 

/* xchg %ax,%ax */

static const char nop_2[] = { 0x66, 0x90 };

 

/* nopl (%[re]ax) */

static const char nop_3[] = { 0x0f, 0x1f, 0x00 };

 

/* nopl 0(%[re]ax) */

static const char nop_4[] = { 0x0f, 0x1f, 0x40, 0x00 };

 

/* nopl 0(%[re]ax,%[re]ax,1) */

static const char nop_5[] = { 0x0f, 0x1f, 0x44, 0x00, 0x00 };

 

/* nopw 0(%[re]ax,%[re]ax,1) */

static const char nop_6[] = { 0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00 };

 

/* nopl 0L(%[re]ax) */

static const char nop_7[] = { 0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00 };

 

/* nopl 0L(%[re]ax,%[re]ax,1) */

static const char nop_8[] =

{ 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00};

 

/* nopw 0L(%[re]ax,%[re]ax,1) */

static const char nop_9[] =

{ 0x66, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };

 

/* nopw %cs:0L(%[re]ax,%[re]ax,1) */

static const char nop_10[] =

{ 0x66, 0x2e, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };

 

(최대 10바이트의 'NOP'은 x86을 위한 것입니다. 소스 'binutils-2.2.3'.)

 

분기 예측 최적화

x86_64 마이크로 아키텍처 / 세대 간에 많은 변형이 있습니다. 그러나 모든 마이크로 아키텍처에 적용 가능한 일반적인 가이드라인은 다음과 같이 요약할 수 있습니다. 참조 : 'Section 3 of Agner Fog's x86 micro-architecture manual' .

1. 약간 너무 높은 반복 횟수를 피하기 위해 루프를 풀어주세요.

 

루프 감지 논리는 64회 이하 반복 루프에 대해서만 작동하는 것이 보장됩니다. 이는 분기 명령이 루프 동작으로 인식되는 경우, 해당 분기가 n-1번 일어난 후에 다른 방향으로 1번 가는 경우의 n이 최대 64까지 될 수 있기 때문입니다.

이는 하스웰과 이후의 예측기에는 TAGE 예측기를 사용하며 특정 분기에 대한 전용 루프 감지 논리가 없기 때문에 실제로 적용되지 않습니다. 스카이레이크에서 내부 루프 내에 있는 외부 루프 (다른 분기 없이)의 최악의 경우는 반복 횟수가 약 23번 정도입니다. 내부 루프의 종료는 대부분 잘못 예측되지만, 여행 횟수는 매우 낮기 때문에 이러한 상황이 자주 발생합니다. 언롤링은 패턴을 짧게 만드는 데 도움이 될 수 있지만, 매우 높은 반복 횟수에서는 끝 부분의 한 번의 잘못된 예측이 여러 번의 반복에 분산되므로 이를 해결하기 위해서는 비합리적인 양의 언롤링이 필요합니다.

 

2. 가까운/짧은 점프에 집중하십시오.

 

원격 점프는 예측되지 않습니다. 새 코드 세그먼트(CS:RIP)로의 원격 점프는 항상 파이프라인이 정지됩니다. 원격 점프를 사용할 이유는 거의 없으므로 대부분 관련이 없습니다.

대부분의 CPU에서는 임의의 64비트 절대 주소로의 간접 점프를 보통 예측합니다.

하지만 Silvermont (Intel의 저전력 CPU)는 대상이 4GB 이상 떨어져 있을 때 간접 점프를 예측하는 데 제한이 있으므로, 실행 파일 및 공유 라이브러리를 가상 주소 공간의 낮은 32비트에 로드/매핑하여 그 문제를 피할 수 있습니다. 예를 들어 GNU/Linux에서는 환경 변수 'LD_PREFER_MAP_32BIT_EXEC'를 설정함으로써 가능합니다. 자세한 내용은 Intel의 최적화 매뉴얼을 참조하세요.

 

 

답변 2

 

제목: x86-64 어셈블리 언어의 성능 최적화 - 정렬과 분기 예측

 

서론:

x86-64 아키텍처는 현대 컴퓨터 시스템에서 가장 널리 사용되는 아키텍처 중 하나입니다. 이 어셈블리 언어를 최대한 효율적으로 사용하기 위해서는 정렬과 분기 예측과 같은 성능 최적화 기법을 이해하는 것이 중요합니다. 이 글에서는 x86-64 어셈블리 언어에서 정렬과 분기 예측을 어떻게 활용하는지에 대해 알아보겠습니다.

 

1. 정렬 최적화:

정렬은 데이터를 메모리에 일정한 규칙에 따라 배열하거나 데이터 구조를 정렬하는 것을 말합니다. x86-64 아키텍처에서 데이터는 보통 워드(4바이트) 또는 더블 워드(8바이트)로 정렬됩니다. 정렬이 된 데이터에 접근할 때는 하드웨어에서 빠르게 처리할 수 있는 이점이 있기 때문에 성능 향상에 도움을 줍니다. 따라서, 정렬 최적화는 데이터 구조를 메모리에 배치할 때 정렬되도록 하는 것과 관련이 있습니다.

 

정렬 최적화를 위해 다음 사항을 고려할 수 있습니다.

- 데이터 구조를 정렬된 크기에 맞게 배치하는 정렬 기법 활용

- 캐시 메모리의 지역성 특성에 맞게 데이터를 정렬

- 데이터의 연관성을 고려하여 관련된 데이터를 인접한 메모리 위치에 배치

 

2. 분기 예측 최적화:

분기 예측은 프로그램이 조건문과 반복문과 같은 제어 구조를 실행할 때 처리되는 브랜치나 조건 분기문을 예측하여 미리 처리해야 할 명령어들을 미리 로드하는 기술입니다. 이를 통해 파이프라인의 지연된 실행을 최소화할 수 있습니다.

 

분기 예측 최적화를 위해 다음 사항을 고려할 수 있습니다.

- 조건 분기문을 잘 구성하여 예측이 용이하도록 함

- 분기 목표로 이동하기 전에 예측되는 다음 명령어를 필요한 메모리 위치에 로드

 

결론:

x86-64 어셈블리 언어의 성능 최적화를 위해 정렬과 분기 예측은 중요한 요소입니다. 정렬 최적화를 통해 데이터 구조의 메모리 배치를 조정함으로써 성능을 향상시킬 수 있습니다. 또한, 분기 예측 최적화를 통해 지연된 실행을 최소화할 수 있으며 이는 프로그램의 성능 향상에 기여합니다. 따라서, x86-64 어셈블리 언어로 프로그래밍을 할 때는 정렬과 분기 예측에 대한 이해를 바탕으로 최적화를 고려해야 합니다.