49

ループmemset() よりも効率的です。for

このコードを検討する：

char x[500];
memset(x,0,sizeof(x));

そしてこれ：

char x[500];
for(int i = 0 ; i < 500 ; i ++) x[i] = 0;

どちらがより効率的で、なぜですか？ブロックレベルの初期化を行うための特別な命令がハードウェアにありますか。

4

7 に答える 7

40

最も確かに、memsetそのループよりもはるかに高速になります。一度に1文字を処理する方法に注意してください。ただし、これらの関数は、MMXおよびSSE命令が使用可能な場合でも、一度に数バイトを設定するように最適化されています。

これらの最適化の典型的な例は、通常は見過ごされがちですが、GNUCライブラリstrlen関数だと思います。少なくともO（n）のパフォーマンスがあると思うかもしれませんが、実際にはアーキテクチャに応じてO（n / 4）またはO（n / 8）があります（そうです、大きなO（）では同じになります、しかし実際には8分の1の時間が得られます）。どのように？トリッキーですが、うまく：strlen。

于 2011-09-09T21:37:03.147 に答える
37

さて、生成されたアセンブリコード、VS2010での完全な最適化を見てみませんか。

char x[500];
char y[500];
int i;      

memset(x, 0, sizeof(x) );   
  003A1014  push        1F4h  
  003A1019  lea         eax,[ebp-1F8h]  
  003A101F  push        0  
  003A1021  push        eax  
  003A1022  call        memset (3A1844h)

そしてあなたのループ...

char x[500];
char y[500];
int i;    

for( i = 0; i < 500; ++i )
{
    x[i] = 0;

      00E81014  push        1F4h  
      00E81019  lea         eax,[ebp-1F8h]  
      00E8101F  push        0  
      00E81021  push        eax  
      00E81022  call        memset (0E81844h)  

      /* note that this is *replacing* the loop, 
         not being called once for each iteration. */
}

したがって、このコンパイラでは、生成されるコードはまったく同じです。 memsetは高速であり、コンパイラは、とにかく一度呼び出すのと同じことをしていることを知るのに十分賢いmemsetので、それはあなたのためにそれを行います。

memsetコンパイラが実際にループをそのままにしておくと、一度に複数のバイトサイズのブロックを設定できるため、速度が低下する可能性があります（つまり、ループを少なくとも少し展開できます。少なくともループなどの単純な実装と同じくらいの速さです。デバッグビルドで試してみると、ループが置き換えられていないことがわかります。

とは言うものの、それはコンパイラがあなたのために何をするかに依存します。分解を見ることは、何が起こっているのかを正確に知るための良い方法です。

于 2011-09-09T21:45:31.070 に答える
13

それは本当にコンパイラとライブラリに依存します。古いコンパイラまたは単純なコンパイラの場合、memsetはライブラリに実装されている可能性があり、カスタムループよりもパフォーマンスが向上しません。

使用する価値のあるほぼすべてのコンパイラーにとって、memsetは組み込み関数であり、コンパイラーはそのために最適化されたインラインコードを生成します。

他の人はプロファイリングと比較を提案しましたが、私は気にしません。memsetを使用するだけです。コードはシンプルで理解しやすいです。コードのこの部分がパフォーマンスのホットスポットであることがベンチマークでわかるまでは、心配しないでください。

于 2011-09-09T21:35:04.277 に答える
9

答えは「状況によって異なります」です。 memsetより効率的である場合もあれば、内部でforループを使用する場合もあります。memset効率が悪くなるケースは考えられません。この場合、より効率的なforループになる可能性があります。ループは500回繰り返され、毎回1バイト相当の配列を0に設定します。64ビットマシンでは、ループスルーして、一度に8バイト（long long）を設定できます。これは、ほぼ8倍速くなり、最後に残りの4バイト（500％8）を処理するだけです。

編集：

実際、これはmemsetglibcで行われることです。

http://repo.or.cz/w/glibc.git/blob/HEAD:/string/memset.c

Michaelが指摘したように、特定の場合（コンパイル時に配列の長さがわかっている場合）、Cコンパイラはインラインmemset化して、関数呼び出しのオーバーヘッドを取り除くことができます。Glibcにはmemset、amd64などのほとんどの主要なプラットフォーム用のアセンブリ最適化バージョンもあります。

http://repo.or.cz/w/glibc.git/blob/HEAD:/sysdeps/x86_64/memset.S

于 2011-09-09T21:37:38.367 に答える
3

優れたコンパイラはforループを認識し、それを最適なインラインシーケンスまたはmemsetの呼び出しに置き換えます。また、バッファサイズが小さい場合は、memsetを最適なインラインシーケンスに置き換えます。

実際には、最適化コンパイラを使用すると、生成されるコード（したがってパフォーマンス）は同じになります。

于 2011-09-09T21:38:50.657 に答える
2

上記に同意します。場合によります。しかし、確かにmemsetはforループよりも高速または同等です。環境が不明な場合、またはテストするのが面倒な場合は、安全なルートを使用してmemsetを使用してください。

于 2011-09-09T21:40:49.340 に答える
1

ループの数を減らすループ展開のような他の手法も使用できます。memset（）のコードは、有名なダフのデバイスを模倣できます。

void *duff_memset(char *to, int c, size_t count)
{
    size_t n;
    char *p = to;
    n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *p++ = c;
    case 7:      *p++ = c;
    case 6:      *p++ = c;
    case 5:      *p++ = c;
    case 4:      *p++ = c;
    case 3:      *p++ = c;
    case 2:      *p++ = c;
    case 1:      *p++ = c;
            } while (--n > 0);
    }
    return to;
}

過去に実行速度を向上させるために使用されたこれらのトリック。しかし、最近のアーキテクチャでは、これによりコードサイズが増加し、キャッシュミスが増加する傾向があります。

したがって、コンパイラの最適化の品質、特別なハードウェア命令を利用するCライブラリの機能、操作しているデータの量、および基盤となるオペレーティングシステム（ページフォールト管理、TLBミス、コピーオンライト）。

たとえば、glibcでは、memset（）の実装、およびbzero（）やstrcpy（）などの他のさまざまな「コピー/セット」関数は、 SSEやAVXなどのさまざまな最適化されたハードウェア命令を利用するためにアーキテクチャに依存しています。

于 2021-02-11T10:50:37.937 に答える