2

私のタスクはstrcpy次のとおりです。次の制約の下で関数を実装する必要があります。

  1. 関数に含めることができるステートメントは 7 つまでです。
  2. できるだけ速くする必要があります。
  3. 可能な限り最小限のメモリを使用する必要があります。
  4. my を呼び出す関数ではstrcpy、宛先アドレスは次のように保持されます。char* newDestination = NULL;
  5. 関数のプロトタイプは次のstrcpyようになります。void myStrcp(void** dst, void* src);

uint64_t各反復を8バイトコピーするために使用するこのソリューションを思いつきました。もしそうなら、私の質問は次のようになります:

  1. 私よりも優れた解決策はありますか?もしそうなら、なぜそれが優れているのか説明してください?
  2. プログラムを実行しているOS(WindowsLinux)および/またはプラットフォームは重要ですか?

私の解決策(Windowsの場合):

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <conio.h>

void strCpy(void **dst, void *src);

int main()
{
    char *newLocation = NULL;

    strCpy((void **)&newLocation, "stringToBeCopied");
    printf("after my strcpy dst has the string: %s \n", newLocation);
    free(newLocation);
    getch();
    return 0;
}

void strCpy(void** dst, void* src)
{
    // Allocating memory for the dst string
    uint64_t i, length = strlen((char *)src), *locDst =
        (uint64_t *) malloc(length + 1), *locSrc = (uint64_t *) src;
    *dst = locDst;

    // Copy 8 Bytes each iteration
    for (i = 0; i < length / 8; *locDst++ = *locSrc++, ++i);

    // In case the length of the string is not alligned to 8 Bytes - copy the remainder
    // (last iteration)
    char *char_dst = (char *)locDst, *char_src = (char *)locSrc;

    for (; *char_src != '\0'; *char_dst++ = *char_src++);

    // NULL terminator
    *char_dst = '\0';
}
4

1 に答える 1

1

ベクトル化は確かに重要です。同じ考えに沿ったより良い解決策は、さらに効率的なコピーのために SSE/AVX を使用することです。もちろん、サポートされている最大ベクトル化を検出する必要があるため、これによりプログラム プラットフォームが特定されます。

また、対処する必要があるいくつかの問題:

  1. src/dst のアラインメント - コピーするチャンク (上記のケースでは 64 ビットのもの) がキャッシュ ラインを超える場合、HW はキャッシュ ラインの分割により、コピーを実行する際にオーバーヘッドが発生する可能性が最も高くなります。オーバーヘッドは、ベクトルが長いほど大きくなる可能性があります (また、より頻繁に発生します)。したがって、テールを処理するようにヘッドを小さなチャンクにコピーすることで、この問題に対処するためにいくつかの初期チェックを追加できます。

  2. src/dst 領域は衝突できますか? その場合、正しい機能動作の定義を提供する必要があります (チャンクでコピーする場合は、それほど簡単ではなくなります)。

  3. strcpy と memcpy の違いに注意してください (こちらも参照)。これにより、ベクトル化がより簡単になるため、ここで要件を定義する必要があります。現在、各チャンク内の null バイトをチェックしていないため、関数は従来の strcpy で期待されるものとは異なる場合があります。それがあなたにとって問題かどうかはわかりません。

  4. コード サイズの制限はパフォーマンスにあまり適していません (ただし、ボトルネックが命令キャッシュの容量または分岐の予測可能性である場合を除きますが、それはかなり高度です)。7ステートメントの制限は、これを考えすぎていることを意味するかもしれません:)

于 2013-10-10T20:45:03.440 に答える