librerias - vector stl c++ ejemplos

La forma más rápida de negar un std:: vector

Question

Supongamos que tengo un std :: vector de doble, a saber

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

Donde N es tan grande que el rendimiento importa. Ahora suponga que MyVec es un vector no trivial (es decir, no es un vector de ceros, pero ha sido modificado por alguna rutina). Ahora, necesito la versión negada del vector: Necesito -MyVec .

Hasta ahora, lo he estado implementando via

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

Pero, en realidad, no sé si esto es algo sensato o simplemente es super ingenuo por mi parte.

¿Lo estoy haciendo correctamente? ¿O std :: transform es solo una rutina súper lenta en este caso?

PD: estoy utilizando las bibliotecas BLAS y LAPACK todo el tiempo, pero no he encontrado nada que coincida con esta necesidad en particular. Sin embargo, si existe una función de este tipo en BLAS / LAPACK que es más rápida que std :: transform, me gustaría saberlo.

Answer 1

Afortunadamente, los datos en std::vector son contiguos, por lo que puede multiplicar por -1 utilizando vectores intrínsecos (utilizando cargas / almacenes no alineados y manejo especial del posible desbordamiento). O use ippsMulC_64f / ippsMulC_64f_I de la biblioteca IPP de intel (le costará escribir algo más rápido) que usará los registros vectoriales más grandes disponibles para su plataforma: https://software.intel.com/en-us/ipp-dev-reference-mulc

Actualización: para aclarar algunas confusiones en los comentarios, la versión completa de Intel IPP es gratuita (aunque puede pagar por el soporte) y viene en Linux, Windows y macOS.

Answer 2

Como han mencionado otros, depende completamente de su caso de uso. Probablemente la forma más simple sería algo como esto:

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

Si este direccionamiento adicional para cada acceso único vale la pena transformar la negación en establecer un único bool depende, como ya se mencionó, de su caso de uso (en realidad dudo que exista un caso de uso en el que esto traiga algún beneficio medible).

Answer 3

Primero, una función de negate genérica para vectores de tipo aritmético como ejemplo:

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

Su deseo de un operator - canario unario operator - función requerirá la creación de un temporal, en la forma:

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

O genéricamente:

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

No se sienta tentado a implementar el operador como:

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

Mientras que (- v) negará los elementos y devolverá el vector modificado sin la necesidad de un temporal, rompe las convenciones matemáticas al establecer efectivamente: v = - v; Si ese es tu objetivo, entonces usa la función negate . ¡No rompa la evaluación esperada del operador!

clang, con avx512 habilitado, genera este bucle, negando 64 impresionantes dobles por iteración, entre el manejo de longitud 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 $512, %rsi ## imm = 0x200
addq $-64, %rdx
jne LBB0_21

gcc-7.2.0 genera un bucle similar, pero parece insistir en el direccionamiento indexado.

Answer 4

Utilizar for_each

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

o C ++ 17 paralelo

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

Answer 5

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

Este código en https://godbolt.org/ con la opción de copia -O3 genera un ensamblaje agradable

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

Es difícil de imaginar más rápido. Su código ya es perfecto, no intente ser más astuto que el compilador y use el código limpio de C ++ que funciona casi todas las veces.