std::replace 实现可以对传递的数组进行冗余写入吗？

Question

std::replace

可以使用矢量化来优化实现（通过专门化库实现或编译器）。

矢量化实现将同时比较和替换多个元素。

为了确保在需要的地方保留旧值，矢量化实现必须执行以下任一操作：

第一种方法看起来最好，但如果向量指令集缺少给定元素大小的掩码存储，则不起作用。在 x86 上，SSE 系列没有屏蔽存储¹，AVX/AVX2 仅具有 32 和 64 位元素屏蔽存储，并且仅当某些 AVX512 子集可用时，每个向量元素大小屏蔽存储才可用。

第二种方法假设如果写入相同的值，则可以写入该元素。这是我质疑的假设。内存的可写性并不总是被授予的。在 C++ 中，可以将带有

const

修饰符的常量数组传递给

std::replace

，并且如果没有任何内容被替换，则期望正确的无操作。通过操作系统内存管理功能，可以将数组设置为部分可写、部分只读。

第三种方法不需要屏蔽存储，不做可写性假设。但它也没有完全受益于矢量化。

我观察到不同的实现使用不同的方法。

x86-64 icc 2021.10.0

编译器和

x86-64 clang 17.0.1

都尝试在启用AVX2的情况下使用16位元素对

std::replace

进行矢量化，但Intel使用写入旧值方法，而clang使用单独存储方法。使用以下代码和

-mavx2

选项。

#include <algorithm>

void f(short* i, short* e)
{
    std::replace(i, e, 0, 1);
}

因此看起来要么

x86-64 icc 2021.10.0

已损坏，要么

x86-64 clang 17.0.1

缺少进一步优化的机会。

除了矢量化本身之外，冗余写入还可用于优化小型数组或矢量化尾部处理的

std::replace

：无分支代码可能需要计算目标值（例如，在 x86 上使用

cmovcc

）并无条件存储它，

所以我的问题是 - 是否允许编译器和标准库实现进行冗余存储以优化

std::replace

？

这个问题与近乎重复的问题不同icc崩溃：编译器可以发明抽象机中不存在的写入吗？因为它是关于标准算法

std::replace

，而不是特定的实现或手写的等效项.

¹ 非时间屏蔽存储不算数，因为它们对于通用优化没有用处

Answer 1

我相信该标准要求（或至少旨在要求）您可以写入指定范围内的所有对象。具体来说，它说（N4950，[alg.replace]/2）：

授权：
new_value
可写 (25.3.1) 至
first
。

它还要求

[first, last)

是一个有效范围，因此我们可以增加

first

并且它将保持有效直到

first == last

。因此，如果它的初始值是可写的，那么它一直保持可写状态，直到

first == last

。

但这可能还不足以使矢量方法在每种情况下都有效。假设您有一个对 8 个对象进行操作的矢量处理器，但传递的

replace

first

和

last

仅指 6 个对象。虽然您可以写入所有 6 个对象，但之后就不允许写入 2 个对象，即使您确实写回与从它们读取的值相同的值。

但我认为它至少是为了强制要求 rand

[first, last)

中的每个迭代器都可以写入，因此写入所有迭代器的实现都是有效的，即使它有时写回它读取的相同值而不是一个重置价值。