짧게 배열 된 double 배열을 통해 검색

Question

매우 짧은 정렬 된 배열을 통해 검색을 최적화하여 주어진 value에 속한 버킷을 찾으려고합니다. 배열의 크기를 가정하면 8 복식, 나는 AVX의 내장 함수의 다음과 같은 순서로 올라와있다된다

_data = _mm256_load_pd(array); 
temp = _mm256_movemask_pd(_mm256_cmp_pd(_data, _value, _CMP_LT_OQ)); 
pos = _mm_popcnt_u32(temp); 
_data = _mm256_load_pd(array+4); 
temp = _mm256_movemask_pd(_mm256_cmp_pd(_data, _value, _CMP_LT_OQ)); 
pos += _mm_popcnt_u32(temp); 

놀랍게도 (I 내 머리의 명령 대기 시간 사양이없는 ..), 그것은 상태

for(i=0; i<7; ++i) if(array[i+1]>=value) break; 

이 루프는 내가 매우 효율적인 코드로 찾았는지에 컴파일 : 빠른 코드는 다음과 같은 C의 루프 GCC에 의해 생성되는 것을

lea ecx, [rax+1] 
vmovsd xmm1, QWORD PTR [rdx+rcx*8] 
vucomisd xmm1, xmm0 
jae .L7 

lea ecx, [rax+2] 
vmovsd xmm1, QWORD PTR [rdx+rcx*8] 
vucomisd xmm1, xmm0 
jae .L8 

[... repeat for all elements of array] 

그래서 4 지침 t ​​소요 o 버킷 1 개를 확인하십시오 (lea, vmovsd, vucomisd, jae). value이 균일하게 퍼져 있다고 가정하면 평균적으로 value에 대해 ~ 3.5 버킷을 확인해야합니다. 분명히 앞서 언급 한 AVX 코드를 능가하기에 충분합니다.

일반적인 경우에, 배열은 당연히 8 개보다 클 수 있습니다. 내가 루프 본문에 대해 다음 명령 시퀀스를 얻을

for(i=0; u<n-1; i++) if(array[i+1]>=value) break; 

: 나는이 같은 C 루프 코드 경우

.L76: 
mov eax, edx 
.L67: 
cmp eax, esi 
jae .L77 
lea edx, [rax+1] 
mov ecx, edx 
vmovsd xmm1, QWORD PTR [rdi+rcx*8] 
vucomisd xmm1, xmm0 
jb .L76 

내가 루프를 풀다하는 GCC를 말할 수 있지만, 요점은 수 있다는 것입니다 요소 당 명령 수는 일정한 경계가있는 루프의 경우보다 커서 코드가 더 느립니다. 또한 vmovsd 주소 지정에 추가 rcx 레지스터를 사용하는 이유를 알 수 없습니다.

내가 수동으로 첫 번째 예처럼 보일 수있는 루프 조립을 수정할 수 있으며, 빠르게 작업 않습니다

.L76: 
cmp edx, esi   # eax -> edx 
jae .L77 
lea edx, [rdx+1]  # rax -> rdx 
vmovsd xmm1, QWORD PTR [rdi+rdx*8] 
vucomisd xmm1, xmm0 
jb .L76 

하지만 난 그것을 GCC를 만들 수없는 것. 그리고 나는 그것이 가능하다는 것을 안다 - 첫번째 예제에서 생성 된 asm은 OK이다.

인라인 asm을 사용하는 대신에 어떻게해야하는지 아이디어가 있습니까? 아니면 더 나은 - 당신은 검색의 빠른 구현을 제안 할 수 있습니까?

Answer 1

답변이 아니지만 의견에 여유가 없습니다.

간단한 C 구현에 대해 AVX 기능을 테스트했으며 완전히 다른 결과를 얻었습니다. Windows 7 x64에서 Linux가 아닌 테스트를 거쳤지 만 생성 된 코드는 매우 비슷합니다. 테스트 방법 : 1) CPU의 SpeedStep을 비활성화했습니다. 2) main() 내에서 프로세스 우선 순위와 스레드 우선 순위를 max (실시간)로 높였습니다. 3) 테스트 된 기능에 대해 10M 통화를 실행하여 CPU를 가열하고 터보를 활성화합니다. 4) 컨텍스트 전환을 피하기 위해 Sleep (0)을 호출했습니다. 5) __rdtscp를 호출하여 측정을 시작했습니다. 6) 루프에서 AVX 찾기 색인 기능 또는 간단한 C 버전을 호출했습니다. 다른 구현은 주석 처리되어 사용되지 않았습니다. 루프 크기는 10M 통화였습니다. 7) __rdtscp를 다시 호출하여 벤치 마크를 마쳤습니다. 8) 틱/반복 인쇄했습니다.전화의 평균 틱 수를 얻으려면

참고 : '인덱스 찾기'기능을 모두 인라인으로 선언했으며 인라인 된 디스 어셈블리에서 확인했습니다. 설명 된 AVX 함수와 C 함수가 동일하지 않습니다. C 함수는 0부터 시작하는 인덱스를 반환하고 AVX 함수는 1부터 시작하는 인덱스를 반환합니다. 내 시스템에서는 AVX 기능이 반복 당 1.1 사이클이 걸리고 C 함수는 반복 당 4.4 사이클이 걸렸습니다.

I가 YMM 레지스터 :(

배열 사용 이상 사용할 MSVC 컴파일러를 강요 할 수 :

double A[8] = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 }; 

결과 (. 평균 틱/ITER) 값 = 0.3 (인덱스 = 2) AVX 1.1 | C : 4.4 값 = 0.5 (인덱스 = 3) AVX 1.1 | C : 11.1 값 = 0.9 (인덱스 = 7) AVX 1.1 | C : 18.1

경우] AVX 함수가 pos-1을 반환하도록 수정 된 후 50 % 느려집니다.사소한 C 루프 기능의 성능이 찾고있는 인덱스에 따라 다르지만 AVX 기능이 일정 시간 작동한다는 것을 알 수 있습니다.

clock()과 100M으로 실행하면 비슷한 결과가 나오며 AVX는 첫 번째 테스트에서 거의 4 배 빠릅니다. 더 긴 테스트를 실행하면 결과가 달라 지지만 AVX가 비슷한 장점을 가질 때마다 유의하십시오.

Answer 2

정수 비교를 시도 할 수 있습니다. double 비교는 NaN에 대한 예외가있는 동일한 비트의 int64_t 비교와 동일합니다. 그것은 더 빨리 돌 수 있습니다. CPU에는 더 많은 정수 실행 단위가 있고 SIMD가 있습니다. 함수 인자에 double *을 보내고 int64_t *를받습니다.