我真的需要扫描内存两次来执行memcmp + memcpy吗?

Question

考虑以下函数:

int memcmp_and_memcpy(void * x, const void * y, size_t n) {
  int c = memcmp(x, y, n);
  memcpy(x, y, n);
  return c;
}

有可能更有效地做到这一点吗?扫描相关内存两次似乎效率不高。

编辑:我正在寻找一种工业强度解决方案，适用于各种输入，特别是当x和y对于第一个m字节相同时，其中0<<m<=n。向量化是必须的。

Answer 1

是的，你可以做得更有效率，但这需要花费时间。一方面，您可以通过编写自己的循环来轻松地消除对内存的重复传递，该循环对所有字节进行一次传递。

由于改进了内存带宽的使用，这几乎肯定会在大型数组上更快。

对于小的拷贝，不清楚你是否会赢，因为memcmp和memcpy的实现本身是经过优化的，并且可以处理比字节更大的数据单位;幼稚的基于字节的实现可能会失败。在比较与复制中重复相同类型的优化需要做一些工作。

天真,未经测试:

int memcmpy(void *dest, const void *src, size_t size)
{ 
  unsigned char *d = dst;
  const unsigned char *s = src;
  int compare = 0;
  for (; size--; s++, d++) {
    int sv = *s;
    int dv = *d;
    /* Thansks to Ben Voigt: if dv == sv, we can 
       avoid checking for the first difference, and skip
       the data move from source to dest: */
    if (dv == sv)
      continue;
    if (!compare) {
       if (dv < sv)
         compare = -1;
       else if (dv > sv)
         compare = 1;
    }
    *d = sv;
  }
  return compare;
}

Answer 2

除非您的内存块始终相等，否则memcmp永远不会读取整个区域直到最后:一旦发现第一个差异，它就退出。只有当两个块相等时，代码才会读取整个块两次，在这种情况下，您可以完全跳过复制:

int memcmp_and_memcpy(void * x, const void * y, size_t n) {
    int c;
    if ((c = memcmp(x, y, n)) != 0) {
        memcpy(x, y, n);
    }
    return c;
}

此代码的最坏情况是区域总是在最后一个字节中不同。如果您有很大一部分这样的情况，如果您的分析器告诉您这确实是一个瓶颈，您可以考虑将这两个函数重写为一个。然而，很难与memcpy的优秀库实现竞争，因为它通常进行了大量优化。

Answer 3

这是我的尝试。在你发现第一个差异之前，没有必要复制任何东西;我认为，由于需要保持缓存一致性，写操作的成本比读操作高。这段代码很有可能是内存带宽有限的，所以英勇的微优化并不重要。请注意，我并没有对它进行测试。

int memcmp_and_memcpy(char * x, const char * y, size_t n)
{
    if (n == 0) return 0;
    int c = 0;
    while (c == 0 && n != 0)
    {
        c = *x++ - *y++;
        --n;
    }
    memcpy(--x, --y, ++n);
    return c;
}

不幸的是，我不知道有一个标准函数告诉你两个缓冲区在哪里不同，或者这可以更简单。

Answer 4

memcmp和memcpy是非常优化的。我的建议是将memcmp代码复制到您的项目中，并将返回值更改为x和y中第一个字符的位置。因此，首先您比较您的memcmp_2函数，然后从此位置进行memcpy到结束。

Answer 5

为什么要复制已经确定相同的值?这会不必要地弄脏缓存。

下面是对Kaz版本的修改，避免了不必要的复制(以及对缓存行独占所有权的争用):

int memcmpy(void *dest, const void *src, size_t size)
{ 
  if (!size) return 0;
  unsigned char *d = dst;
  const unsigned char *s = src;
  int compare = 0;
  do {
    int sv = *s++;
    unsigned char& dv = *d;
    if (dv != sv) {
        if (!compare) compare = dv - sv;
        dv = sv;
    }
  } while (--size);
  return compare;
}