Будет ли компилятор развернуть этот цикл?

Question

Я создаю многомерный вектор (математический вектор), где я разрешаю основные математические операции +, -, /, *, =. Шаблон принимает два параметра, один из которых является типом (int, float и т. Д.), А другой - размером вектора. В настоящее время я применяю операции через цикл for. Теперь, учитывая, что размер известен во время компиляции, компилятор развернет цикл? Если нет, есть ли способ развернуть его без (или минимального) снижения производительности?

template <typename T, u32 size>
class Vector
{
public:
    // Various functions for mathematical operations. 
    // The functions take in a Vector<T, size>.
    // Example:
    void add(const Vector<T, size>& vec)
    {
        for (u32 i = 0; i < size; ++i)
        {
            values[i] += vec[i];
        }
    }

private:
    T   values[size];
};

Прежде чем кто-то прокомментирует Profile then optimize, пожалуйста, обратите внимание, что это основа для моего 3D графического движка, и она должна быть быстрой. Во-вторых, я хочу знать ради самообразования.

Answer 1

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

    Vector<int, 16> a, b;
    Vector<int, 65536> c, d;

    asm("xxx"); // marker
    a.Add(b);
    asm("yyy"); // marker
    c.Add(d);
    asm("zzz"); // marker

Теперь скомпилируйте

gcc -O3 1.cc -S -o 1.s

И вижу беду

    xxx
# 0 "" 2
#NO_APP
    movdqa  524248(%rsp), %xmm0
    leaq    524248(%rsp), %rsi
    paddd   524184(%rsp), %xmm0
    movdqa  %xmm0, 524248(%rsp)
    movdqa  524264(%rsp), %xmm0
    paddd   524200(%rsp), %xmm0
    movdqa  %xmm0, 524264(%rsp)
    movdqa  524280(%rsp), %xmm0
    paddd   524216(%rsp), %xmm0
    movdqa  %xmm0, 524280(%rsp)
    movdqa  524296(%rsp), %xmm0
    paddd   524232(%rsp), %xmm0
    movdqa  %xmm0, 524296(%rsp)
#APP
# 36 "1.cc" 1
    yyy
# 0 "" 2
#NO_APP
    leaq    262040(%rsp), %rdx
    leaq    -104(%rsp), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L2:
    movdqa  (%rcx,%rax), %xmm0
    paddd   (%rdx,%rax), %xmm0
    movdqa  %xmm0, (%rdx,%rax)
    addq    $16, %rax
    cmpq    $262144, %rax
    jne .L2
#APP
# 38 "1.cc" 1
    zzz

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

Answer 2

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

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

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

Итог: не думайте, что вы умнее своего компилятора, если вы не знаете lot об архитектуре процессора. Пишите свой код простым и понятным способом и не беспокойтесь о микрооптимизации, пока ваш профилировщик не скажет вам.

Answer 3

Цикл можно развернуть с помощью рекурсивного создания шаблона. Это может быть или не быть быстрее в вашей реализации C ++.

Я немного подкорректировал ваш пример, чтобы он компилировался.

typedef unsigned u32; // or something similar

template <typename T, u32 size>
class Vector
{
  // need to use an inner class, because member templates of an 
  // unspecialized template cannot be explicitly specialized.
  template<typename Vec, u32 index>
  struct Inner
  {
    static void add(const Vec& a, const Vec& b)
    {
      a.values[index] = b.values[index];
      // triggers recursive instantiation of Inner 
      Inner<Vec, index-1>::add(a,b);
    }
  };
  // this specialization terminates the recursion
  template<typename Vec>
  struct Inner<Vec, 0>
  {
    static void add(const Vec& a, const Vec& b)
    {
      a.values[0] = b.values[0];
    }
  };

public:

    // PS! this function should probably take a 
    // _const_ Vector, because the argument is not modified
    // Various functions for mathematical operations. 
    // The functions take in a Vector<T, size>.
    // Example:
    void add(Vector<T, size>& vec)
    {
      Inner<Vector, size-1>::add(*this, vec);
    }

    T   values[size];
};

Answer 4

Единственный способ понять это - попробовать его на своем компиляторе с вашими параметрами оптимизации. Создайте один тестовый файл с вашим кодом "it it unroll", test.cpp:

#include "myclass.hpp"

void doSomething(Vector<double, 3>& a, Vector<double, 3>& b) {
    a.add( b );
}

затем фрагмент справочного кода reference.cpp:

#include "myclass.hpp"

void doSomething(Vector<double, 3>& a, Vector<double, 3>& b) {
    a[0] += b[0];
    a[1] += b[1];
    a[2] += b[2];
}

и теперь используйте GCC для их компиляции и выкладывайте только сборку:

for x in *.cpp; do  g++ -c "$x" -Wall -Wextra -O2 -S -o "out/$x.s"; done

По моему опыту, GCC будет развертывать циклы не более 3 по умолчанию при использовании циклов, длительность которых известна во время компиляции; использование -funroll-loops заставит его развернуться еще больше.

Answer 5

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

Единственный возможный ответ на ваш вопрос - "это зависит" (от флагов компилятора, от значения size и т. Д.).

Если вы действительно хотите знать, попросите ваш компилятор: скомпилируйте в код сборки с типичными значениями size и с флагами оптимизации, которые вы будете использовать для реального, и проверьте результат.

Answer 6

Многие компиляторы развернут этот цикл, не знаю, будет ли «компилятор», на который вы ссылаетесь, будет.В мире нет только одного компилятора.

Если вы хотите гарантировать, что он развернут, то TMP (с встраиванием) может сделать это.(На самом деле это одно из самых тривиальных приложений TMP, часто используемое в качестве примера метапрограммирования).