Выгодно ли больше развертывать циклы в C++ поверх массивов фиксированного размера?

Я хочу использовать std::array хранить данные N-мерных векторов и реализовывать арифметические операции для таких векторов. Я понял, так как std::array теперь имеет constexprsize() функция-член, я могу использовать это, чтобы развернуть циклы, которые мне нужны для арифметических операций над его элементами.

Вот минимальный пример:

#include <array> 
#include <type_traits>
#include <iostream>
#include <cassert>

template<std::size_t N=0, typename Vector>
void plus_equals(Vector& result, Vector const& input) 
{
    result[N] += input[N]; 

    if constexpr (N + 1 < result.size()) 
        plus_equals<N+1>(result, input); 
}

template<typename INT, size_t N>
class Vector
{
    std::array<INT, N> data_; 

    public: 

        template<typename ... BracketList> 
        Vector(BracketList ... blist)
        :
            data_{std::forward<BracketList>(blist)...}
        {} 

        INT& operator[](std::size_t i)
        {
            return data_[i]; 
        }

        INT operator[](std::size_t i) const 
        {
            return data_[i]; 
        }

        decltype(auto) begin() const 
        {
            return data_.begin(); 
        }

        decltype(auto) end() const 
        {
            return data_.end(); 
        }

        decltype(auto) end() 
        {
            return data_.end(); 
        }

        constexpr decltype(auto) size()
        {
            return data_.size(); 
        }

        void operator+=(Vector const& other)
        {
            plus_equals(*this, other); 
        }
};

template<size_t N = 0, typename Vector> 
Vector operator+(Vector const& uVec, Vector const& vVec)
{
    Vector result {uVec};  

    result += vVec;  

    return result;  
}

template<size_t N = 0, typename Vector> 
Vector sum(Vector const& uVec, Vector const& vVec)
{
    Vector result {uVec};  

    for (decltype(result.size()) i = 0; i < result.size(); ++i)
        result[i] += vVec[i]; 

    return result;  
}

template<typename Vector> 
void print(Vector&& v)
{
    for (const auto& el : v) std::cout << el << " ";  
    std::cout << std::endl;
}

using namespace std; 

int main()
{
    Vector<int, 3> c1 = {1,2,3}; 
    Vector<int, 3> c2 = {3,2,1}; 
    auto r1 = c1 + c2;
    print (r1);

    auto r2 = sum(c2, c2);
    print (r2); 

    Vector<int, 3> s1, s2; 

    for (std::size_t i = 0; i < 3; ++i)
        cin >> s1[i];
    for (std::size_t i = 0; i < 3; ++i)
        cin >> s2[i];

    auto r3 = s1 + s2;
    print(r3);

    auto r4 = sum(s1, s2);
    print(r4);


    return 0;
}

sum операция осуществляется с использованием plus_equals это должно развернуть человека += операции над элементами вектора, а также sum(Vector const&, Vector const&) функция, использует for петля.

Я собрал пример на Godbolt, используя -O3 -std=c++2a,

Если я закомментирую все, кроме

Vector<int, 3> c1 = {2,11,7}; 
Vector<int, 3> c2 = {9,22,5}; 
auto r1 = c1 + c2;
print (r1);

я получил

    movabs  rax, 141733920779
    sub     rsp, 24
    lea     rdi, [rsp+4]
    mov     QWORD PTR [rsp+4], rax
    mov     DWORD PTR [rsp+12], 12
    call    void print<Vector<int, 3ul>&>(Vector<int, 3ul>&)
    xor     eax, eax
    add     rsp, 24
    ret

Что здесь происходит? Почему я не вижу первые две константы c1[0] + c2[0] а также c1[1] + c2[1]? С другой стороны 7 + 5 = 12 перемещен:

    mov     DWORD PTR [rsp+12], 12

Почему сборка кода

int main()
{
    Vector<int, 3> c1 = {2,11,7}; 
    Vector<int, 3> c2 = {9,22,5}; 
    //auto r1 = c1 + c2;
    //print (r1);

    auto r2 = sum(c1, c2);
    print (r2);

точно так же?

Если я попытаюсь использовать переменные времени выполнения:

    Vector<int, 3> s1, s2; 
    for (std::size_t i = 0; i < 3; ++i)
        cin >> s1[i];
    for (std::size_t i = 0; i < 3; ++i)
        cin >> s2[i];

    auto r3 = s1 + s2;
    print(r3);

я получил

    mov     edx, DWORD PTR [rsp+28]
    mov     eax, DWORD PTR [rsp+32]
    lea     rdi, [rsp+36]
    add     eax, DWORD PTR [rsp+20]
    add     edx, DWORD PTR [rsp+16]
    mov     ecx, DWORD PTR [rsp+24]
    add     ecx, DWORD PTR [rsp+12]
    mov     DWORD PTR [rsp+44], eax
    mov     DWORD PTR [rsp+36], ecx
    mov     DWORD PTR [rsp+40], edx

Какие ссылки на plus_equals Функция шаблона и развертывает итерации, как ожидалось.

Для sum:

Vector<int, 3> s1, s2; 
for (std::size_t i = 0; i < 3; ++i)
    cin >> s1[i];
for (std::size_t i = 0; i < 3; ++i)
    cin >> s2[i];

//auto r3 = s1 + s2;
//print(r3);

auto r4 = sum(s1, s2);
print(r4);

Сборка это:

    mov     edx, DWORD PTR [rsp+32]
    add     edx, DWORD PTR [rsp+20]
    add     ecx, eax
    shr     rax, 32
    add     eax, DWORD PTR [rsp+28]
    mov     DWORD PTR [rsp+44], edx
    mov     DWORD PTR [rsp+40], eax
    mov     DWORD PTR [rsp+36], ecx

И нет никаких сравнений равенства и скачков, поэтому цикл был развернут.

Когда я смотрю на код сборки sum В шаблоне есть операторы сравнения и переходы. Я ожидал этого, потому что я считаю, что компилятор сначала генерирует общий код для любого Vectorа потом выяснит, если Vector::size() является constexpr и применяет дальнейшие оптимизации.

В порядке ли интерпретация? Если это так, можно сделать вывод, что нет смысла вручную развертывать итерации для массивов фиксированного размера, потому что с -O3 петли, которые используют constexpr size функции-члены будут развернуты в любом случае компилятором?

Источник

1 ответ

Компилятор достаточно умен, чтобы автоматически развертывать циклы для вас, и вы должны верить, что он сможет выполнить эти (и многие другие) оптимизации.

Вообще говоря, компилятор лучше выполняет микрооптимизацию, а программист лучше выполняет макрооптимизацию.

Микро-оптимизации (что МОЖЕТ сделать компилятор):

  • Развернуть петли
  • встроенные функции автоматически
  • применять оптимизацию хвостовых вызовов для ускорения хвостовых рекурсивных функций (многие в конечном итоге работают так же быстро, как и эквивалентный цикл)
  • elide копирует и перемещает: если вы возвращаете что-то по значению, во многих случаях компилятор может избавиться от копии или полностью перейти.
  • Используйте векторизованные инструкции с плавающей запятой (хотя для этого иногда требуется помощь компилятора)
  • Исключите ненужные или избыточные операторы if (например, когда вы проверяете что-то, а затем вызываете функцию-член, которая также проверяет это, когда она вставляет функцию-член, она устраняет ненужную проверку)
  • Встроенные лямбды передаются другим функциям (это происходит только в том случае, если std::function - это не может быть встроено std::function)
  • Храните локальные переменные и даже целые структуры в регистрах вместо использования RAM или Cache
  • Много математических оптимизаций

Макро-оптимизации (что компилятор НЕ МОЖЕТ сделать):

Это то, на что программист еще должен обратить внимание.

  • Измените способ хранения данных. Если что-то не должно быть указателем, сохраните это в стеке!
  • Измените алгоритм, используемый для расчета чего-либо. Разработка алгоритма все еще важна!
  • Другие вещи
Источник
Другие вопросы по тегам