5

以下是 memcmp 的 Microsoft CRT 实现：

int memcmp(const void* buf1,
           const void* buf2,
           size_t count)
{
    if(!count)
        return(0);

    while(--count && *(char*)buf1 == *(char*)buf2 ) {
        buf1 = (char*)buf1 + 1;
        buf2 = (char*)buf2 + 1;
    }

    return(*((unsigned char*)buf1) - *((unsigned char*)buf2));
}

它基本上执行逐字节比较。

我的问题分为两部分：

  1. 是否有任何理由不将其更改为 int by int 比较 until count < sizeof(int)，然后对剩余的内容进行逐字节比较？
  2. 如果我要做 1，是否有任何潜在/明显的问题？

注意：我根本没有使用CRT，所以无论如何我必须实现这个功能。我只是在寻找有关如何正确实施它的建议。

4

8 回答 8

7

如果您愿意，您可以将其作为 int-by-int 比较或更广泛的数据类型来执行。

您必须注意的两件事（至少）是开始和结束时的悬垂，以及两个区域之间的对齐方式是否不同。

如果您在不遵循对齐规则的情况下访问值，则某些处理器的运行速度会变慢（如果您尝试它，有些甚至会崩溃）。

因此，您的代码可能char会对int对齐区域进行比较，然后进行int比较，然后再char进行比较，但同样，这两个区域的对齐方式可能很重要。

这种额外的代码复杂性是否值得您节省任何费用，这取决于您无法控制的许多因素。一种可能的方法是检测两个区域相同对齐的理想情况并快速进行，否则只需逐个字符地进行。

于 2011-02-16T14:34:56.463 回答
5

您提出的优化很常见。最大的担忧是，如果您尝试在不允许对单个字节以外的任何内容进行非对齐访问的处理器上运行它，或者在该模式下运行速度较慢；x86 系列没有这个问题。

它也更复杂，因此更有可能包含错误。

于 2011-02-16T14:36:35.323 回答
1

不要忘记，当您在较大的块中发现不匹配时，您必须识别该块中的第一个不同char ，以便您可以计算正确的返回值（memcmp()返回第一个不同字节的差异，视为unsigned char值）。

于 2011-02-17T05:16:25.850 回答
0

如果您比较为 int，则需要检查对齐情况并检查 count 是否可被 sizeof(int) 整除（将最后一个字节比较为 char）。

于 2011-02-16T14:41:42.703 回答
0

您找到的代码只是 的调试实现memcmp，它针对简单性和可读性进行了优化，而不是针对性能进行了优化。

内在编译器实现是特定于平台的，并且足够智能，可以生成处理器指令，这些指令可以尽可能一次比较双字或双字（取决于目标体系结构）。此外，如果两个缓冲区具有相同的地址，则内部实现可能会立即返回(buf1 == buf2)。调试实现中也缺少此检查。

最后，即使您确切知道您将在哪个平台上运行，完美的实现仍然是不那么通用的，因为它取决于一系列特定于程序其余部分的不同因素：

  • 最低保证缓冲区对齐是多少？
  • 您可以在不触发访问冲突的情况下读取缓冲区末尾的任何填充字节吗？
  • 缓冲区参数可以相同吗？
  • 缓冲区大小可以为 0 吗？
  • 您只需要比较缓冲区内容是否相等吗？或者你还需要知道哪个更大（返回值<0或>0）？
  • ...

如果性能是一个问题，我建议在汇编中编写比较例程。大多数编译器为您提供了查看它们为源代码生成的程序集列表的选项。您可以采用该代码并使其适应您的需求。

于 2012-11-25T14:17:39.530 回答
0

这真的是他们的实施吗？除了不这样做之外，我还有其他问题：

  • 抛弃恒常。
  • 该退货声明有效吗？无符号字符 - 无符号字符 = 有符号整数？

一次 int 仅在指针对齐时才有效，或者如果您可以从每个字节的前面读取几个字节并且它们仍然对齐，因此如果在对齐边界之前两者都是 1，您可以读取每个字符的一个然后去int-at-a-time，但如果它们以不同的方式对齐，例如一个对齐而一个不对齐，则没有办法做到这一点。

当它们进行实际比较（它必须走到最后）并且数据很长时，memcmp 的效率最低（即它花费的时间最长）。

我不会自己写，但如果你要比较大部分数据，你可以做一些事情，比如确保对齐，甚至填充末端，然后如果你愿意，可以一次一个字地做。

于 2011-02-16T14:49:42.950 回答
0

另一个想法是优化处理器缓存和获取。处理器喜欢随机获取大块而不是单个字节。尽管内部工作可能已经解释了这一点，但无论如何这将是一个很好的练习。始终分析以确定最有效的解决方案。

伪代码：

while bytes remaining > (cache size) / 2 do // Half the cache for source, other for dest.
  fetch source bytes
  fetch destination bytes
  perform comparison using fetched bytes
end-while
perform byte by byte comparison for remainder.

有关更多信息，请在 Web 上搜索“数据驱动设计”和“面向数据的编程”。

某些处理器，例如 ARM 系列，允许有条件地执行指令（在 32 位，非拇指）模式下。处理器获取指令，但只有在满足条件时才会执行它们。在这种情况下，请尝试根据布尔赋值重新表述比较。这也可以减少所采用的分支数量，从而提高性能。

另请参阅循环展开。
另请参见汇编语言。

您可以通过针对特定处理器定制算法来获得很多性能，但在可移植性方面较为松散。

于 2011-02-16T17:31:33.493 回答
-1

许多处理器将其实现为单个指令。如果您可以保证您正在运行的处理器可以使用单行内联汇编程序来实现。

于 2011-02-16T16:33:31.520 回答