편리한 정수 비교 기능
compare함수는 2 개의 인수를 개 취하는 함수이다 a과 b그들의 순서를 나타내는 정수를 반환한다. 가보다 a작 으면 b결과는 음의 정수입니다. 보다 a큰 b결과는 긍정적 인 경우 정수입니다. 않은 경우 오는가 a와 b동일하고, 그 결과는 0이다.
이 함수는 종종 표준 라이브러리에서 정렬 및 검색 알고리즘을 매개 변수화하는 데 사용됩니다.
compare캐릭터에 대한 기능을 구현하는 것은 매우 독립적입니다. 인수를하셨습니다.
int compare_char(char a, char b)
{
return a - b;
}
이는 일반적으로 정수에 맞는 가정하기 때문에 작동합니다. (이 가정은 시스템에 적용되지 않습니다 sizeof(char) == sizeof(int).)
이 트릭은 두 정수의 차이가 일반적으로 정수에 맞지 않기 때문에 정수를 비교할 수 없습니다. 예를 들어, 더 작은 INT_MAX - (-1) = INT_MIN제안 제안합니다 (기술적으로 오버플로는 정의되지 않은 동작으로 이어지지 만 모듈로 산술을 가정 해 보겠습니다).INT_MAX-1
여기서 정수에 대해 비교 함수를 어떻게 구현할 수 있습니까? 첫 번째 시도는 다음과 같습니다.
int compare_int(int a, int b)
{
int temp;
int result;
__asm__ __volatile__ (
"cmp %3, %2 \n\t"
"mov $0, %1 \n\t"
"mov $1, %0 \n\t"
"cmovg %0, %1 \n\t"
"mov $-1, %0 \n\t"
"cmovl %0, %1 \n\t"
: "=r"(temp), "=r"(result)
: "r"(a), "r"(b)
: "cc");
return result;
}
6 개량의 지침을 수행 할 수 있습니까? 더 간단한 간단한 방법이 있습니까?
다음은 항상 저에게 사용되었습니다.
return (a < b) ? -1 : (a > b);
를 사용 gcc -O2 -S하면 다음과 같은 5 가지 지침으로 사용할 수 있습니다.
xorl %edx, %edx
cmpl %esi, %edi
movl $-1, %eax
setg %dl
cmovge %edx, %eax
Ambroz Bizjak의 훌륭한 동반자 답변에 대한 후속 조치로 나는 그의 프로그램이 위에 게시 된 것과 동일한 어셈블리 코드를 테스트 해하지 않습니다. 그리고 컴파일러 출력을 더 자세히 연구 할 때 컴파일러가 우리의 답변 중 하나에 게시 된 것과 동일한 명령을 생성하지 않습니다. 그래서 저는 그의 테스트 프로그램을 가져옵니다 우리가 게시 한 것과 일치하도록 어셈블리 출력을 직접 수정하고 결과를 비교했습니다. 두 버전이 거의 동일하게 비교 될 것입니다.
./opt_cmp_branchless: 0m1.070s
./opt_cmp_branch: 0m1.037s
나는 다른 사람들이 동일한 실험을 시도하고 나의 관찰을 확인하거나 모순 할 수 있도록 각 프로그램의 어셈블리를 전체적으로 게시하고 있습니다.
다음은 cmovge지침 ( (a < b) ? -1 : (a > b)) 이있는 버전입니다 .
.file "cmp.c"
.text
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "%d=0\n"
.text
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB20:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
pushq %rbx
.cfi_def_cfa_offset 24
.cfi_offset 3, -24
movl $arr.2789, %ebx
subq $8, %rsp
.cfi_def_cfa_offset 32
.L9:
leaq 4(%rbx), %rbp
.L10:
call rand
movb %al, (%rbx)
addq $1, %rbx
cmpq %rbx, %rbp
jne .L10
cmpq $arr.2789+4096, %rbp
jne .L9
xorl %r8d, %r8d
xorl %esi, %esi
orl $-1, %edi
.L12:
xorl %ebp, %ebp
.p2align 4,,10
.p2align 3
.L18:
movl arr.2789(%rbp), %ecx
xorl %eax, %eax
.p2align 4,,10
.p2align 3
.L15:
movl arr.2789(%rax), %edx
xorl %ebx, %ebx
cmpl %ecx, %edx
movl $-1, %edx
setg %bl
cmovge %ebx, %edx
addq $4, %rax
addl %edx, %esi
cmpq $4096, %rax
jne .L15
addq $4, %rbp
cmpq $4096, %rbp
jne .L18
addl $1, %r8d
cmpl $500, %r8d
jne .L12
movl $.LC0, %edi
xorl %eax, %eax
call printf
addq $8, %rsp
.cfi_def_cfa_offset 24
xorl %eax, %eax
popq %rbx
.cfi_def_cfa_offset 16
popq %rbp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE20:
.size main, .-main
.local arr.2789
.comm arr.2789,4096,32
.section .note.GNU-stack,"",@progbits
아래 버전은 분기없는 방법 ( (a > b) - (a < b))을 사용합니다 .
.file "cmp.c"
.text
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "%d=0\n"
.text
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB20:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
pushq %rbx
.cfi_def_cfa_offset 24
.cfi_offset 3, -24
movl $arr.2789, %ebx
subq $8, %rsp
.cfi_def_cfa_offset 32
.L9:
leaq 4(%rbx), %rbp
.L10:
call rand
movb %al, (%rbx)
addq $1, %rbx
cmpq %rbx, %rbp
jne .L10
cmpq $arr.2789+4096, %rbp
jne .L9
xorl %r8d, %r8d
xorl %esi, %esi
.L19:
movl %ebp, %ebx
xorl %edi, %edi
.p2align 4,,10
.p2align 3
.L24:
movl %ebp, %ecx
xorl %eax, %eax
jmp .L22
.p2align 4,,10
.p2align 3
.L20:
movl arr.2789(%rax), %ecx
.L22:
xorl %edx, %edx
cmpl %ebx, %ecx
setg %cl
setl %dl
movzbl %cl, %ecx
subl %ecx, %edx
addl %edx, %esi
addq $4, %rax
cmpq $4096, %rax
jne .L20
addq $4, %rdi
cmpq $4096, %rdi
je .L21
movl arr.2789(%rdi), %ebx
jmp .L24
.L21:
addl $1, %r8d
cmpl $500, %r8d
jne .L19
movl $.LC0, %edi
xorl %eax, %eax
call printf
addq $8, %rsp
.cfi_def_cfa_offset 24
xorl %eax, %eax
popq %rbx
.cfi_def_cfa_offset 16
popq %rbp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE20:
.size main, .-main
.local arr.2789
.comm arr.2789,4096,32
.section .note.GNU-stack,"",@progbits
이것은 분기가 시나리오 오버플로 또는 언더 플로가 발생하지 않습니다.
return (a > b) - (a < b);
를 사용 gcc -O2 -S하면 다음 6 개의 급하게됩니다.
xorl %eax, %eax
cmpl %esi, %edi
setl %dl
setg %al
movzbl %dl, %edx
subl %edx, %eax
다음은 다양한 비교 구현을 벤치마킹하는 몇 가지 코드입니다.
#include <stdio.h>
#include <stdlib.h>
#define COUNT 1024
#define LOOPS 500
#define COMPARE compare2
#define USE_RAND 1
int arr[COUNT];
int compare1 (int a, int b)
{
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
int compare2 (int a, int b)
{
return (a > b) - (a < b);
}
int compare3 (int a, int b)
{
return (a < b) ? -1 : (a > b);
}
int compare4 (int a, int b)
{
__asm__ __volatile__ (
"sub %1, %0 \n\t"
"jno 1f \n\t"
"cmc \n\t"
"rcr %0 \n\t"
"1: "
: "+r"(a)
: "r"(b)
: "cc");
return a;
}
int main ()
{
for (int i = 0; i < COUNT; i++) {
#if USE_RAND
arr[i] = rand();
#else
for (int b = 0; b < sizeof(arr[i]); b++) {
*((unsigned char *)&arr[i] + b) = rand();
}
#endif
}
int sum = 0;
for (int l = 0; l < LOOPS; l++) {
for (int i = 0; i < COUNT; i++) {
for (int j = 0; j < COUNT; j++) {
sum += COMPARE(arr[i], arr[j]);
}
}
}
printf("%d=0\n", sum);
return 0;
}
gcc -std=c99 -O2양의 정수 ( USE_RAND=1)에 대한 결과에 대해 64 비트 시스템의 결과 :
compare1: 0m1.118s
compare2: 0m0.756s
compare3: 0m1.101s
compare4: 0m0.561s
C 전용 솔루션 제가 제안한 솔루션이 가장 빠릅니다. user315052의 솔루션은 5 개의 급하게 만 구매 했음에도 불구하고 느 렸습니다. 명령이 하나 적음에도 불구하고 조건부 명령 ( cmovge) 이 있기 때문에 속도가 느려질 수 있습니다.
전반적으로 FredOverflow의 4 급 어셈블리 구현은 양의 정수와 함께 사용할 때 가장 빠 사용합니다. 그러나이 코드는 정수 범위 RAND_MAX 만 벤치마킹 때문에 4-instuction 테스트는 오버플로를 인위적으로 처리하고 테스트에서 발생하지 않기 때문에 바이어스입니다. 속도는 성공적인 분기 예측 때문입니다.
전체 범위의 정수 ( USE_RAND=0)를 사용하면 4 개의 솔루션이 실제로 매우 느립니다 (다른 것들은 함).
compare4: 0m1.897s
좋아, 나는 그것을 네 가지로 만들었습니다. :) 기본 아이디어는 다음과 가변적입니다.
절반의 경우 차이는 정수에 도움만큼 작습니다. 이 경우 차이를 반환하십시오. 숫자 숫자 1을 오른쪽으로 이동하십시오. 중요한 질문은 MSB로 전환 할 비트입니다.
단순함을 위해 32 비트 대신 8 비트를 사용하는 두 가지 극단적 인 예를 살펴 봅니다.
10000000 INT_MIN
01111111 INT_MAX
---------
000000001 difference
00000000 shifted
01111111 INT_MAX
10000000 INT_MIN
---------
111111111 difference
11111111 shifted
캐리 비트를 생성하고 이동하면 첫 번째 경우에는 0이되고 ( INT_MIN같지는 않지만 INT_MAX) 두 번째 경우에는 음수 INT_MAX가 생성됩니다 ( 보다 작지는 않지만 INT_MIN).
하지만 이동하기 전에 캐리 비트를 뒤집 으면 숫자를 얻을 수 있습니다.
10000000 INT_MIN
01111111 INT_MAX
---------
000000001 difference
100000001 carry flipped
10000000 shifted
01111111 INT_MAX
10000000 INT_MIN
---------
111111111 difference
011111111 carry flipped
01111111 shifted
캐리 비트를 뒤집는 것이 합리적 인 수학적 이유가 확신하지만 아직 보지 못합니다.
int compare_int(int a, int b)
{
__asm__ __volatile__ (
"sub %1, %0 \n\t"
"jno 1f \n\t"
"cmc \n\t"
"rcr %0 \n\t"
"1: "
: "+r"(a)
: "r"(b)
: "cc");
return a;
}
100 만 개의 임의 입력과 INT_MIN, -INT_MAX, INT_MIN / 2, -1, 0, 1, INT_MAX / 2, INT_MAX / 2 + 1, INT_MAX의 모든 조합으로 코드를 테스트했습니다. 모든 테스트를 통과했습니다. 나를 잘못 증명할 수 있습니까?
SSE2 구현을한데 모을 가치가 있습니다. vec_compare1다음과 같은 접근 방식을 사용 compare2하지만 SSE2 산술 급 3 개만 필요합니다.
#include <stdio.h>
#include <stdlib.h>
#include <emmintrin.h>
#define COUNT 1024
#define LOOPS 500
#define COMPARE vec_compare1
#define USE_RAND 1
int arr[COUNT] __attribute__ ((aligned(16)));
typedef __m128i vSInt32;
vSInt32 vec_compare1 (vSInt32 va, vSInt32 vb)
{
vSInt32 vcmp1 = _mm_cmpgt_epi32(va, vb);
vSInt32 vcmp2 = _mm_cmpgt_epi32(vb, va);
return _mm_sub_epi32(vcmp2, vcmp1);
}
int main ()
{
for (int i = 0; i < COUNT; i++) {
#if USE_RAND
arr[i] = rand();
#else
for (int b = 0; b < sizeof(arr[i]); b++) {
*((unsigned char *)&arr[i] + b) = rand();
}
#endif
}
vSInt32 vsum = _mm_set1_epi32(0);
for (int l = 0; l < LOOPS; l++) {
for (int i = 0; i < COUNT; i++) {
for (int j = 0; j < COUNT; j+=4) {
vSInt32 v1 = _mm_loadu_si128(&arr[i]);
vSInt32 v2 = _mm_load_si128(&arr[j]);
vSInt32 v = COMPARE(v1, v2);
vsum = _mm_add_epi32(vsum, v);
}
}
}
printf("vsum = %vd\n", vsum);
return 0;
}
이 시간은 0.137 초입니다.
동일한 CPU와 컴파일러를 사용하는 compare2 시간은 0.674 초입니다.
따라서 SSE2 구현은 예상대로 (4 와이드 SIMD이기 때문에) 약 4 배 더 빠 사용합니다.
이 코드는 분기가 5 개의 입찰가를 사용합니다. cmov * 명령이 상당히 비싼 인텔 프로세서에서 다른 분기없는 대안보다 성능이 우수합니다. 단점은 비대칭 반환 값 (INT_MIN + 1, 0, 1)입니다.
int compare_int (int a, int b)
{
int res;
__asm__ __volatile__ (
"xor %0, %0 \n\t"
"cmpl %2, %1 \n\t"
"setl %b0 \n\t"
"rorl $1, %0 \n\t"
"setnz %b0 \n\t"
: "=q"(res)
: "r"(a)
, "r"(b)
: "cc"
);
return res;
}
이 변형은 초기화가 필요하지 않습니다.
int compare_int (int a, int b)
{
__asm__ __volatile__ (
"subl %1, %0 \n\t"
"setl %b0 \n\t"
"rorl $1, %0 \n\t"
"setnz %b0 \n\t"
: "+q"(a)
: "r"(b)
: "cc"
);
return a;
}
다음 아이디어를 사용할 수 있습니다 (의사 코드에서; 구문에 아마도 생각하지 않기 때문에 asm 코드를 작성할 수 있습니다).
- 숫자 빼기 (
result = a - b) - 오버플로가 없으면 완료됩니다 (
jo명령 및 분기 예측이 여기서 매우 잘 작동합니다). - 오버플로가있는 경우 강력한 방법 (
return (a < b) ? -1 : (a > b))을 사용하십시오.
편집 :
추가 단순성을 위해 : 오버플로가있는 경우 3 단계 대신 결과의 부호를 뒤집습니다
.
정수를 64 비트 값으로 승격하는 것을 고려할 수 있습니다.
참고 URL : https://stackoverflow.com/questions/10996418/efficient-integer-compare-function
'ProgramingTip' 카테고리의 다른 글
| MySQL Workbench에서 Blob을 직접 보는 방법 (0) | 2020.11.29 |
|---|---|
| Android- 문자열의 일부를 다른 URL로 바꾸는 방법은 무엇입니까? (0) | 2020.11.29 |
| sqlite3 (~> 1.3.6)을 활성화 할 수 없음, 이미 활성화 된 sqlite3-1.4.0 (0) | 2020.11.29 |
| Python의 사용자 비활성화 인 시간 형식? (0) | 2020.11.29 |
| mysql에 금액 저장 (0) | 2020.11.29 |