배열에서 요소를 빠르게 교체하는 방법 - C
예를 들어 다음과 같은 int가 있다고 가정해 보겠습니다.
const int size = 100000;
int array[size];
//set some items to 0 and other items to 1
123456과 같이 1의 값을 가지는 모든 아이템을 다른 값으로 교체하고 싶습니다.이는 다음과 같은 간단한 방법으로 구현할 수 있습니다.
for(int i = 0; i < size ; i++){
if(array[i] != 0)
array[i] = 123456;
}
호기심 때문에, x86 속임수 같은 것으로 이것을 하는 더 빠른 방법이 있을까요, 아니면 이것이 프로세서에 가장 적합한 코드일까요?
처음에 0과 1이 있는 특정한 경우에는 다음이 더 빠를 수 있습니다.벤치마크를 해주셔야 합니다.일반적인 C로는 훨씬 더 잘 할 수 없을 것입니다. 존재할 수 있는 "x86 속임수"를 이용하려면 조립 과정에 뛰어들어야 할 수도 있습니다.
for(int i = 0; i < size ; i++){
array[i] *= 123456;
}
편집:
벤치마크 코드:
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
size_t diff(struct timespec *start, struct timespec *end)
{
return (end->tv_sec - start->tv_sec)*1000000000 + end->tv_nsec - start->tv_nsec;
}
int main(void)
{
const size_t size = 1000000;
int array[size];
for(size_t i=0; i<size; ++i) {
array[i] = rand() & 1;
}
struct timespec start, stop;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for(size_t i=0; i<size; ++i) {
array[i] *= 123456;
//if(array[i]) array[i] = 123456;
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &stop);
printf("size: %zu\t nsec: %09zu\n", size, diff(&start, &stop));
}
결과:
컴퓨터: 쿼드코어 AMD 현상 @2.5GHz, Linux, GCC 4.7, 컴파일된
$ gcc arr.c -std=gnu99 -lrt -O3 -march=native
if: 전 : ~5-10ms*=: 전 : ~1.3ms
당신과 같은 작은 배열의 경우 다른 알고리즘을 찾으려 해도 소용이 없고, 값이 특정 패턴에 있지 않으면 간단한 루프만이 가능합니다.
그러나 매우 큰 배열을 가지고 있는 경우(수백만 개의 항목을 이야기하는 경우), 작업을 스레드로 분할할 수 있습니다.각각의 개별 스레드는 전체 데이터 세트에서 더 작은 부분을 처리합니다.
이를 벤치마킹하는 방법도 있습니다.
for(int i = 0; i < size ; i++){
array[i] = (~(array[i]-1) & 123456);
}
저는 SchighShagh와 같은 벤치마크를 통해 실행합니다. 제 설정에 거의 차이가 없거나 전혀 없습니다.그러나 당신의 경우에 따라 다를 수 있습니다.
기자들을 멈춰라!
":" 사이의 인수가 상수인 경우 x86이 3항 연산자를 "브랜치 해제"할 수 있다는 것을 방금 기억했습니다.다음 코드를 고려합니다.
for(size_t i=0; i<size; ++i) {
array[i] = array[i] ? 123456 : 0;
}
원래의 코드와 거의 비슷해 보이지 않습니까?해체하면 분기 없이 컴파일되었음을 알 수 있습니다.
for(size_t i=0; i<size; ++i) {
00E3104C xor eax,eax
00E3104E mov edi,edi
array[i] = array[i] ? 123456 : 0;
00E31050 mov edx,dword ptr [esi+eax*4]
00E31053 neg edx
00E31055 sbb edx,edx
00E31057 and edx,1E240h
00E3105D mov dword ptr [esi+eax*4],edx
00E31060 inc eax
00E31061 cmp eax,5F5E100h
00E31066 jb wmain+50h (0E31050h)
}
성능 면에서는 원래의 Schigh Schagh 솔루션과 동등한 수준이거나 조금 나은 것 같습니다.그러나 그것은 더 읽기 쉽고 더 유연합니다.예를 들어, 0과 1이 다른 값을 갖는 배열[i]에서 작동할 수 있습니다.
최종적으로, 벤치마크를 하고 분해 과정을 엿봅니다.
어레이가 캐시에 들어갈 정도로 작으므로 SIMD를 사용할 가치가 있어야 합니다. (테스트되지 않음)
mov ecx, size
lea esi, [array + ecx * 4]
neg ecx
pxor xmm0, xmm0
movdqa xmm1, [_vec4_123456] ; value of { 123456, 123456, 123456, 123456 }
_replaceloop:
movdqa xmm2, [esi + ecx * 4] ; assumes the array is 16 aligned, make that true
add ecx, 4
pcmpeqd xmm2, xmm0
pandn xmm2, xmm1
movdqa [esi + ecx * 4 - 16], xmm2
jnz _replaceloop
2로 풀면 도움이 될 수 있습니다.
SSE 4.1이 있다면 다음과 같이 SchighShagh의 곱셈 트릭을 사용할 수 있습니다.pmulld.
다음은 알고리즘의 다양한 버전을 프로파일링하는 Win32 코드입니다(기본 릴리스 빌드를 사용하여 VS2010 Express를 사용하여 컴파일됨):-
#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
const size_t
size = 0x1D4C00;
_declspec(align(16)) int
g_array [size];
_declspec(align(16)) int
_vec4_123456 [] = { 123456, 123456, 123456, 123456 };
void Test (void (*fn) (size_t, int *), char *test)
{
printf ("Executing test: %s\t", test);
for(size_t i=0; i<size; ++i) {
g_array[i] = rand() & 1;
}
LARGE_INTEGER
start,
end;
QueryPerformanceCounter (&start);
fn (size, g_array);
QueryPerformanceCounter (&end);
printf("size: %u\t count: %09u\n", size, (int) (end.QuadPart - start.QuadPart));
}
void Test1 (size_t size, int *array)
{
for(size_t i=0; i<size; ++i) {
array[i] *= 123456;
}
}
void Test2 (size_t size, int *array)
{
for(size_t i=0; i<size; ++i) {
if(array[i]) array[i] = 123456;
}
}
void Test3 (size_t array_size, int *array)
{
__asm
{
mov edi,array
mov ecx, array_size
lea esi, [edi + ecx * 4]
neg ecx
pxor xmm0, xmm0
movdqa xmm1, [_vec4_123456] ; value of { 123456, 123456, 123456, 123456 }
_replaceloop:
movdqa xmm2, [esi + ecx * 4] ; assumes the array is 16 aligned, make that true
add ecx, 4
pcmpeqd xmm2, xmm0
pandn xmm2, xmm1
movdqa [esi + ecx * 4 - 16], xmm2
jnz _replaceloop
}
}
void Test4 (size_t array_size, int *array)
{
array_size = array_size * 8 / 12;
__asm
{
mov edi,array
mov ecx,array_size
lea esi,[edi+ecx*4]
lea edi,[edi+ecx*4]
neg ecx
mov edx,[_vec4_123456]
pxor xmm0,xmm0
movdqa xmm1,[_vec4_123456]
replaceloop:
movdqa xmm2,[esi+ecx*4]
mov eax,[edi]
mov ebx,[edi+4]
movdqa xmm3,[esi+ecx*4+16]
add edi,16
add ecx,9
imul eax,edx
pcmpeqd xmm2,xmm0
imul ebx,edx
pcmpeqd xmm3,xmm0
mov [edi-16],eax
mov [edi-12],ebx
pandn xmm2,xmm1
mov eax,[edi-8]
mov ebx,[edi-4]
pandn xmm3,xmm1
imul eax,edx
movdqa [esi+ecx*4-36],xmm2
imul ebx,edx
movdqa [esi+ecx*4-20],xmm3
mov [edi-8],eax
mov [edi-4],ebx
loop replaceloop
}
}
int main()
{
Test (Test1, "Test1 - mul");
Test (Test2, "Test2 - branch");
Test (Test3, "Test3 - simd");
Test (Test4, "Test4 - simdv2");
}
테스트용으로 준비되어 있습니다.if()..., 곱하기를 사용하는 C, 해럴드의 심드 버전과 내 심드 버전.
여러 번 실행하면(프로파일을 생성할 때는 여러 번 실행하여 결과를 평균해야 함) 분기 버전을 제외한 모든 버전 간에는 현저하게 느린 차이가 거의 없습니다.
이것은 그다지 놀라운 일이 아닙니다. 왜냐하면 알고리즘은 각 메모리 항목에 대해 거의 작업을 하지 않기 때문입니다.이것은 CPU와 메모리 사이의 대역폭이 실제 제한 요소라는 것을 의미합니다. CPU가 데이터를 프리페칭하는 데 도움을 주지만(ia32의 데이터 검출 및 프리페칭 선형) CPU가 메모리를 따라잡기 위해 끊임없이 대기하고 있음을 의미합니다.
다른 배열이나 다른 데이터 구조를 사용하여 하나로 설정한 요소의 인덱스를 추적한 다음 해당 요소만 방문할 수 있습니다.하나로 설정된 요소가 거의 없는 경우 가장 효과적입니다.
이게 더 빨리 증명될 수도 있습니다.
for(int i = 0; i < size ; i++){
array[i] = ((123456 << array[i]) - 123456);
}
EDIT: 비트 와이즈 연산을 왼쪽 시프트로 변경했습니다.
인라인 어셈블리를 사용하여 배열 할당 속도를 높이는 한 가지 방법이 있습니다.아래와 같이.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int size = 100000;
void main(void) {
int array[size];
int value = 1000;
__asm__ __volatile__("cld\n\t"
"rep\n\t"
"stosl\n\t"
:
:"c"(size*4), "a"(value), "D"(array)
:
);
printf("Array[0] : %d \n", array[0]);
}
이것은 배열 값을 할당하기 위해 평 c 프로그램과 비교했을 때 속도가 되어야 합니다.그리고 스토스 명령어도 4클럭이 소요됩니다.
언급URL : https://stackoverflow.com/questions/16231110/fast-way-to-replace-elements-in-array-c
'source' 카테고리의 다른 글
| 파이썬에서 한 줄 한 줄로 사전을 인쇄하는 방법은? (0) | 2023.10.27 |
|---|---|
| XML로 문자열 이스케이프 (0) | 2023.10.27 |
| 브루로 PHP를 7.4 macOS Catalina로 업데이트 (0) | 2023.10.27 |
| Karaf - 최대 절전 모드 - MariaDB " 스키마 업데이트를 완료할 수 없습니다" 오류 (0) | 2023.10.27 |
| make로 여러 C 파일을 컴파일합니다. (0) | 2023.10.27 |