Самый быстрый способ свести на нет std::vector

Предположим, что у меня есть std::vector double, а именно

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

Где N настолько велика, что производительность имеет значение. Предположим теперь, что MyVec - нетривиальный вектор (т.е. Не является вектором нулей, но был изменен некоторой рутиной). Теперь мне нужна отрицаемая версия вектора: Мне нужно -MyVec.

До сих пор я реализовал его с помощью

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

Но, действительно, я не знаю, это ли это что-то разумное или просто супер наивно с моей стороны.

Я делаю это правильно? Или std:: transform - это просто супер медленная процедура в этом случае?

PS: Я использую библиотеки BLAS и LAPACK все время, но я не нашел ничего, что соответствовало бы этой конкретной потребности. Однако, если в BLAS/LAPACK существует такая функция, которая быстрее, чем std:: transform, я был бы рад узнать.

Ответы

Ответ 1

#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:

Сложно вообразить быстрее. Ваш код уже совершенен, не пытайтесь перехитрить компилятор и использовать чистый код С++, который работает почти каждый раз.

Ответ 2

К счастью, данные в std::vector являются смежными, поэтому вы можете умножить на -1 с использованием векторных свойств (используя нестандартные нагрузки/хранилища и специальную передачу возможного переполнения). Или используйте ippsMulC_64f/ippsMulC_64f_I из библиотеки intel IPP (вы будете пытаться написать что-то быстрее), в которой будут использоваться самые большие векторные регистры, доступные для вашей платформы: https://software.intel.com/en-us/ipp-dev-reference-mulc

Обновление: чтобы устранить некоторую путаницу в комментариях, полная версия Intel IPP бесплатна (хотя вы можете заплатить за поддержку) и поставляется с Linux, Windows и macOS.

Ответ 3

Как уже упоминалось, это полностью зависит от вашего варианта использования. Вероятно, самым простым способом было бы что-то вроде этого:

 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, как уже упоминалось, в вашем случае использования (на самом деле я сомневаюсь, что существует прецедент, когда это принесет какую-либо измеримую пользу).

Ответ 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 '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) будет отрицать элементы и возвращать измененный вектор без необходимости временного, он прерывает математические соглашения, эффективно устанавливая: v = - v; Если это ваша цель, используйте функцию negate. Не нарушайте ожидаемую оценку оператора!

clang, с включенным avx512, генерирует этот цикл, отрицая впечатляющие 64 удвоения на итерацию - между обработкой до/после длины:

        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    $512, %rsi              ## imm = 0x200
        addq    $-64, %rdx
        jne     LBB0_21

gcc-7.2.0 генерирует подобный цикл, но, похоже, настаивает на индексированной адресации.

Ответ 5

Использовать for_each

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

или параллельный С++ 17

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