实施memcmp

以下是微软CRT实现memcmp的：实施memcmp

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)); 
}

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

我的问题是两个部分：

有什么理由不这样改变通过INT比较一个int直到count < sizeof(int)，然后按字节比较什么仍然做字节？
如果我要做1，是否有任何潜在的/明显的问题？

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

来源

2011-02-16 intheskywithdiamonds

大部分情况并非如此。假设你在优化的基础上进行编译，它将转变为编译器本身，而不是调用CRT的实现。 – 2011-02-16 15:19:15

在C标签中添加，因为这是一个真正的C问题 – CashCow 2011-02-16 15:46:34

优化时，需要考虑的一个问题是*在看到任何重大改进之前需要多大的数据大小？*有时执行该函数的开销占用更多时间比实际的比较。 – 2011-02-16 17:41:26

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

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

如果您访问的值没有遵循其对齐规则（有些甚至在尝试使用时甚至会崩溃），某些处理器运行速度会变慢。

所以，你的代码很可能做char比较长达一个int对准区域，然后int比较，然后再char比较，但同样的都地区的路线可能会无所谓。

无论额外的代码复杂度是否值得您节省的成本取决于许多您无法控制的因素。一种可能的方法是检测理想的情况，即两个区域的排列方式完全一致，而且速度很快，否则就按字符逐个排列。

来源

2011-02-16 14:34:56 paxdiablo

难道这样的优化也不会要求* both *指针在开始时超出相同的数量。 – 2011-02-17 11:50:34

你提出的优化是非常普遍的。最大的问题是如果你试图在一个处理器上运行它，而这个处理器不允许对一个字节以外的任何东西进行非对齐访问，或者在该模式下运行速度较慢; x86系列没有这个问题。

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

来源

2011-02-16 14:36:35

如果比较为int，则需要检查对齐并检查count是否可由sizeof（int）整除（以将最后一个字节作为char来比较）。

来源

2011-02-16 14:41:42 fbafelipe

这真的是他们的实施吗？除此之外，我还有其他一些问题int-wise：

castng away constness。
是否会返回语句工作？无符号字符 - 无符号字符=有符号整型？

INT一次只当指针对准工作，或者如果你可以阅读从每个前几个字节，他们都仍然对齐，所以如果对准边界之前都为1，你可以阅读然后每个字符中的一个字符随时都会变成int，但是如果它们以不同方式对齐，例如一个字符对齐而另一个不对齐，则无法执行此操作。

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

我不会写我自己的，但如果你要比较大部分的数据，你可以做的事情，如确保对齐，甚至填补两端，然后做一次一字，如果你想。

来源

2011-02-16 14:49:42 CashCow

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

来源

2011-02-16 16:33:31 Jay

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

的伪代码：

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.

有关详细信息，在网络上搜索“数据驱动设计”和“数据的面向对象编程”。

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

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

通过将算法定制到特定的处理器，可以获得大量的性能，但是在可移植性区域很宽松。

来源

2011-02-16 17:31:33

不要忘了，当你发现一个更大的块内的不匹配，则必须确定第一不同char内该块，这样就可以计算出正确的返回值（memcmp()返回第一个不同的差异字节，视为unsigned char值）。

来源

2011-02-17 05:16:25 caf

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

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

最后，甚至当你确切地知道哪个你会运行平台，完美的实现仍然少通用之一，因为它依赖于一堆不同的因素，这些因素具体到你的程序的其余部分：

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

如果表现都非常关注的问题，我建议写在装配比较常规。大多数编译器给你一个选项来查看它们为源代码生成的程序集。您可以采用该代码并根据您的需求进行调整。

来源

2012-11-25 14:17:39

回答

相关问题