[c] 카운트 다운하는 것보다 카운트 다운하는 것이 더 빠릅니까?

우리의 컴퓨터 과학 교사는 어떤 이유로 든 카운트 다운보다 카운트 다운하는 것이 더 효율적이라고 말했습니다. 예를 들어 FOR 루프를 사용해야하고 루프 인덱스가 어딘가에 사용되지 않는 경우 (N * 행을 화면에 인쇄하는 것과 같이) 다음과 같은 코드를 의미합니다.

for (i = N; i >= 0; i--)
  putchar('*');

보다 낫다:

for (i = 0; i < N; i++)
  putchar('*');

정말 사실입니까? 그렇다면 왜 그런지 아는 사람이 있습니까?

답변

정말 사실입니까? 그렇다면 그 이유를 아는 사람이 있습니까?

고대에는 컴퓨터가 여전히 용융 실리카에서 손으로 찢어 졌을 때, 8 비트 마이크로 컨트롤러가 지구를 돌아 다닐 때, 그리고 교사가 어렸을 때 (또는 교사가 어렸을 때) 감소와 건너 뛰기 라는 일반적인 기계 명령이있었습니다. 0이면 (DSZ). 핫샷 어셈블리 프로그래머는이 명령어를 사용하여 루프를 구현했습니다. 나중에 기계는 더 멋진 지침을 얻었지만 여전히 다른 것과 비교하는 것보다 0과 무언가를 비교하는 것이 훨씬 저렴한 프로세서가 여전히 많았습니다. 전체 레지스터를 항상 0으로 예약하는 PPC 또는 SPARC와 같은 일부 최신 RISC 시스템에서도 마찬가지입니다.

따라서 루프 대신을 0 대신 비교하도록 조작하면 N어떻게 될까요?

레지스터를 저장할 수 있습니다
작은 이진 인코딩으로 비교 명령을 얻을 수 있습니다
이전 명령에서 플래그를 설정 한 경우 (x86 제품군 시스템에서만 가능) 명시적인 비교 명령이 필요하지 않을 수도 있습니다.

이러한 차이 로 인해 현대의 비 순차적 프로세서 에서 실제 프로그램이 개선 될 가능성이 있습니까? 거의 없습니다. 실제로, 당신이 마이크로 벤치 마크에서도 측정 가능한 개선점을 보여줄 수 있다면 감동받을 것입니다.

요약 : 선생님을 머리 위로 거꾸로!습니다! 루프를 구성하는 방법에 대한 구식 의사 사실을 배우지 않아야합니다. 당신은 학습해야 루프에 대한 가장 중요한 것은 그들이 있는지 확인하는 것입니다 종료 , 생산 정답을 하고있는 읽기 쉬운 . 선생님이 신화가 아닌 중요한 것들에 집중하기를 바랍니다.

답변

컴파일러가 사용하는 숫자의 범위에 대해 추론 할 수있는 것에 따라 일부 하드웨어에서 발생할 수있는 사항은 다음과 같습니다. 증가 루프를 사용 i<N하면 루프 라운드마다 매번 테스트해야합니다 . 감소 버전의 경우 캐리 플래그 (빼기의 부작용으로 설정)가 자동으로을 알려줍니다 i>=0. 루프에서 시간당 테스트를 저장합니다.

실제로 최신 파이프 라인 프로세서 하드웨어에서는 명령에서 클럭 사이클에 대한 간단한 1-1 매핑이 없기 때문에 이러한 사항은 거의 관련이 없습니다. (마이크로 컨트롤러에서 정확한 시간에 비디오 신호를 생성하는 것과 같은 일을하고 있다면 어쨌든 올 수 있다고 상상할 수는 있지만 어쨌든 어셈블리 언어로 작성합니다.)

답변

Intel x86 명령어 세트에서 0으로 카운트 다운하는 루프를 구축하는 것은 일반적으로 0이 아닌 종료 조건까지 카운트하는 루프보다 적은 명령어로 수행 할 수 있습니다. 특히 ECX 레지스터는 전통적으로 x86 asm에서 루프 카운터로 사용되며 인텔 명령어 세트에는 ECX 레지스터를 0으로 테스트하고 테스트 결과에 따라 점프하는 특수 jcxz 점프 명령이 있습니다.

그러나 루프가 이미 클럭 사이클 수에 매우 민감하지 않으면 성능 차이는 무시할 수 있습니다. 카운트 다운을 0으로 카운트 다운하면 카운트 업에 비해 루프의 각 반복에서 4 또는 5 클럭 사이클을 줄일 수 있으므로 유용한 기술보다 참신합니다.

또한 요즘 잘 최적화 된 컴파일러는 루프 업 변수를 사용하는 방법에 따라 카운트 업 루프 소스 코드를 0의 기계 코드로 카운트 다운으로 변환 할 수 있어야하므로 실제로 루프를 작성할 이유가 없습니다. 여기저기서주기를 짜는 이상한 방법.

답변

예..!!

하드웨어에서 비교를 처리하는 방법의 관점에서 N에서 0으로 계산하는 것이 0에서 N으로 계산하는 것보다 약간 빠릅니다.

각 루프 의 비교 에 유의하십시오

i>=0
i<N

대부분의 프로세서는 제로 명령어와 비교됩니다. 따라서 첫 번째 프로세서는 다음과 같이 기계어 코드로 변환됩니다.

내가로드
0보다 작거나 같은 경우 비교 및 점프

그러나 두 번째는 매번 N 양식 메모리를로드해야합니다.

내가로드
부하 N
Sub i와 N
0보다 작거나 같은 경우 비교 및 점프

카운트 다운이나 카운트 업이 아니라 코드가 기계 코드로 변환되는 방식 때문입니다.

따라서 10에서 100까지의 계수는 100에서 10까지의 계수와 동일
하지만 i = 100에서 0까지의 계수는 i = 0에서 100보다 빠릅니다. 대부분의 경우
i = N에서 0까지의 계수는 i =보다 빠릅니다. 0에서 N

오늘날 컴파일러는 당신을 위해이 최적화를 수행 할 수 있습니다 (충분히 똑똑하다면)
파이프 라인은 Belady의 변칙적 인 효과를 유발할 수 있습니다 (더 나은 것이 무엇인지 확신 할 수 없음)
마지막으로, 제시 한 2 개의 for 루프는 동일하지 않습니다. 첫 번째는 하나 더 * * 인쇄합니다.

관련 :
왜 n ++이 n = n + 1보다 빠르게 실행됩니까?

답변

C에서 pseudo-assembly로 :

for (i = 0; i < 10; i++) {
    foo(i);
}

로 변하다

    clear i
top_of_loop:
    call foo
    increment i
    compare 10, i
    jump_less top_of_loop

동안:

for (i = 10; i >= 0; i--) {
    foo(i);
}

로 변하다

    load i, 10
top_of_loop:
    call foo
    decrement i
    jump_not_neg top_of_loop

두 번째 의사 조립에서는 비교가 부족합니다. 많은 아키텍처에는 점프에 사용할 수있는 산술 연산 (더하기, 빼기, 곱하기, 나누기, 증분, 감소)으로 설정된 플래그가 있습니다. 이것들은 종종 오퍼레이션 결과와 0을 무료로 비교하는 것을 종종 제공합니다. 실제로 많은 아키텍처에서

x = x - 0

의미 상으로

compare x, 0

또한 내 예제에서 10을 비교하면 코드가 더 나빠질 수 있습니다. 10은 레지스터에 있어야 할 수도 있으므로, 공급이 부족한 경우 루프를 통해 매번 10을 돌아 다니거나 다시로드하는 추가 코드가 발생할 수 있습니다.

컴파일러는 때때로 이것을 이용하기 위해 코드를 재 배열 할 수 있지만, 루프를 통한 방향 반전이 의미 상 동등하다는 것을 확신 할 수 없기 때문에 종종 어렵다.

답변

다음과 같은 경우 더 빨리 카운트 다운하십시오.

for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}

someObject.getAllObjects.size()처음에 한 번 실행 되기 때문 입니다.

물론 size()베드로가 언급했듯이 비슷한 행동을 반복 할 수 있습니다 .

size = someObject.getAllObjects.size();
for (i = 0; i < size; i++) {…}

답변

위로 카운트 다운하는 것이 더 빠릅니까?

아마도. 그러나 시간의 99 % 이상이 중요하지 않으므로 루프를 종료하기 위해 가장 ‘현상적인’테스트를 사용해야하며 합리적인 경우 독자가 생각하는 데 가장 적은 양의 생각이 필요하다는 것을 의미합니다. 루프가 수행하는 작업 (중지되는 작업 포함) 코드가 수행하는 작업의 정신적 (또는 문서화 된) 모델과 일치하도록하십시오.

루프가 배열 (또는 목록 또는 기타)을 통해 작동하는 경우 증가하는 카운터는 종종 독자가 루프가하는 일을 생각하는 방식과 더 잘 일치합니다-루프를 이런 식으로 코딩하십시오.

그러나 N항목 이있는 컨테이너를 통해 작업 하면서 항목을 제거하는 경우 카운터를 아래로 내리는 것이 더인지적일 수 있습니다.

대답의 ‘아마도’에 대해 좀 더 자세히 설명하십시오.

대부분의 아키텍처에서 계산 결과를 0 (또는 0에서 음으로 변경)으로 테스트 할 때는 명시적인 테스트 명령이 필요하지 않으며 결과를 직접 확인할 수 있습니다. 계산 결과 다른 숫자가 나오는지 테스트하려는 경우 명령 스트림에는 일반적으로 해당 값을 테스트하기위한 명시적인 명령이 있어야합니다. 그러나 특히 최신 CPU의 경우이 테스트는 일반적으로 루프 구성에 노이즈 수준보다 적은 시간을 더 추가합니다. 특히 해당 루프가 I / O를 수행하는 경우.

반면에 0에서 카운트 다운하고 카운터를 배열 인덱스로 사용하면 시스템의 메모리 아키텍처에 대해 작동하는 코드를 찾을 수 있습니다. 메모리 읽기는 종종 캐시를 ‘예상’하게합니다 순차 읽기를 예상하여 현재 메모리를 지나는 여러 메모리 위치. 메모리를 통해 거꾸로 작업하는 경우 캐싱 시스템은 낮은 메모리 주소에서 메모리 위치를 읽지 못할 수 있습니다. 이 경우 ‘뒤로’반복하면 성능이 저하 될 수 있습니다. 그러나 정확성이 가장 중요하기 때문에 성능을 문제가되지 않는 한 여전히 루프를 이런 식으로 코딩하고 코드를 모델과 일치시키는 것이 정확성을 보장하는 좋은 방법입니다. 잘못된 코드는 가능한 한 최적화되지 않았습니다.

따라서 코드의 성능이 실제로 문제가되지 않는 한 교수진의 조언을 잊는 경향이 있습니다.