否定 std::vector 的最快方法

Question

假设我有一个std::vector的double，即

std::vector<double> MyVec(N);

其中 N 太大以至于性能很重要。现在假设 MyVec 是一个非平凡向量（即它不是零向量，但已被某些例程修改）。现在，我需要矢量的 negated 版本：我需要 -MyVec.

到目前为止，我一直在通过

实现它

std::transform(MyVec.cbegin(),MyVec.cend(),MyVec.begin(),std::negate<double>());

但是，真的，我不知道这是明智的，还是我这边太天真了。

我做得对吗？或者 std::transform 在这种情况下只是一个超级慢的例程？

PS: 我一直在使用 BLAS 和 LAPACK 库，但我还没有找到任何符合这个特定需求的东西。但是，如果 BLAS/LAPACK 中存在这样一个比 std::transform 更快的函数，我将很高兴知道。

Answer 1

幸运的是 std::vector 中的数据是连续的，因此您可以使用向量内在函数乘以 -1（使用未对齐的 load/stores 和对可能溢出的特殊处理）。或者使用英特尔 IPP 库中的 ippsMulC_64f/ippsMulC_64f_I（你会很难写得更快），它将使用你的平台可用的最大向量寄存器：https://software.intel.com/en-us/ipp-dev-reference-mulc

更新：为了消除评论中的一些混淆，完整版的 Intel IPP 是免费的（尽管您可以付费获得支持）并支持 Linux、Windows 和 macOS。

Answer 2

正如其他人所提到的，这完全取决于您的用例。可能最简单的方法是这样的：

 struct MyNegatingVect {
     MyVect data;
     bool negated = false;
     void negate() { negated = !negated; }
     // ... setter and getter need indirection ...
     // ..for example
     MyVect::data_type at(size_t index) { return negated ? - data.at(index) : data.at(index);
 };

如前所述，是否值得将每次访问的这种额外间接访问转换为设置单个 bool 取决于您的用例（实际上我怀疑是否存在这样的用例带来任何可衡量的好处）。

Answer 3

#include <vector>
#include <algorithm>
#include <functional> 
void check()
{
    std::vector<double> MyVec(255);
    std::transform(MyVec.cbegin(),MyVec.cend(),MyVec.begin(),std::negate<double>());
}

此代码在 https://godbolt.org/ 上使用编译选项 -O3 生成漂亮的程序集

.L3:
[...]
  cmp r8, 254
  je .L4
  movsd xmm0, QWORD PTR [rdi+2032]
  xorpd xmm0, XMMWORD PTR .LC0[rip]
  movsd QWORD PTR [rdi+2032], xmm0
.L4:

很难想象会更快。您的代码已经很完美了，不要试图超越编译器并使用干净的 C++ 代码，它几乎每次都能正常工作。

Answer 4

首先以算术类型向量的泛型negate函数为例：

#include <type_traits>
#include <vector>

...

template <typename arithmetic_type> std::vector<arithmetic_type> &
negate (std::vector<arithmetic_type> & v)
{
    static_assert(std::is_arithmetic<arithmetic_type>::value,
        "negate: not an arithmetic type vector");

    for (auto & vi : v) vi = - vi;

    // note: anticipate that a range-based for may be more amenable
    // to loop-unrolling, vectorization, etc., due to fewer compiler
    // template transforms, and contiguous memory / stride.

    // in theory, std::transform may generate the same code, despite
    // being less concise. very large vectors *may* possibly benefit
    // from C++17's 'std::execution::par_unseq' policy?

    return v;
}

您希望规范一元 operator - 函数需要创建一个临时函数，形式为：

std::vector<double> operator - (const std::vector<double> & v)
{
    auto ret (v); return negate(ret);
}

或者笼统地说：

template <typename arithmetic_type> std::vector<arithmetic_type>
operator - (const std::vector<arithmetic_type> & v)
{
    auto ret (v); return negate(ret);
}

不要不要试图将运算符实现为：

template <typename arithmetic_type> std::vector<arithmetic_type> &
operator - (std::vector<arithmetic_type> & v)
{
    return negate(v);
}

虽然 (- v) 将否定元素和 return 修改后的向量而不需要临时，但它通过有效设置打破了数学约定： v = - v; 如果那是你的目标，那么使用 negate 函数。不要破坏预期的运算符评估！

clang，启用 avx512，生成此循环，每次迭代否定令人印象深刻的 64 个双打 - 在 pre/post 长度处理之间：

        vpbroadcastq    LCPI0_0(%rip), %zmm0
        .p2align        4, 0x90
LBB0_21:
        vpxorq  -448(%rsi), %zmm0, %zmm1
        vpxorq  -384(%rsi), %zmm0, %zmm2
        vpxorq  -320(%rsi), %zmm0, %zmm3
        vpxorq  -256(%rsi), %zmm0, %zmm4
        vmovdqu64       %zmm1, -448(%rsi)
        vmovdqu64       %zmm2, -384(%rsi)
        vmovdqu64       %zmm3, -320(%rsi)
        vmovdqu64       %zmm4, -256(%rsi)
        vpxorq  -192(%rsi), %zmm0, %zmm1
        vpxorq  -128(%rsi), %zmm0, %zmm2
        vpxorq  -64(%rsi), %zmm0, %zmm3
        vpxorq  (%rsi), %zmm0, %zmm4
        vmovdqu64       %zmm1, -192(%rsi)
        vmovdqu64       %zmm2, -128(%rsi)
        vmovdqu64       %zmm3, -64(%rsi)
        vmovdqu64       %zmm4, (%rsi)
        addq    2, %rsi              ## imm = 0x200
        addq    $-64, %rdx
        jne     LBB0_21

gcc-7.2.0 生成类似的循环，但似乎坚持索引寻址。

Answer 5

使用for_each

std::for_each(MyVec.begin(), MyVec.end(), [](double& val) { val = -val });

或C++17并行

std::for_each(std::execution::par_unseq, MyVec.begin(), MyVec.end(), [](double& val) { val = -val });

否定 std::vector 的最快方法

Fastest way to negate a std::vector

c++

optimization

blas

stdvector

lapack