2

我的任务是这样的：我需要strcpy在以下约束下实现该功能：

  1. 该函数最多可以有七个语句。
  2. 它应该尽可能快。
  3. 它应该使用尽可能少的内存。
  4. 在将调用 my 的函数中strcpy，目标地址将按如下方式保存：char* newDestination = NULL;
  5. 该strcpy函数的原型应该是：void myStrcp(void** dst, void* src);

我提出了这个解决方案，它uint64_t用于复制每个迭代八个字节。如果是这样，我的问题是：

  1. 有没有比我更好的解决方案 - 如果有，请解释为什么它更好？
  2. 我们在哪个操作系统上运行程序（WindowsVs. Linux）和/或平台是否重要？

我的解决方案（在 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 位）超过了缓存线，那么由于缓存线拆分，硬件很可能会在进行复制时产生开销。在更长的向量中开销可能会变得更大（并且在那里也更频繁）。因此，您可以添加一些初始检查来解决此问题，方法是将头部复制成较小的块，就像处理尾部一样。

  2. src/dst 区域会发生冲突吗？如果是这样，您需要为正确的功能行为提供定义（在块复制的情况下它变得不那么简单）。

  3. 请注意 strcpy 和 memcpy 之间的区别（另请参见此处）。这使得矢量化变得不那么简单，因此您需要在此处定义要求。当前，您的函数可能与经典 strcpy 中的预期不同，因为您不检查每个块中的空字节。不确定这对您来说是否是个问题。

  4. 代码大小限制对性能不是很友好（嗯，除非你的瓶颈是指令缓存容量或分支可预测性，但这是相当先进的）。7 个语句的限制可能意味着你想太多了 :)

于 2013-10-10T20:45:03.440 回答