루프를 카운트 다운합니다

Question

나는 (일부 연구 읽기에서) for-loops를 계산하는 것이 실제로 런타임이 더 효율적이고 빠르다고 생각합니다. 내 전체 소프트웨어 코드는 C ++입니다

나는 현재 이것을 가지고있다 :

for (i=0; i<domain; ++i) {

내 'I'는 서명되지 않은 Resgister int, 또한 '도메인'도 서명되지 않은 int입니다.

for-loop에서 나는 배열을 통과하는 데 사용됩니다.

array[i] = do stuff

이것을 계산하도록 변환하면 내 루틴의 예상/올바른 출력을 엉망으로 만듭니다.

나는 대답이 상당히 사소하다고 상상할 수 있지만, 나는 머리를 돌릴 수는 없습니다.

업데이트 : '작업'은 이전 또는 이후 반복에 의존하지 않습니다. for-loop 내의 계산은 I의 반복에 대해 독립적입니다. (나는 그것이 말이되기를 바랍니다).

업데이트 : For-Loop로 런타임 속도를 달성하려면 int를 삭제할 때 서명되지 않은 부품을 제거하고 다른 방법을 제거해야합니까?

도와주세요.

Answer 1

루프의 후진이 다음과 같이 보입니다.

for (i = domain - 1; i >= 0; --i) {

이 경우 i ~이다 서명되지 않았습니다, 그것은 할 것입니다 언제나 0보다 크거나 동일합니다. 0과 동일한 서명되지 않은 변수를 줄이면 매우 많은 수로 감싸게됩니다. 해결책은 만들어야합니다 i 서명하거나 다음과 같이 FOR 루프의 조건을 변경하십시오.

for (i = domain - 1; i >= 0 && i < domain; --i) {

또는 카운트 domain 에게 1 출신보다는 domain - 1 에게 0:

for (i = domain; i >= 1; --i) {
    array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}

Answer 2

서명되지 않은 카운터를 사용하여 뒤로 반복하는 올바른 방법은 하나뿐입니다.

for( i = n; i-- > 0; )
{
    // Use i as normal here
}

여기에는 트릭이 있습니다. 마지막 루프 반복의 경우 루프 상단에 i = 1을 가질 수 있습니다. i-> 0은 1> 0이므로 루프 본체에서 i = 0입니다. 다음 반복에서 i--> 0은 i == 0이므로 실패하므로 사후 문제가 카운터 위로 롤링되는 것은 중요하지 않습니다.

내가 아는 것은 분명하지 않다.

Answer 3

문제가없는 것 같기 때문에 이것은 문제에 대한 답이 아닙니다.

이러한 종류의 최적화는 완전히 관련이 없으며 컴파일러에 맡겨야합니다 (완료된 경우).

당신의 루프가 병목 현상인지 확인하기 위해 프로그램을 프로파일 링 했습니까? 그렇지 않다면, 당신은 이것에 대해 걱정하는 데 시간을 할 필요가 없습니다. 더욱이, "I"를 "등록"int로 작성하는 것은 성능 관점에서 실제로 의미가 없습니다.

문제 도메인을 모르더라도 리버스 루핑 기술과 "등록"int 카운터 모두가 무시할 수 있습니다 프로그램 성능에 미치는 영향. "조기 최적화는 모든 악의 근원"을 기억하십시오.

즉, 더 나은 최적화 시간은 전반적인 프로그램 구조, 데이터 구조 및 알고리즘, 리소스 활용 등에 대해 생각하는 것입니다.

Answer 4

숫자가 0인지 확인하면 비교보다 빠르거나 효율적 일 수 있습니다. 그러나 이것은 당신이 실제로 걱정해서는 안되는 일종의 미세 최적화입니다. 몇 번의 클럭 사이클은 다른 Perf 문제에 의해 크게 왜소 될 것입니다.

x86 :

dec eax
jnz Foo

대신에:

inc eax
cmp eax, 15
jl Foo

Answer 5

괜찮은 컴파일러가있는 경우 "카운트 다운"만큼 효과적으로 "계산"을 최적화합니다. 몇 가지 벤치 마크를 시도해 보면 볼 수 있습니다.

Answer 6

그래서 당신은 내려가는 것이 더 효율적이라는 것을 "읽으십시오"? 프로파일 러 결과와 코드를 보여주지 않으면 믿기가 매우 어렵다는 것을 알게되었습니다. 나는 어떤 상황에서 그것을 살 수는 있지만, 일반적으로, no. 이것이 조기 최적화의 고전적인 사례 인 것처럼 보입니다.

"int I"에 대한 귀하의 의견도 매우 말하고 있습니다. 요즘 컴파일러는 항상 레지스터를 할당하는 방법보다 항상 더 잘 알고 있습니다. 코드를 프로파일하지 않으면 레지스터 키워드를 사용하는 사용을 귀찮게하지 마십시오.

Answer 7

모든 종류의 데이터 구조를 통해 반복되면 캐시 미스는 방향보다 훨씬 큰 영향을 미칩니다. 사소한 미세 최적화 대신 메모리 레이아웃 및 알고리즘 구조의 더 큰 그림에 관심을 갖습니다.

Answer 8

계산과 관련이 없습니다 위로 또는 아래에. 더 빠른 것은 계산입니다 0으로 향합니다. 마이클의 대답 이유를 보여줍니다 - x86은 많은 지침의 암시 적 부작용으로 0과 비교할 수 있으므로 카운터를 조정 한 후 명시 적 비교 대신 결과를 기준으로 분기됩니다. (아마도 다른 아키텍처도 그렇게 할 것입니다. 모르겠습니다.)

Borland의 Pascal 컴파일러는 그 최적화를 수행하는 것으로 유명합니다. 컴파일러는이 코드를 변환합니다.

for i := x to y do
  foo(i);

이것과 더 유사한 내부 표현으로 :

tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
  foo(i);
  Inc(i);
  Dec(tmp);
end;

(최적화가 루프 결과에 영향을 미치기 때문에 악명 높은 말이 아니라 디버거가 카운터 변수를 잘못 표시하기 때문에 프로그래머가 검사 할 때 i, 디버거는 값을 표시 할 수 있습니다 tmp 대신, 루프가 뒤로 가고 있다고 생각하는 프로그래머들에게 혼란과 공황을 일으키지 않습니다.)

아이디어는 추가로도 마찬가지입니다 Inc 또는 Dec 교육은 명백한 비교를 수행하는 것보다 여전히 러닝 타임 측면에서 순 승리입니다. 당신이 실제로 할 수 있는지 여부 알아채다 그 차이는 논쟁의 여지가 있습니다.

그러나 변환은 컴파일러가 할 일입니다. 자동으로, 그것이 변화가 가치있는 것으로 간주되는지에 근거합니다. 컴파일러는 일반적으로 자신보다 코드를 최적화하는 데 더 나은 것이므로 경쟁하는 데 너무 많은 노력을 기울이지 마십시오.

어쨌든, 당신은 파스칼이 아닌 C ++에 대해 물었습니다. "루프의 경우 C ++"는 "루프의 경계가 루프가 실행되기 전에 항상 완전히 계산되기 때문에"루프에 대한 최적화 "에 적용하기가 쉽지 않다. 내용물. C ++ 컴파일러는 주어진 루프가 무조건적으로 자격이되는 변환의 종류에 대한 요구 사항에 맞는지 여부를 결정하기 위해 어느 정도의 정적 분석을 수행해야합니다. C ++ 컴파일러가 분석을 수행하면 유사한 변환을 수행 할 수 있습니다.

당신이 당신의 루프를 스스로 쓰는 것을 막는 것은 없습니다.

for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
  array[i] = do stuff

그렇게하고 있습니다 ~할 것 같다 코드를 더 빨리 실행하십시오. 내가 전에 말했듯이, 당신은 아마 눈치 채지 못할 것입니다. 루프를 수동으로 배열하여 지불하는 비용이 더 커지면 코드가 더 이상 확립 된 관용구를 따르지 않는다는 것입니다. 루프는 "루프"의 경우 완벽하게 평범하지만 더 이상은 아닙니다. 외모 하나와 마찬가지로 - 두 가지 변수가 있으며 반대 방향으로 계산하고 있으며 그 중 하나는 루프 본문에도 사용되지 않으므로 코드를 읽는 사람 (귀하, 일주일, 한 달 또는 지금부터 1 년입니다. 당신이 달성하고자하는 "최적화"를 잊어 버렸을 때) 루프가 실제로 변장의 일반적인 루프라는 것을 스스로 증명하기 위해 추가 노력을 기울여야합니다.

(위의 내 코드가 0에서 래핑 할 위험이없는 서명되지 않은 변수를 사용했음을 알았습니까? 두 개의 별도 변수를 사용하여이를 가능하게합니다.)

이 모든 것을 빼앗아 갈 세 가지 :

1. Optimizer가 그 일을하게하십시오. 전체적으로 그것은 당신보다 더 낫습니다.
2. 특수 코드가 검토, 디버깅 또는 유지 관리로부터 관심을 끌기 위해 경쟁 할 필요가 없도록 일반 코드를 평범하게 보이게하십시오.
3. 테스트하고 프로파일 링이 필요하다는 것을 보여줄 때까지 성능의 이름으로 멋진 일을하지 마십시오.

Answer 9

다음을 시도 할 수 있습니다. 어떤 컴파일러가 매우 효율적으로 최적화 할 것입니다.

#define for_range(_type, _param, _A1, _B1) \
    for (_type _param = _A1, _finish = _B1,\
    _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
    _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))

이제 사용할 수 있습니다.

for_range (unsigned, i, 10,0)
{
    cout << "backwards i: " << i << endl;
}

for_range (char, c, 'z','a')
{
    cout << c << endl;
}

enum Count { zero, one, two, three }; 

for_range (Count, c, three, zero)
{
    cout << "backwards: " << c << endl;
}

어떤 방향 으로든 반복 할 수 있습니다.

for_range (Count, c, zero, three)
{
    cout << "forward: " << c << endl;
}

루프

for_range (unsigned,i,b,a)
{
   // body of the loop
}

다음 코드를 생성합니다.

 mov esi,b
L1:
;    body of the loop
   dec esi
   cmp esi,a-1
   jne L1 

Answer 10

주어진 정보로 말하기 어렵지만 ... 배열을 뒤집고 계산 하시겠습니까?

Answer 11

Jeremy Ruten은 서명되지 않은 루프 카운터를 사용하는 것이 위험하다고 지적했습니다. 내가 알 수있는 한도 불필요합니다.

다른 사람들은 또한 조기 최적화의 위험을 지적했습니다. 그들은 절대적으로 옳습니다.

그 말로, 여기에 몇 년 전 내장 시스템을 프로그래밍 할 때 모든 바이트와 모든 사이클이 무언가를 계산했을 때 사용한 스타일이 있습니다. 이 형태 ~이었다 내가 사용하고 있던 특정 CPU 및 컴파일러에서 유용하지만 마일리지는 다를 수 있습니다.

// Start out pointing to the last elem in array
pointer_to_array_elem_type p = array + (domain - 1);
for (int i = domain - 1; --i >= 0 ; ) {
     *p-- = (... whatever ...)
}

이 양식은 설정된 조건 플래그를 활용합니다. 약간 산술 작업 후 프로세서 - 일부 아키텍처에서 분기 조건의 감소 및 테스트를 단일 명령으로 결합 할 수 있습니다. 사전 조정 사용 (--i)는 여기에 핵심입니다.i--)도 효과가 없었을 것입니다.

대안 적으로,

// Start out pointing *beyond* the last elem in array
pointer_to_array_elem_type p = array + domain;
for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) {
     *(--p) = (... whatever ...)
}

이 두 번째 형태는 포인터 (주소) 산술을 활용합니다. 나는 양식을 거의 보지 못한다 (pointer - int) 요즘 (정당한 이유로) 그러나 언어는 포인터에서 int를 빼면 포인터가 감소한다는 것을 보장합니다. (int * sizeof (*pointer)).

이 양식이 귀하에게 승리 여부를 다시 강조하겠습니다. CPU와 컴파일러에 달려 있습니다. 그들은 Motorola 6809 및 68000 아키텍처에서 저를 잘 섬겼습니다.

Answer 12

일부 후기 암 코어에서는 감소 및 비교는 단일 명령 만 필요합니다. 이것은 루프 감소를 증분하는 것보다 더 효율적으로 만듭니다.

왜 증분 컴퓨터 지침이 없는지 모르겠습니다.

이 게시물이 진정한 문제 일 때 -1로 선정 된 것에 놀랐습니다.

Answer 13

여기있는 모든 사람들은 성능에 초점을 맞추고 있습니다. 실제로 클리너 코드를 초래할 수있는 0으로 반복해야 할 논리적 이유가 있습니다.

마지막 요소를 반복하는 것은 배열 끝과 교환하여 유효하지 않은 요소를 삭제할 때 편리합니다. 끝에 인접하지 않은 나쁜 요소의 경우 엔드 위치로 바꾸고 배열의 끝 경계를 줄이며 반복을 계속할 수 있습니다. 당신이 끝을 향해 반복한다면, 끝으로 바꾸면 나쁜 대체가 나빠질 수 있습니다. 끝을 0으로 반복함으로써 우리는 배열 끝의 요소가 이미이 반복에 유효한 것으로 입증되었다는 것을 알고 있습니다.

자세한 설명은 ...

만약에:

1. 배열의 한쪽 끝으로 바꾸고 배열 경계를 변경하여 잘못된 요소를 제외하여 잘못된 요소를 삭제합니다.

분명히 :

2. 이 반복에서 이미 테스트 된 좋은 요소를 스왑 할 것입니다.

그래서 이것은 다음과 같습니다.

3. 변수 바운드에서 반복하면 변수 바운드와 현재 반복 포인터 사이의 요소가 입증되었습니다. 반복 포인터가 ++를 얻는 지 여부는 중요하지 않습니다. 중요한 것은 우리가 변수 바운드에서 반복하여 인접한 요소가 양호하다는 것을 알고 있다는 것입니다.

그래서 마지막으로 :

4. 0으로 반복하면 하나의 변수 만 사용하여 배열 경계를 나타낼 수 있습니다. 이것이 중요한지 여부는 귀하와 귀하의 컴파일러 사이의 개인적인 결정인지 여부입니다.

Answer 14

카운터를 늘리거나 감소시키는 것보다 훨씬 중요한 것은 메모리를 올리거나 메모리를 낮추는 지 여부입니다. 대부분의 캐시는 메모리가 아닌 메모리를 올리는 데 최적화됩니다. 메모리 액세스 시간은 오늘날 대부분의 프로그램이 직면하는 병목 현상이므로, 이는 카운터를 0이 아닌 값과 비교해야하더라도 프로그램을 변경하면 성능 향상을 초래할 수 있음을 의미합니다. 내 프로그램 중 일부에서는 코드를 변경하여 내 코드 대신 메모리를 올리기 위해 코드를 변경하여 성능이 크게 향상되었습니다.

의심 많은? 내가 얻은 출력은 다음과 같습니다.

sum up   = 705046256
sum down = 705046256
Ave. Up Memory   = 4839 mus
Ave. Down Memory =  5552 mus
sum up   = inf
sum down = inf
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 RAI, class T>
inline void sum_abs_up(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

template<class RAI, class T>
inline void sum_abs_down(RAI first, RAI 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;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  {
  typedef int ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  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 << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  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;
  }
  {
  typedef double ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  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 << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  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 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 이러한 변화가 미래의 타이밍에 영향을 미치도록 허용하지는 않지만.

타이밍이 얼마나 타이밍인지 주목하는 것이 중요합니다. 루프의 몸체가 크면 반복자가 루프의 본체를 실행하는 데 걸리는 시간 이후로 ITERATOR가 올라가거나 아래로 내려가는 지 중요하지 않을 수 있습니다. 또한, 희귀 한 루프를 사용하면 메모리를 내려가는 것이 때로는 올라가는 것보다 빠릅니다. 그러나 그러한 루프에도 불구하고 올라가는 경우는 항상 아래로 내려가는 것보다 느리지 않았습니다 (메모리를 올리는 루프와는 달리, 동등한 다운 메모리 루프보다 항상 빠릅니다. +% 더 빨리).

요점은 옵션이 있다면, 루프의 본체가 작 으면, 루프가 아래로 내려 오는 대신 메모리를 올리는 것 사이에 차이가 거의 없다면 기억이 나면 메모리가 올라가야한다는 점입니다.