카운트 다운하는 것보다 카운트 다운하는 것이 더 빠릅니까?
우리의 컴퓨터 과학 교사는 어떤 이유로 든 카운트 다운보다 카운트 다운하는 것이 더 효율적이라고 말했습니다. 예를 들어 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 루프는 동일하지 않습니다. 첫 번째는 하나 더 * * 인쇄합니다.
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에서 카운트 다운하고 카운터를 배열 인덱스로 사용하면 시스템의 메모리 아키텍처에 대해 작동하는 코드를 찾을 수 있습니다. 메모리 읽기는 종종 캐시를 '예상'하게합니다 순차 읽기를 예상하여 현재 메모리를 지나는 여러 메모리 위치. 메모리를 통해 거꾸로 작업하는 경우 캐싱 시스템은 낮은 메모리 주소에서 메모리 위치를 읽지 못할 수 있습니다. 이 경우 '뒤로'반복하면 성능이 저하 될 수 있습니다. 그러나 정확성이 가장 중요하기 때문에 성능을 문제로하지 않는 한 여전히 루프를 이런 식으로 코딩하고 코드를 모델과 일치시키는 것이 정확성을 보장하는 좋은 방법입니다. 잘못된 코드는 가능한 한 최적화되지 않았습니다.
따라서 코드의 성능이 실제로 문제가되지 않는 한 교수진의 조언을 잊는 경향이 있습니다 (물론 그의 시험은 아닙니다-교실이 진행되는 한 실용적이어야 함).
일부 구형 CPU에는 DJNZ== "0이 아닌 경우 감소 및 점프" 와 같은 명령이있었습니다 . 이를 통해 초기 카운트 값을 레지스터에로드 한 효율적인 루프가 가능하며 하나의 명령으로 감소 루프를 효과적으로 관리 할 수 있습니다. 우리는 여기서 1980 년대 ISA를 이야기하고 있습니다. 선생님이이 "엄지 규칙"이 여전히 현대 CPU에 적용된다고 생각한다면, 당신의 교사는 진지하게 연락이 없습니다.
단발,
미세 최적화를 수행하기 전까지는 CPU에 대한 매뉴얼이 제공됩니다. 또한, 당신이 그런 종류의 일을하고 있다면 어쨌든이 질문을 할 필요가 없을 것입니다. :-) 그러나 선생님은 분명히 그 아이디어를 구독하지 않습니다 ....
루프 예제에서 고려해야 할 4 가지가 있습니다.
for (i=N;
i>=0; //thing 1
i--) //thing 2
{
putchar('*'); //thing 3
}
- 비교
비교는 (다른 사람들이 지적했듯이) 특정 프로세서 아키텍처 와 관련이 있습니다 . Windows를 실행하는 것보다 많은 유형의 프로세서가 있습니다. 특히 0과의 비교를 단순화하고 속도를 높이는 명령이있을 수 있습니다.
- 조정
경우에 따라 위 또는 아래로 조정하는 것이 더 빠릅니다. 일반적으로 좋은 컴파일러는 알아 내고 가능하면 루프를 다시 실행합니다. 모든 컴파일러가 좋은 것은 아닙니다.
- 루프 바디
putchar로 syscall에 액세스하고 있습니다. 엄청 느립니다. 또한 화면에 간접적으로 렌더링됩니다. 심지어 더 느립니다. 1000 : 1 이상의 비율을 생각하십시오. 이 상황에서 루프 바디는 전체적으로 루프 조정 / 비교 비용을 능가합니다.
- 캐시
캐시 및 메모리 레이아웃은 성능에 큰 영향을 줄 수 있습니다. 이 상황에서는 중요하지 않습니다. 그러나 어레이에 액세스하고 최적의 성능이 필요한 경우 컴파일러와 프로세서가 메모리 액세스를 어떻게 배치했는지 조사하고 소프트웨어를 최대한 활용하도록 튜닝해야합니다. 스톡 예제는 행렬 곱셈과 관련하여 주어진 것입니다.
카운터를 늘리거나 줄이는 것보다 훨씬 중요한 것은 메모리를 늘리거나 내리는 것입니다. 대부분의 캐시는 메모리가 아닌 메모리를 늘리는 데 최적화되어 있습니다. 메모리 액세스 시간은 오늘날 대부분의 프로그램이 직면하는 병목 현상이므로 카운터를 0이 아닌 값과 비교해야하는 경우에도 메모리를 늘리도록 프로그램을 변경하면 성능이 향상 될 수 있습니다. 일부 프로그램에서 코드를 변경하지 않고 메모리를 늘리도록 코드를 변경하여 성능이 크게 향상되었습니다.
의심 많은? 내가 얻은 결과는 다음과 같습니다.
Ave. Up Memory = 4839 mus
Ave. Down Memory = 5552 mus
Ave. Up Memory = 18638 mus
Ave. Down Memory = 19053 mus
이 프로그램을 실행에서 :
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
std::random_device rnd_device;
std::mt19937 generator(rnd_device());
std::uniform_int_distribution<T> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}
template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
std::random_device rnd_device;
std::mt19937_64 generator(rnd_device());
std::uniform_real_distribution<double> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}
template<class Iterator, class T>
inline void sum_abs_up(Iterator first, Iterator one_past_last, T &total) {
T sum = 0;
auto it = first;
do {
sum += *it;
it++;
} while (it != one_past_last);
total += sum;
}
template<class Iterator, class T>
inline void sum_abs_down(Iterator first, Iterator one_past_last, T &total) {
T sum = 0;
auto it = one_past_last;
do {
it--;
sum += *it;
} while (it != first);
total += sum;
}
template<class T>
std::chrono::nanoseconds TimeDown(std::vector<T> &vec, const std::vector<T> &vec_original,
std::size_t num_repititions, T &running_sum) {
std::chrono::nanoseconds total{0};
for (std::size_t i = 0; i < num_repititions; i++) {
auto start_time = std::chrono::high_resolution_clock::now();
sum_abs_down(vec.begin(), vec.end(), running_sum);
total += std::chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
template<class T>
std::chrono::nanoseconds TimeUp(std::vector<T> &vec, const std::vector<T> &vec_original,
std::size_t num_repititions, T &running_sum) {
std::chrono::nanoseconds total{0};
for (std::size_t i = 0; i < num_repititions; i++) {
auto start_time = std::chrono::high_resolution_clock::now();
sum_abs_up(vec.begin(), vec.end(), running_sum);
total += std::chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
template<class ValueType>
void TimeFunctions(std::size_t num_repititions, std::size_t vec_size = (1u << 24)) {
auto lower = std::numeric_limits<ValueType>::min();
auto upper = std::numeric_limits<ValueType>::max();
std::vector<ValueType> vec(vec_size);
FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
const auto vec_original = vec;
ValueType sum_up = 0, sum_down = 0;
auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
std::cout << "Ave. Up Memory = " << time_up/(num_repititions * 1000) << " mus\n";
std::cout << "Ave. Down Memory = " << time_down/(num_repititions * 1000) << " mus"
<< std::endl;
return ;
}
int main() {
std::size_t num_repititions = 1 << 10;
TimeFunctions<int>(num_repititions);
std::cout << '\n';
TimeFunctions<double>(num_repititions);
return 0;
}
모두 sum_abs_up와 sum_abs_down같은 일을하고에게 유일한 차이 존재와 같은 방법으로 시간이 초과되는 sum_abs_up동안 메모리를 간다 sum_abs_down메모리 아래로 이동합니다. vec두 함수가 동일한 메모리 위치에 액세스하도록 참조로 전달 합니다. 그럼에도 불구하고 sum_abs_up지속적으로보다 빠릅니다 sum_abs_down. 직접 실행하십시오 (g ++ -O3으로 컴파일했습니다).
참고로 vec_original쉽게 나를 변화 할 수 있도록하기 위해, 실험을 위해 존재 sum_abs_up하고 sum_abs_down그들을 변경할 수있는 방법으로 vec이러한 변화는 미래의 타이밍에 영향을 허용하지 않는 동안.
내가 타이밍을 맞추고있는 루프가 얼마나 타이트한 지 주목하는 것이 중요하다. 루프 본문이 크면 루프 본문을 실행하는 데 걸리는 시간이 완전히 지배되므로 반복자가 메모리를 늘리거나 내리는 지 여부는 중요하지 않습니다. 또한 드문 루프를 사용하면 메모리를 낮추는 것이 때로는 올리는 것보다 빠르다는 점을 언급하는 것이 중요합니다. 그러나 그러한 루프의 경우에도 메모리가 올라가는 작은 몸체의 루프와 달리 반대 방향이 자주 적용되는 작은 몸체의 루프와 달리 올라가는 것보다 항상 느리게 진행되는 경우는 거의 없습니다. 사실, 소수의 루프의 경우 시간이 초과되면 메모리를 늘리면 성능이 40 % 이상 증가합니다.
요컨대, 선택의 여지가 있다면 루프의 몸체가 작고 루프가 메모리를 내리는 대신 메모리를 올리는 것 사이에 차이가 거의 없다면 메모리를 올리는 것이 중요합니다.
흥미로운 질문이지만, 실제 문제로서 중요하지 않다고 생각하고 하나의 루프를 다른 루프보다 나은 것으로 만들지 않습니다.
이 위키 백과 페이지에 따르면 , 윤초 (Leap second )는 "... 일조 는 주로 조력 마찰로 인해 세기마다 1.7ms 더 길어진다"고 말했다. 그러나 생일까지 며칠을 세고 있다면 시간의 작은 차이에 정말로 신경을 씁니까?
소스 코드를 읽고 이해하기가 더 중요합니다. 이 두 루프는 가독성이 중요한 이유에 대한 좋은 예입니다. 동일한 횟수만큼 반복되지 않습니다.
나는 대부분의 프로그래머가 (i = 0; i <N; i ++)를 읽고 이것이 N 번 반복된다는 것을 즉시 이해한다고 확신합니다. 어쨌든 (i = 1; i <= N; i ++)의 루프는 조금 덜 명확하고 (i = N; i> 0; i--)로 잠시 생각해야합니다. . 코드의 의도가 생각없이 뇌로 직접 들어가는 것이 가장 좋습니다.
이상하게도 차이가있는 것으로 보입니다. 적어도 PHP에서는. 다음 벤치 마크를 고려하십시오.
<?php
print "<br>".PHP_VERSION;
$iter = 100000000;
$i=$t1=$t2=0;
$t1 = microtime(true);
for($i=0;$i<$iter;$i++){}
$t2 = microtime(true);
print '<br>$i++ : '.($t2-$t1);
$t1 = microtime(true);
for($i=$iter;$i>0;$i--){}
$t2 = microtime(true);
print '<br>$i-- : '.($t2-$t1);
$t1 = microtime(true);
for($i=0;$i<$iter;++$i){}
$t2 = microtime(true);
print '<br>++$i : '.($t2-$t1);
$t1 = microtime(true);
for($i=$iter;$i>0;--$i){}
$t2 = microtime(true);
print '<br>--$i : '.($t2-$t1);
흥미로운 결과 :
PHP 5.2.13
$i++ : 8.8842368125916
$i-- : 8.1797409057617
++$i : 8.0271911621094
--$i : 7.1027431488037
PHP 5.3.1
$i++ : 8.9625310897827
$i-- : 8.5790238380432
++$i : 5.9647901058197
--$i : 5.4021768569946
누군가 이유를 안다면, 알아두면 좋을 것입니다 :)
편집 : 0에서 시작하지 않고 다른 임의의 값을 계산하더라도 결과는 동일합니다. 그렇다면 아마도 0과 비교하여 차이를 만드는 것은 아닐까요?
그것은 수 빠릅니다.
현재 작업중인 NIOS II 프로세서에서 전통적인 for 루프
for(i=0;i<100;i++)
어셈블리를 생성합니다.
ldw r2,-3340(fp) %load i to r2
addi r2,r2,1 %increase i by 1
stw r2,-3340(fp) %save value of i
ldw r2,-3340(fp) %load value again (???)
cmplti r2,r2,100 %compare if less than equal 100
bne r2,zero,0xa018 %jump
카운트 다운하면
for(i=100;i--;)
우리는 2 명령이 덜 필요한 어셈블리를 얻습니다.
ldw r2,-3340(fp)
addi r3,r2,-1
stw r3,-3340(fp)
bne r2,zero,0xa01c
내부 루프가 많이 실행되는 중첩 루프가있는 경우 측정 가능한 차이가 있습니다.
int i,j,a=0;
for(i=100;i--;){
for(j=10000;j--;){
a = j+1;
}
}
내부 루프가 위와 같이 작성된 경우 실행 시간은 0.12199999999999999734 초입니다. 내부 루프가 전통적인 방식으로 작성된 경우 실행 시간은 0.17199999999999998623 초입니다. 따라서 루프 카운트 다운은 약 30 % 빠릅니다.
그러나이 테스트는 모든 GCC 최적화가 해제 된 상태에서 수행되었습니다. 그것들을 켜면 컴파일러는 실제로이 손쉬운 최적화보다 똑똑하고 전체 루프 동안 레지스터에 값을 유지하며 다음과 같은 어셈블리를 얻습니다
addi r2,r2,-1
bne r2,zero,0xa01c
이 특정 예제에서 컴파일러 는 루프 실행 후 변수 a 가 항상 1이고 루프를 모두 건너 뜁니다.
그러나 때로는 루프 본문이 충분히 복잡하면 컴파일러 가이 최적화를 수행 할 수 없으므로 항상 빠른 루프 실행을 얻는 가장 안전한 방법은 다음과 같습니다.
register int i;
for(i=10000;i--;)
{ ... }
물론 루프가 반대로 실행되고 Betamoo가 말한 것처럼 0으로 카운트 다운하는 경우에만 작동 합니다.
선생님이 말씀하신 내용은 명확하지 않은 약간의 진술입니다. 감소가 증분보다 빠르지는 않지만 증분보다 감소로 훨씬 빠른 루프를 만들 수 있습니다.
루프 카운터 등을 사용할 필요없이 길이에 관계없이 속도와 루프 수 (0이 아님)가 중요합니다.
대부분의 사람들이 10 회 반복하여 루프를 구현하는 방법은 다음과 같습니다.
int i;
for (i = 0; i < 10; i++)
{
//something here
}
99 %의 경우 모두 필요하지만 PHP, PYTHON, JavaScript와 함께 CPU 틱이 중요한 중요한 시간 소프트웨어 (보통 임베디드, OS, 게임 등)가 있습니다. 어셈블리 코드를 간단히 살펴보십시오.
int i;
for (i = 0; i < 10; i++)
{
//something here
}
컴파일 후 (최적화없이) 컴파일 된 버전은 다음과 같습니다 (VS2015).
-------- C7 45 B0 00 00 00 00 mov dword ptr [i],0
-------- EB 09 jmp labelB
labelA 8B 45 B0 mov eax,dword ptr [i]
-------- 83 C0 01 add eax,1
-------- 89 45 B0 mov dword ptr [i],eax
labelB 83 7D B0 0A cmp dword ptr [i],0Ah
-------- 7D 02 jge out1
-------- EB EF jmp labelA
out1:
전체 루프는 8 개의 명령어 (26 바이트)입니다. 그 안에는 실제로 2 개의 분기가있는 6 개의 명령어 (17 바이트)가 있습니다. 예 네, 더 잘할 수 있다는 것을 알고 있습니다 (단지 예일뿐).
이제 임베디드 개발자가 작성하는 빈번한 구성을 고려하십시오.
i = 10;
do
{
//something here
} while (--i);
또한 10 번 반복합니다 (예 : for 루프와 비교하여 i 값이 다르다는 것을 알고 있지만 반복 횟수에 관심이 있습니다). 이것은 이것으로 컴파일 될 수 있습니다 :
00074EBC C7 45 B0 01 00 00 00 mov dword ptr [i],1
00074EC3 8B 45 B0 mov eax,dword ptr [i]
00074EC6 83 E8 01 sub eax,1
00074EC9 89 45 B0 mov dword ptr [i],eax
00074ECC 75 F5 jne main+0C3h (074EC3h)
5 개의 명령어 (18 바이트)와 단 하나의 브랜치. 실제로 루프에는 4 개의 명령어가 있습니다 (11 바이트).
가장 좋은 점은 일부 CPU (x86 / x64 호환 포함)에 레지스터를 감소시킬 수있는 명령이 있고 나중에 0과 결과를 비교하고 결과가 0과 다른 경우 분기를 수행하는 것입니다. 거의 모든 PC CPU가이 명령어를 구현합니다. 그것을 사용하면 루프는 실제로 하나의 (예 하나) 2 바이트 명령입니다.
00144ECE B9 0A 00 00 00 mov ecx,0Ah
label:
// something here
00144ED3 E2 FE loop label (0144ED3h) // decrement ecx and jump to label if not zero
어느 쪽이 더 빠른지 설명해야합니까?
이제 특정 CPU가 위의 명령을 구현하지 않더라도 이전 명령의 결과가 0이면 조건을 뛰어 넘고 감소시키는 에뮬레이션에 필요한 모든 것입니다.
따라서 어떤 경우에 관계없이 내가 왜 잘못되었는지 등의 의견으로 지적 할 수 있습니다. 나는 강조합니다-예, 방법과 이유 및시기를 알고 있다면 다운 루프를 만드는 것이 유리합니다.
추신. 예, 현명한 컴파일러 (적절한 최적화 수준의)는 루프 (오름차순 루프 카운터 사용)를 위해 루프를 다시 작성한다는 것을 알고 있습니다.
아니요, 사실이 아닙니다. 더 빠를 수있는 상황 중 하나는 루프를 반복 할 때마다 범위를 확인하기 위해 함수를 호출하는 경우입니다.
for(int i=myCollection.size(); i >= 0; i--)
{
...
}
그러나 그렇게하는 것이 명확하지 않으면 가치가 없습니다. 현대 언어에서는 가능하면 foreach 루프를 사용해야합니다. 인덱스가 필요 없을 때 foreach 루프를 사용해야하는 경우를 구체적으로 언급합니다.
방향에 관계없이 항상 접두사 양식 (i ++ 대신 ++ i)을 사용하십시오!
for (i=N; i>=0; --i)
또는
for (i=0; i<N; ++i)
설명 : http://www.eskimo.com/~scs/cclass/notes/sx7b.html
또한 당신은 쓸 수 있습니다
for (i=N; i; --i)
그러나 현대 컴파일러가 이러한 최적화를 정확하게 수행 할 수있을 것으로 기대합니다.
요점은 카운트 다운 할 때 i >= 0감소 시키기 위해 별도로 확인할 필요가 없다는 것 i입니다. 관찰 :
for (i = 5; i--;) {
alert(i); // alert boxes showing 4, 3, 2, 1, 0
}
비교와 감소 i는 하나의 표현으로 이루어질 수 있습니다.
x86 명령어 수가 더 적은 이유에 대한 다른 답변을 참조하십시오.
그것이 응용 프로그램에서 의미있는 차이를 만드는지 여부에 관해서는, 그것은 얼마나 많은 루프가 있고 얼마나 중첩되어 있는지에 달려 있다고 생각합니다. 그러나 나에게 이런 식으로 읽을 수있는 것처럼 읽을 수 있으므로 어쨌든합니다.
이제, 당신은 충분한 어셈블리 강의를 받았다고 생각합니다.
정상에서 출발하는 이유는 매우 간단합니다. 루프 본문에서 실수로 경계를 변경하여 잘못된 동작 또는 종료되지 않은 루프로 끝날 수 있습니다.
Java 코드의이 작은 부분을보십시오 (이 이유 때문에 언어는 중요하지 않습니다).
System.out.println("top->down");
int n = 999;
for (int i = n; i >= 0; i--) {
n++;
System.out.println("i = " + i + "\t n = " + n);
}
System.out.println("bottom->up");
n = 1;
for (int i = 0; i < n; i++) {
n++;
System.out.println("i = " + i + "\t n = " + n);
}
내 요점은 위에서 아래로가는 것을 선호하거나 경계로 상수를 갖는 것을 고려해야한다는 것입니다.
어셈블러 수준에서 0으로 카운트 다운하는 루프는 일반적으로 주어진 값까지 카운트되는 루프보다 약간 빠릅니다. 계산 결과가 0이면 대부분의 프로세서는 0 플래그를 설정합니다. 하나를 빼면 0을지나 계산 랩을 만드는 경우 일반적으로 캐리 플래그가 변경됩니다 (일부 프로세서에서는 다른 플래그를 설정합니다) .0과의 비교는 본질적으로 무료입니다.
반복 횟수가 상수가 아니라 변수 인 경우 더욱 그렇습니다.
사소한 경우에는 컴파일러가 루프의 카운트 방향을 자동으로 최적화 할 수 있지만 더 복잡한 경우에는 루프의 방향이 전체 동작과 관련이 없음을 알고 있지만 컴파일러는이를 입증 할 수 없습니다.
참고 URL : https://stackoverflow.com/questions/2823043/is-it-faster-to-count-down-than-it-is-to-count-up
'Programming' 카테고리의 다른 글
| 자바 스크립트를 사용하여 브라우저 뒤로 버튼을 중지하는 방법 (0) | 2020.07.01 |
|---|---|
| 신속한 대의원? (0) | 2020.07.01 |
| 객체 배열에서 속성이 검색과 일치하는 객체의 색인을 찾는 가장 빠른 방법 (0) | 2020.07.01 |
| Java로 맵을 인쇄하십시오 (0) | 2020.07.01 |
| node.js로 고유 ID를 생성하는 방법 (0) | 2020.07.01 |