for-loop 메커니즘 효율성 팁

Question

대형 다중 배열에 for 루프를 사용할 때 for 루프 메커니즘 자체를 저장하는 것은 의미가 있습니다.

따라서 오버 헤드를 줄이는 방법에 대한 팁을 찾고 있습니다.

: int 대신에 uint를 사용하여 카운트 다운하고! = 0을 0 대신에 정지로 사용하면 CPU가 작업량을 줄일 수 있습니다 (한 번만 들었으므로 항상 틀림 없습니다)

Answer 1

먼저 작은 것들을 땀을 내지 마십시오. 카운트 다운 대 카운트 다운과 같은 세부 사항은 일반적으로 실행 시간과 전혀 관련이 없습니다. 인간은 코드에서 속도가 빨라질 필요가있는 영역을 발견하는 것이 악명 높습니다. 프로파일 러를 사용하십시오. 프로파일 러가 다르게 말하는 경우를 제외하고 루프의 반복되지 않는 부분에 거의 또는 전혀 신경을 쓰지 마십시오. 현대 컴파일러는 불필요한 반복을 피하는 것이 현명하기 때문에 내부 루프에 작성된 내용이 반드시 내부 루프에서 실행되는 것은 아닙니다.

즉, 현대 CPU에서 루프를 풀 때 매우주의해야합니다. 캐시가 빡빡할수록 캐시에 더 잘 들어 맞을 것입니다. 작년에 작업 한 고성능 응용 프로그램에서 직선 코드 대신 루프를 사용하여 최대한 성능을 향상시키고 가능한 한 최대로 성능을 향상 시켰습니다. (예, 필자는 문제의 기능이 실행 시간의 80 %를 차지했습니다.또한 일반적인 입력보다 시간을 벤치마킹하여 변경 사항이 도움이된다는 것을 알았습니다.

또한 효과적인 코드를 선호하는 개발 습관에는 아무런 해가 없습니다. C++에서는 루프 변수를 증가시키기 위해 후행 증가 (i ++) 대신 사전 증가 (++ i)를 사용하는 습관을 습득해야합니다. 그것은 대개 중요하지 않지만 중요한 차이를 만들 수 있습니다. 코드를 읽기 쉽거나 쓰기 가능하게 만들지 않으며 상처를주지 않습니다.

Answer 2

하나의 중요한 제안 : 가능한 한 외부 루프. 모든 컴파일러가 자동으로 그렇게 할 수있는 것은 아닙니다. 대신 eample의 경우 :

사용

for row = 0 to 999 
    for col = 0 to 999 
     cell[row*1000+col] = row * 7 + col 

: 정말로 중요한 것은 당신이 루프에 넣어 무엇을 O (N^D) 복잡성 (D = 차원)가됩니다 루프로

for row = 0 to 999 
    x = row * 1000 
    y = row * 7 
    for col = 0 to 999 
     cell[x+col] = y + col 

Answer 3

입니다 루프 자체는 아닙니다. 루프 내부에서 수백만 사이클의 비효율적 인 알고리즘의 루프 프레임 워크에서 몇 사이클을 최적화하면 뱀 오일 일뿐입니다.

Answer 4

루프 풀기는 한 가지 방법 일 수 있습니다. 즉 : N은 위의 예에서 4의 배수가 아닌 경우 특수 처리가 필요합니다

for (i=0; i<N; i+=4) { 
    a[i]=...; 
    a[i+1]=...; 
    a[i+2]=...; 
    a[i+3]=...; 
} 

:

for (i=0; i<N; i++) { 
    a[i]=...; 
} 

는로 변환합니다.

Answer 5

오버 헤드를 측정 했습니까? for 루프 처리에 소요되는 시간과 응용 프로그램 코드를 실행하는 데 소요되는 시간을 아십니까? 당신의 목표는 무엇입니까?

Answer 6

이것은 언어에 무관심한 질문이 아니며, 언어뿐 아니라 컴파일러에도 크게 의존합니다. 내가 믿는 대부분의 컴파일러는 동등하게이 두 컴파일 :

for (int i = 0; i < 10; i++) { /* ... */ } 

int i = 0; 
while (i < 10) { 
    // ... 
    i++; 
} 

대부분의 언어/컴파일러에서는 for 루프는 루프 동안 나중에 단지 문법 설탕입니다. Foreach는 또 다른 질문이며 언어/컴파일러에 대한 의존도가 매우 높지만 일반적으로 for/while 루프가 효율적이지 않습니다. 얼마나 더 많이 언어와 컴파일러에 의존 하는가?

가장 좋은 방법은 테마에 대한 여러 가지 유사 콘텐츠로 일부 벤치 마크를 실행하고 맨 위에 나오는 것을 보는 것입니다.

편집 :이 목적을 위해 suggestions here은 루프 자체에 대해 걱정할 필요없이 시간을 절약 할 수 있습니다.

Answer 7

나는 @Greg에 동의한다. 우선해야 할 일은 벤치마킹을 실시하는 것입니다. 모든 처리 시간이 소비되는 곳을 증명할 때까지는 아무 것도 최적화하지 않을 것입니다. "조기 최적화는 모든 악의 뿌리입니다!"

Answer 8

루프를 연속적으로 메모리에 만들도록하면 캐시 사용이 최적화됩니다. 즉,이 작업을 수행하지 않습니다되어 이미지를 처리하는 단일 인덱스와 픽셀에 하나 개의 루프에 두 개의 루프로 변환

for (int i = 0; i < m; i++) 
    for (j = 0; j < n; j++) 
     s += arr[j][i]; 

• 합니다.
• 파이프 라인이 루프가 끝나는 것이 아니라 계속 진행된다고 가정하기 때문에 루프가 0 번 실행되지 않도록하십시오.

Answer 9

알아두기가 필요하지 않으면 항상 증분 연산자를 사용해야합니다. 사소한 차이 일뿐 더 효율적입니다.

int postincrement(int &i)
{
int itmp = i;
i = i + 1;
return itmp;
}

사전 Inc의 :

i++;

같이 동일

• 포스트 증가 :

  는 내부적으로이 차이입니다

  int preincrement(int &i)
{
i = i + 1;
return i;
}

Answer 10

내가 수표로, 대부분의 컴파일러는 아마 더 효율적이어야한다 제로로 사임, 어쨌든 이런 짓을 했을까 생각 :

++i;

같이 동일 rement 제로는 프로세서에 대해 매우 빠릅니다. 다시 말하지만, 어쨌든 대부분의 루프에서이 작업을 수행 할만한 가치가있는 컴파일러가 있습니다. 컴파일러가 수행하는 작업에 익숙해 져야합니다.

Answer 11

질문에 대한 정확한 정보가 충분하지 않습니다. 루프에서 뭐하고 있니? 한 번의 반복에서 계산은 이전 반복에서 계산 된 값에 따라 달라집니다. 그렇지 않다면 적어도 듀얼 코어 프로세서가 있다고 가정 할 때 2 개의 스레드를 사용하여 거의 절반의 시간을 절약 할 수 있습니다.

대용량 배열 처리를 수행하는 경우 데이터에 액세스하는 방법은 이 메모리에 저장되어있는대로에 순차적으로 액세스하는지 확인하고 L1/L2 캐시를 비우지 않도록하는 것입니다 모든 반복에서 (이전에 작은 L1 캐시에서 보았을 때, 그 차이는 극적 일 수 있음).

또 다시 루프 내부에 무엇이 있는지 살펴볼 것입니다. 외부 루프 배관이 아닌 대부분의 이득이 (> 99 %) 될 것입니다.

그러나 루프 코드가 I/O 경계이면 다시 최적화에 소요되는 시간이 낭비됩니다.

Answer 12

또 다른 stackoverflow 질문 인 how cache memory works에 대한 답변 중 몇 가지 관련 정보가 있습니다. 나는 Ulrich Drepper에 의해 종이가 this에서 특히 유용하다고 대답했다.

Answer 13

그런데 Int16 용량이 충분하다고 보장되면 for 루프에서 int 대신 short을 사용하는 것이 좋습니까?