Вычесть или добавить константу в большой массив

Question

У меня большой массив uint8_t (размер = 1824 * 942). Я хочу сделать ту же операцию для каждого элемента. В частности, мне нужно вычесть -15 из каждого элемента.

Этот массив обновляется 20 раз в секунду, поэтому время является проблемой, и я избегаю циклов по массиву.

Есть липростой способ сделать это?

Answer 1

Вы можете просто написать функцию с простым циклом:

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

И надеяться, что компилятор векторизует это для вас, что он делает, см. сборка .

Решения с 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 и 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-кэша, чтоуказывает на то, что алгоритм ограничен доступом к памяти. Современные процессоры могут обрабатывать несколько обращений к памяти одновременно, так что вы можете увеличить здесь ~ 5% производительности, параллельно обращаясь к 4 областям памяти, что и делает 4-сторонний цикл (для вашего конкретного размера массива 4 способа - этосамый быстрый). См. Параллелизм на уровне памяти: Intel Skylake против Intel Cannonlake для получения более подробной информации.

Answer 2

Вы можете использовать std::for_each:

uint8_t value = 15;
std::for_each(std::begin(nums), std::end(nums), [value](uint8_t& num) { num -= value; });

, где nums - это массив uint8_t.

Answer 3

Это должен быть самый быстрый способ сделать это:

#include <iostream>
#include <cstdint>
#include <array>
#include <algorithm>
#include <execution>


int main() {
    constexpr size_t  size = 1824 * 942;
    uint16_t input{};
    std::cout << "Initialize with: ";
    std::cin >> input;
    std::array<uint8_t, size> array{};
    std::fill(std::execution::par_unseq, array.begin(), array.end(), input);

    std::transform(std::execution::par_unseq,array.begin(), array.end(), array.begin(), [] (const auto& value) { return value + 15; });

    std::for_each(array.begin(),array.end(), [] (auto value) {
        std::cout << static_cast<uint16_t>(value) << ",";
    });
    std::cout << "\n";
}

Обратите внимание на значимую строку std::transform(std::execution::par_unseq,array.begin(), array.end(), array.begin(), [] (const auto& value) { return value + 15; });, остальное для примера.

Также обратите внимание, что, поскольку вы этого не сделалиукажите, какой тип массива вы можете преобразовать встроенные массивы, например uint8_t array[1924*924];, в std::array с помощью std::to_array.

Answer 4

Вы можете создать структуру (или класс), которая будет содержать этот параметр, общий для всех элементов вашего массива.

struct nameIt
{
    uint8_t* arr;
    uint8_t delta;
}