다른 스택 오버플로 질문에 답하면 ( 이 질문 ) 흥미로운 하위 문제가 발생했습니다. 6 개의 정수 배열을 정렬하는 가장 빠른 방법은 무엇입니까?
질문이 매우 낮은 수준이므로
- 우리는 라이브러리를 사용할 수 있다고 가정 할 수 없으며 (통화 자체에는 비용이 있습니다) 평범한 C 만
- 명령 파이프 라인 비우기 ( 비용 이 매우 높음) 를 피하려면 분기, 점프 및 다른 모든 종류의 제어 흐름 차단 (
&&또는 시퀀스 지점 뒤에 숨겨져있는 것과 같은)을 최소화해야합니다||. - 공간이 제한되어 있고 레지스터를 최소화하고 메모리 사용이 문제입니다. 이상적으로는 장소에 따라 정렬하는 것이 가장 좋습니다.
실제로이 질문은 소스 길이를 최소화하는 것이 아니라 실행 시간을 목표로하는 일종의 골프입니다. 책의 제목에서 사용 나는 ‘Zening’코드를 호출하는 코드 최적화의 선 에 의해 마이클 애 브라시 와 그 속편 .
왜 흥미로운 지에 대해서는 몇 가지 계층이 있습니다.
- 예는 간단하고 이해하기 쉽고 측정하기 쉬운 C 기술이 아닙니다.
- 문제에 대한 올바른 알고리즘 선택의 효과뿐만 아니라 컴파일러 및 기본 하드웨어의 효과도 보여줍니다.
여기 내 참조 (순진하고 최적화되지 않은) 구현 및 테스트 세트가 있습니다.
#include <stdio.h>
static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
};
unsigned long long cycles = rdtsc();
for (i = 0; i < 6 ; i++){
sort6(d[i]);
/*
* printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],
* d[i][8], d[i][9], d[i][10]);
*/
}
cycles = rdtsc() - cycles;
printf("Time is %d\n", (unsigned)cycles);
}
원시 결과
많은 변형이 커지면서 여기 에서 찾을 수있는 테스트 스위트에 모두 모았습니다. . Kevin Stock 덕분에 사용 된 실제 테스트는 위에 표시된 것보다 약간 순진합니다. 자신의 환경에서 컴파일하고 실행할 수 있습니다. 다른 대상 아키텍처 / 컴파일러의 동작에 상당히 관심이 있습니다. (좋아요, 답을 넣으면 새로운 결과 집합의 모든 제공자를 +1 할 것입니다).
나는 1 년 전에 Daniel Stutzbach (골프 용)에게 해답을주었습니다.
Linux 64 비트, gcc 4.6.1 64 비트, Intel Core 2 Duo E8400, -O2
- qsort 라이브러리 함수 직접 호출 : 689.38
- 순진한 구현 (삽입 정렬) : 285.70
- 삽입 정렬 (Daniel Stutzbach) : 142.12
- 삽입 정렬 언 롤링 : 125.47
- 순위 순서 : 102.26
- 레지스터 순위 : 58.03
- 정렬 네트워크 (Daniel Stutzbach) : 111.68
- 정렬 네트워크 (Paul R) : 66.36
- 빠른 스왑으로 네트워크 12 정렬하기 : 58.86
- Sorting Networks 12 재정렬 Swap : 53.74
- Sorting Networks 12 재정렬 Simple Swap : 31.54
- 재순환 정렬 네트워크 (빠른 교체 포함) : 31.54
- 재 순서 정렬 네트워크 (빠른 교체 V2 포함) : 33.63
- 인라인 버블 정렬 (파올로 본 지니) : 48.85
- 펼쳐진 삽입 정렬 (Paolo Bonzini) : 75.30
Linux 64 비트, gcc 4.6.1 64 비트, Intel Core 2 Duo E8400, -O1
- qsort 라이브러리 함수 직접 호출 : 705.93
- 순진한 구현 (삽입 정렬) : 135.60
- 삽입 정렬 (Daniel Stutzbach) : 142.11
- 삽입 정렬 언 롤링 : 126.75
- 순위 순서 : 46.42
- 레지스터 순위 : 43.58
- 정렬 네트워크 (Daniel Stutzbach) : 115.57
- 정렬 네트워크 (Paul R) : 64.44
- 빠른 스왑으로 네트워크 12 정렬하기 : 61.98
- Sorting Networks 12 재정렬 Swap : 54.67
- Sorting Networks 12 재정렬 Simple Swap : 31.54
- 재순환 정렬 네트워크 (빠른 교체 포함) : 31.24
- 재순환 정렬 네트워크 (빠른 교체 V2 포함) : 33.07
- 인라인 버블 정렬 (파올로 본 지니) : 45.79
- 펼쳐진 삽입 정렬 (Paolo Bonzini) : 80.15
놀랍게도 여러 프로그램에서 O2가 O1보다 덜 효율적 이기 때문에 -O1과 -O2 결과를 모두 포함했습니다 . 어떤 최적화가이 효과를 가지는지 궁금합니다.
제안 된 솔루션에 대한 의견
삽입 정렬 (Daniel Stutzbach)
예상대로 분기를 최소화하는 것이 좋습니다.
정렬 네트워크 (Daniel Stutzbach)
삽입 정렬보다 낫습니다. 주요 효과가 외부 루프를 피하지 못했는지 궁금했습니다. 나는 그것을 확인하기 위해 롤링되지 않은 삽입 정렬로 시도했으며 실제로 우리는 대략 같은 수치를 얻었습니다 (코드는 here ).
정렬 네트워크 (Paul R)
지금까지 최고입니다. 테스트에 사용한 실제 코드는 다음과 같습니다 . 왜 다른 정렬 네트워크 구현보다 거의 두 배나 빠른지 아직 모릅니다. 매개 변수 전달? 빠른 최대?
빠른 스왑으로 네트워크 정렬 12 SWAP
Daniel Stutzbach가 제안한 것처럼 12 개의 스왑 정렬 네트워크를 분기없는 빠른 스왑과 결합했습니다 (코드는 다음과 같습니다) ) . 1 더 적은 스왑을 사용하여 예상 할 수 있듯이 적은 마진 (약 5 %)으로 지금까지 가장 빠릅니다.
또한 분기없는 스왑은 PPC 아키텍처에서 if를 사용하는 간단한 것보다 훨씬 효율적이지 않은 것으로 보입니다.
호출 라이브러리 qsort
다른 참조 포인트를 제공하기 위해 라이브러리 qsort (코드는 here )를 호출하는 것이 좋습니다 . 예상보다 훨씬 느리다 : 10 ~ 30 배 느리다 … 새로운 테스트 스위트에서 명백해 졌기 때문에 주요 문제는 첫 번째 호출 후 라이브러리의 초기로드 인 것처럼 보이고 다른 것과 비교할 때 나쁘지 않습니다. 버전. 내 리눅스에서는 3 배에서 20 배 정도 느립니다. 다른 아키텍처의 테스트에 사용되는 일부 아키텍처에서는 훨씬 빠릅니다 (라이브러리 qsort가 더 복잡한 API를 사용하기 때문에 실제로 놀랍습니다).
순위
Rex Kerr은 완전히 다른 방법을 제안했습니다. 배열의 각 항목마다 최종 위치를 직접 계산합니다. 계산 순위 순서에 분기가 필요하지 않기 때문에 효율적입니다. 이 방법의 단점은 배열의 메모리 양 (배열의 한 사본과 순위 순서를 저장하는 변수의 사본)의 3 배가 걸린다는 것입니다. 성능 결과는 매우 놀랍고 흥미 롭습니다. 32 비트 OS 및 Intel Core2 Quad E8300을 사용하는 참조 아키텍처에서주기 수는 분기 스왑이있는 정렬 네트워크와 같이 1000보다 약간 작습니다. 그러나 내 64 비트 상자 (Intel Core2 Duo)에서 컴파일되고 실행될 때 훨씬 더 잘 수행되었습니다. 지금까지 가장 빠릅니다. 나는 진실한 이유를 마침내 발견했다. 내 32 비트 상자는 gcc 4.4.1 및 64 비트 상자 gcc 4.4를 사용합니다.
업데이트 :
위에 공개 된 그림에서 알 수 있듯이이 효과는 이후 버전의 gcc에 의해 여전히 향상되었으며 순위 순서는 다른 대안보다 일관되게 두 배 빨라졌습니다.
재정렬 된 스왑으로 정렬 네트워크 12
gcc 4.4.3을 사용한 Rex Kerr 제안의 놀라운 효율성으로 인해 3 배나 많은 메모리를 사용하는 프로그램이 분기없는 정렬 네트워크보다 더 빠를 수 있을까? 내 가설은 쓰기 후 읽은 종류의 종속성이 적어 x86의 슈퍼 스칼라 명령 스케줄러를 더 잘 사용할 수 있다는 것입니다. 그것은 나에게 아이디어를 주었다 : 쓰기 의존성 후 읽기를 최소화하기 위해 재정렬 스왑. 더 간단히 말하면 SWAP(1, 2); SWAP(0, 2);두 번째 공통 메모리 셀에 액세스하기 때문에 두 번째 스왑을 수행하기 전에 첫 번째 스왑이 완료 될 때까지 기다려야합니다. 당신이 할 SWAP(1, 2); SWAP(4, 5);때 프로세서는 병렬로 실행할 수 있습니다. 나는 그것을 시도하고 예상대로 작동하며 정렬 네트워크는 약 10 % 더 빠르게 실행됩니다.
간단한 스왑으로 네트워크 12 정렬
원래 게시물 Steinar H. Gunderson이 제안한 1 년 후, 컴파일러를 현명하게 바꾸고 스왑 코드를 단순하게 유지해서는 안된다고 제안했습니다. 결과 코드가 약 40 % 빠르므로 실제로 좋은 생각입니다! 또한 더 많은 사이클을 절약 할 수있는 x86 인라인 어셈블리 코드를 사용하여 수작업으로 최적화 된 스왑을 제안했습니다. 가장 놀랍게도 (프로그래머의 심리학에 관한 책은 1 년 전 어느 누구도 그 버전의 스왑을 시도하지 않았다는 것입니다. 테스트하는 데 사용한 코드는 여기에 있습니다 . 다른 사람들은 C 빠른 스왑을 작성하는 다른 방법을 제안했지만 괜찮은 컴파일러를 사용하는 간단한 것과 동일한 성능을 제공합니다.
“최상의”코드는 다음과 같습니다.
static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
const int b = max(d[x], d[y]); \
d[x] = a; d[y] = b; }
SWAP(1, 2);
SWAP(4, 5);
SWAP(0, 2);
SWAP(3, 5);
SWAP(0, 1);
SWAP(3, 4);
SWAP(1, 4);
SWAP(0, 3);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
테스트 세트를 믿는다면 (그리고 예, 상당히 나쁘다. 단순하고 단순하며 측정 대상을 이해하기 쉽다는 장점이있다), 한 종류의 결과 코드의 평균주기 수는 40주기 미만이다 ( 6 개의 테스트가 실행됩니다). 이는 각 스왑을 평균 4 주기로 설정했습니다. 나는 그것을 놀랍게도 빨리 부릅니다. 다른 개선 사항이 있습니까?
답변
최적화를 위해서는 항상 테스트, 테스트, 테스트하는 것이 가장 좋습니다. 적어도 네트워크 정렬과 삽입 정렬을 시도합니다. 베팅하는 경우 과거 경험을 바탕으로 삽입 금액에 돈을 넣었습니다.
입력 데이터에 대해 알고 있습니까? 일부 알고리즘은 특정 종류의 데이터에서 더 잘 수행됩니다. 예를 들어, 정렬 정렬은 정렬되거나 거의 정렬 된 데이터에서 더 잘 수행되므로 평균보다 거의 정렬 된 데이터가있을 경우 더 나은 선택이 될 것입니다.
게시 한 알고리즘은 삽입 정렬과 유사하지만 더 많은 비교 비용으로 스왑 수를 최소화 한 것으로 보입니다. 분기가 명령 파이프 라인을 정지시킬 수 있기 때문에 비교는 스왑보다 훨씬 비쌉니다.
삽입 정렬 구현은 다음과 같습니다.
static __inline__ int sort6(int *d){
int i, j;
for (i = 1; i < 6; i++) {
int tmp = d[i];
for (j = i; j >= 1 && tmp < d[j-1]; j--)
d[j] = d[j-1];
d[j] = tmp;
}
}
정렬 네트워크를 구축하는 방법은 다음과 같습니다. 먼저이 사이트 를 사용 하여 적절한 길이의 네트워크에 대한 최소 SWAP 매크로 세트를 생성하십시오. 함수로 마무리하면 다음과 같은 이점이 있습니다.
static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
SWAP(1, 2);
SWAP(0, 2);
SWAP(0, 1);
SWAP(4, 5);
SWAP(3, 5);
SWAP(3, 4);
SWAP(0, 3);
SWAP(1, 4);
SWAP(2, 5);
SWAP(2, 4);
SWAP(1, 3);
SWAP(2, 3);
#undef SWAP
}
답변
다음을 사용한 구현이 있습니다. 정렬 네트워크를 .
inline void Sort2(int *p0, int *p1)
{
const int temp = min(*p0, *p1);
*p1 = max(*p0, *p1);
*p0 = temp;
}
inline void Sort3(int *p0, int *p1, int *p2)
{
Sort2(p0, p1);
Sort2(p1, p2);
Sort2(p0, p1);
}
inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
Sort2(p0, p1);
Sort2(p2, p3);
Sort2(p0, p2);
Sort2(p1, p3);
Sort2(p1, p2);
}
inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
Sort3(p0, p1, p2);
Sort3(p3, p4, p5);
Sort2(p0, p3);
Sort2(p2, p5);
Sort4(p1, p2, p3, p4);
}
당신은 정말 효율적으로 분기가 필요합니다 min 및 max구현이 필요합니다. 왜냐하면이 코드가 효과적으로 순서 min와 max연산 (각각 13 개)으로 요약되기 때문입니다 . 나는 이것을 독자를위한 연습으로 남겨둔다.
이 구현은 벡터화 (예 : SIMD-대부분의 SIMD ISA에는 벡터 최소 / 최대 명령이 있음) 및 GPU 구현 (예 : CUDA-분기가없는 경우 워프 발산에 문제가 없음)에 쉽게 적용됩니다.
다음을 참조하십시오 : 매우 작은 목록을 정렬하는 빠른 알고리즘 구현
답변
이들은 정수이고 비교가 빠르기 때문에 각각의 순위 순서를 직접 계산해보십시오.
inline void sort6(int *d) {
int e[6];
memcpy(e,d,6*sizeof(int));
int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
int o5 = 15-(o0+o1+o2+o3+o4);
d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}
답변
1 년 늦게 파티에 온 것 같지만 여기에 …
gcc 4.5.2에서 생성 된 어셈블리를 살펴보면 모든 스왑에 대해로드와 저장이 수행되고 있으며 실제로는 필요하지 않습니다. 6 개의 값을 레지스터에로드하고 정렬 한 다음 다시 메모리에 저장하는 것이 좋습니다. 나는 매장에 가해지는 부하를 가능한 한 가깝게 주문했다. Steinar H. Gunderson의 SWAP 매크로도 사용했습니다. 업데이트 : gcc가 Gunderson과 유사한 것으로 변환되는 Paolo Bonzini의 SWAP 매크로로 전환했지만 gcc는 명시 적 어셈블리로 제공되지 않으므로 지침을 더 잘 주문할 수 있습니다.
더 나은 순서가있을 수 있지만 최고의 성능으로 제공된 재정렬 된 스왑 네트워크와 동일한 스왑 순서를 사용했습니다. 더 많은 시간을 찾으면 많은 순열을 생성하고 테스트합니다.
4000 개 이상의 어레이를 고려하도록 테스트 코드를 변경하고 각주기를 정렬하는 데 필요한 평균주기 수를 보여주었습니다. i5-650에서 ~ 34.1 사이클 / 정렬 (-O3 사용)을 얻는 반면 원래의 재정렬 된 정렬 네트워크가 ~ 65.3 사이클 / 정렬 (-O1, 비트 -O2 및 -O3 사용)을 얻는 것과 비교했습니다.
#include <stdio.h>
static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
register int x0,x1,x2,x3,x4,x5;
x1 = d[1];
x2 = d[2];
SWAP(x1, x2);
x4 = d[4];
x5 = d[5];
SWAP(x4, x5);
x0 = d[0];
SWAP(x0, x2);
x3 = d[3];
SWAP(x3, x5);
SWAP(x0, x1);
SWAP(x3, x4);
SWAP(x1, x4);
SWAP(x0, x3);
d[0] = x0;
SWAP(x2, x5);
d[5] = x5;
SWAP(x1, x3);
d[1] = x1;
SWAP(x2, x4);
d[4] = x4;
SWAP(x2, x3);
d[2] = x2;
d[3] = x3;
#undef SWAP
#undef min
#undef max
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
return x;
}
void ran_fill(int n, int *a) {
static int seed = 76521;
while (n--) *a++ = (seed = seed *1812433253 + 12345);
}
#define NTESTS 4096
int main() {
int i;
int d[6*NTESTS];
ran_fill(6*NTESTS, d);
unsigned long long cycles = rdtsc();
for (i = 0; i < 6*NTESTS ; i+=6) {
sort6_fast(d+i);
}
cycles = rdtsc() - cycles;
printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);
for (i = 0; i < 6*NTESTS ; i+=6) {
if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
printf("d%d : %d %d %d %d %d %d\n", i,
d[i+0], d[i+1], d[i+2],
d[i+3], d[i+4], d[i+5]);
}
return 0;
}
내가 변경된 테스트 스위트를 수정 또한 더 많은 테스트를 종류에 따라 시계를보고하고 실행에합니다 (CMP 기능이 아니라 핸들 정수 오버 플로우로 업데이트), 여기에 몇 가지 다른 아키텍처에 결과입니다. AMD CPU에서 테스트를 시도했지만 사용 가능한 X6 1100T에서 rdtsc가 신뢰할 수 없습니다.
Clarkdale (i5-650)
==================
Direct call to qsort library function 635.14 575.65 581.61 577.76 521.12
Naive implementation (insertion sort) 538.30 135.36 134.89 240.62 101.23
Insertion Sort (Daniel Stutzbach) 424.48 159.85 160.76 152.01 151.92
Insertion Sort Unrolled 339.16 125.16 125.81 129.93 123.16
Rank Order 184.34 106.58 54.74 93.24 94.09
Rank Order with registers 127.45 104.65 53.79 98.05 97.95
Sorting Networks (Daniel Stutzbach) 269.77 130.56 128.15 126.70 127.30
Sorting Networks (Paul R) 551.64 103.20 64.57 73.68 73.51
Sorting Networks 12 with Fast Swap 321.74 61.61 63.90 67.92 67.76
Sorting Networks 12 reordered Swap 318.75 60.69 65.90 70.25 70.06
Reordered Sorting Network w/ fast swap 145.91 34.17 32.66 32.22 32.18
Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function 870.01 736.39 723.39 725.48 721.85
Naive implementation (insertion sort) 503.67 174.09 182.13 284.41 191.10
Insertion Sort (Daniel Stutzbach) 345.32 152.84 157.67 151.23 150.96
Insertion Sort Unrolled 316.20 133.03 129.86 118.96 105.06
Rank Order 164.37 138.32 46.29 99.87 99.81
Rank Order with registers 115.44 116.02 44.04 116.04 116.03
Sorting Networks (Daniel Stutzbach) 230.35 114.31 119.15 110.51 111.45
Sorting Networks (Paul R) 498.94 77.24 63.98 62.17 65.67
Sorting Networks 12 with Fast Swap 315.98 59.41 58.36 60.29 55.15
Sorting Networks 12 reordered Swap 307.67 55.78 51.48 51.67 50.74
Reordered Sorting Network w/ fast swap 149.68 31.46 30.91 31.54 31.58
Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function 559.97 451.88 464.84 491.35 458.11
Naive implementation (insertion sort) 341.15 160.26 160.45 154.40 106.54
Insertion Sort (Daniel Stutzbach) 284.17 136.74 132.69 123.85 121.77
Insertion Sort Unrolled 239.40 110.49 114.81 110.79 117.30
Rank Order 114.24 76.42 45.31 36.96 36.73
Rank Order with registers 105.09 32.31 48.54 32.51 33.29
Sorting Networks (Daniel Stutzbach) 210.56 115.68 116.69 107.05 124.08
Sorting Networks (Paul R) 364.03 66.02 61.64 45.70 44.19
Sorting Networks 12 with Fast Swap 246.97 41.36 59.03 41.66 38.98
Sorting Networks 12 reordered Swap 235.39 38.84 47.36 38.61 37.29
Reordered Sorting Network w/ fast swap 115.58 27.23 27.75 27.25 26.54
Nehalem (Xeon E5640)
====================
Direct call to qsort library function 911.62 890.88 681.80 876.03 872.89
Naive implementation (insertion sort) 457.69 236.87 127.68 388.74 175.28
Insertion Sort (Daniel Stutzbach) 317.89 279.74 147.78 247.97 245.09
Insertion Sort Unrolled 259.63 220.60 116.55 221.66 212.93
Rank Order 140.62 197.04 52.10 163.66 153.63
Rank Order with registers 84.83 96.78 50.93 109.96 54.73
Sorting Networks (Daniel Stutzbach) 214.59 220.94 118.68 120.60 116.09
Sorting Networks (Paul R) 459.17 163.76 56.40 61.83 58.69
Sorting Networks 12 with Fast Swap 284.58 95.01 50.66 53.19 55.47
Sorting Networks 12 reordered Swap 281.20 96.72 44.15 56.38 54.57
Reordered Sorting Network w/ fast swap 128.34 50.87 26.87 27.91 28.02
답변
며칠 전에 Google 에서이 질문에 우연히 발견했습니다. 왜냐하면 6 개의 정수로 된 고정 길이 배열을 신속하게 정렬해야하기 때문입니다. 그러나 필자의 경우 정수는 32 비트 대신 8 비트에 불과하며 C 만 사용해야하는 엄격한 요구 사항은 없습니다. 어쨌든 누군가에게 도움이 될 수 있기 때문에 결과를 공유 할 것이라고 생각했습니다 …
SSE를 사용하여 비교 및 스왑 작업을 가능한 한 벡터화하는 어셈블리의 네트워크 정렬 변형을 구현했습니다. 배열을 완전히 정렬하려면 6 개의 “패스”가 필요합니다. PADDB (벡터화 된 추가) 만 사용하고 일부 경우에는 PAND (비트 AND) 명령을 사용하여 PCMPGTB (벡터화 된 비교)의 결과를 PSHUFB (벡터화 된 스왑)에 대한 셔플 매개 변수로 직접 변환하는 새로운 메커니즘을 사용했습니다.
이 방법은 또한 진정한 분기없는 기능 을 생성하는 부작용이있었습니다 . 점프 명령은 없습니다.
이 구현 은 현재 질문에서 가장 빠른 옵션 ( “Sorting Networks 12 with Simple Swap”)으로 표시된 구현보다 약 38 % 빠릅니다 . char테스트 중에 배열 요소 를 사용 하여 비교를 공정하게 만들기 위해 해당 구현을 수정했습니다 .
이 방법은 최대 16 개의 요소까지 배열 크기에 적용 할 수 있습니다. 더 큰 어레이에서는 대안에 비해 상대 속도 이점이 더 커질 것으로 예상합니다.
이 코드는 SSSE3가있는 x86_64 프로세서 용 MASM으로 작성되었습니다. 이 기능은 “새로운”Windows x64 호출 규칙을 사용합니다. 여기있어…
PUBLIC simd_sort_6
.DATA
ALIGN 16
pass1_shuffle OWORD 0F0E0D0C0B0A09080706040503010200h
pass1_add OWORD 0F0E0D0C0B0A09080706050503020200h
pass2_shuffle OWORD 0F0E0D0C0B0A09080706030405000102h
pass2_and OWORD 00000000000000000000FE00FEFE00FEh
pass2_add OWORD 0F0E0D0C0B0A09080706050405020102h
pass3_shuffle OWORD 0F0E0D0C0B0A09080706020304050001h
pass3_and OWORD 00000000000000000000FDFFFFFDFFFFh
pass3_add OWORD 0F0E0D0C0B0A09080706050404050101h
pass4_shuffle OWORD 0F0E0D0C0B0A09080706050100020403h
pass4_and OWORD 0000000000000000000000FDFD00FDFDh
pass4_add OWORD 0F0E0D0C0B0A09080706050403020403h
pass5_shuffle OWORD 0F0E0D0C0B0A09080706050201040300h
pass5_and OWORD 0000000000000000000000FEFEFEFE00h
pass5_add OWORD 0F0E0D0C0B0A09080706050403040300h
pass6_shuffle OWORD 0F0E0D0C0B0A09080706050402030100h
pass6_add OWORD 0F0E0D0C0B0A09080706050403030100h
.CODE
simd_sort_6 PROC FRAME
.endprolog
; pxor xmm4, xmm4
; pinsrd xmm4, dword ptr [rcx], 0
; pinsrb xmm4, byte ptr [rcx + 4], 4
; pinsrb xmm4, byte ptr [rcx + 5], 5
; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer. Same on extract
; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
movd xmm4, dword ptr [rcx]
pinsrw xmm4, word ptr [rcx + 4], 2 ; word 2 = bytes 4 and 5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass1_shuffle]
pcmpgtb xmm5, xmm4
paddb xmm5, oword ptr [pass1_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass2_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass2_and]
paddb xmm5, oword ptr [pass2_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass3_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass3_and]
paddb xmm5, oword ptr [pass3_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass4_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass4_and]
paddb xmm5, oword ptr [pass4_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass5_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass5_and]
paddb xmm5, oword ptr [pass5_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass6_shuffle]
pcmpgtb xmm5, xmm4
paddb xmm5, oword ptr [pass6_add]
pshufb xmm4, xmm5
;pextrd dword ptr [rcx], xmm4, 0 ; benchmarked with this
;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
;pextrb byte ptr [rcx + 5], xmm4, 5
movd dword ptr [rcx], xmm4
pextrw word ptr [rcx + 4], xmm4, 2 ; x86 is little-endian, so this is the right order
ret
simd_sort_6 ENDP
END
이것을 실행 가능한 객체로 컴파일하여 C 프로젝트에 연결할 수 있습니다. Visual Studio에서이 작업을 수행하는 방법에 대한 지침은 이 문서를 참조하십시오 . 다음 C 프로토 타입을 사용하여 C 코드에서 함수를 호출 할 수 있습니다.
void simd_sort_6(char *values);
답변
테스트 코드는 꽤 나쁩니다. 초기 배열을 오버플로합니다 (여기 사람들이 컴파일러 경고를 읽지 않습니까?). printf가 잘못된 요소를 인쇄하고 있습니다. 정당한 이유없이 rdtsc에 .byte를 사용합니다. 한 번만 실행됩니다 (!). 최종 결과는 실제로 정확합니다 (따라서 미묘하게 잘못된 것을“최적화”하는 것이 매우 쉽습니다). 포함 된 테스트는 매우 기초적이지 않고 (음수가 아님) 컴파일러가 전체 함수를 죽은 코드로 버리는 것을 막을 수는 없습니다.
즉, 비트 닉 네트워크 솔루션을 개선하는 것도 매우 쉽습니다. 간단히 min / max / SWAP 항목을
#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }
그리고 그것은 나에게 약 65 % 더 빠릅니다 (-O2, amd64, Core i7의 데비안 gcc 4.4.5).
답변
제공된 스왑 매크로가 정말 마음에 들지만 :
#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
개선 사항이 있습니다 (좋은 컴파일러가 만들 수 있음).
#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }
최소 및 최대 작동 방식을 기록하고 공통 하위 표현식을 명시 적으로 가져옵니다. 이렇게하면 최소 및 최대 매크로가 완전히 제거됩니다.
