10

最近、memcpyを実装する必要があるインタビューの質問がありました。私は私の経験でmemcpyをたくさん使ったので、それは難しい問題のようには思えませんでした。

そこで、ポインタからポインタに一度に1つのアドレスをコピーするループの実装を開始しました。次のようになります。

void memcpy(void* dest, void* src, int size){
    for(int index = 0; index < size; index++){
        dest[index] = src[index];
    }
}

ただし、インタビュアーは、memcpyのマニュアルページに「srcからdestにnバイトをコピーする」（後で確認しました）と書かれていることに気づき、代わりにsize / 4で繰り返し処理して、残りを別のインデックスループで取得するように指示しました。 <size％4（32ビットシステムだと思いますか？）

まあ、これは、私がmemcpyを何年も問題なく使用していて、* 4修飾子を付けなくても問題がないことを考えると、奇妙に思えました）。家に帰ったとき、gdbを起動し、小さな文字列 "hello"をコピーし、strlen（）と定数の両方でサイズを慎重に入力して、開始位置と停止位置を確認しました。

    char* src = "hello";
    char* dest = calloc(16, sizeof(char));
    int len = strlen(src);
    memcpy(dest, src, len); // both my version and official version

ここで、srcとdestを両方とも「hello\0」を含むgdbで注意深く調べました。

だから私の質問は：数字の4（または「バイト単位のサイズ」）を使用することについて私が理解していないことは何ですか？そして、それが実際の動作ではないのに、なぜドキュメントに「nバイト」と記載されているのですか？ここではっきりと見えないものは何ですか？

4

7 に答える 7

15

他の人が言っているように、一度に4バイトをコピーする方が、一度に1バイトをコピーするよりも高速です。インタビュアーはあなたにこのようなことをしてほしいと思っていました：

void memcpy(void* dest, void* src, int size)
{
    uint8_t *pdest = (uint8_t*) dest;
    uint8_t *psrc = (uint8_t*) src;

    int loops = (size / sizeof(uint32_t));
    for(int index = 0; index < loops; ++index)
    {
        *((uint32_t*)pdest) = *((uint32_t*)psrc);
        pdest += sizeof(uint32_t);
        psrc += sizeof(uint32_t);
    }

    loops = (size % sizeof(uint32_t));
    for (int index = 0; index < loops; ++index)
    {
        *pdest = *psrc;
        ++pdest;
        ++psrc;
    }
}
于 2012-08-09T04:00:10.797 に答える
13

彼らは、実装を最適化し、ループ内で一度に32ビットワードをコピーするのに対して、一度に1バイトをコピーするように求めていました。sizeこれには、4の倍数でない、または4バイト境界に整列されていないdestなどsrc、境界の場合を処理するための注意深いチェックが必要になります。

于 2012-08-09T03:31:10.600 に答える
1

memcpyのロジックは正しく、インタビュアーはそれを変更したり制限を追加したりするように要求しませんでした。一度に4バイトをコピーする方が高速ですが、サイズが4の倍数でない場合は問題になります。したがって、インタビュアーは2つのループを使用するように指示しました。最初のループは一度に4バイトをコピーし、2番目のループは一度に1バイトをコピーします。時間（最大で3回繰り返されます）。

したがって、コピーの大部分は高速の4バイトコピーで実行されますが、2番目の「クリーンアップ」ループは4の倍数ではないものをコピーするため、サイズが4の倍数に制限されることはありません。

1番目のループ：uint32_tをコピーして4ずつインクリメント
2番目のループ：uint8_tをコピーして1ずつインクリメント

于 2012-08-09T03:34:57.960 に答える
1

インタビュアーは、コンピューターアーキテクチャに関する知識をテストしていて、アルゴリズムを最適化することを望んでいました。メモリはバイトではなくワードで動作します。32ビットシステムでは、ワードは通常4バイトであり、1バイトの読み取り/書き込みには1ワードの読み取り/書き込みと同じ時間がかかります。2番目のループは、コピーするバイト数が4バイトで正確に割り切れない場合を処理するためのものです。

実際に必要なのは3つのループです。destの後、dest + sizeの前のバイトに対して、どちらかがワードアラインされていない場合に2ループします。次に、その間のすべての単語に対して別のループを実行します。

アーキテクチャ固有の命令を利用することで、実際にはさらに最適化できます。興味がある場合は、この記事をチェックしてください：http ://www.eetimes.com/design/embedded/4024961/Optimizing-Memcpy-improves-speed

于 2012-08-09T03:41:58.290 に答える
1

インタビュアーは、何らかの理由で時期尚早の最適化を実行するように依頼しました。これは通常悪い考えです。

確かに、32ビットマシンは4x1バイトをコピーするよりも1つの32ビットチャックを速くコピーします。しかし、最適化にはそれ以上のものがあります。

32ビットマシンがデータをキャッシュメモリに配置する可能性が高く、突然高速なメモリアクセスがCPU命令よりもはるかに重要になる可能性があります。キャッシュメモリには、さまざまなアライメント要件がある場合があります。プレーンループを好む場合もあれば、32ビットで整列されたチャンクを好む場合もあります。私はこのテーマの専門家ではないので、時期尚早の最適化を避け、コンパイラーに任せます。コンパイラーは、私よりもキャッシュメモリーについて詳しく知っているといいのですが。

次に、CPU分岐予測と命令配管があります。この特定のコードはかなり決定論的であるため、これは問題ではない可能性があります。しかし、経験則として、単純なコードは複雑なコードよりも効果的な分岐予測をもたらします。

さらに、多くのCPUアーキテクチャでは遅い分割があります。コピーするデータの量によっては、分割によってmemcpyの速度が大幅に低下する場合があります。

要約すると、手動最適化は非常に複雑であり、CPUとハードウェアに関する深い知識が必要です。「32ビットCPU用に最適化」することはできませんし、すべきではありません。詳細を知る必要があります。ほとんどの場合、コンパイラはコードをあなたよりもはるかに効果的に最適化します。特にライブラリmemcpy（）は、特定のターゲット用に最適化されたインラインアセンブラで記述されることがよくあります。

于 2012-08-09T06:41:52.363 に答える
0

彼らはあなたにそれをスピードアップして欲しかった。32ビットプロセッサは、8ビットをコピーするよりも32ビット速くコピーできます。したがって、誰かが一度に1バイトずつコピーするのではなく、4バイトをコピーしたい場合は、一度にすべてをコピーできます。

于 2012-08-09T03:31:35.023 に答える
0

これをチェックしてください。

void myMemCpy(void *dest, void *src, size_t n)
{
   // Typecast src and dest addresses to (char *)
   char *csrc = (char *)src;
   char *cdest = (char *)dest;

   // Copy contents of src[] to dest[]
   for (int i=0; i<n; i++)
       cdest[i] = csrc[i];
}

詳細については

于 2017-04-24T06:34:26.140 に答える