时间戳

首页 > 解决方案 > 将常量减去或添加到大型数组

c++ - 将常量减去或添加到大型数组

问题描述

我有一个大uint8_t数组（大小 = 1824 * 942）。我想对每个元素做同样的操作。特别是我需要从每个元素中减去 -15。

这个数组每秒刷新 20 次，所以时间是个问题，我要避免在数组上循环。

是否有捷径可寻？

标签： c++arraysmathpointer-arithmeticinteger-arithmetic

解决方案

您可以只编写一个带有普通循环的函数：

void add(uint8_t* a, size_t a_len, uint8_t b) {
    for(uint8_t* ae = a + a_len; a < ae; ++a)
        *a += b;
}

并希望编译器为您将其向量化，它确实如此，请参阅assembly。

解决方案，std::for_each例如std::transform：

void add(uint8_t* a, size_t a_len, uint8_t b) {
    std::transform(a, a + a_len, a, [b](auto value) { return value + b; });
}

应该生成完全相同的代码，但有时它们不会。

[更新]

出于好奇，我对以下解决方案进行了基准测试：

#include <benchmark/benchmark.h>

#include <cstdint>
#include <array>
#include <algorithm>

#include <immintrin.h>

constexpr size_t SIZE = 1824 * 942;
alignas(32) std::array<uint8_t, SIZE> A;

__attribute__((noinline)) void add_loop(uint8_t* a, size_t a_len, uint8_t b) {
    for(uint8_t* ae = a + a_len; a < ae; ++a)
        *a += b;
}

__attribute__((noinline)) void add_loop_4way(uint8_t* a, size_t a_len, uint8_t b) {
    a_len /= 4;
    for(uint8_t* ae = a + a_len; a < ae; ++a) {
        a[a_len * 0] += b;
        a[a_len * 1] += b;
        a[a_len * 2] += b;
        a[a_len * 3] += b;
    }
}

__attribute__((noinline)) void add_transform(uint8_t* a, size_t a_len, uint8_t b) {
    std::transform(a, a + a_len, a, [b](auto value) { return value + b; });
}

inline void add_sse_(__m128i* sse_a, size_t a_len, uint8_t b) {
    __m128i sse_b = _mm_set1_epi8(b);
    for(__m128i* ae = sse_a + a_len / (sizeof *sse_a / sizeof b); sse_a < ae; ++sse_a)
        *sse_a = _mm_add_epi8(*sse_a, sse_b);
}

__attribute__((noinline)) void add_sse(uint8_t* a, size_t a_len, uint8_t b) {
    add_sse_(reinterpret_cast<__m128i*>(a), a_len, b);
}

inline void add_avx_(__m256i* avx_a, size_t a_len, uint8_t b) {
    __m256i avx_b = _mm256_set1_epi8(b);
    for(__m256i* ae = avx_a + a_len / (sizeof *avx_a / sizeof b); avx_a < ae; ++avx_a)
        *avx_a = _mm256_add_epi8(*avx_a, avx_b);
}

__attribute__((noinline)) void add_avx(uint8_t* a, size_t a_len, uint8_t b) {
    add_avx_(reinterpret_cast<__m256i*>(a), a_len, b);
}

template<decltype(&add_loop) F>
void B(benchmark::State& state) {
    for(auto _ : state)
        F(A.data(), A.size(), 15);
}

BENCHMARK_TEMPLATE(B, add_loop);
BENCHMARK_TEMPLATE(B, add_loop_4way);
BENCHMARK_TEMPLATE(B, add_transform);
BENCHMARK_TEMPLATE(B, add_sse);
BENCHMARK_TEMPLATE(B, add_avx);

BENCHMARK_MAIN();

i7-7700k CPU 和结果g++-8.3 -DNDEBUG -O3 -march=native -mtune=native：

------------------------------------------------------------------
Benchmark                        Time             CPU   Iterations
------------------------------------------------------------------
B<add_loop>                  31589 ns        31589 ns        21981
B<add_loop_4way>             30030 ns        30030 ns        23265
B<add_transform>             31590 ns        31589 ns        22159
B<add_sse>                   39993 ns        39992 ns        17403
B<add_avx>                   31588 ns        31587 ns        22161

循环、转换和 AVX2 版本的时间几乎相同。

SSE 版本较慢，因为编译器生成更快的 AVX2 代码。

perf report报告〜50％的L1d缓存未命中率，这表明该算法受到内存访问的瓶颈。现代 CPU 可以同时处理多个内存访问，因此您可以通过并行访问 4 个内存区域来挤压额外的约 5% 的性能，这就是 4 路循环所做的（对于您的特定数组大小，4 路是最快的）。有关更多详细信息，请参阅内存级并行性：英特尔 Skylake 与英特尔 Cannonlake。

推荐阅读