for ループでのカウントダウン

Question

（いくつかの調査結果から）私は、for ループでカウントダウンする方が実際にはより効率的で実行時間が速いと信じています。私の完全なソフトウェア コードは C++ です

私は現在これを持っています：

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

私の「I」は署名されていないResgister intであり、「ドメイン」も符号なしintです

for ループでは、i は配列を通過するために使用されます。

array[i] = do stuff

これをカウントダウンに変換すると、ルーチンの期待される/正しい出力が台無しになります。

答えは非常に些細なものであることは想像できますが、よくわかりません。

アップデート：「処理」は、前後の反復には依存しません。for ループ内の計算は、i の反復に対して独立しています。（それが理にかなっているといいのですが）。

アップデート：for ループで実行時の高速化を達成するには、カウントダウンする必要がありますか。削除する場合は、int をデカールするときに署名されていない部分を削除しますか、それとも他の方法ですか?

助けてください。

Answer 1

後方forループは次のように見えると思います：

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

その場合、 i は unsigned であるため、 always はゼロ以上になります。ゼロに等しい符号なし変数をデクリメントすると、非常に大きな数にラップアラウンドされます。解決策は、 i に署名するか、forループの条件を次のように変更することです。

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

または domain-1 から 0 ではなく、 domain から 1 にカウントします：

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

Answer 2

符号なしカウンタを使用して逆方向にループする正しい方法は1つだけです。

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

コツがあります。最後のループの繰り返しでは、ループの先頭にi = 1があります。i--＆gt; 1＆gt;のため0は合格です。 0、ループ本体ではi = 0。次の反復でi--＆gt; i == 0であるため、0は失敗します。したがって、接尾辞のデクリメントがカウンタをロールオーバーしたことは問題ではありません。

知っていることはほとんどありません。

Answer 3

これはあなたの問題に対する答えではありません。あなたは問題を抱えていないようだからです。

この種の最適化は完全に無関係であり、コンパイラーに任せる必要があります（実行する場合）。

forループがボトルネックであることを確認するためにプログラムのプロファイルを作成しましたか？そうでない場合は、これについて心配する時間を費やす必要はありません。さらに、「i」が「登録」としてあなたが書いているように、intはパフォーマンスの観点からは意味がありません。

問題のドメインを知らなくても、逆ループ手法と「登録」の両方が保証されます。 intカウンターは、プログラムのパフォーマンスにごくわずかな影響しか与えません。 「早すぎる最適化はすべての悪の根源」であることに注意してください。

とはいえ、最適化時間は、全体的なプログラム構造、使用されるデータ構造とアルゴリズム、リソース使用率などについて考えることに費やした方が良いということです。

Answer 4

数値がゼロであるかどうかを確認することは、比較よりも迅速または効率的です。しかし、これはあなたが本当に心配するべきではない一種のマイクロ最適化です-いくつかのクロックサイクルは、他のパフォーマンスの問題について非常に小さくなります。

x86の場合：

dec eax
jnz Foo

代わりに：

inc eax
cmp eax, 15
jl Foo

Answer 5

まともなコンパイラーがある場合、「カウントアップ」を最適化します; 「カウントダウン」と同じくらい効果的です。いくつかのベンチマークを試してみてください。表示されます。

Answer 6

だからあなたは「読む」その計算はより効率的ですか？プロファイラーの結果とコードを見せてくれない限り、これは信じがたいことです。状況によっては購入することもできますが、一般的な場合はありません。これは時期尚早な最適化の古典的なケースのように思えます。

＆quot; register int i＆quot;に関するコメントとてもわかりやすいです。最近では、コンパイラはレジスタを割り当てる方法よりも常によく知っています。コードのプロファイルを作成していない限り、registerキーワードの使用を気にしないでください。

Answer 7

あらゆる種類のデータ構造をループしている場合、キャッシュミスは、進行方向よりもはるかに大きな影響を与えます。些細な最適化ではなく、メモリレイアウトとアルゴリズム構造の全体像に関心を持ちます。

Answer 8

アップまたはダウンのカウントとは関係ありません。より高速にできるのは、ゼロに向かってを数えることです。 マイケルの答えは、＆＃8212;の理由を示しています。 x86では、多くの命令の暗黙的な副作用としてゼロとの比較が行われるため、カウンターを調整した後、明示的な比較を行う代わりに、結果に基づいて分岐するだけです。 （たぶん他のアーキテクチャもそうしています;私は知りません。）

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 を検査すると、デバッガーはを使用すると、ループが逆方向に実行されていると考えるプログラマーにとって混乱やパニックが終わりません。）

アイデアは、余分な Inc または Dec 命令を使用しても、明示的な比較を行うよりも、実行時間の点で依然として正味の勝ちであるということです。 議論の余地があることを実際に通知できるかどうか

しかし、変換が価値があると判断したかどうかに基づいて、変換はコンパイラが自動的に行うものであることに注意してください。 コンパイラは通常、コードを最適化するのがあなたよりも優れているため、コンパイラとの競合にあまり労力を費やさないでください。

とにかく、PascalではなくC ++について質問しました。 C ++＆quot; for＆quot;ループは、Pascal＆quot; for＆quot;ほど最適化を適用するのは簡単ではありません。ループは、Pascalのループの境界がループの実行前に常に完全に計算されるのに対し、C ++ループは停止条件とループの内容に依存する場合があるためです。 C ++コンパイラは、一定のループがPascalループが無条件に適格な変換の要件に適合するかどうかを判断するために、ある程度の静的分析を行う必要があります。 C ++コンパイラが分析を行う場合、同様の変換を行うことができます。

自分でループをそのように書くことを妨げるものは何もありません：

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

それを行うと、可能性があります、コードの実行が速くなります。前にも言ったように、おそらく気付かないでしょう。そのようなループを手動で配置することによって支払う大きなコストは、コードが確立されたイディオムに従っていないことです。あなたのループは完全に普通の「for」です。ループしますが、外見のようになりません＆＃8212;これには2つの変数があり、それらは反対方向にカウントし、そのうちの1つはループ本体でも使用されません＆＃8212;そのため、コードを読んでいる人（あなたが達成したいと思っていた「最適化」を忘れていた1週間、1か月、1年を含む）は、ループを証明するために余分な努力を費やす必要があります。実際、変装した普通のループです。

（上記のコードで符号なし変数を使用し、ゼロでラップアラウンドする危険がないことに気付きましたか？2つの別個の変数を使用すると、それが可能になります。）

これらすべてから取り除く3つのこと：

1. オプティマイザーに仕事をさせます。全体的にはあなたよりも上手です。
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 ...)
}

この形式は、算術演算後に一部プロセッサに設定される条件フラグを利用します。一部のアーキテクチャでは、分岐条件のデクリメントとテストを1つの命令に組み合わせることができます。ここでは、predecrement（-i ）を使用することが重要です。postdecrement（ 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 ...)
}

この2番目の形式は、ポインター（アドレス）演算を利用します。最近では（pointer-int）という形式はめったに見られませんが（正当な理由により）、言語は、ポインターからintを減算すると、ポインターが（int * sizeof（* pointer））。

これらの形式があなたにとって有益かどうかは、使用しているCPUとコンパイラに依存することを再度強調します。モトローラ6809および68000アーキテクチャでうまく機能しました。

Answer 12

後のいくつかのアームコアでは、デクリメントと比較は1つの命令のみを取ります。これにより、ループの増分よりもループの減分が効率的になります。

増分比較命令も存在しない理由がわかりません。

この投稿が本当の問題である場合、この投稿が-1に投票されたことに驚いています。

Answer 13

ここでは全員がパフォーマンスに焦点を当てています。実際には、ゼロに向かって反復する論理的な理由があり、コードがよりきれいになる可能性があります。

最初の最後の要素を反復処理すると、無効な要素を配列の末尾と交換して削除するときに便利です。端に隣接していない不良な要素については、端の位置にスワップし、配列の端の境界を減らして、繰り返し続けることができます。あなたが最後に向かって反復する場合、最後と交換すると、悪いものから悪いものへの交換になる可能性があります。 endを0に反復することにより、配列の最後の要素がこの反復で既に有効であることが証明されていることがわかります。

詳細については...

If：

1. 不良要素を削除するには、配列の一方の端と交換し、不良要素を除外するように配列の境界を変更します。

その後、明らかに：

2. 優れた要素、つまりこの反復で既にテストされた要素と交換します。

つまり、これは次のことを意味します。

3. 変数バウンドから反復する場合、変数バウンドと現在の反復ポインターの間の要素は良好であることが証明されています。反復ポインターが++を取得するかどうかは関係ありません。重要なのは、変数の境界から離れて反復しているため、それに隣接する要素が適切であることを知っていることです。

最後に：

4. 0に向かって反復すると、1つの変数のみを使用して配列の境界を表すことができます。これが重要かどうかは、あなたとあなたのコンパイラの間の個人的な決定です。

Answer 14

カウンタを増やすか減らすかよりもはるかに重要なのは、メモリを増やすか減らすかです。ほとんどのキャッシュは、メモリのダウンではなくメモリのアップに最適化されています。現在のほとんどのプログラムが直面しているボトルネックはメモリ アクセス時間であるため、メモリを増やすようにプログラムを変更すると、カウンタをゼロ以外の値と比較する必要がある場合でも、パフォーマンスが向上する可能性があることを意味します。一部のプログラムでは、メモリを下げるのではなくメモリを増やすようにコードを変更することで、パフォーマンスが大幅に向上しました。

懐疑的ですか？得られた出力は次のとおりです。

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 ただし、これらの変更が将来のタイミングに影響を与えることはありません。

タイミングを計っているループがどれほど緊密であるかに注目することが重要です。ループ本体が大きい場合、ループ本体の実行にかかる時間が完全に支配する可能性が高いため、反復子がメモリ上に移動するか下降するかは問題になりません。また、まれなループでは、メモリを下降する方が上昇するよりも速い場合があることに言及することが重要です。しかし、そのようなループであっても、上昇が常に下降よりも遅いということはほとんどありません (メモリを上昇するループとは異なり、メモリを上昇するループは、同等のメモリを下降するループよりも常に高速であることがよくあります)。ほんの一握りの場合、40% 以上速かったこともありました)。

重要なのは、経験則として、オプションがあり、ループの本体が小さい場合、およびループをメモリを下降させるのではなくメモリ上に移動させることにほとんど違いがない場合は、メモリを上に移動する必要があるということです。