给出:
#include <string.h>
bool test_data(void *data)
{
return memcmp(data, "abcd", 4) == 0;
}
编译器可以将其优化为:
test_data:
cmpl $1684234849, (%rdi)
sete %al
ret
这很好
但是如果我使用自己的memcmp()
(而不是来自<string.h>
),编译器就不能将其优化为一条cmpl
指令。相反,它这样做:
static int memcmp(const void *s1, const void *s2, size_t n)
{
const unsigned char *p1 = s1, *p2 = s2;
size_t i;
for (i = 0; i < n; i++) {
int ret = p1[i] - p2[i];
if (ret)
return ret;
}
return 0;
}
bool test_data(void *data)
{
return memcmp(data, "abcd", 4) == 0;
}
test_data:
cmpb $97, (%rdi)
jne .L5
cmpb $98, 1(%rdi)
jne .L5
cmpb $99, 2(%rdi)
jne .L5
cmpb $100, 3(%rdi)
sete %al
ret
.L5:
xorl %eax, %eax
ret
友情链接:https://godbolt.org/z/Kfhchr45a
- 是什么阻止编译器进一步优化它?
- 我做了什么妨碍优化的事情吗?
3条答案
按热度按时间iyr7buue1#
Data-dependent branching defeats auto-vectorization in GCC/Clang(但不是经典ICC)。在第一次迭代之前(在抽象机器中)不能计算出trip-count,所以GCC和clang甚至不会尝试使用
pcmpeqb
/pmovmskb
来处理大尺寸。(对于大输入,这是在x86-64上实现memcmp
的有效方法。)显然,这是一个很难解决的问题,因为GCC/Clang已经有15到20年没有解决这个问题了(从现在开始,GCC第一次开始做自动向量化)。
另请参阅 * how to auto vectorization array comparison function * -将其编写为一个循环,该循环计数不匹配并始终接触所有元素,可以给予自动向量化。(或减少而不是减少)。但这对于像4字节这样的小的固定大小没有帮助。对于第一个字节有差异的1GiB memcmp来说,完全删除early-out是一场灾难。(一个好的SIMD memcmp,比如glibc的SSE 2/AVX 2版本,可能会在向量比较结果上每隔64到128字节进行一次分支。)
显然也没有习语识别,至少这种写作方式没有。(
memcpy
)GCC和clang可以将简单的复制循环转换为call memcpy
或call memset
,或者这些函数的内联扩展。所以如果你自己写,你需要-fno-builtin-memcpy
,否则你的函数会变成一个对自身的调用。为实验取一个不同的名字。)将其编写为无条件接触所有字节的循环可以给予自动向量化,但在GCC的内部可能不会被识别为
memcmp
习惯用法。我认为这对于有小问题的好代码来说是必要的,比如我们想要一个单一的dwordcmp
。**编译器必须避免引入segfaults,因为它会在抽象机器停止的地方进行读取。**如果
void *data
指向一个保存'z'
的1字节缓冲区,则您的手动循环在抽象机器中具有定义良好的行为。阅读所有4个字节将超过缓冲区的末尾。但是
memcmp
是UB,如果数组的任何部分是不可访问的,所以编译器 * 可以 * 接触所有4个字节,而不检查早期或指针对齐。(* Can std::memcmp read any bytes past the first difference? * 是的,与您的循环不同。)(In x86-64 asm,超过结尾可能会进入未Map的页面,导致segfault,违反as-if规则。* Is it safe to read past the end of a buffer within the same page on x86 and x64? * -是的,但仅在同一页内。对于
strlen
和strchr
的对齐加载,这是可以解决的问题,但是对于使用不同对齐的指针对strcmp
进行矢量化,这是一个更大的障碍。我没有比较函数args中的两个未知指针,而是将
test_data
调用者改为将指针传递给两个全局数组char foo[4], bar[4];
,编译器肯定知道这两个数组都是可读的。但那没有帮助,所以还是没有。k7fdbhmy2#
正如所编写的那样,编译器无法针对您的特殊情况优化实现,因为它无法确定如果第一个字节与
'a'
不同,则是否允许阅读data
指向的第二个字节,并以此类推。memcmp
在C标准中被指定为具有未定义的行为,如果两个指针指向的任何n
字节都不可访问。编译器和/或标准库假设4个字节是可访问的,并且目标体系结构上支持非对齐访问。如果你修改你的实现来读取所有4个字节,假设目标架构的非对齐访问是可以的,gcc和clang都会像预期的那样优化
test_data
,generating 3 instructions:q9rjltbz3#
除了已经说过的内容之外,64位计算机的
memcmp
库实现可以尝试在单个指令中执行比较,只要它可以推断出数据足够小。因此,针对64位CPU的优化
memcmp
的简单实现可能如下所示:https://godbolt.org/z/edjn4hx8h
尽管是相当幼稚的代码,但这仍然生成了相当有效的汇编程序。在
memcmp1
的内联过程中,编译器应该放弃调用更复杂函数的选择,因为它在编译时就知道数据的大小。在这种情况下,gcc没有这样做,clang没有,但无论如何,结果看起来都很好。至于“适合较大块的函数”,它可能会从检查对齐开始,然后将数据开头和结尾的未对齐字节视为特殊情况。然后在x86_64上逐字执行其余检查,每次8个字节。
正如我们所提到的,在不滥用严格别名的情况下实现这样的库函数可能会很棘手-在glibc和类似的函数中有许多函数包含公然的严格别名违规,只要库没有被编译为严格符合标准C,这就很好。在这种情况下,这些库通常会突然中断,所以如果您自己构建库,请遵循库的构建说明。请参阅本答案中关于glibc的strlen的部分:“* 为什么作为glibc的一部分这是安全的,而不是其他的。*”
但这个答案中的代码实际上是安全的;
memcpy
对于混叠和对齐是安全的。